编译原理作业一
1、第一章课后作业
1、解释下列术语：
编译程序，源程序，目标程序，编译程序的前端、后端和遍
解：
(1)
编译程序：从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。
(2) 源程序：源语言编写的程序。
(3) 目标程序：目标语言书写的程序。
(4)
编译程序的前端：将与仅依赖于源程序而与目标机器（硬件）无关的阶段组合成前端。
(5) 后端：将与目标机器（硬件）相关的阶段组合成后端。
(6)
遍：“遍”也称为“趟”。所谓“一遍”，就是对源程序或等价的中间程序从头到尾扫视一次，并完成编译任务之过程。
2、编译程序有哪些主要构成成分？各自的主要功能是什么？
解：
一个典型的编译程序通常包含 8 个组成部分，它们是：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。
各自的功能如下：
- 词法分析程序：从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出一个个的单词。
- 语法分析程序：层次分析。依据源程序的语法规则把源程序的单词序列组成语法短语（表示成语法树）。
- 语义分析程序：审查程序有无语义错误，为代码生成阶段收集类型信息。
- 中间代码生成程序：按照语义规则，将语法分析程序分析的结果保存到各类语义信息表中。
- 代码优化程序：改进中间代码，以便生成更好的目标代码。
- 目标代码生成：以源程序的中间表示形式作为输入，并把它映射到目标语言。
- 表格管理程序：记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息。
- 出错处理程序：报告出错信息、排错和恢复编译工作。
3、什么是解释程序？它与编译程序的主要不同是什么？
解释程序是解释、执行高级语言源程序的程序。
它与编译程序的主要不同是它并部通过翻译的方式生成目标程序。从用户的角度看，解释器直接利用用户提供的输入执行源程序中指定的操作。
4、对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
(1) else 没有匹配的 if。
(2) 数组下标越界。
(3) 使用的函数没有定义。
(4) 在数中出现非数字字符。
解：
(1) 语法分析
(2) 语义分析
(3) 语法分析
(4) 词法分析
2、课堂作业
试设计一文法 \(G\)，使得 \(L(G)\) 为能被 \(3\) 整除的整数集。
解：
首先，将 0-9 这十个数字分成三组。
- 0，3，6，9：可以被 3 整除
- 1，4，7：被 3 整除余 1
- 2，5，8：被 3 整除余 2
文法表达式为：\(G = (V_N, V_T, P, S)\)，其中
\[ \begin{split} V_N = \{ S, A, B \} \\ V_T = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8 9 \} \end{split} \]
然后，分类讨论。
对开始符 \(S\)
- 若和 \(0, 3, 6, 9\) 组合，有 \(S \rightarrow (0|3|6|9)S|\varepsilon\)
- 若和 \(1, 4, 7\) 组合，有 \(S \rightarrow (1, 4, 7)A\)
- 若和 \(2, 5, 8\) 组合，有 \(S \rightarrow (2|5|8)B\)
对非终结符 \(A\)，其左边是 \(1, 4, 7\) 三个数字。
- 若和 \(0, 3, 6, 9\) 组合，有 \(A \rightarrow (0, 3, 6, 9)A\)
- 若和 \(2, 5, 8\) 组合，有 \(A \rightarrow (2|5|8)S\)
- 若和 \(1, 4, 7\) 组合，有 \(A \rightarrow (1|4|7)B\)
对非终结符 \(B\)，其左边是 \(1, 4, 7\) 三个数字。
- 若和 \(0, 3, 6, 9\) 组合，有 \(B \rightarrow (0|3|6|9)B\)
- 若和 \(1, 4, 7\) 组合，有 \(B \rightarrow (1|4|7)S\)
- 若和 \(2, 5, 8\) 组合，有 \(B \rightarrow (2|5|8)A\)
综上，\(P\) 的规则是
\[ \begin{align} &S \rightarrow (0|3|6|9)S|(1|4|7)A|(2|5|8)B|\varepsilon \\ &A \rightarrow (0|3|6|9)A|(2|5|8)S|(1|4|7)B \\ &B \rightarrow (0|3|6|9)B|(1|4|7)S|(2|5|8)A \end{align} \]
3、第二章课后作业
1、文法 \(G = (\{ A, B, S \}, \{ a, b, c \}, P, S)\)，其中 \(P\) 为
\[ \begin{align} & S \rightarrow Ac|aB \\ & A \rightarrow ab \\ & B \rightarrow bc \end{align} \]
写出 \(L(G[S])\) 的全部元素。
解：
\[ L(G[S]) = \{ abc \} \]
4、证明文法
\[ G = (\{ E, O \}, \{ (, ), +, *, v, d \}, P, E) \]
是二义的，其中 \(P\) 为
\[ \begin{align} &E \rightarrow EOE|(E)|v|d \\ &O \rightarrow +|* \end{align} \]
证明：
可为句子 \(v * v + v\) 构造两个不同的最左推导：
\[ \begin{align} E &\Rightarrow EOE \\ &\Rightarrow EOEOE \\ &\Rightarrow vOEOE \\ &\Rightarrow v*EOE \\ &\Rightarrow v*vOE \\ &\Rightarrow v*v+E \\ &\Rightarrow v*v+v \\ E &\Rightarrow EOE \\ &\Rightarrow vOE \\ &\Rightarrow v*E \\ &\Rightarrow v*EOE \\ &\Rightarrow v*vOE \\ &\Rightarrow v*v+E \\ &\Rightarrow v*v+v \end{align} \]
故文法 \(G\) 是二义的。
11、一个上下文无关语法生成句子 \(abbaa\) 的唯一语法树如下：
(1)、给出该句子相应的最左推导和最右推导。
(2)、该文法的产生式集合 \(P\)
可能有哪些元素？
(3)、找出该句子的所有短语、简单短语、句柄。
解：
(1)、句子 \(abbaa\) 的最左推导如下
\[ \begin{align} S &\Rightarrow ABS \\ &\Rightarrow aBS \\ &\Rightarrow aSBBS \\ &\Rightarrow a\varepsilon BBS \\ &\Rightarrow a\varepsilon bBS \\ &\Rightarrow a\varepsilon bbS \\ &\Rightarrow a\varepsilon bbAa \\ &\Rightarrow a\varepsilon bbaa \\ \end{align} \]
最右推导如下
\[ \begin{align} S &\Rightarrow ABS \\ &\Rightarrow ABAa \\ &\Rightarrow ABaa \\ &\Rightarrow ASBBaa \\ &\Rightarrow ASBbaa \\ &\Rightarrow ASbbaa \\ &\Rightarrow A\varepsilon bbaa \\ &\Rightarrow a\varepsilon bbaa \\ \end{align} \]
(2)、
产生式有：
\[ \begin{split} S &\rightarrow ABS|Aa|\varepsilon \\ A &\rightarrow a \\ B &\rightarrow SBB|b \end{split} \]
可能的元素有：
\[ \varepsilon \; aa \; ab \; abbaa \; aaabbaa \; \cdots \]
(3)、
该句子的短语有：
\(a\) 是相对 \(A\) 的短语；
\(\varepsilon\) 是相对 \(S\) 的短语；
\(b\) 是相对 \(B\) 的短语；
\(\varepsilon bb\) 是相对 \(B\) 的短语；
\(aa\) 是相对 \(S\) 的短语；
\(a\varepsilon bbaa\) 是相对 \(S\) 的短语；
直接短语有：\(a \; \varepsilon \; b\)；
句柄是：\(a\)。
12、构造产生如下语言的上下文无关文法各一个：
\[ \begin{align} &(2) \; \{ a^m b^n | m \geqslant n \geqslant 0 \} \\ &(5) \; \{ a^n b^m | n \geqslant 0, m \geqslant 0, 且 3n \geqslant m \geqslant 2n \} \\ &(6) \; \{ ww^R | w \in \{ a, b \}^*, 其中, w^R 表示 w 的反向串，其含义是将 w 中的字母依次反转，首尾字母交换位置 \} \\ \end{align} \]
解：
(2)、
\[ \begin{split} S \rightarrow aSb|aS|\varepsilon \end{split} \]
(5)、
\[ \begin{split} S \rightarrow aSbb|aSbbb|\varepsilon \end{split} \]
(6)、
\[ S \rightarrow aSa|bSb|\varepsilon \]
18、给出生成下述语言的一个 3 型文法：
(2)、\(\{ a^nb^m|n, m \geqslant 1 \}\)
解：
\[ \begin{split} S &\rightarrow aA \\ A &\rightarrow aA|B \\ B &\rightarrow bB|b \end{split} \]