编译原理期末：一些可能考的题

简答题

① 文法及翻译方案

S -> bTc       {print"1"}
S -> a         {print"2"}
T -> R         {print"3"}
R -> R/S       {print"4"}
R -> S         {print"5"}

输入符号串 bR/bTc/bSc/ac的输出是什么?

思路：先构建语法树，然后按次序执行相应的语义动作

Pasted image 20260703020350.png
按照归约次序，得到的输出结果为 1453142431

② 翻译算术表达式

分别将算术表达式 和 翻译成：

  • 语法树
  • 有向无环图（DAG）
  • 后缀表达式
  • 三地址代码

语法树

图片1.png

有向无环图

图片1.png

后缀表达式

三地址代码

语法树

图片3.png

有向无环图

图片4.png

后缀表达式

三地址代码

计算题

③ 从 NFA 到 DFA

设有字母表 ， 上的正规式

  1. 构造该正规式所对应的非确定有限自动机（NFA）（本题10分）
  2. 给出该NFA对应的状态转换表（本题5分）
  3. 将所得到的 NFA 确定化（本题10分）
  4. 将所得到的 DFA 化简（本题5分）

v1：直观构造法（观察题目，不难看出……）

1. NFA

Pasted image 20260702213029.png

2. 状态转换表
状态
1
2
3. DFA

Pasted image 20260702213806.png

4. DFA化简
分区

最简DFA：
Pasted image 20260702214228.png

v2：汤普森构造法

1. NFA

Pasted image 20260702215100.png

2. 状态转换表
状态
1
2
3
4
5
3. DFA

Pasted image 20260702215306.png

4. DFA化简
分区

最简DFA：
Pasted image 20260702214228.png

v3：未知构造法（折中方案）

1. NFA

Pasted image 20260702215624.png

2. 状态转换表
状态
1
2
3
4
3. DFA

Pasted image 20260702215752.png

4. DFA化简
分区

最简DFA：
Pasted image 20260702214228.png

④ LL(1) 文法

已知文法 ：

  1. 计算文法 的每一个非终结符的 FIRST 集和 FOLLOW 集（本题10分）
  2. 构造 LL(1) 分析表（本题10分）

1. FIRST 集和 FOLLOW 集

FIRST 集

知识回顾： 是从 出发能推导出的所有串的首终结符集合。若 能推导出 ，则 。


  • 找 出现在左部的产生式


    • 首终结符是
      即

    • 首终结符是
      即
      且


  • 找 出现在左部的产生式

    的首符集取决于 的首符集
    即


  • 出现在左部的产生式


    • 首终结符是
      即


小结：

FOLLOW 集

知识回顾： 是所有句型中紧跟在非终结符 之后的终结符集合，对于开始符号，还要加入结束符 。


  • 是开始符号

    找 出现在右部的产生式：


    • 后跟


      即 可能会消失
      当 消失时

      在末尾
      后跟

    • 后跟

      又
      当 消失时

      在末尾
      后跟

    预知未来可知：



  • 出现在右部的产生式：


    • 后跟
      即


  • 出现在右部的产生式：


    • 在末尾
      后跟
      即

    • 在末尾
      后跟 ，无新信息

小结：

2. 构造 LL(1) 分析表

逐个处理产生式















  • 不填

分析表

⑤ 消除左递归

顾

题

已知文法 ：


  • 消去文法 的左递归