程序设计语言与编译 语言的设计和实现 第三版 课后答案 (王晓斌 陈文宇)

### 知识点总结 #### 一、文法类型与语言定义 1. **上下文有关文法（1型文法）** - 定义：上下文有关文法是一种形式文法，在乔姆斯基分层中属于第1级。这种文法允许产生规则中的非终结符可以被任何字符串替换，只要该字符串符合特定条件即可。 - 示例：给定文法 `G` 产生语言 `L(G) = {a^n b^n c^n | n ≥ 1}`。这表示所有形如 `abc`, `aabbc`, `aaabbbccc`, ... 的字符串都属于这个语言。 2. **3型文法** - 定义：3型文法也称为正规文法，包括右线性文法和左线性文法两种类型。这类文法通常用于描述正则语言。 - 示例：给定文法 `G` 产生语言 `L(G) = {a^n | n ≥ 1且n为奇数}`。这表示所有形如 `a`, `aaa`, `aaaaa`, ... 的字符串都属于这个语言。 3. **2型文法** - 定义：2型文法即上下文无关文法，这类文法在乔姆斯基分层中属于第2级，可以用来描述上下文无关语言。 - 示例：给定文法 `G` 产生语言 `L(G) = {a^n b^n | n ≥ 1}`。这表示所有形如 `ab`, `aabb`, `aaabbb`, ... 的字符串都属于这个语言。 4. **1型文法** - 本例中提到的1型文法与前面的1型文法相同，此处不再赘述。 #### 二、文法的推导与语法树 - **最左推导与最右推导** - 最左推导是指在每一步推导中总是选择当前串中最左边的非终结符进行展开。 - 最右推导则是指在每一步推导中总是选择当前串中最右边的非终结符进行展开。 - 示例：对于给定文法 `S → ((A))`，我们可以看到最左推导和最右推导的步骤略有不同。 - **语法树** - 语法树是一种图形化表示句子结构的方法，它通过节点和边来展示一个句子如何按照文法规则逐步构造出来。 - 在示例中，虽然给出了语法树的符号表示 `[pic]`，但实际上并没有提供具体的图形，这里我们可以通过文字描述理解其含义。 #### 三、文法的属性 1. **二义性** - 文法的二义性是指一个文法对于某些输入串存在多棵合法的语法树。 - 示例：给定文法 `G(S)` 对于串 `aaabaa` 可以构造出两棵不同的语法树，因此该文法具有二义性。 2. **消除递归** - 直接左递归：如果在文法的某个产生式中，非终结符直接出现在自身右侧，则称该产生式包含直接左递归。 - 间接左递归：如果在一系列产生式的推导过程中，一个非终结符最终导致了自身的出现，则称这些产生式包含间接左递归。 - 消除左递归的方法通常包括提取公共前缀、重新组织产生式等形式。 - 示例：通过一系列步骤消除了文法中的直接和间接左递归，并给出了消除后的文法形式。 3. **LL(1) 文法** - LL(1) 文法是一种特殊的上下文无关文法，其中“LL”表示自顶向下、从左到右的解析，“1”表示在读入一个符号的情况下可以唯一确定下一个非终结符的产生式。 - 判断一个文法是否为LL(1) 文法的主要方法是构建预测分析表并检查是否存在冲突。 - 示例：根据给定的文法构建预测分析表，并证明它是LL(1) 文法。 #### 四、句型与短语 - **句型** - 句型是指文法中由起始符号经过一系列推导后产生的串，可以是终结符和非终结符的混合体。 - 示例：通过推导验证了 `FaPbc` 和 `FaPbc` 分别是两个不同文法的句型。 - **短语、直接短语与句柄** - 短语是指在一个句型中，可以从起始符号通过一系列推导得到的最大子串。 - 直接短语是指短语中不能再被进一步推导的子串。 - 句柄是指直接短语中包含起始符号的子串。 - 示例：对于给定的推导过程，列出了短语、直接短语和句柄的具体实例。 通过以上分析可以看出，《程序设计语言与编译 语言的设计和实现 第三版》这本书中的习题涵盖了文法的基本概念、文法的分类、推导过程以及语法树等方面的知识，这些知识点都是学习编译原理的重要基础。