资源描述：
《编译原理题目模拟gai》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、选择题：1.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位是_______。A字符B单词C句子D句型2．编译程序前三个阶段完成的工作是________。A词法分析、语法分析和代码优化B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成D词法分析、语法分析和代码优化3．语法分析所依据的是_____。A语义规则B词法规则C语法规则D等价变换规则4．对应Chomsky四种文法的四种语言之间的关系是AL0ÌL1ÌL2ÌL3BL3ÌL2ÌL1ÌL0C
2、L3=L2ÌL1ÌL0DL0ÌL1ÌL2=L35.给定文法G:A→Ab
3、cc，试问在下面的符号中,为该文法句子的是______.AccbbBbcbccCbccbccDcbbcc6．属于自上而下分析法的是（）ALL（1）BLR（0）CSLRD算符优先7．在自下而上的语法分析中，应从开始分析。A最左素短语B句子C文法的开始符号D句柄二、简答题：1.在自上而下语法分析中遇到的问题是什么，又是如何对其进行分析解决的？答：在自上而下语法分析中遇到的问题是左递归与回溯问题，可以对其进行消除，如果能够判断其是LL
4、（1）文法，则对其分析的每一步都是确定无疑的。2.什么是属性文法？属性分哪几类？答：属性文法是在文法的基础上，为每个文法符号配备若干相关的值称为属性，这些属性代表与文法符号相关的信息。属性文法包含S属性文法和L属性文法。（3分）3.给出下面两式的后缀式形式：1）a*(-b+c)2）notAandBorC答：1）abuminusc+*2)AnotBandCor三、综合题：1.请给出在∑={a,b}上b(a
5、b)*aa的DFA。(1)构造NFA；（2）对NFA确定化得到DFA。1)得到NFA（4分）2）
6、NFA转换成DFA状态转换矩阵为：（4分）IIaIb{X}---{1}{1}{1,2}{1}{1,2}{1,2,Y}{1}{1,2,Y}{1,2,Y}{1}重新命名后为：表格1（3分）Sab0--1121231331SBbBSab2.对于文法G[S]：S®AB，A®Aa
7、bB，B®a
8、Sb求句型baSb的全部短语、直接短语和句柄。A短语：abaSbbaSb直接短语：aSb句柄：a规范规约的依据素短语：aSb最左素短语：a算符优先分析法的依据3.对文法G(V):V→N
9、N[E]E→V
10、V+EN→i要求
11、：1）消除回溯（公共左因子）；2）求出各非终结符的first集和follow集；3)判断改造后的方法是否是LL（1）文法。要求构造预测分析表。(12分)解：1）LL（1）文法的基本条件是不含左递归和回溯，而文法G中含在回溯，所以先消除回溯得到文法G’(V)：（2分）First(V’)={ε,[}First(E’)={ε,+}First（N）={i}First(V)={i}First(E)={i}Follow(V)={#,],+}Follow(N)={[,#,],+]Follow(V)在follow(
12、V’)中=,follow(V’)={#,],+}Follow(E)={]}Follow(E’)={]}V→NV’V’→ε
13、[E]E→VE’E’→ε
14、+EN→i2）求Ｇ’的first和follow集：（8分）First(N)=First(V)=first(E)={i};First(V)={[,ε};First(E’)={+,ε};Follow(V)={#，+}Follow(V’)={#,+}Follow(E’)={]}Follow(N)={[，#，+}Follow(E)={]}3）改造后的文法是LL（
15、1）文法。（2分）4）构造其预测分析表[]+i#VV->NV’NN->iV’V’->[E]V’->εV’->εV’->εEV->NV’E’E’->εE’->+EFirstVT(B)={(,)}firstVT(A)={(,+,)}firstVT(S)={(,+,),i}LastVT(B)={(,*}LastVT(A)={(,*,+}LastVT(S)={i,(,*,+,}4.（11分）设文法G(S)：1)构造各非终结符的FIRSTVT和LASTVT集合；2)构造优先关系表。i+*()i><<<+>>>
16、<<*>>>(>>>)<=<<5.已知文法的翻译模式，用回填法给出语句a>bandc>dore>f的四元式序列，要求给出简单过程。(1)E→E1andME2{backpatch(E1truelist,M.quad);E.truelist:=,E2.truelist)E.falselist:=merge(E1.falselist,E2.falselist)(2)E→E1orME2{backpatch(E1.falselist,M.quad);E.truelist:=me
