编译原理-龙书-习题答案

资源描述

本仓库提供《编译原理》（龙书）的习题答案，格式为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 *

为此符号串构造语法树：

    S
   / \
  S   S *
 / \   \
a   S + a
   / \
  a   a

文法生成什么样的语言？证明结论：

解：将 a 看作运算数，文法生成语言 L={支持加法、乘法的表达式的后缀表示形式}。证明类似2.2题。

2.2 下列文法生成什么样的语言？证明你的结论。是否有二义性？

S → 0 S 1 | 0 1

解：生成语言 L={0^n 1^n | n>=1}。

证明： 1) 证文法推导出的符号串都在 L 中：

• 考虑最小语法树，推导出的符号串 01 显然 ∈ L。
• 假定结点数 < n 的语法树对应的符号串都 ∈ L，考虑结点数 = n 的语法树 S，其结构必为 S → 0 S 1，子树 S1 结点数 < n，因此对应符号串 t1 ∈ L，S 对应符号串为 t = 0 t1 1，因此 t ∈ L。
• 综合 i)、ii)，1) 得证。

使用说明

1. 下载本仓库中的 编译原理-龙书-习题答案.docx 文件。
2. 使用 Microsoft Word 或其他支持 Word 格式的软件打开文件。
3. 查看并参考习题答案。

注意事项

• 本资源仅供学习参考，请勿用于商业用途。
• 如有任何问题或建议，欢迎在仓库中提交 Issue。

下载链接

编译原理-龙书-习题答案