第六章 自下而上的语法分析

自下而上

从输入串开始，逐步进行归约，直到文法的开始符号。
归约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号。
从树叶节点开始，构造语法树。
算符优先分析法、LR分析法。

第一部分：算符优先文法

1 自下而上分析的基本思想-“移进－归约”

用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

2 短语和直接短语

以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语；
如果子树只有两代，则该短语就是直接短语。

3 算符文法

一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含…QR…形式的产生式右部，则我们称该文法为算符文法。

4 算符优先文法的概念

假定G是一个不含𝜀-产生式的算符文法。对于任何一对终结符a、b，我们说：

  1. a的优先级等于b，当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；
  2. a的优先级小于b，当且仅当G中含有形如P→…aR…的产生式， 而R⇒b…或R⇒Qb…；
  3. a的优先级大于b，当且仅当G中含有形如P→…Rb…的产生式，而 R⇒…a或R⇒…aQ。

如果一个算符文法G中的任何终结符对(a，b)至多只满足a的优先级大于b、a的优先级等于b和 a的优先级小于b这三个关系之一，则称G是一个算符优先文法。

例子：
文法G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P ↑ F | P
(4) P→(E) | i
的优先关系表:

优先关系表

5 FIRSTVT和LASTVT集合

FIRSTVT集合：FIRSTVT(P) = {𝑎 | P ⇒ 𝑎… 或 P ⇒ Q𝑎…， 𝑎 ∈ VT且Q ∈ VN }
LASTVT集合：LASTVT(P) = {𝑎 | P ⇒ …𝑎 或 P ⇒ …𝑎Q， 𝑎 ∈ VT且Q ∈ VN }

假定有个产生式的一个候选形为…aP…， 那么，对任何b∈FIRSTVT(P)，有 a的优先级小于b
假定有个产生式的一个候选形为…Pb…， 那么，对任何a∈LASTVT(P)，有 a的优先级大于b

6 构造集合FIRSTVT(P)和LASTVT(P)的算法

FIRSTVT(P)：

  1. 若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)
  2. 若a∈FIRSTVT(Q)，且有产生式P→Q…，则a∈FIRSTVT(P)

LASTVT(P)：

  1. 若有产生式P→… a或P→ … aQ，则 a∈LASTVT(P)
  2. 若a∈LASTVT(Q)，且有产生式P→… Q，则a∈LASTVT(P)

例子：
考虑下面的文法G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P ↑ F | P
(4) P→(E) | i

FIRSTVT(E)={ +, *, ↑, (, i }
FIRSTVT(T)={ *, ↑, (, i }
FIRSTVT(F)={ ↑, (, i }
FIRSTVT(P)={ (, i }

LASTVT(E)={ +, *, ↑, ), i }
LASTVT(T)={ *, ↑, ), i }
LASTVT(F)={ ↑, ), i }
LASTVT(P)={ ), i }

7 构造优先关系表的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR  每条产生式P→X1X2…Xn  DO
  FOR  i:=1  TO  n-1 DO
    BEGIN
        IF  Xi和Xi+1均为终结符  THEN  置Xi的优先级等于Xi+1
        IF  i≤n-2且Xi和Xi+2都为终结符, 但Xi+1为非终结符  THEN  
            置Xi的优先级等于Xi+2；
        IF  Xi为终结符而Xi+1为非终结符  THEN
            FOR  FIRSTVT(Xi+1)中的每个a  DO
                置 Xi的优先级小于a；
        IF  Xi为非终结符而Xi+1为终结符  THEN
            FOR  LASTVT(Xi)中的每个a   DO
                置  a的优先级大于Xi+1
    END

8 最左素短语

一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。
最左素短语是指处于句型最左边的那个素短语。

9 最左素短语定理

算符优先文法句型(括在两个＃之间)的一般形式：
#N1a1N2a2…NnanNn+1#
其中，ai都是终结符，Ni是可有可无的非终结符。
定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1，
aj-1的优先级小于aj
aj的优先级等于 aj+1，…，ai-1的优先级等于ai
ai的优先级大于ai+1

10 算符优先分析算法

使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。
在正确的情况下，算法工作完毕时，符号栈S应呈现：# N # 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
k:=1;		
S[k]:=‘#’;
REPEAT
	把下一个输入符号读进a中；
	IF S[k]∈VT THEN  j:=k  ELSE  j:=k-1;
	WHILE S[j]的优先级大于a DO
	BEGIN
		   REPEAT
	         Q:=S[j];
			IF S[j-1]∈VT THEN j:=j-1 
						ELSE j:=j-2
	     UNTIL S[j]的优先级小于Q;
		   把S[j+1]…S[k]归约为某个N；
		   k:=j+1;
		   S[k]:=N
	END OF WHILE;
	IF S[j]的优先级小于a OR S[j]的优先级等于a THEN
			BEGIN k:=k+1;S[k]:=a END
	ELSE ERROR /*调用出错诊察程序*/
