编译原理龙书第二章

《编译原理龙书第二章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章部分习题答案2.1考虑文法S→SS+

2、SS*

3、aa)证明文法可生成符号串aa+a*解：S→SS*→SS+S*→aS+S*→aa+S*→aa+a*b)为此符号串构造语法树解：c)文法生成什么样的语言？证明结论解：将a看作运算数，文法生成语言L={支持加法、乘法的表达式的后缀表示形式}证明类似2.2题b)＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝2.2下列文法生成什么样的语言？证明你的结论。是否有二义性？a)S→0S1

4、01解：生成语言L={0n1n

5、n>=1}证明：1)证文法推导出的符号串都在L中i)考虑

6、最小语法树，推导出的符号串01显然∈Lii)假定结点数

7、合1)、2)，文法生成的语言即为L另外，文法没有二义性＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝a)S→+SS

8、-SS

9、a解：生成语言L={支持加法、减法的表达式的前缀表示形式}证明：1)证文法推导出的符号串都在L中i)考虑最小语法树，推导出的符号串a显然∈Lii)假定结点数

10、由文法推导出i)L中最短符号串a，显然可由文法推导出ii)假定L中长度

11、e解：生成语言L={括号匹配的符号串，包括e}证明：1)证文法推导出的符号串都在L中i)考虑最小语法树，推导

12、出的符号串e显然∈Lii)假定结点数

13、论哪种情况，必有t2∈L，t1、t2长度

14、bSaS

15、e解：生成语言L={相同个数的a、b组成的所有符号串，包括e}证明：1)证文法推导出的符号串都在L中i)考虑最小语法树，推导出的符号串e显然∈Lii)假定结点数

16、n的语法树S，其结构有两种可能，子树S1、S2结点数

17、1、t2构造语法树，则可为t构造语法树，即t可被文法推导出综合i)、ii)，2)得证综合1)、2)，文法生成的语言即为L另外，文法有二义性，符号串abab可对应两个语法树＝＝＝＝