### 华东交通大学编译原理试题库解析
#### 一、左线性文法到右线性文法的转换及DFA构造
**题目描述**：
已知正规文法中的左线性文法 \(G_1:S→Sa|Sb|c\) ，试构造无 \(\varepsilon\) 产生式的等价右线性文法，并构造相应的确定有限自动机（DFA），画出状态转换图。
**解答**：
1. **构造右线性文法**：左线性文法的形式为 \(A → aB\) 或 \(A → a\) （其中 \(A\) 和 \(B\) 是非终结符，\(a\) 是终结符）。为了将其转换为右线性文法，我们需要交换 \(a\) 和 \(B\) 的位置，并添加一个新的开始符号。因此，对于 \(G_1\) ，我们可以得到等价的右线性文法 \(G_1'\) 如下：
- \(S' → S\)
- \(S → aS|bS|c\)
2. **构造DFA**：根据 \(G_1'\) ，我们可以构建一个简单的DFA来识别该文法产生的语言。DFA的状态转换图如下：
- **初始状态**：\(q_0\)
- **接受状态**：\(q_f\)
- **转换规则**：
- \(q_0\) 接收输入 \(a\) 或 \(b\) 进入自身，接收输入 \(c\) 进入 \(q_f\)
- \(q_f\) 对任何输入均保持不变
**状态转换图**：
```
q_0 --a,b--> q_0
--c--> q_f (接受状态)
```
#### 二、正规文法的分析与DFA构造
**题目描述**：
已知正规文法 \(G_2:X→0Y|1Z|0\)，其中 \(Y→0X|1Y|1\) 和 \(Z→1X\)。
1. 该文法产生语言是什么？请用正规式表示。
2. 构造最简的确定有限自动机（DFA），并画出状态转换图。
**解答**：
1. **语言分析**：该文法产生的是以0开头或以0结尾的语言。可以表示为正规式 \(0(0|1)^*0 + 0\)。
2. **构造DFA**：
- **初始状态**：\(q_0\)
- **接受状态**：\(q_f\)
- **转换规则**：
- \(q_0\) 接受输入 \(0\) 进入 \(q_1\)
- \(q_1\) 接受输入 \(0\) 或 \(1\) 进入自身，接受输入 \(0\) 进入 \(q_f\)
- \(q_f\) 对任何输入均保持不变
**状态转换图**：
```
q_0 --0--> q_1
q_1 --0,1--> q_1
--0--> q_f (接受状态)
```
#### 三、消除左递归并求First/Follow集合
**题目描述**：
已知上下文无关文法 \(G_3:E→ET+|T\)，其中 \(T→TF*|F\) 和 \(F→E|i\)。
1. 消除文法左递归，并给出改写后的文法产生式；
2. 给出文法改写以后的各非终结符 \(X\) 的 \(First(X)\) 与 \(Follow(X)\) 集合，并由此判定它是否是 \(LL(1)\) 文法。
**解答**：
1. **消除左递归**：为了消除左递归，我们可以将 \(E\) 和 \(T\) 的定义重新组织如下：
- \(E → T E'\)
- \(E' → +TE'|ε\)
- \(T → F T'\)
- \(T' → *FT'|ε\)
- \(F → i\)
2. **求 \(First\) 和 \(Follow\) 集合**：
- **\(First\) 集合**：
- \(First(E) = First(T) = {i}\)
- \(First(E') = {+,ε}\)
- \(First(T) = First(F) = {i}\)
- \(First(T') = {*,ε}\)
- \(First(F) = {i}\)
- **\(Follow\) 集合**：
- \(Follow(E) = {$}\) （假设输入字符串的结束符号为 $）
- \(Follow(E') = Follow(E) = {$}\)
- \(Follow(T) = Follow(E') ∪ Follow(T') = {+,ε,$}\)
- \(Follow(T') = Follow(T) = {+,ε,$}\)
- \(Follow(F) = Follow(T') ∪ Follow(T) = {*,+,ε,$}\)
**是否是 \(LL(1)\) 文法判断**：通过观察 \(First\) 和 \(Follow\) 集合，可以发现不存在冲突，因此该文法是 \(LL(1)\) 文法。
#### 四、构造LR(0)项目集规范族及LR分析表
**题目描述**：
已知表达式文法（已拓广） \(G_4:E'→E\)，其中 \(E→E+E|i\)。
1. 试构造文法 \(G_4\) 的 LR(0) 项目集规范族；
2. 若 ‘+’ 服从右结合率，请给出 LR 分析表。
**解答**：
1. **构造LR(0)项目集规范族**：
- 初始化项目集 \(I_0\) 包含项目 \(E'→•E\)。
- 通过闭包操作不断扩展项目集，直到没有新的项目加入为止。具体步骤略。
2. **构造LR分析表**：LR分析表的构造基于 LR(0) 项目集规范族，考虑到 ‘+’ 的右结合性，需要调整 ACTION 和 GOTO 表格中的某些条目以确保正确的解析策略。具体的构造过程较为复杂，涉及到多个步骤，包括但不限于状态间的跳转、冲突解决等。
#### 五、构造算符优先分析表及分析过程
**题目描述**：
已知文法 \(G_5:Z→bMb\)，其中 \(M→(Ma)|a\)。
1. 试构造算符优先分析表；
2. 若某相邻的终结符 \(a,b\) 间存在 \(a≤b\) 两种关系，那么在进行算符优先分析做归约动作时，试按此规定的算法给出语句 \(b((aa)a)b\) 的算符优先分析过程。
**解答**：
1. **构造算符优先分析表**：由于 \(G_5\) 的简单性，我们可以通过比较不同终结符之间的关系来构造算符优先分析表。具体构造过程略。
2. **算符优先分析过程**：对于给定的输入串 \(b((aa)a)b\)，其分析过程大致如下：
- 初始栈为 \(#\)。
- 输入串依次读取，每次读取一个符号，并按照算符优先分析表中的关系进行归约或移进操作。
- 归约操作遵循 \(a≤b\) 的原则，找到与栈顶串匹配的产生式，并进行归约。
- 具体的分析过程略。
#### 六、翻译成中间代码
**题目描述**：
1. 将如下程序段翻译成后缀式（逆波兰式），填在一维数组 POST[i] 中。
2. 翻译布尔表达式成转移四元式序列，并指出待填真假链序号。
**解答**：
1. **翻译成后缀式**：对于给定的程序段，可以通过语法树或直接转换的方法将其翻译成逆波兰式。具体转换过程略。
2. **翻译布尔表达式**：布尔表达式翻译成转移四元式序列的过程涉及条件分支的处理，以及真假链的构建。具体转换过程略。
#### 七、运行时栈结构
**题目描述**：
给出一个计算 \(m*2^n\) 的 C 语言程序，试给出运行时整个栈或数据区的结构。
**解答**：该程序的栈结构主要包含了函数调用堆栈的信息，包括函数的返回地址、局部变量、形参单元区等。具体结构如下：
- **函数 f 返回值**：用于存储函数的返回值。
- **局部变量区**：存储函数内部定义的局部变量。
- **全程变量区**：存储全局变量和静态变量。
- **形参单元区**：存储传入函数的参数。
- **返回地址**：存储函数调用后的返回地址。
- **基 SP**：指向当前栈帧的基地址。
#### 八、程序优化
**题目描述**：
已知如下程序段，试进行代码优化。
**解答**：
1. **生成四元式中间代码序列**：根据程序段的语法制导，可以生成相应的四元式序列。具体生成过程略。
2. **程序流图划分**：基于生成的四元式序列，划分基本块，并绘制程序流图。具体划分和绘制过程略。
3. **优化**：执行循环中代码外提、强度减弱优化和基本块内删除公共子表达式优化，然后绘制包含优化后的中间代码的程序流图。具体优化过程略。
