编译原理计科05-南京信息工程大学.doc
《编译原理计科05-南京信息工程大学.doc》由会员分享，可在线阅读，更多相关《编译原理计科05-南京信息工程大学.doc（5页珍藏版）》请在冰点文库上搜索。
编译原理期中试卷（计科05）
1、（5’）设G=（VT，VN，S，P）是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？
若G是1型文法呢？
上下文无关文法，产生式形式为：
P®a，PÎVN，aÎ（VTÈVN）*。
1型文法：
产生式形式为:
a®b其中：
|a|£|b|，仅S®e例外。
2、（5’）何谓二义性文法？
试举一例说明。
答：
如果一个文法的句子存在两颗分析树，称该句子是二义性的；
如果一个文法包含二义性的句子则称该文法是二义性的，否则该文法无二义性。
例子：
有如下文法：
S→ifexprthenS|other
S→ifexprthenSelseS
句子ife1thenife2thens1elses2是二义性的。
注：
原因请参见提纲。
3、（20’）给定正则表达式b*（d|ad）（b|ab）+构造DFA
（1）画出NFA:
（2）将NFA确定化为DFA
Ia
Ib
Id
{X,4,1}
{6}
{4,1}
{2}
{6}
Ф
Ф
{2}
{4,1}
{6}
{4,1}
{2}
{2}
{7}
{3,5,Y}
Ф
{7}
Ф
{3,5,Y}
Ф
{3,5,Y}
{8}
{5,Y}
Ф
{8}
Ф
{5,Y}
Ф
{5,Y}
{8}
{5,Y}
Ф
根据上面状态转换举证赋予状态新的符号：
Ia
Ib
Ic
S
A
B
C
A
Ф
Ф
C
B
A
B
C
C
D
E
Ф
D
Ф
E
Ф
E
F
G
Ф
F
Ф
G
Ф
G
F
G
Ф
E,G为终态。
画出DFA:
（3）DFA最小化:
1）首先分为非终态集{S,A,B,C,D,F}和终态集{E,G}
2）对于集合{S,A,B,C,D,F}，因为S,B,C有a条件输入这个状态转化，而A,D,F没有a条件输入这个状态转化，首先因分为{S,B,C}和{A,D,F}两个集合
{S,B}b={B}{C}b={E}不属于已划分出的同一个集合的子集，所以{S,B,C}分为{S,B}和{C}，而{S,B}d={C}是已划分出的同一个集合的子集，所以不需再分
{A,D,F}中A条件b作为输入，而{D,F}b={E,G}是同一集合的子集，并且{D,F}都没有d条件作为输入，所以{D,F}不需再分。
3）3）对于{E,G}，{E,G}a={F}{E,G}b={G}E和G都无条件d输入，所以{E,G}不需划分
综上所述：
所有状态分为{S,B}{C}{A}{D,F}{E,G}
注：
落在统一集合的元素等价，画图时只需选一个为代表，并把与它等价的元素的状态转化加到它身上即可。
4、（10’）按指定的类型给出下列语言的文法
（1）L1={anbmc|n>=0,m>0}用正规文法
S→aS|AA→bA|bBB→c
（2）L2={a0n1nbdm|n>0,m>0}用二型文法
S→ABA→aTT→0T1|01B→bDD→dD|d
5、（20’）判断下面文法是不是LL
（1）文法，若是请构造相应的LL
（1）分析表，写出aaabd的分析过程。
S→aHH→aMd|dM→Ab|eA→aM|e
答：
1）首先将规则分解：
S→aHH→aMdH→dM→AbM→eA→aMA→e可以判断该文法无左递归；
2）求First和Follow集合
非终结符X
First（X）
Follow（X）
S
a
#
H
a,d
#
M
e,a,e
d,b
A
a,e
b
求Select集合
Select（S→aH）=First（aH）={a}Select（H→aMd）=First（aMd）={a}
Select（H→d）={d}Select（M→Ab）=First（Ab）={a,e}
Select（M→e）=First（e）UFollow（M）=Follow（M）={d,b}
Select（A→aM）=First{aM}={a}Select（A→e）=First（e）={e}
∵Select（H→aMd）∩Select（H→d）=Ф
Select（M→Ab）∩Select（M→e）=Ф
Select（A→aM）∩Select（A→e）=Ф
∴该文法是LL
（1）文法。
3LL
（1）分析表如下：
令输入符号串已#结尾，即aaabd#
a
d
b
e
S
S→aH
H
H→aMd
H→d
M
M→Ab
M→e
M→e
M→Ab
A
A→aM
A→e
4）aaabd的分析过程如下：
步骤
符号栈
输入串
所用产生式
0
#S
aaabd#
1
#Ha
aaabd#
S→aH
2
#H
aabd#
3
#dMa
aabd#
H→aMd
4
#dM
abd#
5
#dbA
abd#
M→Ab
6
#dbMa
abd#
A→aM
7
#dbM
bd#
8
#db
bd#
M→e
9
#d
d#
10
#
#
6、（15’）写出文法G[A]:
A→Ba|Cb|cB→dA|Ae|fC→Bg|h
消除左递归后的文法。
答：
（1）经分析发现文法G[A]并无直接左递归；
（2）消除间接左递归：
将A,B,C按照B,C,A排序（建议将A放在最后）
由于出现C→Bg形式，将B代入C得：
C→dAg|Aeg|fg|h
又由于A出现A→BaA→Cb
将B,C带入A得到：
A→dAa|Aea|fa|dAgb|Aegb|fgb|hb|c
等价于A→Aea|Aegb|dAa|fa|dAgb|fgb|hb|c
将A消除直接左递归（方法请参见书69页倒数10、11行）
A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|cA’
A’→eaA’|egbA’|e
此时，对于B→dA|Ae|f，C→dAg|Aeg|fg|h由于未在任何产生式的右部出现，所以是多余的。
综上所述:
消除递归后的文法为：
A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|cA’
A’→eaA’|egbA’|e
7、（15’）为文法G[E]:
E→E+E|E*E|-E|id|（E）构造递归下降识别程序
答：
（1）消除左递归后有E→—EE’|idE’|（E）E’
E’→+EE’|*EE’|e
（2）
8、（5’）简述编译程序的构造过程
答1）构造此法分析器：
用于输入源程序进行词法分析，输出单词符号；
2）构造语法分析器：
对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序
3）构造语义分析和中间代码产生器：
按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。
4）构造优化器：
对中间代码进行优化。
5）构造目标代码生成器：
把中间的代码翻译成目标程序。
6）构造表格管理程序：
登记源程序的各类信息和编译各阶段的进展情况。
7）构造错误处理程序：
对出错进行处理。
9、（5’）构造预测分析算法的算法流程图
升级会员 