编译原理期末试题（8套含答案+大题集）(7)

2 +

-+ a 0 b a 1 + a

（3）对（2）得到的DFA化简，合并状态0和2 为状态2：

2 -+ b a 1 +

（4）令状态1和2分别对应非终结符B和A

G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε

a 四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。

G：S→S*aT|aT|*aT； T→+aT|+a

解：消除左递归后的文法G’: S→aTS’|*aTS’

S’→*aTS’|ε

T→+aT|+a

提取左公因子得文法G’’: S→aTS’|*aTS’

S’→*aTS’|ε T→+aT’

T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}

Select(T’→T)=First(T) ={+}

Select(T’→ ε)=Follow(T’)={*,#}

Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S →*aTS’ →aTS’ 第21页共6页

S’ →*aTS’ T T’ → ε →ε → ε →+aT’ →T 6设文法G 为： S→A；A→BA|ε；B→aB|b

解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4)

B→aB (5) B→b ； FIRST(A) = {ε, a, b}；FIRST(B) = {a, b}

构造的DFA 如下:

项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。

（2） LR(1)分析表如下：

(3)输入串abab 的分析过程为：

第22页共6页

简答题 3、设有文法G[S]: S→S(S)S|ε，该文法是否为二义文法？说明理由。 答：是二义的，因为对于（）（）可以构造两棵不同的语法树。 S S

S ( S ) S S ( S ) S

ε ε S ( S ) S S ( S ) S ε ε

ε ε ε ε ε ε

五、 给定文法G[S]：

S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF

F→bD|aE|b

构造相应的最小的DFA 。

解：先构造其NFA： 用子集法将NFA确定化：

S A Q BZ DZ D B a A A Q Q A A Q b Q BZ DZ D B B D

第23页共6页

将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。

令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割：

P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。 再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。 最小化为右上图。

六、 对文法G(S)：S → a | ^ | (T)；T → T，S | S

答：(1)

FIRSTVT(S)?{a,^,(}FIRSTVT(T)?{,,a,^,(}

LASTVT(S)?{a,^,)}LASTVT(T)?{,,a,^,)} a ^ ) a ^ ( ) , # > > > > > > = > > > < (2) 是算符优先文法，因为任何两个

终结符之间至多只有一种优先关系。（2分）

(3) 给出输入串(a,a)#的算符优先

分析过程。 步骤 1 2 3 4 5 6 7 8 9 10 栈 # #( #(a #(N #(N, #(N,a #(N,N #(N #(N) #N ( < < < = < , < < < > > # < < 当前输入字符 剩余输入串 动作 ( a,a# #<( 移进 a ,a)# (, 归约 , a)# (<, 移进 a )# ,) 归约 ） # ,>) 归约 ) # (=) 移进 # )># 归约 # 接受 第24页共6页

《编译原理》期末试题（四）

一、简述编译程序的工作过程。（10）

编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。

二、构造下列正规式相应的DFA（用状态转换图表示）（15） （1） 1（0 | 1）*1

0,1 （2） 0*10*10*10*1 （3） letter（letter | digit）*

（1）

（2）

(3)

1 0 0 2 0 1 1 2 1 3 0 1 3 1 4 0 1 5 letter letter 1 2 digit 三、给出下面语言的相应文法：（15）

L1={an bn | n≥1} L2={anbm+nam | n≥1，m≥0}