搜索
东北农业大学网络教育学院编译原理作业题参考答案第一章编译概述多项选择题：1.编译程序各阶段的工作都涉及到（BC）。（﹡﹡）A.语法分析B.表格管理C.出错处理D.语义分析E.词法分析2.编译程序工作时，通常有（ABCE）阶段。（﹡）A.词法分析B.语法分析C.中间代码生成D.语义检查E.目标代码生成填空题：1．解释程序和编译程序的区别在于（是否生成目标程序）。（﹡）2．编译过程通常可分为5个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、（代码优化）和（目标代码）生成。（﹡）3．编译程序工作过程中，第一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。（﹡）4．编译程序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。（﹡）综合题：1.画出编译程序的总体结构图，简述各部分的主要功能。（﹡﹡﹡）解答：编译程序的总体结构如下图所示：词法分析程序：输入源程序，进行词法分析，输出单词符号。语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一定形式的中间代码，比如说四元式。优化程序：对中间代码进行优化处理。目标代码生成程序：把中间代码翻译成目标语言程序。表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理程序对发现的错误都及时进行处理。第二章文法和语言的基本知识多项选择题：1.ABC2.ACE3.BCD4.AC5.BC填空题：1．文法中的终结符和非终结符的交集是（空集）。词法分析器交给语法分析器的文法符号一定是（终结符），它一定只出现在产生式的（右）部。（﹡）2．最左推导是指每次都对句型中的（最左）非终结符进行扩展。（﹡）3．在语法分析中，最常见的两种方法一定是（自上而上）分析法，另一是（自下而上）分析法。（﹡）4．采用（自上而下）语法分析时，必须消除文法的左递归。（﹡）5．（语法）树代表推导过程，（分析）树代表归约过程。（﹡）6．自下而上分析法采用（移进）、归约、错误处理、（接受）等四种操作。（﹡﹡）7．Chomsky把文法分为（4）种类型，编译器构造中采用（2型）和（3型）文法，它们分别产生（上下文无关语言）和（正规语言）语言，并分别用（下推自动机）和（有限）自动机识别所产生的语言。（﹡﹡）判断题：1．正确2．错误3．错误4．错误5．错误6．错误7．正确8．正确9．错误简答题1句柄：（﹡）解答：一个句型的最左直接短语称为该句型的句柄。2．素短语：（﹡﹡）解答：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3．语法树：（﹡﹡）解答：满足下面4个条件的树称之为文法G[S]的一棵语法树。①每一终结均有一标记，此标记为VN∪VT中的一个符号；②树的根结点以文法G[S]的开始符S标记；③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,Xk，则A→X1,X2,…,Xk，必然是G的一个产生式。4．归约：（﹡﹡）解答：我们称αγβ直接归约出αAβ，仅当A→γ是一个产生式，且α、β∈(VN∪VT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5．推导：（﹡﹡）解答：我们称α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是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。2.文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？（﹡﹡﹡）解答：（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：SabQabcSaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc……于是得到文法G[S]生成的语言L={anbncn|n≥1}3．按指定类型，给出语言的文法。L={aibj|j＞i≥1}的上下文无关文法。（﹡﹡）解答：由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：G[S]：S→aSb|Sb|b4．有文法G：S→aAcB|BdA→AaB|cB→bScA|b（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）写出句子acabcbbdcc的最左推导过程。（﹡﹡﹡）解答：（1）分别画出对应两句型的语法树，如下图所示句柄:AaBBd图语法树（2）句子acabcbbdcc的最左推导如下：STaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5．对于文法G[S]：S→（L）|aS|aL→L,S|S（1）画出句型（S,（a））的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。（﹡﹡﹡）解答：（1）句型（S,（a））的语法树如下图所示。图句型（S,（a））的语法树（2）由上图可知：①短语：S、a、(a)、S,(a)、(S,(a))；②直接短语：a、S；③句柄：S；④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；因此素短语为a。6.考虑文法G[S],其产生式如下:S→(L)|aL→L，S|S(a)试指出此文法的终结符号、非终结符号。(b)给出句子(a,(a，a))的分析树。(c)构造句子(a,(a，a))的一个最左推导。(d)构造句子(a,(a，a))的一个最右推导。(e)这个文法生成的语言是什么？（﹡﹡）解答：(a)终结符号为：{(,),a,,,}非终结符号为：{S,L}开始符号为：S(b)分析树（c）S(L)(L,S)(S,S)(a,S)(a,(L)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))(d)S(L)(L,S)(L,(L))(L,(L,S))(L,(L,a))(L,(S,a))(L,(a,a))(S,(a,a))(a,(a,a))(e)L(G[S])=(α1,α2,...,αn)或a其中αi(1≤i≤n)是L(G[S])。即L(G[S])产生一个以a为原子的纯表，但不包括空表。7．考虑文法G[T]：T→T*F|FF→F↑P|PP→（T）|i证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。（﹡﹡）解答：首先构造T*P↑（T*F）的语法树如下图所示。图句型T*P↑（T*F）的语法树由上图可知，T*P↑（T*F）是文法G[T]的一个句型。直接短语有两个，即P和T*F；句柄为P。8．试描述下列文法产生的语言L（G[S]）（﹡﹡）S→10S0|aAA→bA|a解答：L(G)={(10)iabna0in≥0i≥0}9．已知语言L(G)={abnc|n≥1}试对该语言构造相应文法。（﹡﹡）解答：G[Z]:Z→aBCB→Bb|b10．证明下列文法的二义性（﹡﹡﹡）1．G[Z]2．G[S]Z→aZbZ|aZ|aS→ABA→bB|bC|baB→Sb|ba|aC→Bb|b解答：（1）对于句子aaaba，画出二棵不同的语法树，因而是二义的。（2）G[S]对于句子baba，画出二棵不同的语法树，因而是二义的。11．有文法G[S]：S→iSeS|iS|i该文法是否是二义的。试证明之。（﹡﹡）解答：对于句子iiiei，有两棵不同的语法树，故文法是二义的。12．文法G[T]：T→aR，R→Tb|d生成的语言是什么？G[T]是否为3型文法？（﹡﹡）解答：不是3型文法。13.试写出能够描述下列电话号码格式的文法。（﹡﹡）67391742010-67391742(010)67391742解答：文法产生式规则如下：电话号码→局代码本机码电话号码→区前缀局代码本机码区前缀→地区码‘-’区前缀→‘(’地区码‘)’地区码→DIGDIG地区码→DIGDIGDIG局代码→DIGDIGDIGDIG本机码→DIGDIGDIGDIG14.试构造生成语言的上下文无关文法。（﹡﹡﹡）(1){anbnci|n≥1,i≥0}(2){w|w∈{a,b}+，且w中a的个数恰好比b多1}解答：(1)把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S→ABA→aAb|abB→cB|ε(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|ε15.下面的二义性文法描述命题演算公式，为它写一个等价的非二义性文法。G[S]:S-SANDS|SORS|NOTS|p|q|(S)（﹡﹡）解答：G[S]:S-SANDA|AA-AORB|BB-NOTB|p|q|(S)16.对于下列语言分别写出它们的正规表达式。（﹡﹡）(1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。解答：(1)令Letter表示除这五个元音外的其它字母。((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2)A*B*....Z*第三章词法分析与有穷自动机多项选择题：1.ACE2.ABD填空题：1．确定有限自动机DFA是（NFA）的一个特例。（﹡）2．若二个正规式所表示的（正规集）相同，则认为二者是等价的。（﹡）3．一个字集是正规的，当且仅当它可由（DFA/NFA）所（识别）。（﹡）判断题：1．错误2．错误3．错误4．正确5．正确6．正确7．正确8．正确9．错误10．正确综合题：1．设M＝（{x,y},{a,b},f,x,{y}）为一非确定的有限自动机，其中f定义如下：f（x,a）＝{x,y}f（a,b）＝{y}f（y,a）＝φf（y,b）＝{x,y}试构造相应的确定有限自动机M′。（﹡﹡）解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFAM相应的状态图，如图下所示。图NFAM用子集法构造状态转换矩阵下表所示。将转换矩阵中的所有子集重新命名而形成下表所示的状态转换矩阵。表状态转换矩阵即得到M′＝（{0,1,2},{a,b},f,0,{1,2}），其状态转换图如下图所示。将上图的DFAM′最小化。首先，