UNTIL a=‘#’

算符优先分析结果不一定是语法树。

11 算符优先分析程序构成

总控程序，根据现行栈顶符号和当前输入符号，执行动作；
优先关系表，用于指导总控程序进行移进-归约；
分析栈 STACK，用于存放文法符号。

特点：
优点: 简单，快速；
缺点: 可能错误接受非法句子。
使用广泛，用于分析各类表达式，ALGOL 60。

第二部分：LR分析法

L：从左到右扫描输入串；
R：自下而上进行归约。

12 句柄

一个句型的最左直接短语称为该句型的句柄。
可用句柄来对句子进行归约。

13 规范归约与规范句型

定义：假定α是文法G的一个句子，我们称序列 αn， αn-1，… ，α0 是α的一个规范归约，如果此序列满足：

  1. αn= α
  2. α0为文法的开始符号，即α0=S
  3. 对任何i，0 ≤ i ≤ n， αi-1是从αi经把句柄替换成为相应产生式左部符号而得到的

算符优先分析一般并不等价于规范归约。

规范归约是最左归约，规范归约的逆过程就是最右推导。
S ⇒ aAcBe ⇒ aAcde ⇒ aAbcde ⇒ abbcde
最右推导也称为规范推导，由规范推导推出的句型称为规范句型。

规范归约的关键问题是寻找句柄。

14 LR分析

LR分析器的结构

LR分析器的结构

历史：已移入符号栈的内容；
展望：根据产生式推测未来可能遇到的输入符号；
现实：当前的输入符号。
LR分析方法是把”历史”及”展望”综合抽象成状态，由栈顶的状态和现行的输入符号唯一确定每一步工作。

LR分析器的核心是一张分析表：
ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作；
GOTO[s，X]：状态s面对文法符号X时，下一状态是什么。

例子：
根据文法G(E)：
(1) E→E＋T
(2) E→T
(3) T→T*F
(4) T→F
(5) F→(E)
(6) F→I
分析输入串i*i+i。
LR分析例子

表中s表示移进(shift)：把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入符号；
表中r表示归约(reduce)：用某产生式A→β进行归约。 假若β的长度为r， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把下一状态s’=GOTO[sm-r, A]和文法符号A推进栈；
表中acc表示接受：宣布分析成功，停止分析器工作；
表中空白表示错误。

15 LR文法

对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。
定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。

LR文法不是二义的，二义文法肯定不会是LR的；
LR文法 ⊂ 无二义文法。

第三部分： LR(0)分析表的构造

16 字的前缀、活前缀

字的前缀：是指字的任意首部，如字abc的前缀有𝜀，a，ab，abc。
活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型αβδ，β为句柄，如果αβ=u1u2…ur，则符号串u1u2…ui(1≤i≤r)是αβδ的活前缀。(δ必为终结符串)。
规范归约过程中，保证分析栈中总是活前缀，就说明分析采取的移进/归约动作是正确的。

17 构造识别活前缀的DFA

将文法G(S)拓广为G’(S’)：
构造文法G’，它包含了整个G，并引进不出现在G中的非终结符S’、以及产生式S’→S，S’是G’的开始符号。称G’是G的拓广文法。

LR(0)项目：
在每个产生式的右部添加一个圆点，表示我们在分析过程中看到了产生式多大部分。
A → XYZ有四个项目：A → •XYZ，A → X•YZ，A → XY•Z，A → XYZ• 。
A → α• 称为”归约项目”。
归约项目 S’→ α • 称为”接受项目”。
A → α•aβ (a∈VT) 称为”移进项目”。
A → α•Bβ (B∈VN) 称为”待约项目”。

构造识别文法所有活前缀的NFA：
若状态i为X → X1 … Xi-1•Xi … Xn，状态j为X → X1 … Xi-1Xi•Xi+1 … Xn，则从状态i画一条标志为Xi的有向边到状态j；
若状态i为X → α•Aβ，A为非终结符，则从状态i画一条𝜀边到所有状态A → •γ。

例子：
文法G(S’)
S’→E
E→aA|bB
A→cA|d
B→cB|d

识别文法所有活前缀的DFA

构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。

18 通过计算项目集规范族构造识别活前缀的DFA

有效项目：
项目A → β1•β2对活前缀αβ1是有效的，其条件是存在规范推导S’⇒R𝛼𝐴𝜔⇒R𝛼𝛽1𝛽2𝜔。
在任何时候，分析栈中的活前缀X1X2 … Xm的有效项目集正是从识别活前缀的DFA的初态出发，读出X1X2 … Xm后到达的那个项目集(状态)。
若项目A → α•Bβ对活前缀η=δα是有效的且 B → γ 是一个产生式，则项目B → •γ 对η=δα 也是有效的。

