内蒙古大学2009级编译期末试卷A
- 格式：doc
- 大小：42.65 KB
- 文档页数：5
软件学院2009级软件专业11~12学年第一学期<<编译原理>> 期末试卷(A)
一、简答题（第1、2、3、4小题各5分，第5小题10分，本大题共30分）
1．已知文法G[A]：A → 0B|1C B → 1|1A|0B C → 0|0A|1CC 写出该文法的开始符号、非终结符集和终结符集。
2．考虑下列文法G[S]: S->a | (T) T->T, S |S
指出句型(T,(S))的所有直接短语,句柄,短语
3．设Σ={a,b}，构造语言L1={a n b n | n≥1}的文法。
4．写出下列语句的四元式序列
if a>b and c<d then a:= a-b else c:=c*d;
5．对下列四元式序列，划分基本块，画出流图、判断哪些是回边，给出与回边对应的循环所包含的基本块。
(1) read (C)
(2) A:= 0
(3) B:= 1
(4) A:=A + B
(5) if B>= C goto (8)
(6) B:=B+1
(7) goto (4)
(8) write (A)
(9) halt
二、自动机（20分）
1．（12分）将下图的NFA确定化并最小化。
b
2． （8分）给出与下图的DFA 等价的正规文法
三、自上而下分析（15分）
对文法G[S]：
S → C m
C → b A | a B
A → a D | b A A
B → b D | a B B
D → C | ε
(1) 求出该文法的每个非终结符的FIRST 集和FOLLOW 集；
(2) 判断该文法是否是LL(1)文法。
⇒a, b
四、LR分析（每小题5分，共25分）
考虑移进-归约分析中，对文法G[A]采用以下的语法制导的翻译模式，在按一产生式归约时，立即执行括号中的动作。
A →aBB{print “0”}
A →c {print “1”}
B →Ab {print “2”}
(1) 构造LR(0)的识别该文法活前缀的有限自动机；
(2) 判断该文法是否为SLR(1)文法并说明理由；
(3) 构造SLR(1)分析表；
(4) 当分析器的输入为acbcb时，打印的字符串是什么？
(5) 求LR(1)项目A->a. B B, # 的闭包。
五、语法制导翻译（10分）
设有文法G[L]：
L-> L, S
L->S
S-> (L)
S-> a
写一个语法制导定义，输出给定输入中括号的最大嵌套层数。
如句子
(a ) ,(a, (a,a ) )的输出是2。
