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

将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 )# ,) 归约 ） # ,>) 归约 ) # (=) 移进 # )># 归约 # 接受 第25页共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}

G1：

A→aAb |ab

G1： S→AB

第26页共6页

A→aAb | ab B→bBa | ε

四、对下面的文法G：

S→a | b | （T） T→T，S | S

(1) 消去文法的左递归，得到等价的文法G2；

(2) 判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15） G2：

S→a | b | （T）

T→ ST’

T’→，S T’ | ε G2是LL（1）文法。 S T T’ a S→a b S→b （ ） ， # S→（T） T→ ST’ T→ ST’ T→ ST’ T’→ ε T’→，S T’ 五、设有文法G[A]： A→BCc | gDB

B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c

(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集； (2) 试判断该文法是否为LL（1）文法。（15） A B C D E FIRST A,b,c,d,g b A,c,d D C,g FOLLOW A,c,d C,d,g A,b,c,g 是LL（1）文法。

六、对表达式文法G：

E → E+T | T T → T*F | F F → (E) | I

（1）造各非终结符的FIRSTVT和LASTVT集合； （2）构造文法的算符优先关系表。（15）

第27页共6页

E T F

算符优先关系表 + * I （ ） # + > > > < > < FIRSTVT *，+，（，i *，（，i （，i LASTVT *，+，），i *，），i ），i * < > > < > < I < < < < （ < < < < ） > > > = > # > > > > = 七、有定义二进制整数的文法如下：

L →LB | B B →0 | 1

构造一个翻译模式，计算该二进制数的值（十进制的值）。（15） 引入L、B的综合属性val，翻译模式为： S →L {print(L.val)}

L →L1B {L.val= L1.val*2+B.val} L →B {L.val= B.val} B →0 {B.val=0} B →1 {B.val=1}

第28页共6页