编译原理-龙书-习题答案,word版。内容举例:
第二章部分习题答案
2.1 考虑文法
S→ S S + | S S * | a
证明文法可生成符号串 a a + a *
解:S→ S S * → S S + S * →a S + S * → a a + S *→ a a + a *
为此符号串构造语法树
解:
文法生成什么样的语言?证明结论
解:将a看作运算数,文法生成语言L={支持加法、乘法的表达式的后缀表示形式}
证明类似2.2题b)
=====================================
2.2 下列文法生成什么样的语言?证明你的结论。是否有二义性?
S → 0 S 1 | 0 1
解:生成语言L={0n1n | n>=1}
证明:1) 证文法推导出的符号串都在L中
考虑最小语法树,推导出的符号串01显然∈L
假定结点数
1