编译原理期末考试试卷(A卷).doc

编译原理期末考试试卷(　A卷）
一、 简述编译程序的工作过程.（10)
二、构造下列正规式相应的DFA(用状态转换图表示)(15）
（1） 1(0 ｜ 1)＊100
（2） 0＊10*10*10*1
（3） letter（letter ｜ digit）＊
三、给出下面语言的相应文法：（15）
L1=｛an bn | n≥1} L2={anbm+nam | n≥1，m≥0｝
四、对下面的文法G:
S→a | b | (T）
T→T,S ｜ S
（1) 消去文法的左递归，得到等价的文法G2;
(2) 判断文法G2是否LL（1）文法,如果是，给出其预测分析表。（15）
五、设有文法G[A]：
A→BCc ｜ gDB
B→bCDE |ε
C→DaB ｜ ca
D→dD ｜ε
E→gAf ｜ c
(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集；
(2) 试判断该文法是否为LL(1）文法。(15）
六、对表达式文法G:
E → E+T ｜ T
T → T*F ｜ F
F → （E) ｜ I
(1）造各非终结符的FIRSTVT和LASTVT集合；
（2)构造文法的算符优先关系表。（15）
七、有定义二进制整数的文法如下：
L →LB ｜ B
B →0 | 1
构造一个翻译模式，计算该二进制数的值(十进制的值)。（15)
简述编译程序的工作过程。（10）
编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位;③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式.
二、构造下列正规式相应的DFA(用状态转换图表示）（15)
（4） 1（0 | 1）*1
0,1
（5） 0＊10*10*10*1
（6） letter(letter ｜ digit）*
3
1
0

2
1
(1）
0
0

5
1
（2）
1
0
4
1
3
0
2
1
1

letter
（3）

2
letter

1

digit

三、给出下面语言的相应文法：（15）
L1=｛an bn ｜ n≥1｝ L2=｛anbm+nam ｜ n≥1,m≥0}
G1：
S→AB
A→aAb | ab
B→bBa | ε
G1：
A→aAb |ab

四、对下面的文法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）文法。

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

T
T→ ST'
T→ ST’
T→ ST’

T’

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）

FIRST
FOLLOW
A
B
C
D
E

A，b,c，d,g
b
A,c,d
D
C，g
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)

FIRSTVT
LASTVT
E
T
F
＊,+,(,i
*，（，i
（，i
*，+，），i
*，），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｝