第07章 自底向上LR分析法(New)

于是： 4+8-6/2*3 运算过程和结果唯一。 13
例: G[E] E→E+E | E*E | (E) | i
Vt={+, *, (, ), i} 这是一个二义文法，要用算符优先法分析有该文法所确定的 语言句子。 如：i+i*i
(1) 先确定终结符之间的优先关系
优先关系的定义:
设 a, b 为可能相邻的终结符
23
例: 文法G[E] E::=E+T|T T::=T*F|F F::=(E)|i
1、求每个非终结符号的FIRSTVT及LASTVT
FIRSTVT
LASTVT
E {+,*,(,i}
{+.*,),i}
T {*,(,i }
{*,),i}
F {(,i}
{),i}
2、求=关系：(=)
3、求<关系：+<FIRSTVT(T),*<FITSTVT(F),(<FIRSTVT(E) 4、求>关系： LASTVT(E)>+,LASTVT(T)>*,LASTVT(E)>)
i*i# *i# *i#
i# # # # #
优先关系 动作
#<i 移进
i>+ 规约
#<+ 移进
+<i 移进
i>* 规约
+<* 移进 *<i 移进 i># 规约 *># 规约
+># 规约 接受 16
6.3.2 算符优先文法的定义
(1)算符优先文法(OPG) (2)构造优先关系矩阵 (3)算符优先分析算法的设计
构造优先关系表：
b(右栈外) +

第讲LR分析法LR分析法是一种常用的语法分析方法，可以用于生成语法树，它是自底向上的语法分析方法。

在LR分析法中，L表示“自左向右扫描输入串的方式”，R表示“反向构建和规约的方式”。

LR分析法包括以下几个步骤：1.构造LR(0)项目集规范族：LR(0)项目集是指在一些语法分析的过程中，每个项目表示对应的产生式的哪一部分已经被扫描过了，哪一部分还没有被扫描过。

根据给定的文法，构造出所有可能的项目集，并将它们进行编号，得到项目集规范族。

2.构造LR(0)项目集规范族的DFA：根据构造出的LR(0)项目集规范族，可以构造出一个DFA（确定性有限自动机）来表示LR(0)语法分析的过程。

DFA的每个状态表示一个项目集，每个转移表示在一个状态下扫描一些符号后转移到另一个状态。

3.构造LR(0)分析表：根据构造出的LR(0)项目集规范族的DFA，可以构造出一个分析表，即LR(0)分析表。

分析表的行表示当前状态，列表示当前输入符号，表格中的每个元素表示下一步应该做的动作，可以是移进一些符号，也可以是规约一些项目。

4.进行LR(0)分析：根据构造出的LR(0)分析表，可以进行LR(0)语法分析。

分析的过程是根据当前状态和输入符号，在分析表中查找对应的动作，并执行该动作。

如果遇到移进动作，就将符号加入到解析栈中，同时移动输入指针；如果遇到规约动作，就从解析栈中弹出一些符号，然后根据规约产生式将新的非终结符加入到解析栈中。

5.构造SLR(1)分析表：LR(0)分析表中存在冲突的情况，无法完全正确地进行语法分析。

为了解决这个问题，需要对LR(0)分析表进行优化，得到SLR(1)分析表。

SLR(1)分析表与LR(0)分析表的结构类似，只是在一些冲突的情况下给出更加具体的动作指令。

6.进行SLR(1)分析：根据构造出的SLR(1)分析表，可以进行SLR(1)语法分析。

与LR(0)分析类似，根据当前状态和输入符号，在分析表中查找对应的动作，并执行该动作。

识别活前缀的DFA
拓广文法G[S]： 句子abbcde的可归前缀：
S’ → S[0]
S[0]
S → aAcBe[1] ab[1]
A → b[2]
aAb[3]
A → Ab[3]
aAcd[4]
B → d[4]
aAcBe[1]
识别活前缀及可归前缀的有限自动机
0S 2a
a 5
a 9
14 a
1*
b
3
4
6 A7b
第7章 LR分析法
LR分析法
自底向上分析法的关键是如何在分析过程中 确定句柄
LR分析法给出一种能根据当前栈中的符号 串进行分析的方法，即：向右查看输入串的 K个符号就可以唯一确定分析器的动作是移 进还是归约；用哪个产生式归约。
因而也就能唯一地确定句柄 R 最右推导
规范推导 规范句型 规范归约
LR分析算法
then begin pop || 令当前栈顶状态为S’ push GOTO[S’,A]和A(进栈)
end else if ACTION[s,a]=acc
then return (成功) else error end.重复
7.2 LR(0)分析
例 G[S]： S aAcBe A b A Ab B d
⇔aAcBe[1]
用(1)规约，前部aAcBe[1]
⇔S
这些前部符号串为归约时在栈里的符号串， 规范句型的这种前部称为可归前缀。
可归前缀和子前缀
分析上述每个前部的前缀，对应分别为：
ab[2]
,a,ab
aAb[3] ,a,aA,aAb
aAcd[4] ,a,aA,aAc,aAcd
aAcBe[1] ,a,aA,aAc,aAcB,aAcBe

LR(0)分析表的构造 7.2 LR(0)分析表的构造
文法共有１５个LR(0) 项目，表示在对这个文法 的句子进行分析的时候可能出现的１５种状态， 但是其中一些状态是等价的。 等价项目识别的活前缀是相同的，可以由他们组 成的项目集作为将要构造的ＤＦＡ的一个状态。
7.2 LR(0)分析表的构造
CLOSURE(I)函数 CLOSURE(I)函数——求与I相关的所有LR(0)项目的等 函数 价项目 I中的每一项目都属于它 若A→α·Bβ属于CLOSURE(I)且B→γ是文法中的一个产 生式，则关于产生式B的任何形如B→·γ的项目也属 于它 重复上述步骤，直到它不再增大为止 利用闭包算法可以把ＬＲ（０）项目分为几个等价 类
LR分析器的工作过程
总控程序在分析的每一步， 总控程序在分析的每一步，都是按照 栈顶状态q和当前输入符号a 查阅LR 栈顶状态q和当前输入符号a，查阅LR 分析表，并执行其中ACTION[q，a]和 分析表，并执行其中ACTION[q，a]和 ACTION[q GOTO部分规定的操作。 GOTO部分规定的操作。 部分规定的操作
x1
S1 S2
x2
… xi
xn
X1,X2…Xn为文法字汇 表中的全部文法符号
GOTO[Si,X]规定了 当前状态为Si,栈顶 为文法符号X时,转 移到的下一个状态.
Goto [sm,xi]
Sm sn
LR分析器的工作过程
LR分析器的一个构形由两部分构成:栈中符号串 和尚待扫描的输入串 (S0X1S1X2S2…XmSm,aiai+1…an$) 分析器的工作过程就是从一种构形到另一种构形 的转换过程. (S0，a1a2…an$)为初始构形 (S0AZ,$),其中A是文法开始号,ACTION[Z,$]= 接 收 分析器的下一次移动是由栈顶状态Sm和当前输入 符号ai去查看ACTION表并执行ACTION[Sm,ai]规定 的动作并根据GOTO[Sm,ai]表去确定栈顶状态