编译原理试题及答案(期末复习版).pdf

.

词法分析器：输入源程序，进行词法分析，输出单词符号。 语法分析器：在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分 照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定

解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。 中间代码生成器：按

形式的中间代码，比如说四元式。 优化：对中间代码进行优化处理。 目标代码生成器：把中间代码翻译成目标语言程序。

表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编 译

程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编

译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。此外，编译的各阶段都可能出现错误，

出错处理程序对发现的错误都及时进行处理。 2． 【解答】

该句型对应的语法树如下：该句型相对于 E 的短语有 FF^^*；相对于 T 的短语有 FF^^*,F; 相对于 F 的短语有 F^;F^^;简单短语有 F;F^;句柄为 F. 3．

【解答】

最简 DFA 如图 2.66 所示。 4．

【解答】

(1)

S→(L)|aS’ S’→S|ε L→S L’ L’→S L’|ε

评分细则：消除左递归 2 分，提公共因子 2 分。 (2) FIRST 和 FOLLOW

FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε} FOLLOW(L’〕＝{ )}

5．

【解答】

(1)拓广文法

(0)S->A (1) A->aAd (2)A-> aAb (3)A->ε (2)构造识别活前缀的 DFA

可编辑

.

FOLLOW(A)={d,b,#}

对于状态 I0：FOLLOW(A)∩{a}=Ф 对于状态 I1：FOLLOW(A)∩{a}=Ф

因为，在 DFA 中无冲突的现象，所以该文法是 SLR(1)文法。 (3)SLR(1)分析表 状态

a

ACTION B d

GOTO

#

A 可编辑

.

0 1 2 3 4 5

S2 r3 r3

acc r3 S4 r1 r2

r3 1

S2

r3 S5 r1 r2

r3

3

r1 r2

(4)串 ab#的分析过程 步骤 1 2 3 4 5

动作 状态栈 符号栈 当前字符 剩余字符串 0 # a b# 移进 02 #a b # 归约 A->ε 023 #aA b # 移进 0235 01

#aAb #A

# #

归约 A-> aAb 接受

6．

【解答】

由 M→d 和 M→a…得：FIRSTVT(M)=｛d,a｝； 由 H-H;…得：FIRSTVT(H)=｛；｝

由 H→M 得：FIRSTVT(M) cFIRSTVT(H)，即 FIRSTVT(H)={;,d,a} 由 M→d 和 M→…b 得：LASTVT(M)={d,b}； 由 H---，；m 得：LASTVT(H)=｛；｝；

由 H→M 得：LASTVT（M）cLASTVT(H），即 LASTVT(H)=｛;,d,b}

对文法开始符 H,有#H#存在，即有＃=＃，##,也即＃对形如 P→…ab…，或 P→…aQb…，有 a=b，由 M→a|b 得：a=b；

对形如 P→…aR…，而 b∈FIRSTVT(R)，有 a

＜；， ##, b>#。

有 a>b。

由 H→…；M 得：；

由 M→aH…得：a

由 H→H；’’?得：LASTVT(H)>;，即：；＞；，d>；，b＞；

由 M→…Hb 得：LASTVT(H)>b，即：；＞b，d>b，b＞b

由此得到算符优先关系表，见表 3.5。

7． 【解答】 （1）LR 分析表如下： （2）分析表

状态

0

ACTION GOTO a b # S s3 s4 1

B

2

可编辑

.

1 2 3

S3 s3

S4 s4

acc

5 6

可编辑