文档介绍：二工大温敬和
2008年1月25日
第5章自下而上的语法分析
1
自下而上的语法分析概述
LR分析法的基本原理
项目集规范族的构造
有效项目(略)
LR(0)分析表的构造
SLR(1)分析表的构造
LR语法分析器的控制程序
二义文法在LR分析法中的应用
应用举例(略)
LR分析法在词法分析器自动构造中的应用(略)
2
从叶结点出发,步步向上归约。若能归约到根结点,说明输入串是文法的一个句子,否则输入串存在语法错误。
㈠常用的自下而上语法分析方法
①算符优先分析法(本书略)
宜于手工构造,特别适合于算术表达式的语法分析。但适用范围较小,实用意义不大。
②LR分析法
适用范围广,宜于自动生成,目前大多数编译程序的语法分析器都采用LR分析法。
㈡LR分析器组成
由控制程序和分析表组成。控制程序与文法无关,分析表随文法而异。
㈢LR分析法的优点
适用范围大,对文法要求低,无需消除左递归,无需消除左因子。
3
㈣LR分析法的缺点
实现代价高,LR分析表的规模要比同一文法的LL(1)分析表大得多。
㈤LR分析法的分类
①LR(0)分析法
简单、分析能力弱,是LR分析法的基础。
②SLR(1)分析法
或称简单LR分析法。分析能力中,实现代价同LR(0),比较容易实现,具有实用价值。
③LR(1)分析法(本书略)
或称规范LR分析法,分析能力强,实现代价高,或者说分析表的规模非常大。
④LALR(1)分析法(本书略)
或称向前LR分析法。分析能力介于SLR(1)和LR(1)之间,实现代价同LR(0),有实用价值,但构造方法较复杂。
4
b
A
a
A
a
c
A
a
d
c
A
a
A
a
b
a
a
B
c
A
a
e
B
c
A
a
S
1 2 3 4 5 6 7 8 9 10
因最终归约到根结点,输入串abbcde是文法的一个句子。
自下而上的语法分析概述
㈠概述
实质上是一种移进归约法,设置一个栈,将输入串符号逐个移进栈内,一旦发现栈顶形成某个产生式的候选式时,立即将栈顶这一部分符号替换(归约)成该产生式的左部符号。
例给定文法G:
S→aAcBe
A→b
A→Ab
B→d
和输入串abbcde,
其移进归约过程如下所示:
5
㈡问题
从第④步到第⑤步有二种选择,可将b归约成A,栈顶成aAA;也可将Ab归成A,栈顶成aA,显然后者是正确的。
由此可见,可归约串必然是产生式的右部符号串(必要条件),但是构成某产生式右部的符号串未必是可归约串,故需精确定义可归约串。
㈢句柄和规范归约
①短语
设αβδ是文法G的一个句型。如果有SαAδ且 Aβ,则称β是句型αβδ中相对于非终结符A的短语,其中α、β、δ∈(VT∪VN)*。
②直接短语(简单短语)
设αβδ是文法G的一个句型。若有SαAδ且Aβ,则称β是句型αβδ中相对于非终结符A(或称相对于规则A→β)的直接短语,其中α、β、δ∈(VT∪VN)*。
6
句型aAbcde有三个短语,它们是:Ab(A)、d(B)、aAbcde(S)。
Ab(A)
S aAcBe aAcde 且 A Ab
∵S aAcde 且 A Ab
∴Ab是句型aAbcde中相对于A的短语
d(B)
S aAcBe aAbcBe 且 B d
∵S aAbcBe 且 B d
∴d是句型aAbcde中相对于B的短语
aAbcde(S)
S=S 且 S aAcBe aAbcBe aAbcde
∵S S 且 S aAbcde
∴ aAbcde是句型aAbcde中相对于S的短语
Ab是直接短语
d是直接短语
文法G:
S→aAcBe
A→b
A→Ab
B→d
7
③句柄
一个句型的最左面的直接短语称为该句型的句柄(在上例中Ab是句柄)。
Aβ或A→β不一定意味着β是一个短语,还必须有SαAδ这一条件。离开句型来讨论短语是没有意义的,这一点和求β的first集不一样。
短语是直接短语的必要条件,直接短语是句柄的必要条件。
若一个文法是无二义的,则句型的短语和直接短语是确定的,句柄是唯一的。
在LR分析法中,句柄就是可归约串。
继续问题的讨论。句型aAbcde中存在三个短语,它们是Ab、d和aAbcde,其中Ab和d是直接短语,句柄是Ab。不能因为存在规则A→b,就断定b是这个句型的一个短语,b不是句柄,甚至连短语都不是。
8
④规范归约(最左归约)
设α是文法G的一个句子,并且序列αn、αn-1、…α0满足下列三个条件,称该序列是α的一个规