编译原理课后习题解答.pdfVIP

编译原理课后习题解答 第4 章 4.2 节 上下文无关文法 解： 1）生成aa+a*的最左推导： S  SS*  SS+S*  aS+S*  aa+S*  aa+a* 2 ）生成aa+a*的最右推导： S  SS*  Sa *  SS+a*  Sa+a*  aa+a* 3 ）语法分析树如图 4 ）文法是无二义的。后缀表达式中运算符出现的次序就是计算的次序。 5 ）文法生成的语言是以a 为基本运算分量的+和*运算表达式的后缀形式。 解答： ①最左推导 S  0S1 00S11  000111 ②最右推导 S  0S1 00S11  000111 ③语法分析树 S 0 S 1 0 S 1 0 1 ④ 文法无二义 n n ⑤ 文法生成的语言L={0 1 | n=1} ①最左推导 S  +SS  +*SSS  +*aSS  +*aaS  +*aaa ②最右推导 S  +SS  +Sa  +*SSa  +*Saa  +*aaa ③语法分析树 S + S S * S S a a a ④文法无二义 ⑤文法生成以a 为基本运算分量的+和-运算的前缀表达式。 ①最左推导 S  S(S)S  (S)S  (S(S)S)S  (S(S)S(S)S)S  ((S)S (S)S)S  (()S (S)S)S  (()(S)S)S  (()()S)S  (()())S  (()()) ②最右推导 S  S(S)S  S(S)  S(S(S)S)  S(S(S)S(S)S)  S(S(S)S(S))  S(S(S)S())  S(S(S)())  S(S()())  S(()())  (()()) ③语法分析树 S S ( S ) S ε ε S S ( S ) ε ε S ( S ) S ε ε ε ④对文法的句子()()，存在两棵不同的语法分析树如下： S S S ( S ) S S ( S ) S ε ε ε ε S ( S ) S S ( S ) S ε ε ε ε ε ε 所以文法是二义的。 ⑤文法生成具有对称括号对的串。 ①最左推导 S  SS  S*S  (S)*S  (S+S)*S  (a+S)*S  (a+a)*S  (a+a)*a ②最右推导 S  SS  Sa  S*a  (S)*a  (S+S)*a  (S+a)*a  (a+a)*a ③语法分析树 S S S S * a ( S ) S