由底向上语法分析

1、2022-4-271第五章第五章自底向上的语法分析自底向上的语法分析2022-4-272内内 容容 5.1 自底向上的分析方法简介 5.2 算符优先分析法 5.3 LR 分析2022-4-273自自底向上的分析方法简介底向上的分析方法简介自底向上的语法分析器除自底向上的语法分析器除“接受接受”外，一般有两种外，一般有两种动作：动作：移进，将一个位于输入带上的最前面的终极符移入符号栈，符号栈中可以有符号，非终极符和一些其它的状态信息；2. 归约，将栈顶的符号串 利用产生式A归约为非终极符自底向上的语法分析器有时也称为移进-规约分析器。2022-4-274归约归约（Reduction） 推导的相反

2、过程叫归约 如果 S u1 u2 un-1 un 是最右推导，则它的逆向过程 ： un un-1 u2 u1 S, 被称为规范规约/ 最左归约。2022-4-275规约的例子规约的例子给定文法 G : S aAcBe A b | Ab B d句子 abbcde 的推导为 :SSacABe aAbcde abbcde dAbb规范规约为: aAbcde aAcde SacABedAbb aAcBe SaAcBe aAcdeabbcdebAbdaABcSe2022-4-276自底向上的语法分析存在中的自底向上的语法分析存在中的问题问题1 如果句型存在有多个子串与一产生式右部相匹配，该选择哪一个进行

3、规约？选择位于句型最左边的那一个子串。Why?因为分析器是从左向右扫描的。Answer:2022-4-277回顾回顾: 短语与句柄短语与句柄 w 是 uAv 相对于 A的短语，当且仅当 A +w, 这是一棵根为A的子树。 w是 uAv 相对于 A的直接短语，当且仅当 A w, 这是一棵高度为 1的子树。 句柄是句型的最左直接短语。 设 G是一个CFG, uAv 是G的一个句型 即 S +uAv, 那么：2022-4-278句柄句柄? 是否匹配产生式右部的的最左子串一定是句柄？Answer:不不, 可能是，也可能不是。可能是，也可能不是。2022-4-279句柄的例子句柄的例子 给定文法 G:

