编译原理 [0x04][0x01] ==（5.2）语法分析__LR分析法

 

规范归约

定义：假定a是文法G的一个句子，我们称序列 an， an-1，...，a0     是a的一个规范归约，如果此序列满足：

  1.  an= a

  2.  a0为文法的开始符号，即a0=S

  3.  对任何 i，0 ≤ i ≤ n， ai-1是从ai经把句柄替换成为相应产生式左部符号而得到的

 

用句柄归约

eg：

 

 

 

• 规范归约是最左归约
• 规范归约的逆过程就是最右推导

SaAcBeaAcde  aAbcdeabbcde

• 最右推导也称为规范推导
• 由规范推导推出的句型称为规范句型

 

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

 

• 历史：已移入符号栈的内容
• 展望：根据产生式推测未来可能遇到的输入符号
• 现实：当前的输入符号

 

LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作

 

LR分析法

 

LR分析器的性质

• 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
• 一旦栈的顶部出现可归约串(句柄)，则进行归约

 

 

字的前缀、活前缀

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

 

 

LR分析表

 

LR分析器的核心是一张分析表

• ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
• GOTO[s，X]：状态s面对文法符号X时，下一状态是什么

 

 

文法的拓广

将文法G(S)拓广为()

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

 

LR(0)项目

• 在每个产生式的右部添加一个圆点
• 表示我们在分析过程中看到了产生式多大部分

A→XYZ有四个项目

A→ •XYZ    A→X•YZ   A→XY•Z    A→XYZ•

A→a• 称为"归约项目"

归约项目 →a • 称为"接受项目"

A→a•ab (a∈VT)  称为"移进项目"

A→a•Bb (B∈VN) 称为"待约项目"

 

 eg:

文法G()

→E

E→a A | b B

A→cA | d

B→cB | d

 该文法的项目有：

1. →•E   2. →E•   3. E→•aA   4. E→a•A   5. E→aA•   6. A→•cA  7. A→c•A   8. A→cA•   9. A→•d   10. A→d•

11. E→•bB   12. E→b•B  13. E→bB•   14. B→•cB   15. B→c•B   16. B→cB•   17. B→•d   18. B→d•

 

构造识别文法所有活前缀的DFA

 

 

构造识别文法所有活前缀的NFA

• 若状态i为X→X1 … Xi-1•Xi … Xn ，状态j为X→X1 … Xi-1Xi•Xi+1 … Xn ，则从状态i画一条标志为Xi的有向边到状态j；(注意点的位置)（图一）
• 若状态i为X→a•Ab ，A为非终结符，则从状态i画一条边到所有状态A→•（图二）

把识别文法所有活前缀的NFA确定化

 

 

 

根据上面的例子得出的LR（0）项目，构造NFA得

 

 

构造DFA得

 

 

 

LR(0)项目集规范族

 

 

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

 

 

 

LR(0)分析表的构造

 

 

假若一个文法G的拓广文法的活前缀识别自动机中的每个状态(项目集)不存在下述情况：

• 既含移进项目又含归约项目；
• 含有多个归约项目

   则称G是一个LR(0)文法。

 

 

ACTION和GOTO子表构造

 

 得到下列这个表：

	ACTION					GOTO
状态	a	b	c	d	#	E	A	B
0	s2	s3				1
1					acc
2			s4	s10			6
3			s5	s11				7
4			s4	s10			8
5			s5	s11				9
6	r1	r1	r1	r1	r1
7	r2	r2	r2	r2	r2
8	r3	r3	r3	r3	r3
9	r5	r5	r5	r5	r5
10	r4	r4	r4	r4	r4
11	r6	r6	r6	r6	r6