自底向上语法分析技术

思想:从分析树的底部向顶部方向构造分析树,是将输入串w归约为文法开始符号S的过程。自顶向下语法分析采用最左推导方式,而自底向上的语法分析采用最左归约方式(规范归约)。

句柄

短语:若S=>*αAβ并且A=>+γ,则称γ是句型αγβ的相对于变量A的短语
直接短语:若S=>*αAβ并且A=>γ,则称γ是句型αγβ的相对于变量A的直接短语
句柄:若S=>*αAw=>αβw,则称β是句型αβw相对于A→β的直接短语,一个句型的最左直接短语称为该句型的句柄

在一个最右句型句柄右边只有终结符号,若文法无二义性,那么每个句型都有且只有一个句柄。

句型的句柄与一个产生式右部相匹配,将句柄归约为该产生式左部非终结符号代表了最右推导中的逆过程的一步。

规范归约

设α为文法G的句子,若

  • α= αn<=αn-1<=……<=α2<=α1=S
  • 对每个i(1≤i≤n),αi-1是将句型α$_i$中的句柄归约后得到的句型
  • 则称αn……α1为α的规范归约序列

移入-归约分析

使用一个栈来保存归约/扫描移入的文法符号,栈中符号(自底向上)和待扫描的符号组成了一个最右句型。

  • 移入:将下一个输入符号移动到栈顶
  • 归约:将句柄归约为相应的非终结符号,句柄总是在栈顶。具体操作时弹出句柄,压入被归约到的非终结符号。
  • 接受:宣布分析过程成功完成
  • 报错:发现语法错误,调用错误恢复子程序

移入-归约中的存在的问题举例:

对于如下文法:

(1)<S>→var<IDS>:<T>

(2)<IDS>→i

(3)<IDS>→<IDS>,i

(4)<T>→real | int

剩余输入 动作
1 $ var iA , iB : real $
2 $var iA , iB : real $ 移入
3 $var iA , iB : real $ 移入
4 $var <IDS> , iB : real $ 按(2)归约
5 $var <IDS>, iB : real $ 移入
6 $var <IDS>,iB : real $ 移入
7 $var <IDS>,<IDS> : real $ 按(2)归约
8 $var <IDS>,<IDS>: real $ 移入
9 $var <IDS>,<IDS>:real real $ 移入
10 $var <IDS>,<IDS>:<T> $ 按(4)归约,报错

识别的句子显然是属于该文法的,然而分析过程中却报错,是因为在第6步移入的终结符号iB并不是一个句柄,而在第7步对一个错误的句柄进行了归约。

对于每个句型,都能构造该句型的分析树,上图为第六步的分析树,下面给出关于分析树的一些定义:

根节点:文法的开始符号
边缘:分析树的边缘为从左到右排列叶节点得到的符号串
短语:分析树中每棵子树的边缘称为该句型的一个短语
直接短语:若子树只有父子两代结点(高度为2),则该子树的边缘称为该句型的一个直接短语

句柄是句型的最左直接短语,它是分析树中某棵高度为2的子树的边缘,在上图所示的对应于第6步的分析树中,iB不是某棵高度为2的子树的边缘。当前句型有两个直接短语:

  • 一是以<IDS>为根节点的高度为2的子树的边缘<IDS>,iB
  • 二是以<T>为根节点的高度为2的子树的边缘real

最左直接短语即<IDS>,iB为句柄,因此正确做法是将<IDS>,iB归约为<IDS>。

确定句柄的两种方法

  • 优先法:根据归约先后次序为句型中相邻文法符号规定优先关系(本文不讨论)
  • 状态法:根据句柄的识别状态确定句柄,下文的LR分析法即采用状态法

LR分析法

LR文法是最大的,可以构造出响应移入-归约语法分析器的文法类。

  • L:对输入进行从左至右扫描
  • R:反向构造出一个最右推导序列

LR(k)分析:

  • 需要向前查看k个输入符号的LR分析(k=0,1具有实践意义)

基本原理

句柄是逐步形成的,用状态表示句柄识别的进展程度。例:对于S→bBB:

  • S→·bBB 移进状态
  • S→b·BB 待约状态
  • S→bB·B 待约状态
  • S→bBB· 归约状态

LR分析器基于这样一些状态来构造自动机进行句柄识别。

优点

  • LR语法分析器由表格驱动;虽然手工构造表格工作量大,但表格可以自动生成
  • 对于几乎所有的程序设计语言,只要写出上下文无关文法,就能够构造出识别该构造的LR语法分析器
  • 最通用的无回溯移入归约分析技术,且和其它技术一样高效
  • 可以尽早检测到错误
  • 能分析的文法集合是LL(k)文法的超集,例如上下文无关文法就是正则文法的超集

分析器总体结构

LR(0)分析

LR(0)项和LR(0)自动机

LR语法分析器的栈中元素包含状态,状态指明了在移入归约分析中的位置。状态是项的集合。

LR(0)项:

  • 文法的产生式加上在产生式体某处的一个点,例A→·XYZ,A→X·YZ,A→XY·Z,A→XYZ·
  • A→ε只有一个项A→·