4、S var L: T L id, L | id T real 句子 var id, id: real 的语法树如下：varidLL:TSrealid,看位于最左边的 “id” id它是句柄吗?2022-4-2710问题问题2:如何识别句柄？如何识别句柄？ 试探。 当子串与某个产生式的右部匹配时，将其视为句柄，如果分析失败，则 回溯。 对文法做一些限制，这样可以根据规则来识别句柄，例如算符优先文法 (Operator Precedence Grammar， OPG ）识别句柄是移进-规约分析器的主要任务，它可以用如下方法实现：2022-4-2711OPG的基本思想的基本思想 每一个运算符均有其优

5、先级。 当两个运算符相邻，则优先级高的先计算。 表达式中所的操作数均被运算符隔开。 OPG的基本思想来源于算术表达式的计算。在算术表达式中：2022-4-2712运用算符优先级的例子运用算符优先级的例子 GE：EEE | EE | E*E | E/E | (E) | i 这是一个二义文法，但如规定*和/的优先级比+和-的高时，只有一棵语法树。对于句子 “i-i+i*(i-i)” ，我们有如下的归约：2022-4-2713i-i+i*(i-i)=E-i+i*(i-i)=E-E+i*(i-i)=E+i*(i-i) =E+E*(i-i)=E+E*(E-i)=E+E*(E-E)=E+E*(E)=E+E

6、*E=E+E=E* 的优先级比 +高运用算符优先级的例子运用算符优先级的例子2022-4-2714算符文法与算符优先文法算符文法与算符优先文法 若文法G的产生式右部不含两个VN符相邻的情况,则称G为算符文法算符文法.G的VT符被称为算符算符 可以证明,算符文法算符文法不会含有两个VN符相邻的句型 常见语言不一定是算符文法算符文法,但可容易地对其进行改造。例 PASCAL中的循环语句:for:= do可将其改为可将其改为 for := do to 2022-4-2715OPG定义定义 G中没有 产生式 (如： X) ，也没有含连续的非终极符的产生式。 对于任意的终极符对 (a, b)， 最多只有

7、下面的一种关系 a b, a b, a b, 它们分别表示a的优先级低于，等于，高于 b的优先级。 一个 CFG G 是 OPG, 当且仅当:2022-4-2716优先性的实质优先性的实质 a b：a比b先归约2022-4-2717什么时候什么时候 a = b ? a = b, 当且仅当a 和 b 同时归约 于是, a 和 b 应该是在同一个句柄中相邻。PaQbP ab or P aQb.于是有: a = b 当且仅当 G中有产生式，形如:2022-4-2718什么时候什么时候 a b? a b, 当且仅当 a 先于 b归约。 a 在位于b 前的R的短语中。 a 在短语R的最右边：. R+ a

8、 or R+ aQ 于是a和b 是邻居。 R短语的根, 应该是b 的邻居或者b跟随于 R。 R 和 b 在同一个产生式中, 如： P Rb , 因为在OPG中没有后继的非终极符。 PRbWaQ2022-4-2719什么时候什么时候 a b? 综上所述, 我们有: a b 当且仅当 a是b的哥哥的最小的子孙。s 形式地, a b当且仅当在G中有一产生式，形如： P Rb 并且 R + a 或 R + aQPRbWaQ2022-4-2720什么时候什么时候 a b 同样地, 我们有: a b当且仅当 b是a 的弟弟的最大的子孙。s 形式地, a b当且仅当在G中有一产生式，形如： P aR 且 R

9、 + b 或 R + Qb PaRWQb2022-4-2721优先级的总结优先级的总结孩子优先，叔伯随后，兄弟一同走。.(Children First, Uncles Later, and Brothers Together.)2022-4-2722 a = b,当且仅当在G中有一产生式，形如： Pab 或 PaYb a b,当且仅当在G中有一产生式，形如： P Rb 且 R+ a 或 R + aQ即:2022-4-2723计算计算a = b 很容易通过扫描所有的产生式找出形如 a = b所有的 (a, b)对: 如果存在有产生式 P ab 或 P aQb则a = b.2022-4-2724计

10、算计算 a b 我们已经知道 a b,当且仅当在G中有一产生式，形如：P aR 且(1) R + b or R + Qb 于是我们定义符合条件 (1) 的所有终极符如下Firstvt (R) = b | R + b or R + Qb . 如果对每一个终极符R求出了Firstvt(R)， 则如果存在有产生式 P aR ,那么对于 Firstvt(R) 中的任意的终极符b 都有有a b 定义Lastvt (R) 为 a | R + a 或R + aQ. 同样地 , 对a b的计算过程： 存在有产生式 : Ra 或 RaQ, 则 aLastvt(R) 如果 RT, 则对于任意的 a Lastvt(

11、T)， 将a加入 Lastvt（R）集合如果有产生式 P Rb, 则对于 Lastvt(R) 中的每个a，有a b2022-4-2727计算优先关系的例子计算优先关系的例子设文法 G:EE+T | T TT*F | F FPF | P P(E) | id首先计算 Firstvt(E) = + Firstvt(T)于是有: Firstvt (E) = +, *, , (, idFirstvt (T) = *, , (, id Firstvt (F) = , (, id Firstvt(T)=* Firstvt(F)Firstvt(F)= Firstvt(P) Firstvt(P)=( id同样地

12、可得到 : Lastvt (E) = +, *, , ), idLastvt (T) = *, , ), id Lastvt (F) = , ), id Lastvt (P) = ), id 2022-4-2728于是我们可得到所有非终极符的优先级。例如, 对 EE+T 和 Lastvt (E), 有: + +, * +, +, ) +, id + 运算符的优先级运算符的优先级2022-4-2729运算符的优先级运算符的优先级+*+(id)#*id()#右左 2022-4-2730算符优先分析的算法算符优先分析的算法 栈顶符号栈顶符号 输入符号输入符号, 找到栈中句柄，并用左部替代它。0. 用

13、栈来比较优先级； 1. 初始化栈顶为 “#”;2. 读入输入符号,比较栈顶符号和输入符号的优先级，当3. 重复步骤 2, 直到所有的输入符号都已处理且栈中只有开始符号为止。2022-4-2731OP 分析的例子分析的例子给定算术表达式： id + id * id其自底向上的分析过程如下: 有限状态控制#栈输入带id + id * id # idPush(id)#id+ id * id #id +Reduce by E ididEE# +Push(+)#E+id * id #+ id Push(id)#E+id* id #id *Reduce by E idEidE+ *Push(*)#E+E*

14、id #* idPush(id)#EE*id#+id #Reduce by E ididEE* #Reduce byE E * EE*#E+EReduce byE E + EE+#E+ #Hi, the string is accepted successfully!Do you see its structure on the right?EE+E | E*E | (E) | id2022-4-2732Stack Precedence Relation Input String Action# +id*id# Reduce # P +id*id# Shift# P+ *id# Reduce#

15、 P+P *id# Shift# P+P * # Reduce# P+P * P # Reduce# P+T # Reduce# E # Accept2022-4-2733Stack Input String Action# id+id*id# Shift # id +id*id# Reduce Pid # P +id*id# Reduce PF# F +id*id# Reduce FT# T +id*id # Reduce ET# E +id*id # Shift# E+ id*id# Shift# E+id *id # Reduce Pidid+id*id 的规范规约的规范规约2022-4

