编译原理试卷及答案

-1-东北大学秦皇岛分校课程名称：编译原理试卷：(B)答案考试形式：闭卷授课专业：计算机科学与技术考试日期：年月日试卷：共2页题号一二三四总分得分阅卷人一、填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工作是理和出错处理。表格管2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。3、语法分析方法主要可分为自顶向下和自底向上两大类。4、LR（0）文法的项目集中不会出现移进-归约冲突和归约-归约冲突。5、数据空间的动态存储分配方式可分为栈式和堆式两种。6、编译程序是指能将源语言程序翻译成目标语言程序的程序。7、确定有穷自动机DFA是NFA的一个特例。8、表达式(a+b)*c的逆波兰表示为ab+c*。二、选择题（每题2分，共20分）1、LR语法分析栈中存放的状态是识别B的DFA状态。A、前缀B、可归前缀C、项目D、句柄2、D不可能是目标代码。A、汇编指令代码B、可重定位指令代码C、绝对机器指令代码D、中间代码3、一个控制流程图就是具有C的有向图A、唯一入口结点B、唯一出口结点C、唯一首结点D、唯一尾结点4、设有文法G[S]：S→b|bBB→bS，则该文法所描述的语言是C。A、L（G）={bi|i≥0}B、L（G）={b2i|i≥0}C、L（G）={b2i+1|i≥0}D、L（G）={b2i+1|i≥1}5、把汇编语言程序翻译成机器可执行的目标程序的工作是由B完成的。A、编译器B、汇编器C、解释器D、预处理器6、在目标代码生成阶段，符号表用于D。A、目标代码生成B、语义检查C、语法检查D、预处理器地址分配07、规范归约是指B。A、最左推导的逆过程B、最右推导的逆过程C、规范推导D、最左归约逆过程8、使用A可以定义一个程序的意义。A、语义规则B、词法规则C、语法规则D、左结合规则9、经过编译所得到的目标程序是D。A、三元式序列B、四元式序列C、间接三元式D、机器语言程序或汇编语言程序10、在一个基本块内进行的代码优化是B。A、全局优化B、局部优化C、循环优化D、代码外提三、简答题（3小题，共30分）1、已知文法G[S]：S→Ac|aBA→abB→bc证明该文法具有二义性（本题6分）证明：因为该文法的句型abc存在如下两棵语法树：装订线装订线内不要答题学号姓名班级-2-所以，该文法具有二义性3、若有文法G[S]：S→bAbA→（B|aB→Aa）。构造该文法的简单优先关系矩阵。（10分）解：4、构造正规表达式（a|b）*b的DFA并化简。（14分）解：先构造其NFA如下：确定化为DFA：将其最小化如下：四、综合题（20分）设有文法G[S]：S→BAA→BS|dB→aA|bS|c（1）证明文法G是LL（1）文法。（2）构造LL（1）分析表。（3）写出句子adccd的分析过程。解：（1）可见，文法G是是LL（1）文法。（2）（3）备注:学生不得在试题纸上答题(含填空题、选择题等客观题装订线装订线内不要答题学号姓名班级-3-一、填空题（每空1分，共20分）1．编译过程一般分为、、中间代码生成、和目标代码生成五个阶段。2．语法分析最常用的两类方法是和分析法。3．确定的有穷自动机是一个，通常表示为。4．所谓最右推导是指。5．语法分析器的任务是。6．如果一个文法的任何产生式的右部都不含有的非终结符，则这种文法称为文法。7．进行确定的自上而下语法分析要求语言的文法是无和的。8．LR分析法是一种的语法分析方法。9．根据优化对象所涉及的程序范围，代码优化分为、和等。10．常用的优化技术包括：、、强度削弱、复写传播、等。二、是非题（下列各题，你认为正确的，请在题后的括号内打“√”，错的打“×”。每题2分，共20分）1．正规文法产生的语言都可以用上下文无关文法来描述。……………………()2．仅考虑一个基本块，不能确定一个赋值是否真是无用的。………………………（）3．如果一个文法是递归的，则其产生的语言的句子是无穷个。…………………（）4．四元式之间的联系是通过符号表实现的。…………………………………………（）5．文法的二义性和语言的二义性是两个不同的概念。…………………………（）6．一个LL(l)文法一定是无二义的。………………………………………………()7．在规范规约中用最左素短语来刻划可归约串。………………………………()8．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。……………()9．编译程序是对汇编程序的翻译。……………………………………（）10．逆波兰法表示的表达式亦称前缀式。……………………………………………()三、简答题（每题5分，共15分）1、简述栈式存储管理策略；2、何谓DAG；3、何谓文法的二义性；四、给出下述文法对应的正规式（7分）S→0A|1BA→1S|1B→0S|0五、已知文法G(E)：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是该文法的一个句型，并指出该句型的所有短语、直接短语和句柄。（8分）六、设有文法G[S]：SaBc|bABAaAb|bBb|ε构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子.(10分)-4-七、设有文法G[E]:E(E)|ε试判断该文法是否为SLR(1)文法，若不是，请说明理由；若是请构造SLR(1)分析表。(10分)八、假设可用寄存器为R0和R1，试写出下列四元式序列对应的目标代码。（10分）T1=B-CT2=A*T1T3=D+1T4=E-FT5=T3*T4参考答案一、填空题(1X20=20分)1．词法分析、语法分析、代码优化2．自上而下、自下而上3．五元组、DFA=(K,∑,M,S,Z)4．任何一步都是对中最右非终结符进行替换5．分析一个文法的句子结构6．相邻、算符7．左递归、公共左因子8．自下而上9．局部优化、循环优化、局部优化10．删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除无用赋值（任选3个）二、是非题（2X10=20分）1、×2、√3、√4、×5、√6、√7、×8、√9、×10、×三、简答题（见书中相应部分）（5X3=15分）四、解：首先得正规式方程组：S=0A+1BA=1S+1B=0S+0求解该方程组得：S=(01|10)(01|10)*（8分）五、解（2分）是文法G[S]的句型。短语：E+T*F,T*F（2分）直接短语：T*F（2分）句柄：T*F（2分）六、解：、因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}(2分),所以构造文法G[S]的LL（1）分析表（5）如下：aBc#SaBcbABAaAbbBbεε符号串baabbb是该文法的句子(3分)（分析过程略）。七(2分)所以该文法为SLR(1)文法。其分析表如下：(8分)状态ACTIONGOTO()#E0S2r2r211acc-5-2S2r2r233S44r1r1八、目标代码为：(10分)LDR0,BSUBR0,CLDR1,AMULR1,R0LDR0,DADDR0,1STR1,MLDR1,ESUBR0,FMULR0,R1LDR1,MDIVR1,R0STR1,W