(整理完)编译原理网上作业题参考答案20121101.doc

《(整理完)编译原理网上作业题参考答案20121101.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东北农业大学网络教育学院编译原理作业题参考答案第一章编译概述多项选择题：1.编译程序各阶段的工作都涉及到（BC）。（﹡﹡）A.语法分析B.表格管理C.出错处理D.语义分析E.词法分析2.编译程序工作时，通常有（ABCE）阶段。 （﹡）A.词法分析B.语法分析C.中间代码生成D.语义检查E.目标代码生成填空题：1．解释程序和编译程序的区别在于（是否生成目标程序）。（﹡）2．编译过程通常可分为5个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、（代码优化）和（目标代码）生成。（﹡）3．编译程序工作过程中，第

2、一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。（﹡）4．编译程序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。（﹡）综合题：1.画出编译程序的总体结构图，简述各部分的主要功能。（﹡﹡﹡）解答：编译程序的总体结构如下图所示：词法分析程序：输入源程序，进行词法分析，输出单词符号。语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一

3、定形式的中间代码，比如说四元式。优化程序：对中间代码进行优化处理。目标代码生成程序：把中间代码翻译成目标语言程序。表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理程序对发现的错误都及时进行处理。第二章文法和语言的基本知识多项选择题：1.ABC2.ACE3.BCD4.AC5.BC 填空题：1

4、．文法中的终结符和非终结符的交集是（空集）。词法分析器交给语法分析器的文法符号一定是（终结符），它一定只出现在产生式的（右）部。（﹡）2．最左推导是指每次都对句型中的（最左）非终结符进行扩展。（﹡）3．在语法分析中，最常见的两种方法一定是（自上而上）分析法，另一是（自下而上）分析法。（﹡）4．采用（自上而下）语法分析时，必须消除文法的左递归。（﹡）5．（语法）树代表推导过程，（分析）树代表归约过程。（﹡）6．自下而上分析法采用（移进）、归约、错误处理、（接受）等四种操作。（﹡﹡）7．Chomsky把文法分为（4）

5、种类型，编译器构造中采用（2型）和（3型）文法，它们分别产生（上下文无关语言）和（正规语言）语言，并分别用（下推自动机）和（有限）自动机识别所产生的语言。（﹡﹡）判断题： 1．正确2．错误3．错误4．错误5．错误6．错误7．正确8．正确9．错误简答题1句柄：（﹡）解答：一个句型的最左直接短语称为该句型的句柄。2．素短语：（﹡﹡）解答：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3．语法树：（﹡﹡）解答：满足下面4个条件的树称之为文法G[S]的一棵语法树。　　①每一终结均有一标记，此标记为V

6、N∪VT中的一个符号；　　②树的根结点以文法G[S]的开始符S标记；　　③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；　　④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,Xk，则A→X1,X2,…,Xk，必然是G的一个产生式。4．归约：（﹡﹡）解答：我们称αγβ直接归约出αAβ，仅当A→γ是一个产生式，且α、β∈(VN∪VT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5．推导：（﹡﹡）解答：我们称α

7、Aβ直接推出αγβ，即αAβTαγβ，仅当A→γ是一个产生式，且α、β∈(VN∪VT)*。如果α1α2…αn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。问答题1．给出上下文无关文法的定义。（﹡﹡）解答：　　一个上下文无关文法G是一个四元式（VT,VN,S,P），其中：　　●VT是一个非空有限集，它的每个元素称为终结符号；　　●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ；　　●S是一个非终结符号，称为开始符号；　　●P是一个

8、产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。2.文法G[S]：　　　　　　　S→aSPQ

9、abQ　　　　　　　QP→PQ　　　　　　　bP→bb　　　　　　　bQ→bc　　　　　　　cQ→cc　　　（1）它是Chomsky哪一型文法？　　　（2）它生成的语言是什么？（﹡﹡﹡）解答：　　（