16、-2734# E+P *id# Reduce FP# E+F *id # Reduce FT# E+T *id# Shift# E+T* id# Shift# E+T*id # Reduce Pid# E+T*P # Reduce Fid# E+T*F # Reduce TF# E+T # Reduce EE+T# E # Accept2022-4-2735 OPG 与规范归约的比较与规范归约的比较“id+id*id” 的语法树FidEE+TTFTPF*idPPidEP+TidPP*idid“id+id*id”的分析框架 2022-4-2736 在算符优先文法中,由于优先关系仅定义于VT符中,

17、所以当句柄仅由一个VN符构成时,无法通过优先关系识无法通过优先关系识别出别出; 在扫描句型时,利用两个VT符之间的关系,我们总能找出一个被归约的子串(不一定是句柄),称为. 由于被归约的子串()不一定是(甚至甚至不一定是产生式的右部不一定是产生式的右部),因此,归约时可能无完全一致的产生式可用.解决的办法: 在P中找形为 的产生式,其中,Ui与Ni不一定相同,但每个ai必须相同.若存在这样的产生式,则用其归约,否则分析报错.2022-4-2737素短语（素短语（Prime Phrase） 实际上，OPG 中归约的不是句柄，因为它忽略了A B这样的推导。 例如，右边语法树的归约为: id P P

18、*P T其中 ,“P*P” 是短语但不是句柄。我们称其为素短语: 一个素短语是包含至少一个终极符，并且如自身外不再包含其它素短语的短语。EP+TidPP*idid2022-4-2738素短语素短语 算符优先分析的句型具有形式 w=#N1a1N2a2NnanNn+1#, 其中,(1)是一个短语,(2)它至少含有一个VT符,(3)满足(1),(2)的最小短语. 寻找的方法: 从左到右扫描w,找到第一个aiai+1时,记下ai,再回扫,找到第一个aj-1 aj,此时, 就是应被子归约的最左素短语2022-4-2739素短语的例子素短语的例子在右图中，有多少个素短语?EE+TFPidE+TT*F有两个

19、素短语: T*F id其中， “T*F” 是最左素短语。2022-4-2740有关素短语更多说明有关素短语更多说明 引入形如是为了定义终级符的优先级，在得到优先级后，可以将这些产生式删除。 实际上，如果事先已经定义了终极符的优先级，则可不需要引入形如A B的产生式。 2022-4-2741算符优先函数算符优先函数 是否可以将优先级的比较变为数的比较? 由此引入了优先函数。2022-4-2742算符优先函数的定义算符优先函数的定义 注意到左边和右边终极符的区别，需要使用两个函数f (a) 和 g (a) 来分别表示左边和右边的优先级。优先函数定义如下： s 两个函数 f, g 是优先函数， 如果

20、对任意的 a 和 b有有: f (a) g (b) iff a g (b) iff a b. 2022-4-2743算符优先函数的缺点算符优先函数的缺点 推迟了一些错误的发现， 可能会对一些不存在优先关系的非终极符进行比较。 对于一些 OPG， 不存在优先函数，如在下表中 ：aba=b=如果存在 f 和 g, 则有: f (a) g (b) = f (b) = g (a) = f (a), 矛盾矛盾! 于是该文法不存在优先函数。 2022-4-2744根据定义 : 初始化:For aVT, f(a)=g(a)=1 对 a,b VT 做 (1) 如果ab 但 f(a) g(b) 则 f(a)=g

21、(b)+1 (3) 如果 a=b 但 f(a) g(b) 则 minf(a), g(b)=maxf(a),g(b) 直到 f 和 g 不再改变。算符优先函数的计算算符优先函数的计算(1)2022-4-2745算符优先函数的计算算符优先函数的计算(2)用有向图 对于 aVT, 设置两个结点 fa 和 ga . 如果 a=b 或 ab ,从 fa 画弧至 gb;如果 a=b 或 ab，从 gb 画弧至 fa; 对于每个结点 fa 或 ga , 都赋一个数，这个数是从该结点出发所能到达的结点的个数，表示为f (a ) 或 g (a ); 如果不矛盾，则 f 和 g 是优先函数，否则没有优先函数。20

22、22-4-2746 id + * # id + * # = gidfidf*g*g+f+f#g# id + * # f 6 4 6 2 g 7 3 5 2 算符优先函数的例子算符优先函数的例子2022-4-2747自顶向下对由底向上, 哪个更好?由底向上更好。自顶向下自顶向下 对对 由底向上由底向上 1.自顶向下 在消除左递归和回溯时需要引入许多新的非终极符和空产生式 而由底向上却不会。 2. 更重要的是由底向上比自顶向下在中间代码生成晨更加有效。2022-4-2748看看看看OPG OPG 分析器很有效. OPG 比较窄， 只能应用于很小的一类，例如 文法： . S aAb | bBa A

