编译原理期中试卷(软件工程)
1．简答题（每题5分，共计15分）
(1) 简述编译程序与解释程序的区别。

解释程序不生成目标代码，而编译程序生成目标代码
(2) 什么是句柄？
令G[S]是一个文法，如果有S=>*αAδ且A=>*β则称β是一个关于非终结符号A 的，句型αβδ的短语。

其次如果有S=>αAδ且A=>β则称β是直接短语。

一个句型的最左直接短语称为该句型的句柄。

(3) 自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么？
自顶向下的语法分析解决的核心问题是：（1）消除左递归 (2) 避免回溯
自底向上的语法分析解决的核心问题是：寻找句柄
2．文法G[S]: S∷=a｜b｜(T) T∷=T,S｜S
给出句型(a,(b,S))的短语与直接短语(简单短语)、句柄和最左素短语。

（10分）短语：(a,(b,S))，a,(b,S)，a，(b,S)，b,S，b
直接短语(简单短语)：a，b
句柄：a
最左素短语：a
3．按指定类型给出下列语言的文法,并指出语言的类型。

（每个5分，共10分）
(1) L1={ a n b m| n≥0,m>0 } S::= aS|bS|b
(2) L2={ 0n1n b m c m| n>0，m ≥0}S::=AB A::=0A1|01 B::=bBc|ε4．构造正则式ba*|(ab)*b对应的DFA并最小化。

（要求步骤清楚，15分）
5. 请在划线处填空。

（5分）
BEGIN /* Start Algorithms */
(1) PUSH(‘#’),PUSH(‘S ’);
把第一个输入符号读进b; FLAG = TRUE ； WHILE FLAG DO BEGIN
把栈顶符号上托出去并放在X 中；
IF X ∈ Vt THEN
IF X==b THEN
把下一个输入符号读进a ELSE ERROR
ELSE IF X==‘#’ THEN FLAG = FALSE ELSE ERROR
ELSE IF M [X,b]={X → X1X2…XK} THEN
(2) 将XkXk-1…X1入栈 ELSE ERROR
END /* End Of While */ END /* End of Algorithms */
6．为文法G[P]：P ∷=begin S end S ∷=A ｜C A ∷=V:=E C ∷=if E then S
E::=VE' E'::=+VE' | ε V ∷=i
构造递归下降识别程序（15分） 构造程序（略，注意判断预测的符号）
7．请给出文法的First和Follow集合，给出分析表（15分）
E∷=TE' E'∷=+E｜ε T∷=FT' T'∷= /T｜ε F∷=PF' F'∷= *F｜εP∷=(E)｜a｜b
根据下列分析表，分析句子i+i*i。

（10分）
将分析过程填入如下的表格中。

8．文法G[E]： (1) E→KFc (2) K→aK (3) K→d (4) F→b，对应的LR(0)分析表如图，
依据右边的表格格式，写出分析adbc的过程。

（10分）
答题格式如下：
9. 有穷状态自动机分为哪几种，主要区别是什么？（5分）
有穷状态自动机分为：NFA和DFA
主要区别：NFA的映射函数是K×∑→2K，而DFA的映射函数是K×∑→K。