编译原理-第4章+语法分析文档.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 为了节省空间，我们将文法Ｇ［Ｅ］分析动作表（ACTION）和状态转换表（GOTO）关于终结符的各列对应地进行合并，合并之后分析表如下表所示。（关于表的构造方法以后再讨论） * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 其分析过程如下： S ?AB ?bBB ?bSbB ? bABbB ? bbBBbB(得第二个字符与输入串不匹配） S ?AB ?bBB ?bSbB ? bABbB ? bAaBbB (只能用A ∷＝Aa推倒，又遇A，出现了死循环） 由于文法规则中有左递归A ∷＝Aa，所以无法分析下去 * * * * * * * * * * * * * * * * * * * * * 即对文法中的任意一个非终结符号，其规则右部有多个选择时，若由各个选择所推出的终结符号串首符号集合要两两不相交。这样，就可能根据当时读进的符号是属于哪个选择的FIRST（αi），来唯一地确定应该选用哪个选择来匹配输入串。 * * * * * * * ④ 用SＬＲ方法解决“移进---归约”冲突。 在十二个项目集中，Ｉ１、Ｉ２和Ｉ９都含有“移进---归约”冲突，其解决办法是： 对于项目集Ｉ1＝｛S′∷＝Ｅ·，Ｅ ∷＝Ｅ·＋Ｔ｝，由于集合 ＦＯＬＬＯＷ（S′）＝｛＃｝与集合｛＋｝不相交，所以当状态为１时，面临着输入符号为＋时便移进，而面临着输入符号为＃时，则按规则S′∷＝Ｅ归约。 对于项目集Ｉ2＝｛Ｅ∷＝Ｔ·，Ｔ∷＝Ｔ·*Ｆ｝，由于集合 ＦＯＬＬＯＷ（Ｅ）＝｛＋，），＃｝与集合｛*｝不相交， 因此状态２面临输入符号为*时移进，而面临输入符号为＋或）或＃时，按规则Ｅ∷＝Ｔ归约。 对于项目集Ｉ9＝｛Ｅ ∷＝Ｅ＋Ｔ·，Ｔ ∷＝Ｔ·*Ｆ｝，同样由于FOLLOW（Ｅ)={+,),#}与集合｛*｝不相交，因此状态９面临着输入符号为*时移进，面临着输入符号为＋或）或＃ 时，按规则E∷＝E＋T归约。 * ⑤ 根据SLR(１）分析表构造方法构造SLR(１）分析表. 对于冲突项目的状态，如状态1，2，9，按用SＬＲ方法解决构造SLR(１）分析表. 对于其他状态项目集，只有一个归约项目，也是按照修改后构造SLR(１）分析表方法进行构造 状态 ACTION（动作） GOTO（状态转换） i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 S7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 * §4.3 自底向上语法分析 五、二义性文法的应用 1.问题的提出 从前面讨论可知，各种ＬＲ文法都是非二义性文法，如果对二义性文法构造其ＬＲ分析表，必然导致失败。但是某些二义性文法是非常有用的，有些二义性文法描述程序设计语言的结构比较直观，使用方便，例如关于表达式文法和条件语句文法。 例如关于算术表达式文法Ｇ［Ｅ］为 (1)Ｅ∷＝Ｅ＋Ｅ (3)Ｅ∷＝（Ｅ） (2)Ｅ∷＝Ｅ*Ｅ (4)Ｅ∷＝i 由于该文法本身没规定＋和*优先顺序，所以是二义性文法。 对该文法增加规则 (0)Ｅ′∷＝Ｅ 形成拓广文法，其ＬＲ（０）项目集族如下图所示 * 二义文法的LR(0)项目集 I0: E’→ ? E E → ? E+E E → ? E*E E → ?（E） E → ? i I3: E → i ? I1: E’→ E ? E → E ? +E E → E ? *E I2: E →（ ?E） E → ? E+E E → ? E*E E → ?（E） E → ? i I6: E →（ E ? ） E → E ? +E E → E ? *E I9: E →（ E ）? I4: E → E+ ? E E → ? E+E E → ? E*E E → ?（E） E → ? i