状态转换函数：
为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：GO(I，X)＝CLOSURE(J)。其中J＝{任何形如A→αX•β的项目| A→α•Xβ属于I}。直观上说，若I是对某个活前缀 γ 有效的项目集，那么，GO(I，X)便是对 γX 有效的项目集。

项目集的转移函数计算：
项目集I的闭包CLOSURE(I)：

  1. I的任何项目都属于CLOSURE(I)；
  2. 若A→αB•β属于CLOSURE(I)，那么，对任何关于A的产生式B→γ，项目B→•γ也属于CLOSURE(I)；
  3. 重复执行上述两步骤直至CLOSURE(I) 不再增大为止。

两种构造识别活前缀的DFA的方法：
项目 → NFA → DFA
Closure → GO → DFA

19 LR(0)分析表的构造

假若一个文法G的拓广文法G’的活前缀识别自动机中的每个状态(项目集)不存在下述情况：
既含移进项目又含归约项目、含有多个归约项目，则称G是一个LR(0)文法。

令每个项目集Ik的下标k作为分析器的状态，包含项目S’→•S的集合Ik的下标k为分析器的初态。
构造LR(0)分析表的ACTION和GOTO子表。

  1. 若项目A→α•aβ属于Ik且GO(Ik, a)＝Ij，a为终结符，则置ACTION[k, a] 为“sj”。
  2. 若项目A→α•属于Ik，那么，对任何终结符a(或结束符#)，置ACTION[k, a]为 “rj”(假定产生式A→α是文法G’的第j个产生式)。
  3. 若项目S’→S•属于Ik，则置ACTION[k,#]为“acc”。
  4. 若GO(Ik, A)＝Ij，A为非终结符，则置GOTO[k, A]=j。
  5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。

第四部分： SLR(1)和LR(1)

20 SLR(1)冲突解决办法

含有“移进－归约”冲突，导致LR(0)失效。

假定LR(0)规范族的一个项目集I={A1→α•a1β1，A2→α•a2β2，…，Am→α•amβm，B1→α•，B2→α•，…，Bn→α• } 如果集合{a1，…，am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则当状态I面临任何输入符号a时：

  1. 若a是某个ai，i=1,2,…,m，则移进；
  2. 若a∈FOLLOW(Bi)，i=1,2,…,n，则用产生式Bi→α进行归约；
  3. 此外，报错。

SLR(1)解决办法：最多向前看一个单词。

21 SLR(1)分析表的构造

与LR(0)的分析表的构造步骤仅第二步不同：
若项目A→α•属于Ik，那么，对任何终结符a∈FOLLOW(A)，置ACTION[k,a]为 “rj”；其中，假定A→α为文法G’的第j个产生式。

例子：
拓广文法G(S’)：
(0) S’→E
(1) E→E+T
(2) E→T
(3) T→T*F
(4) T→F
(5) F→(E)
(6) F→i

LR(0)活前缀的DFA
LR(0)项目集规范族

I1、I2和I9都含有“移进－归约”冲突，FOLLOW(S’)＝{ # }，FOLLOW(E)＝{ +, ), # }，FOLLOW(T)＝{ +, *, ), # }，FOLLOW(F)＝{ +, *, ), # }。

SLR(1)分析表

22 SLR(1)冲突消解存在的问题

SLR在方法中，如果项目集Ii含项目A → α• 而且下一输入符号a∈FOLLOW(A)，则状态i面临a时，可选用“用A → α归约”动作。
但在有些情况下，当状态i显现于栈顶时，当前单词是a，栈里的活前缀βα未必允许把α归约为A，因为可能根本就不存在一个形如“βAa”的规范句型。在这种情况下，用“A → α”归约不一定合适。
这是因为FOLLOW集合提供的信息太泛。

23 LR(k)项目

LR(k)项目：扩展LR(0)项目，附带有k个终结符[A→α•β, a1a2…ak]，a1a2…ak 称为向前搜索符串(或展望串)。
归约项目[A→α•，a1a2…ak]的意义：当它所属的状态呈现在栈顶且后续的k个输入符号为 a1a2…ak 时，才可以把栈顶上的α归约为A。
对于任何移进或待约项目[A→α•β, a1a2…ak], β≠𝜀，搜索符串 a1a2…ak 没有直接作用。

24 LR(1)分析表

与LR(0)和SLR(1)的分析表的构造步骤仅第二步不同：
若项目[A→α•，a]属于Ik，则置ACTION[k, a]为 “rj”；其中假定A→α为文法G’的第j个产生式。

按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。
具有规范的LR(1)分析表的文法称为一个LR(1)文法。
使用LR(1)分析表的分析器叫做一个规范的LR分析器。
LR(0) ⊂ SLR(1) ⊂ LR(1) ⊂ 无二义文法