23、aA|b B bB | a 我们需要有功能更加强大的由底向上的分析器。2022-4-2749为什么为什么OPG如此受限？如此受限？ 实际上在短语aAb中有 a a。 OPG分析器并不知道是位于哪个短语中，因此会发生冲突 。 因为只是根据局部的信息而不是全局的信息来做选择，就像是旅游者在一陌生的城市因为没有地图而迷路一样。2022-4-2750LL（1）分析器如何做的？）分析器如何做的？ 如果当前符号是 a 则选择 aAb , 如果当前符号是 b 则选择。 LL(1) 分析器因为是采用自顶向下的分析方法，用栈来保存进入的短语，它总是有全局信息。 思路思路: 由底向上的分析方法中是否也可以像LL(

24、1)分析器一样，在归约的时候也具有全局的信息呢？ 2022-4-2751LR(k) 分析分析 LR(k)分析在 1960年代提出。 LR(k) 分析是由底向上的分析方法。 LR(k) 意思是从左至右朝前看K个符号。 LR(k) 分析是有效的，且经常应用于实际的编译器中。2022-4-2752LR分析综述分析综述 计算机理论研究已证明了如下结论: LR(k)文法是无二义性无二义性文法; LR(k)文法与LR(1)文法等价等价. 由于常见的程序设计语言均能由LR(1)文法产生,因此我们只讨论k=0,1两种情况;2022-4-2753LR 分析器分析器 LR(0)：简单简单,能力低能力低; SLR（

25、1）: 简单的简单的 LR 最易实现,但功能较弱，能力仅强于LR(0) 。 LR（1）: 经典的经典的 LR 功能最强，但分析表大。 LALR:朝前看朝前看 LR 能力介于SLR(1)与LR(1)之间,表大小与SLR(1)相同,是最常用最常用的分析方法2022-4-2754LR 分析器模型分析器模型 输入串输入串LR 控制器控制器输出输出 栈栈actiongotoXmsm X2s2X1s1#s0a1 ai an#TS SS 分析器自左至右地扫描输入串的各符号，并根据当前分析栈的内容及正扫描的符号按分析表的指示完成相应的动作。 分析栈记录了已分析的内容及当前的状态； 开始时，栈内放入#及开始状态

