编译原理期末试题及答案.doc

### 编译原理知识点解析 #### 一、逆波兰表示法与三元序列 1. **逆波兰表示法**：是一种后缀表达式，没有括号，运算符位于操作数之后。 - **例题1**：对于表达式 `w+(a+b)*(c+d/(e-10)+8)`： - 逆波兰表示为：`w a b + c d e 10 - / + 8 + * +` - **例题2**：对于表达式 `a+b*(c-d)/e`： - 逆波兰表示为：`a b c d - * e / +` - **例题3**：对于表达式 `a:=(b+c)*e+(b+c)/f`： - 逆波兰表示为：`a b c + e * b c + f / + :=` 2. **三元序列**：用于表示计算过程中的临时变量和操作，通常形式为`(目标变量, 操作符, 操作数1, 操作数2)`。 - **例题1**： - 三元序列为：`(t1, +, a, b) (t2, /, d, e) (t3, -, e, 10) (t4, +, t2, t3) (t5, +, t4, 8) (t6, *, t5, c) (res, +, t6, w)` - **例题2**： - 三元序列为：`(t1, -, c, d) (t2, *, b, t1) (t3, /, t2, e) (res, +, a, t3)` - **例题3**： - 三元序列为：`(t1, +, b, c) (t2, *, t1, e) (t3, /, t1, f) (t4, +, t2, t3) (a, :=, t4)` #### 二、文法及其应用 3. **例题4**：给定文法 `G(S)` 及翻译方案： - 文法：`S→aAb {print “1”}`，`S→a {print “2”}`，`A→AS {print “3”}`，`A→c {print “4”}` - 输入：`acab` - **解析**：根据给定文法，输入串 `acab` 的推导过程为 `S => aAb => acAb => acab`，根据翻译方案，输出顺序为 `1`, `4`, `2`。 4. **例题5**：给定文法 `G(S)`： - 文法：`S→bAa`，`A→(B | a`，`B→Aa` - **规范归约过程**：句子 `b(aa)b` 的规范归约过程如下： - 步骤1：`b(aa)b` - 步骤2：`S` - 步骤3：`bAa` - 步骤4：`b(Aa)a` - 步骤5：`b((B)a)a` - 步骤6：`b((Aa)a)a` - 步骤7：`b(((B)a)a)a` - 步骤8：`b(((Aa)a)a)a` - 步骤9：`b((((B)a)a)a)a` - 步骤10：`b((((Aa)a)a)a)a` - 步骤11：`b((((aa)a)a)a)a` - 步骤12：`b(((aa)a)a)a` - 步骤13：`b((aa)a)a` - 步骤14：`b(aa)a` - 步骤15：`b(aa)b` 5. **例题6**：给定文法 `G[S]`： - 原文法：`S→S*aF | aF | *aF`，`F→+aF | +a` - **消除左递归**：首先将 `S` 和 `F` 的规则分别重写为消除左递归的形式。 - `S→aF S'` - `S'→*aF S' | ε` - `F→+a F'` - `F'→+a F' | ε` #### 三、语法分析 6. **例题10**：给定文法 `G(S)`： - 文法：`S→(T) | aS | a`，`T→T,S | S` - **消除左递归和提公共左因子**： - 消除左递归后的文法为： - `S→a S'` - `S'→S | ε` - `T→S T'` - `T'→,S T' | ε` - 构造相应的 `FIRST` 和 `FOLLOW` 集合： - `FIRST(S)={a, (}` - `FOLLOW(S)={#, ), }` - `FIRST(T)={a, (}` - `FOLLOW(T)={#, , , )}` - 构造预测分析表： - `a`: `S→a S'`, `T→S T'` - `(`: `S→( T`, `T→S T'` - `,`: `T'→, S T'` - `#`: `S'→ε`, `T'→ε` 7. **例题12**：给定文法 `G(S)`： - 文法：`E→E+T | T`, `T→T*F | F`, `F→(E) | i` - **最左推导**：对于句型 `(i+i)*i+i`： - 推导过程：`E => E+T => T+T => T*T => F*T => (E)*T => (E+T)*T => (T+T)*T => (F+T)*T => (i+T)*T => (i+i)*T => (i+i)*i => (i+i)+i` - 语法树如下： ``` E / \ + i / \ E i / \ + i / \ ( i \ / + / \ i i ``` - **短语、素短语和最左素短语**：对于句型 `(E+T)*i+F`： - 短语：`(E+T)*i+F`, `(E+T)*i`, `(E+T)*`, `E+T`, `E` - 素短语：`(E+T)*i`, `(E+T)*`, `E+T`, `E` - 最左素短语：`(E+T)*` 以上是基于给定文档中例题的详细解析，涵盖了逆波兰表示法、三元序列、文法规则的应用以及语法分析等方面的知识点。这些内容是学习编译原理课程的重要组成部分，有助于理解和掌握编译器设计的基本原理和技术。