《编译原理》第四单元测试

编译原理2014—2015学年第二学期单元测试试卷模板（闭卷考试）时间：45分钟满分：100分姓名班级出题人班级题目一二三四五总分得分一、选择题（5*2分）（每题2分，共10分）1．____文法不是LL(1)的。A、递归B、右递归C、2型D、含有公共左因子的2．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是_____。A.非终极符集B．终极符集C．字母表D.状态集3．代码优化时所依据的是。A、语法规则B、词法规则C、等价变换规则D、语义规则4．词法分析器的输出结果是_____。A．()单词的种别编码B．()单词在符号表中的位置C．()单词的种别编码和自身值D．()单词自身值5．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码二、简答题（2*10分）（每题10分，共20分）6．LL(1)文法应满足什么条件？7.一个文法G别是LL(1)文法的充要条件是什么？三、分析题（4题共70分）8、考虑文法G[S]:S→(T)|a+S|aT→T,S|S消除文法的左递归及提取公共左因子。(15分)9.设文法G（S）：(15分)S→T|S∨TT→U|T∧UU→i|-U10、设将文法G改写成等价的LL(1)文法，并构造预测分析表。(20分)G：S→S*aT|aT|*aT；T→+aT|+a11证明正规式(ab)*a与正规式a(ba)*等价（用构造他们的最小的DFA方法）。(20分)一、选择题1、D2.B3.C4.C5.A二、简答题6、若文法的任何两个产生式A|都满足下面两个条件：（1）FIRST()FIRST()=；（2）若*，那么FIRST()FOLLOW(A)=。7、一个文法G别是LL(1)文法的充要条件是:(1)FIRST(α)∩FIRST(β)=Ф(2)如果β=*ε,FIRST(α)∩FOLLOW(A)=Ф三、分析题8、解：消除文法G[S]的左递归：S→(T)|a+S|aT→ST′T′→,ST′|ε提取公共左因子：S→(T)|aS′S′→+S|εT→ST′T′→,ST′|ε9、（1）计算FIRSTVT和LASTVT；FIRSTVT(S)={∨,∧,i,-}FIRSTVT(T)={∧,i,-}FIRSTVT(U)={i,-}LASTVT(S)={∨,∧,i,-}LASTVT(T)={∧,i,-}LASTVT(U)={i,-}10、消除左递归后的文法G’:S→aTS’|*aTS’S’→*aTS’|εT→+aT|+a提取左公因子得文法G’’:S→aTS’|*aTS’S’→*aTS’|εT→+aT’T’→T|ε*+a#S→*aTS’→aTS’S’→*aTS’→εT→+aT’T’→ε→T→ε11、