B d
e
SaAcBeaAcdeaAbcdeabbcde SS→aAcBeB→d A→Ab A→b
每次归约的都是句型中的句柄。
22
算符优先分析法
LR分析法
23
1. LR分析法介绍
2. LR(0)分析表的构造
3. SLR分析表的构造
24
从左(Left,L)向右扫描输入串,构造一 个最右推导(Rightmost,R)的逆过程 进行规范归约(最左归约),每次归约 的都是真正的句柄; 对文法限制最少,是识别效率较强的方 法; 出错处理能力较强; 采用自动构造技术(构造LR分析表)
B
e
A
b
d
S → aAcBe A → Ab A→b B→d
b
分 析 树
输入串:abbcde
7
短语 直接短语 句柄
8
定义:设文法G的开始符号为S,是文法 *则称β是 的一个句型,若有SA且Aβ, + 相对于非终结符A的一个短语。 句型
短语是指句型中的某个部分,这部分可以由某 个非终结符推出。 可以利用语法树来找出句型中的所有短语。
查表 A[0,a]=s2,进栈 A[2,a]=s2,进栈 A[2,b]=s5,进栈 A[5,b]=r2,按第2条产生式归约 G[2,A]=3,进入状态3 A[3,b]=s4,进栈 A[4,#]=r1,归约 G[0,A]=1,进入状态1 A[1,#]=acc 31
对于一个文法,如果能够构造一张分析表, 使得它的每个入口均是唯一确定的,则我们 把这个文法称为LR文法。
33
前缀:字的任意首部。即移去符号尾
部零个或多于零个符号得到的一个符
号串。 例:abc的前缀有ε,a, ab, abc