编译原理复习题2012.docVIP

文法类型的辨别(说明文法类型并说明原因)。 文法G: S-aB|bA A-a|aS B-aB|b 画出语法树，写出最右推导和最左推导过程，指出短语、直接短语、句柄。 文法Ｇ： S- S S *| S S +|( 句型为：aa+a* 3.把下列中缀表达式改写成和前缀表达式。 中缀表达式：-a/c+b*(-a+c) 4.下列文法能否用确定的自顶向下分析的方法分析(写出判断过程)。 文法G： S-AB A-aA|a B-bB|b 5．把下列正规式转换为DFA a（b|a）*aba 文法类型的辨别(说明文法类型并说明原因)。 文法G: S-aB|bA A-a|aS B-aB|b 答：3型文法，因为每个产生式都是形如A-aB或A-a 画出语法树，写出最右推导和最左推导过程，指出短语、直接短语、句柄。 文法Ｇ： S- S S *| S S +|a 句型为：aa+a* 最右推导: S= S S* = S a *=SS+a*=Sa+a*=aa+a* 最左推导S= S S* = S S + S *=aS+S*=aa+S *=aa+s * 短语:a1;a2;a1;a2a3+;a1a2+a3* 直接短语: a1;a2;a3; 句柄:a1 3.把下列中缀表达式改写成后缀表达式和前缀表达式。 中缀表达式：-a/c+b*(-a+c) 答：后缀表达式: @ac/b@ac+*+ 前缀表达式: +/@ac*b+@ac 4.下列文法能否用确定的自顶向下分析的方法分析(写出判断过程)。 文法G： S-AB (1) A-aA|a (2) B-bB|b (3) 答： (2)含有左公共因子，提取 A-aA` A`-A|( (3)含左公共因子，提取 B-aB` B`-B|( 能推出(的非终结符有：A`和B`。 求FIRST集： FIRST(S)={a,b}; FIRST(A)={a}; FIRST(A`)={a, (}; FIRST(B)={b}; FIRST(B`)={b, (} 求FOLLOW集： FOLLOW(S)={#}; FOLLOW(A)={# }; FOLLOW (A`)={# }; FOLLOW (B)={ #}; FOLLOW (B`)={#} 求Prodict集： Prodict (A-aA`)={a} Prodict(A`-A)={a} Prodict (A`-()={# } Prodict(B-bB`)={b} Prodict (B`-B)={b} Prodict(B`-()={ # } 求左部相同产生式的SELECT集的交集： Prodict (A`-A)( Prodict (A`-()={a}({# }=( Prodict (B`-B)( Prodict (B`-()={b}({# }=( 交集为空，能用确定的自顶向下分析的方法分析。 S S S * S S + a1 a2 a3