第三章 语法分析3.ppt

有文法如下， ( S’ →S ) 1) S →A|B 2) A →aAc 3) A →a 4) B →bBd B →b 构造识别其所有规范句型活前缀的DFA。 练习 I0: S’→.S S→.A S→.B A→.aAc A→.a B→.bBd B→.b S I1:S’→S. A I2:S→A. B I3:S→B. a I4: A→a.Ac A→a. A→.aAc A→.a b I5: B→b.Bd B→b. B→.bBd B→.b A I6:A→aA.c a b B I7: B→bB.d c I8:A→aAc. d I7: B→bBd. S’ →S S →A|B A →aAc A →a B →bBd B →b 只有当一个文法G是LR(0)文法，即G的每一个状态不出现冲突时，才能构造出LR(0)分析表。 由于大多数适用的程序设计语言的文法不能满足LR(0) 文法的条件，因此要使用向前查看一个符号的办法来处理冲突。 只对有冲突的状态向前查看一个符号，即查看FOLLOW集，以确定做哪个动作，这种分析方法为简单的LR分析法，用SLR(1)表示。 如果每个项目都附上k个终结符号，表示要对它进行归约时，后续的k个输入符号与这k个符号相同时，才能对栈顶进行归约。这就是LR(k)分析。 3.5.3 SLR分析表的构造 该项目集中既含有移进项目，又含有归约项目，出现了冲突。 解决冲突的办法是：分析所有含A、B的句型，根据后继符号来判断。当面临的输入符号a为： 当a = b，则b应移进； 当a ∈FOLLOW(A)，则用产生式A?α进行归约； 当a ∈FOLLOW(B)，则用产生式B? β进行归约。 I = { X?δ·bγ A?α· B?β· } SLR(1)解决办法 可见，{b} ∩FOLLOW(A) ∩FOLLOW(B)=? (0) S′ →E (1)E→E+T (2)E →T (3)T →T*F (4)T →F (5)F →(E) (6)F →i 移进-归约冲突 移进-归约冲突 FOLLOW(E)={#,),+} 如果当前输入符号为#, ), +时，就使用E→T进行归约； 如果当前输入符号为*时，就移进； 当面临其他输入符号时，出错。 I2: E→T· T→T·*F SLR(1)分析表的构造算法 设有文法G，则SLR(1)分析表的构造方法为： ? 对于A ??·X??Ik，GOTO(Ik,X)=Ij 若X ?Vt，则置action[k,X]=Sj ,即把(j,X)移进栈 若X ?VN，则置goto[Ik,X]=j ? 对于A?? · ? Ik ，则对x?FOLLOW(A) ，则置action[k,x]=rj (设A ??是第j个产生式)，即用A ??归约 ? 若S’ ?S · ?Ik，则置action[k,#]=acc，即接受 ? 其他均置出错。 按照该方法构造的分析表，如果每个入口不含多重定义，则称为SLR表，文法G称为SLR(1)文法。 【例】表达式文法的SLR分析表构造如下。 求非终结符的 FISRT 集和 FOLLOW 集 FIRST( F ) = { id, ( } FIRST( T ) = { id, ( } FIRST( E ) = { id, ( } FOLLOW( E ) = { ), +, # } FOLLOW( T ) = { ), +, #, * } FOLLOW( F ) = { ), +, #, * } 1) Ｅ→Ｅ+Ｔ 2) Ｅ→Ｔ 3) Ｔ→Ｔ*Ｆ 4) Ｔ→Ｆ 5) Ｆ→(Ｅ) 6) Ｆ→id 见课本P77 表3.13 1) Ｅ→Ｅ+Ｔ 2) Ｅ→Ｔ 3) Ｔ→Ｔ*Ｆ 4) Ｔ→Ｆ 5) Ｆ→(Ｅ) 6) Ｆ→id SLR(1)分析的局限性 如果 SLR(1) 分析表仍有多重入口（移进归约冲突或归约归约冲突），则说明该文法不是 SLR(1) 文法； 说明仅使用 LR(0) 项目集和 FOLLOW 集还不足以分析这种文法。 请看下页中的例子。 【例】有文法G[S]如下： (1) S→L=R (2) S→R (3) L →*R (4) L →i (5) R →L I0: S’→.S S→.L=R S→.R L→.*R L→.i R→.L I1: S’→S. I2: S→L.=R R→L. L I3: S→R. R I4: L→*.R R→.L L→.*R L→.i I5: L→i . * i I6: S→L=.R R→.L L→.*R L→.i = I7: L→*R. R L I8: S→L=R. R * L i S I2: S→L.=R R→L. *