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

再令｛０｝为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) 给出输入串()#的算符

优先分析过程。

步骤 1 2 3 4 5 6 7 8 9 10

栈 # #( #(a #(N #(N, #( #( #(N #(N) ( < < < = < , < < < > > # < < 当前输入字符 剩余输入串 动作 ( #<( 移进 a )# (, 归约 , a)# (<, 移进 a )# ,) 归约 ） # ,>) 归约 ) # (=) 移进 # )># 归约 # 接受 《编译原理》期末试题（四）

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

36 / 81

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

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

0,

（1） （2） (3)

1 0 2 1 3 0 0 0 1 0 1 4 1 5 1 1 2 3

37 / 81

2 1

三、给出下面语言的相应文法：（15）L1={ | n≥1} L2={ | n G1：

G1： A→

S→

A→ |

四、对下面的文法G：

S→a | b | （T）

38 / 81

≥1，m≥0}

T→T，S | S

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

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

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

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

A→ | B→ |ε C→ | D→ |ε E→ | c (1) (2)

计算该文法的每一个非终结符的集和集； 试判断该文法是否为（1）文法。（15）

39 / 81

A B C D E b D 是（1）文法。

六、对表达式文法G：

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

（1）造各非终结符的和集合；

（2）构造文法的算符优先关系表。（15）

E T F

算符优先关系表

40 / 81

*，+，（，i *，（，i （，i *，+，），i *，），i ），i