编译原理课后习题解答.pdf
文本预览下载声明
编译原理课后习题解答 第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
显示全部