编绎试卷答案.doc

词法分析器(扫描器):输入源程序,进行词法分析,输出单词符号。
语法分析器(分析器):对单词符号串进行语法分析,识别出各类语法单位。
语义分析与中间代码产生器:按照语义规则对语法分析器归约出的语法单位进行语义分析并翻译成一定形式的中间代码。
优化器:对中间代码进行优化处理。
目标代码生成器:把中间代码翻译成目标程序。
2.
(1)
G(S): S→AB
A→aAb|ξ
B→aAb|ξ
(2)
G(S): S→1S0|A
A→0A1|ξ
3、构造一个DFA,它接收∑={a, b}上所有满足下述条件的字符串:字符串中的每个a都有至少一个b直接跟在其右边。
解:已知∑={a, b},根据题意得出相应的的正规式为: (b*abb*)*
根据正规式画出相应的DFA M,如下图所示
用子集法将其确定化
4:有文法G[s]:
S→BA A→BS|d B→aA|bS|c
(1)证明文法G是LL(1)文法。
(2)构造LL(1)分析表。
(3)d的分析过程
解:
(1)一个LL(1)文法的充要条件是:对每一个非终结符A的任何两个不同产生式A→α|β,有下面的条件成立:
① FIRST(α)∩FIRST(β)=Φ;
②若β*Þε, 则有FIRST(α)∩FOLLOW(A)=Φ。
对于文法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)\{ε}加入FOLLOW(B), 即FOLLOW(B)={a, b, c, d };
对A→BS有:FIRST(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 };