编译原理-2023期中考试（原题）

【前言】

这是某高校本科编译原理2023年的期中考试，分享在这里仅供同学学习交流使用，如果课程组老师觉得这样不妥，请联系我，我会及时撤回。

题目比较基础，再加上是开卷考试，知道考点基本就能做出来。我就不给出答案了。

一、(15分)尝试把下列表达式转换为有限自动机:
(1) (a) xy( x* ) l yx( y* )
(2) (b) ( xyz )*( yzx )*
(3) (c) x*( y l z ) l y*xz

二、(25分)有正则表达式“ ( + | - | ε )( digit )( digit )* ”，请详细描述:
(1) 用 thompson 算法将上述正则表达式转成 NFA 的过程和结果；
(2) 用子集构造法进一步将 NFA 转成 DFA 的过程和结果；
(3) 进一步将 DFA 最小化的过程和结果。
注:题干正则表达式中符号“digit”表示0-9中任意一个整数数字，为简化答题过程可以用digit代表0-9中任意一个数字。

三、(30分)考虑以下文法(大写字母表示非终结符)G(S):
S → I : L
S → I
I → i
I → L b
L → i
L → ( b : L )
(1) 给出一个由该文法所产生的长度为7的字符串/句子;
(2) 计算文法中所有非终结符的FIRST集合和FOLLOW集合;
(3) 给出该文法的LL(1)自动机及分析表，判断该文法是否是LL(1)文法，并解释原因。

四、(30分)考虑下列文法G(S)(大写字母为非终结符) :
S → a g d
S → a A c
S → b A d
S?→ b g c
A → B
B → g
(1) 构建LR(1)项目集和分析表，判断该文法是否是LR(1)文法，给出原因;
(2) 构建LALR(1)分析表，判断该文法是否是LALR(1)文法，给出原因。