规范LR(0)项集族

规范LR(0)项集族的项集可作为LR(0)自动机的状态,并以此为基础构造自动机的基础。

LR(0)语法分析过程:

  • 状态存放在栈中
  • 栈中的状态(自底向上)形成自动机的一条路径,路径上的标号就是栈中的文法符号序列
  • 若到达接受状态,则栈顶某个符号串形成句柄
规范LR(0)项集族的构造

增广文法:G的增广文法G’是在G中增加新的开始符号S’,并加入产生式S’→S得到的。

用到的子函数:

  • CLOSURE(I):I的项集闭包
  • GOTO(I,X):I的X后继

CLOSURE(I)构造算法:

  • 首先将I中的各个项加入到CLOSURE(I)中
  • 如果A→α·Bβ在CLOSURE(I)中,那么对B的任意产生式B→γ,将B→·γ加到CLOSURE(I)中
  • 不断重复第二步,直到收敛

例:增广文法:

  • E'→E
  • E→E+T | T
  • T→T*F | F
  • F→(E) | id

项集{[E‘→E]}的闭包:

  • [E'→·E]
  • [E→·E+T],[E→·T]
  • [T→·T*F],[T→·F]
  • [F→·(E)],[F→·id]

GOTO函数:

  • GOTO(I,X):I中形如[A→α·Xβ]的项对应的项[A→αX·β]的闭包,定义了LR(0)自动机中状态I在X之上的转换
  • 例:I={[E'→E·],[E→E·+T]},则GOTO(I,+):
    • I中第二项·后出现+,对应项为[E→E·+T]
    • GOTO(I,+)=CLOSURE({[E→E+·T]})={ [E→E+·T], [T→·T*F], [T→·F], [F→·(E)], [F→·id] }

求增广文法G’的LR(0)项集规范族算法:

1
2
3
4
5
6
7
8
9
void items(G'){
C = CLOSURE({[S'→·S]});
repeat
for (C中的每个项集I)
for (,每个文法符号X)
if (GOTO(I,X)非空且不在C中)
将GOTO(I,X)加入C中;
until 没有新的项集加入到C
}

对于上例中的增广文法,求出各个规范集族为:

如何使用LR(0)自动机

假设文法符号串γ是LR(0)自动机从开始状态运行到状态j路径上的输入符号的串,那么

  • 若下个输入符号为a,且j状态有一个a上的转换,则移入a
  • 若j中有形如A→a·的项,则按A→a归约
  • 若有多种可能,即存在冲突

LR语法分析表的结构有两部分,动作ACTION和转换GOTO,ACTION(i,a)其中i为状态,a为终结符,表示状态i遇到终结符a应采取的动作;GOTO(i,A)其实i为状态,A为非终结符,表示i遇到归约出的A应进入的状态。下面给出构造LR(0)分析表的算法:

为表区分,构造规范LR(0)项集族的GOTO函数在这里用GO表示

sj表示移入终结符号,进入状态j;rj表示按第j个产生式归约

  • 0为开始状态
  • Ii∈C:
    • if A→α·aβ∈Ii and GO(Ii,a)=Ij then ACTION[i,a] = sj
    • if A→α·Bβ∈Ii and GO(Ii,B)=Ij then GOTO[i,B] = j
    • if A→α·属于Ii then
      • for ∀a∈T∪{$} do
        • ACTION[i,a] = rj
    • if S’→S·∈Ii then ACTION[i,$] = acc
  • 空格处为error
LR语法分析算法

输入:文法G的LR语法分析表,输入串w

输出:若w在L(G)中,输出最左归约步骤,否则输出错误提示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
令a为w$的第一个符号
while(true){
令s为栈顶状态;
if(ACTION[s,a] = 移入t){
将t压入栈中;
令a为下一个输入符号
}else if(ACTION[s,a] = 规约A→β){
从栈中弹出|β|个符号;
令t为当前栈顶状态;
将GOTO[t,A]压入栈中;
输出产生式A→β
}else if(ACTION[s,a] = acc) break;
else 调用错误恢复例程;
}

用以下例子说明分析过程,分析id*id:

符号 输入 动作
1 0 $ id*id$ 移入id,进入5
2 0 5 $id *id$ 按F→id归约,5出栈,0遇到F进入3
3 0 3 $F *id$ 按T→F归约,3出栈,0遇到T进入2
4 0 2 $T *id$ 移入*,进入7
5 0 2 7 $T* id$ 移入id,进入5
6 0 2 7 5 $T*id $ 按F→id归约,5出栈,7遇到F进入10
7 0 2 7 10 $T*F $ 按T→T*F归约,10,7,2出栈,0遇到T进入2
8 0 2 $T $ 按E→T归约,2出栈。0遇到E进入1
9 0 1 $E $ 接受

LR(0)分析过程中的冲突

对于该部分采用的增广文法的例子,观察其LR(0)自动机状态转换图可以发现,在I2I9中在下一个输入符号为*的情况下,不知道是该采取归约动作还是移入动作 。若LR(0)分析表中没有语法分析动作的冲入,则称其为LR(0)文法。不是所有的CFG都能用LR(0)方法分析。