编绎试卷答案.docx

编绎试卷答案.docx词法分析器（扫描器）：输入源程序，进行词法分析，输出单词符号。
语法分析器（分析器）：对单词符号串进行语法分析，识别出各类语法单位。
语义分析与中间代码产生器：按照语义规则对语法分析器归约出的语法单位进行语义分析 并翻译成一定形式的中间代码。
优化器：对中间代码进行优化处理。
目标代码生成器：把中间代码翻译成目标程序。
2.
(1)
G(S): S-AB
A—aAb I &
B—aAb I &
(2)
G(S): S—ISO I A
A-0A1 I &
3、构造一个DFA,它接收£={a, b}上所有满足下述条件的字符串：字符串中的每个a都有 至少一个b直接跟在其右边。
解：已知Z={a,b},根据题意得出相应的的正规式为：(b*abb*)*
根据正规式画出相应的DFAM,如下图所示
用子集法将其确定化
(b*abb*)*
重新命名
b*abb*
I
«a
lb
{X,1,2,3,Y}
{4}
{2,3}
{4}
一
{5,6,1,2,3, Y)
{2,3}
{4}
0,3}
{5,6,1,2,3, Y)
{4}
(6,1,2,3, Y)
{6,1,2,3, Y)
{4}
{6,1,2,3, Y}
1
•a
■b
0
1
2
1
—
3
2
-1
2
3
1
4
4
1
4
A由彳导状冬图
A用蕨，J、化方最化简得：
{O}, <?1)， <2>，
{3,4}, 0倾疗•重新■苛 右 DFZX M，
4：有文法G[s]:
S—BA A—BS|d
⑴证明文法G是LL⑴文法。
构造LL⑴分析表。
写出句子abccd的分析过程 解：
B 一 aA|bS|c
对每••个非终结符A的任何两个不同产生式A—a||3,有
(1)一个LL⑴文法的充要条件是:
下面的条件成立：
FIRST(a)nFIRST(p)=O;
若[3* £,则有 FIRST(a)nFOLLOW(A)=<D。
对于文法G[s]:
S—BA A—BS|d B—aA|bS|c
其FIRST集如下：
FIRST(B)={a, b, c}; FIRST(A)={a, b, c, d}; FIRST(S)={a, b, c}。
其FOLLOW集如下：
首先，FOLLOW(S)={#};
对 S—BA 有：FIRST(A)\{e}加入 FOLLOW(B),即 FOLLOW(B)={a, b, c, d };
对 A—BS 有：FIRST(S)\{s)加入 FOLLOW(B),即 FOLLOW(B)={a, b, c, d };
对 B—aA 有：FOLLOW(B)加入 FOLLOW(A),即 FOLLOW(A)={a, b, c, d };
对 B—bS 有：FOLLOW(B)加入 FOLLOW(S),即 FOLLOW(S)={#, a, b, c, d };
由 A一BS|d 得：
FIRST(BS) nFIRST(d) = { a, b, c } n{d} = O;
由 B—aA|bS|c 得：
FIRST(aA) AFIRST(bS) HFIRST(c) ={a} H{b} Cl{c}=<D。
由于文