26、S0，随着分析的深入，栈内容总是刻划了当前的状态，及分析的“”。2022-4-2755是LR分析器的核心，它由分析动作(ACTION)表和状态转移(GOTO)表两个子表组成;指明当栈顶为Sm,输入符为ai时应完成的分析动作;指明当分析栈移进一个输入符号或按某产生式进行归约后所要转移到的下一状态.a1a2alS1ACTION(S1 ,a1ACTION(S1 ,a2ACTION(S1 ,alS2ACTION(S2 ,a1ACTION(S2 ,a2ACTION(S2 ,alSnACTION(Sn ,a1ACTION(Sn ,a2ACTION(Sn ,alX1X2XlS1GOTO(S1 ,X1GOTO

27、(S1 ,X2GOTO(S1 ,XlS2GOTO(S2,X1GOTO(S2 ,X2GOTO(S2 ,XlSnGOTO(Sn ,X1GOTO(Sn ,X2GOTO(Sn ,XlACTION 表GOTO表2022-4-2756分析表的合并从分析表的功能及实例中,我们可看出,GOTO表中所有关于终结符的状态转换都与相应的ACTION表相关，因此我们可将其合并到ACTION表中，只将关于VN符的状态转换保留在GOTO表中：状态状态ACTIONGOTOab，#LE0s3s4 121 ac 2 s5r2 3 r3r3 4 r4r4 5s3s4 626 r1 在实际的分析表中，大在实际的分析表中，大多数表项

28、内容为多数表项内容为ERRORERROR，若略去不填，则分析表若略去不填，则分析表是一稀疏表，可采用是一稀疏表，可采用紧紧凑的格式凑的格式存储。存储。2022-4-2757LR 的分析算法的分析算法 用两个栈, TS 和 SS 来分别保存移入的符号和状态。 重复如下的动作： 设 SS栈的栈顶为 q ，TS的栈顶为 a。 动作 LRq,a = X: 如果X = sn,将 a 移进TS ，将 In 移入 SS; 如果X = rn, 用规则Au 进行归约：在TS和SS中都分别弹出 | u | 个单元 ；将 A 压入 TS；如果 LRp,A =m ，则将 Im 压入 SS，p 是 SS的栈顶。 直到输

29、入串被接受或者是出错为止。2022-4-2758StepTSInputAction 1） # abbcde# Shift 0 S2 2） #a bbcde# Shift 02 S4 4） #aA bcde# Shift 023 S6 6） #aA cde# Shift 023 S5 7） #aAc de# Shift 0235 S8 9） #aAcB e# Shift 02357 S911） #S # Accept 01 accMoves of LR parser on abbcde# 3） #ab bcde# Reduce(Ab) 024 r2 3 5） #aAb cde# Reduce(A

30、Ab) 0236 r3 3 8） # aAcd e# Reduce(Bd) 02358 r4 710） #aAcBe # Reduce(SaAcBe) 023579 r1 1ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1SSACTIONGOTOGS：(1) S aAcBe(2) A b(3) A Ab(4) B d2022-4-2759 规范推导的过程：S=aAcBe=aAcde=aAbcde=abbcdeGS：(1) S aAcBe(2) A b(3

31、) A Ab(4) B d待分析的句子待分析的句子abbcde# aAcBe 、aAcde、 aAbcde、 abbcde都是规范句型 aAcBe的前缀：a aA aAc aAcB aAcBe aAcde的前缀： a aA aAc aAcd aAcde aAbcde的前缀： a aA aAb aAbc aAbcd aAbcde abbcde的前缀： a ab abb abbc abbcd abbcde2022-4-2760StepTSInputAction 1） # abbcde# Shift 0 S2 2） #a bbcde# Shift 02 S4 4） #aA bcde# Shift 0

32、23 S6 6） #aA cde# Shift 023 S5 7） #aAc de# Shift 0235 S8 9） #aAcB e# Shift 02357 S911） #S # Accept 01 acc 3） #ab bcde# Reduce(Ab) 024 r2 3 5） #aAb cde# Reduce(AAb) 0236 r3 3 8） #aAcd e# Reduce(Bd) 02358 r4 710） #aAcBe # Reduce(SaAcBe) 023579 r1 1SSACTIONGOTO aAcBe的前缀： a aA aAc aAcB aAcBe aAcde的前缀： a

33、 aA aAc aAcd aAcde aAbcde的前缀： a aA aAb aAbc aAbcd aAbcde abbcde的前缀： a ab abb abbc abbcd abbcdeGS：(1) S aAcBe(2) A b(3) A Ab(4) B d2022-4-2761LR(0) 分析器分析器2022-4-2762LR（0）分析）分析 LR(0)分析就是k=0时的LR(k)分析.即在分析的每一步,根据当前的栈顶状态确定下一步动作.2022-4-2763活前缀活前缀从前面例子的分析过程可知,将栈内符号与未扫描的输入串拼接起来,可得一规范句型规范句型.即栈内符号串总是规规范句型的前缀范

34、句型的前缀,且不含句柄右侧的符号不含句柄右侧的符号.:句柄一旦在栈顶形成,就不再移进新符号,而是要进行归约了.我们把具有上述性质的符号串称为.有两个要点: (1)它是规范句型的前它是规范句型的前缀缀; (2)它不含句柄右侧符号它不含句柄右侧符号2022-4-2764活前缀活前缀 能够出现在移进-归约分析器的栈中的右句型的前缀集合称为活前缀。 S+Aww是GS的一规范推导，其中：AVN，、V*，wVT*，如果 是 的一个前缀, 则称 是文法的一个活前缀。在LR的分析中，活前缀 在符号栈中, 当出现 时，我们可用产生式A 来进行归约。2022-4-2765 GS: SaAcBe Ab AAb Bd

35、活前缀的例子活前缀的例子活前缀(包括句柄在内):aAcBeabaAbaAcd栈中的变化：aabaAaAbaAaAcaAcdaAcBaAcBeS: 若能构造一个,则构造分析表就不难了.2022-4-2766Sx59214306710111216151718aaaaAAAbccbdeB B 识别与有活前缀的识别与有活前缀的NFA2022-4-2767DFAX235789641AbaSbcBedGS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d*2022-4-2768由活前缀不含句柄右侧符号这一性质可知,活前缀与当前句柄的关系只能是下述三种情况之一:句

36、柄全部在活前缀中(句柄是活前缀的后缀);活前缀只含句柄的部分符号(活前缀的后缀是句柄的前缀);活前缀不含任何句柄符号.对于(1), 应进行归约: A, 记为A;对于(2),应移进(句柄的后半部分),A12;对于(3),期望移进一产生式的右部: A我们把右部添加了一个“”的产生式,称为2022-4-2769为由底向上制一张地图为由底向上制一张地图 如果分析器碰到 aAb 或 bBa , 我们可认为它将进入不同的状态。 移入 a (或 b) ，分析器将变为分析器将变为a Ab (或 b Ba )的状态。 在状态aAb时规约A的短语，分析器将进行变化，但依旧还是在短语aAb 中 如何来区分这种变化?

37、2022-4-2770引进了一个点引进了一个点 我们在产生式中用一个点 “.”来标识分析器正处的位置，这样的产生式称为一个点项目或项目 。 对前面所给例子，其项目如下: 2022-4-2771例S aAcBeS a AcBeS aA cBeS aAc BeS aAcB eS aAcBe GS: (0) SS (1) S a A c B e (2) A b (3) A Ab(4) B dS S SS A b A b A Ab A A b A Ab B d B d 2022-4-2772DFAX235789641AbaSbcBedS S SS A b A b A Ab A A b A Ab B d

38、 B d S aAcBeS a AcBeS aA cBeS aAc BeS aAcB eS aAcBe 2022-4-2773建立初始状态建立初始状态很容易考虑到初始状态 I0 可设置如下I0:S.a AbS.b BaI1S a .AbI2S b .Aaab如果移入 a/ b , 状态 I0 将转换到 I1 / I2, 如左图：状态状态I1 和和 状态状态 I2 又如何转换又如何转换 ? 2022-4-2774如何转换状态如何转换状态 I1?I0:S.a AbS.b BaI1S a .AbI2S b .BaabI1S a .AbA. aAA. bI3S a A .bA如果在状态 I1分析器已经

39、读入 A ( A 的短语已经被归约), I1 将转移到 I3，如图：如果 A 的短语没有被归约，状态 I1 应包括 A . aA 和 A . b, 如图：继续对 I1进行转换： I4A a . AA. aAA. bI5A b .ab2022-4-2775整个地图整个地图S.a AbS.b BaS b .BaB.b BB. aabS a .AbA. aAA. bS a A .bAA a . AA. a AA. bA b .baI1I2I0B b . BB. b BB. aI3S a Ab .I5B a .aS b B .abBI4bS b Ba.aI6I7I8I9abA a A.B b B.BA

40、I10I11I12ba2022-4-2776项目族项目族 当考虑状态 I1的转换时, 我们将A.aA 和 A.b 都置于状态中, 因为在 Sa.Ab中点正好在A的前面 状态中的项目称为LR(0) 的项目族。 实际上项目族上一闭包。2022-4-2777构造项目族构造项目族 对于每一个项目，我们依下列方法来构造其项目族I： 首先 I 包括项目 如果 I 包括 A u .Xv 和 X VN 则将所有 X . w 加入 I. 重复至 I稳定为止。2022-4-2778项目族间的转换项目族间的转换 如果一项目族 Ii 包括 Au .Xv , 则 Ii 将转移至 Ij , 其中Ij 包括 AuX.v ,

41、 如下图:X2022-4-2779构造转换图构造转换图 为了容易确定接受状态，拓广文法，新增产生式S S， S 为开始符号。 首先设置初始项目集 I0 ，它包括项目 S.S 。 从 I0开始，根据转换一一设置其它的项目集，直至没有新的状态产生为止。2022-4-2780S.S S b .BaabS a .AbS a A .bAA a . AA b .baI2I3I0B b . BI4S a Ab .I6B a .aS b B .abBI5bS b Ba.aI7I8I9I10abA a A.B b B.BAI11I12I13baS.S S.a AbS.b BaSS. I1SS a .AbA. a

42、AA. bS b .BaB.b BB. aA a . AA. a AA. bB b . BB. b BB. a转换图转换图2022-4-2781归约和移进归约和移进 S aAb . , A aA. , A b . S . aAb, S a .Ab, A aA.b 圆点在尾部意味着整个句柄被移入，应该进行归约。这种项目称为归约项目。 圆点在尾部之前意味着还没有得到句柄。这种项目称为移进项目。2022-4-2782Action 和和 Goto 对于归约项目，分析器应该进行归约。我们对所有规则进行编号，用 “r n” 表示 “用规则 n进行规约”。 对于移进项目如 S .X: 如果 XVT, 分析器

43、移入 X 并转移至下一个状态 n, 表示为 “sn”. 如果XVN, 分析器不需要移入 X ，只需转移至下一个状态n, 表示为 “n”. 前两种情况是Action，第三种情况是 Goto. 2022-4-2783构造构造LR(0)分析表分析表 一个LR(0) 分析表是一矩阵 LR I, VT VN , 其中 I 是项目族集, 它根据状态转换图来进行构造。 对于任意的 IMI ，且 a VT, 如果 IM对a转移至 IN,则将 “sN” 填入 LRIM, a. 对于任意的 IMI 且 A VN, 如果IM 对A转移至 IN ，则将 “N” 填入 LRIM, A. 对于任意的规约项目 IM, 如果

44、 IM 用规则N进行规约,则将 “rN” 填入 LRIM, T.2022-4-2784LR(0)分析表分析表 a b # A B S I0 s2 s3 1I1 accI2 s5 s6 4I3 s7 s8 9I4 s10I5 s5 s6 11I6 r4 r4 I7 r6 r6I8 s7 s8 12I9 s13I10 r1 r1I11 r3 r3I12 r5 r5I13 r2 r2 左边的分析表是所举例子的LR(0) 分析表。 左边部分是 Action表，右边部分是 Goto表。 在 Action中, sN: 移入符号并转移到状态 N; rN: 用规则 N进行规约 (所有规则已进行编号). acc

45、. 符号串已被接受。 在 Goto中, N: 转移至 N 2022-4-2785LR(0)的另一个例子的另一个例子设G: E aA | bB A cA | d B cB | d首先拓广文法： S ES.EI0S EE .aAE .bBEI1S E.aE a.AE a.AA .cAA .dI2bE b.BI3E b.BB cBB .dAE aA.I4cA c.AI5A c.AA .cAA .ddA d.I6BE bB.I7cB c.BI8B c.BB .cBB .ddB d.I9AA cA.I10cdBB cB.I11cd2022-4-2786LR(0) 分析表的例子分析表的例子I0 s2 s3

46、 1 I1 accI2 s5 s6 4 I3 s8 s9 7I4 r2 r2 r2 r2 r2I5 s5 s6 10I6 r5 r5 r5 r5 r5I7 r3 r3 r3 r3 r3I8 s8 s9 11I9 r7 r7 r7 r7 r7 I10 r4 r4 r4 r4 r4I11 r6 r6 r6 r6 r6abc#dEAB 规则: S E E aAE bB A cA A d B cB B d2022-4-2787用分析表进行分析用分析表进行分析 a b # A B S I0 s2 s3 1I1 accI2 s5 s6 4I3 s7 s8 9I4 s10I5 s5 s6 11I6 r4 r

47、4 r4 I7 r6 r6 r6I8 s7 s8 12I9 s13I10 r1 r1 r1I11 r3 r3 r3 FiniteI12 r5 r5 r5 ControlI13 r2 r2 r2#I0Token Stack (TS)State Stack (SS)Input TapeAt First, we put # in TS and the initial state I0 in SS. Given an input: aaaabb aaabb#For LRI0, a = s2, Push a in TS; Push I2 in SS. #aI0I2aabb#For LRI2, a = s

48、5,Push a into TS;Push I5 into SS.#I0aI2aI5abb#For LRI5, a = s5,Push a into TS;Push I5 into SS.#I0aI2aI5aI5bb#For LRI5, b = s6,Push b in TS;Push I6 in SS.#I0aI2aI5aI5bI6b#For LRI6, b = r4,Reduce by Rule 4: A b;Push A in TS.AbAFor LRI5, A = 11,Push I11 in SS.I11For LRI11, b = r3,Reduce by Rule 3: A aA

49、;Push A in TS .aI5aI2#I0AaAFor LRI5, A = 11,Push I11 in SS .I11For LRI11, b = r3,Reduce by Rule 3: A aA;Push A in TS .aI2#I0AaAFor LRI2, A = 4,Push I4 in SS.I4For LRI4, b=s10,Push b in TS;:Push I10 in SS.#I0aI1AI4b I10#For LRI10, #=r1,Reduce by Rule 1: S aAbPush S in TS;:#I0SabSFor LRI1, #=acc,So th

50、e string is accepted and the parsing is ended.I1For LRI0, S=1,Push I1 in SS.2022-4-2788用用LR(0)分析算术表达式分析算术表达式S .EE .E+TE .TT .T*FT .FF .(E)F .iI0 S E. E E.+TEI1T F.FF (.E)E .E+TE .TT .T*FT .FF .(E) F .i F i.iI3I4I5(E E+.TT .T*FT .FF .(E) F .i E T. T T.*FTT T* .FF .(E) F .i+I6I7 E ( E.) E E.+TETiI5I3F

51、*(I8 E E+T. T T. * FI5I4TI9Fi(I7* T T* F.I10FiI4(+ E (E).)I11I2?2022-4-2789LR(0) 应用讨论应用讨论 LR(0) 分析方法的应用范围还是太窄，它对于大部分的语言都有不太适用，甚至对于经常使用的诸如算术表达式之类的语言都有不适用。 这是因为对于大部分的语言的项目的状态转换图都有存在有冲突。如在表达式的例子中，状态I1, I2, I9 都有冲突。2022-4-2790SLR(1) 分析器分析器2022-4-2791LR 分析中的冲突分析中的冲突 移进-规约：如果在一个状态中存在有移进项目和规约项目，那么就产生了移进规约冲

52、突。 分析器应该如何来选择，是移进还是规约？ 规约-规约：如果在一个项目中有多于一个规约项目，则发生了规约-规约冲突，分析器应该如何来选择进行规约?2022-4-2792解决冲突的方法解决冲突的方法 朝前看，根据事件未来的发展来决定 或 优先级, 先做最重要的或最紧急的事件或 尝试, 如果可能的话。2022-4-2793解决解决LR(0)的冲突的冲突 根据Follow 集合，这就是 SLR(1)分析的思想。 根据超前搜索符号集合, 在构造项目时生成超前搜索符号集合，具有不同超前搜索符号集合的项目被认为是不同的项目。这是 LR(1)分析的思想。 根据优先级：可以根据产生式的优先级。2022-4-

53、2794SLR 分析的基本思想分析的基本思想 (1如果当前符号是 b, 则进行移入; (2)如果当前符号属于 Follow(A) ，则将 u 归约为 A; (3)如果当前符号属于 Follow(B) ，则将 u 归约为 B; (4) 其它情况为错误。 2022-4-2795构造构造 SLR 分析表分析表 加入新的项目 S .S, 得到其项目集记为 I0. 构造其项目集的状态转换图。 根据转换图构造 SLR 分析表，对于每一个项目： 如果没有冲突，就按LR(0)的方法去做； 如果有冲突，就根据SLR分析的思想利用 Follow集合解决。2022-4-2796算术表达式的算术表达式的SLR分析表分

54、析表 I0 *I1 *I2 I3 I4 I5 I6 I7 I8*I9 I10 I11i + * ( ) # E T Fs5 s4 1 2 3I1 中有 S E.和 E E.+ T, 这是冲突， Follow(S)= # 不包括 +, 于是如果当前符号是+, 则移入 + ; 如果当前符号是 # 则接受; 其它情况是出错。 s6accI2 中有 E T.和 T T.* F, 这是冲突， Follow(E)=+, ), # ，其中没有 *, 于是如果当前符号是 *,则移入 * ; 如果当前符号是 +, ) 或 # 则用 E T进行规约，其它情况是出错。 s7r2r2r2I3 中只有规约项目 T F.

55、我们可用两种方式处理，一种是对 Follow(T)=+, ), # 中的符号用填写 r3 ，其它符号则是错误，另外一种方法像 LR(0)一样，对所有的符号均填入 r3 。 r4 r4 r4 r4 s5 s4 8 2 3r6 r6 r6 r6 s5 s49 3 s5 s4 10 s6 s11I9 中包括 E E+T.和 T T.* F, 是冲突， Follow(E)=+, ), # 不包括 *，所以如果 当前符号是 *, 则移入 * ; 如果当前称号是 +, )或 # 则用产生式E T规约; 其它情况则是错误。r1 s7 r1 r1r3 r3 r3 r3 r5 r5 r5 r52022-4-27

56、97用优先级解决冲突用优先级解决冲突 在 OPG分析中，非终极符都没有什么区别，所以实际上在下面的文法中 ：E E+E | E*E | (E) | i 是用操作符的优先级来分析的。 如何用SLR(1)来分析这个文法? E .EE .E+EE .E*EE .(E)E .iI0EE E.E E.+EE E.*EI1(E (.E)E .E+EE .E*EE .(E)E .iI2iE i.I3+E E+.EE .E+EE .E*EE .(E)E .iI4*E E* .EE .E+EE .E*EE .(E)E .iI5EE ( E.)E E.+EE E.*EI6(iEE E+ E.E E.+EE E.*

57、EI7(I2iI3EE E* E.E E.+EE E.*E(iI8) E (E).I9+I4*+*+*?2022-4-2798用优先级解决冲突用优先级解决冲突 用优先级来解决冲突, SLR(1) 分析表如下： i + * ( ) # EI0 s3 s2 1I1 s4 s5 accI2 s3 s2 6I3 r4 r4 r4 r4I4 s3 s2 7I5 s3 s2 8I6 s4 s5 r1 r1I7 r1 s5 r1 r1I8 r2 r2 r2 r2I9 r3 r3 r3 r32022-4-2799用二义文法用二义文法设 G: SiSeS | iS | a 首先拓广文法 SS .S.SS .iS

58、eSS .iSS .aS i.SeSS i.SS .iSeSS .iSS .aiS .SSS a.aaS iS.eSS iS.SS iSe.SS i.SS .iSeSS .iS S .aI0I3I1I2iieI4I5aS iSeS.I6S由于 Follow(S) = e, #,我们不能用 Follow(S)来解决 I4中的冲突。 2022-4-27100IF语句的语句的SLR(1) 分析表分析表 i e a # S0 s2 s3 11 acc2 s2 s3 43 r3 r3 4 s5 r25 s2 s3 66 r1 r1如果我们约定在状态4中移进的优先级比归约要高，即意味着 else 匹配最近的 if, 我们可得到 SLR(1) 的分析表如下:2022-4-27101LR(1) 分析器分析器2022-4-27102SLR 分析器的问题分析器的问题 SLR 分析器在碰到下列情况时会中止 不能确定是移进还是归约时有多个可能的归约时,例如：Sid.Eid.idS .SS .E = ES .idE .E + idE .idFOLLOW(S) = #FOLLOW(E) = #,+,=SiSeS | iS | a2022-4-27103经典的经典的LR 分析器分析器 问题：问题： FOLLOW 不能够区分。回顾SLR的思想，状态 i 中有项目A