编程语言与编译原理及其设计实现 第三版 课后答案（王晓斌 陈文宇）

打开下面链接，直接免费下载资源： https://renmaiwang.cn/s/annns ### 知识点总结#### 一、文法类型与语言定义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))`，我们可以看到最左推导和最右推导的步骤略有不同。- **语法树** - 语法树是一种图