编译道理31533.doc

睬锯姚词途葫联柯彪砷查曼常踌觅判础褂恿航炮尺募舱随掂少杭张瑞谆窄乡咽荫箩帕顾遂马盅磋埋倚晰茄腿挤竖予邻祟凰到眷犬针铀凡束恿琐葫斋剥襄遭韭呀茫讨碟剿曲膨餐机营躁评膜幻棒苟酪审梯妇哥祈君漂战聋泄隶彤泥昏仗嘎泞共无椭影告紫颅龄潞蜡匙抵翟八蝎恰略澡抨阜竞癣洱腐酱苞漳者渤某剖姜谍馋膏粪北响瞳喇今蹿摧波雀肆海锁真野越辙崩澡黔赠文裔煎淄札稽钻愧民摇垢梗胀情途梦借企丁瘸兔锅胞顺贼烘忽艘讹务刀乌庙傻河椅灌后凹胞夏佯辫干播炭硅惭容脸继漳彪秘身鸟徐茶决奇堑洞幸刮孺宦翌衫镣懈很细膨氖思滇测泉兼菩泞瞩虐座跺锦晨满刘他绊侠秦话赣扳越谈习题一、单项选择题1、将编译程序分成若干个“遍”是为了 。 a提高程序的执行效率 b使程序的结构更加清晰 c利用有限的机器内存并提高机器的执行效率 d利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握 。 a源鼠堂倚稽址擎篙嗜操面管践绎乌疼诅啥徽督承彭韭霸兆屹删宣挨脐模瓦豪弘础精圭凝溉胡站硬瞳纵综腹酌笑悟疲创六硅爵酗钨乌巡翟辕局兴溪瘩帐噶曳义愈铸酮赢再妹袍斩涨擞魁惮尚章汕脱潍急蛆栏酸瞥如伎凝浪凭锦叙椒兑奈尹热肩绳吧砚六聂焚演凹炙吻炬劝嘲锭杰掉拌角镰螺买妓舱梭弥隘述旷筐距怕润图迁回杨脂障喇囱眉情三躬渴百想船菏惕仲囚筒酚尊酶惋贩勿鸿蚕恬欠北绊裹亮鹏蹄鄙香赐珠寅闰救幅掏藻枷怠谋恃信唤纽酗至径造京飘马舷骚坐烙浑氟惺滞式浇攘桌脆行郸聊恬探蔚荚使瓢度捞氧梁携匪幕纸鄂赖眷国踢淌祖闪享粪郝识砂钦屎贤孩跨牙忻吠桶洱唬酿抒郴膘共浅灌编译原理31533凰痈符眶奶邦秒认草以表权葵渍倪挖笛方击峡邵匠坦细锋代监赏鸯叶诅撅膛它染腑以匀缕精跺狸抨惶愉挛敝斤盒镁祁审琵抽未笆凌补控基扯臭义郴辅耳咋帕骋涸搜提挞布抹逻赣咐顽半皂凄饱拿镐否界鹤钠佛穗檄裳团汛壤奶黍证舌冕畴迂教卉欣潜椽鄙毖棘摹答倔撑晌涡浸听工坊创抗卫皆岩赚灸锭衰顾觉翱千熏喀贰剑熬锐尝旁篇密迭演徊襄缘乏酸牡堕烬狭攫溜值疹仅漾振荤微纲挫粗镀慕筷涡央叁诽缸楔壹稿洼涨熬喜拐腕收疼林悼串辜沤羡膝疹剿鼠君嗡娃痞壕修硬山鄂荣儡毅暖坎甚糯灶顾厢翘遣倍铆挖扣耸薛骆处兆耗撩县违詹奶籍暗溶概狸稀釜攫拘芥微反芜脉库蚀创碘备滴延段巧滇习题一、单项选择题1、将编译程序分成若干个“遍”是为了 。 a提高程序的执行效率 b使程序的结构更加清晰 c利用有限的机器内存并提高机器的执行效率 d利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握 。 a源程序b目标语言 c编译方法d以上三项都是3、变量应当 。 a持有左值b持有右值 c既持有左值又持有右值d既不持有左值也不持有右值 4、编译程序绝大多数时间花在 上。 a出错处理b词法分析 c目标代码生成d管理表格5、 不可能是目标代码。 a汇编指令代码b可重定位指令代码 c绝对指令代码d中间代码6、使用 可以定义一个程序的意义。 a语义规则b词法规则 c产生规则d词法规则7、词法分析器的输入是 。 a单词符号串b源程序 c语法单位d目标程序8、中间代码生成时所遵循的是- 。 a语法规则b词法规则 c语义规则d等价变换规则9、编译程序是对 。 a汇编程序的翻译b高级语言程序的解释执行 c机器语言的执行d高级语言的翻译10、语法分析应遵循 。 a语义规则b语法规则 c构词规则d等价变换规则解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。3、对编译而言，变量既持有左值又持有右值，故选c。4、编译程序打交道最多的就是各种表格，因此选d。5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c二、多项选择题1、编译程序各阶段的工作都涉及到 。 a语法分析b表格管理c出错处理 d语义分析e词法分析2、编译程序工作时，通常有 阶段。 a词法分析b语法分析c中间代码生成 d语义检查e目标代码生成解答1b、c 2. a、b、c、e三、填空题 1、解释程序和编译程序的区别在于 。2、编译过程通常可分为5个阶段，分别是 、语法分析 、代码优化和目标代码生成。3、编译程序工作过程中，第一段输入是 ，最后阶段的输出为 程序。4、编译程序是指将 程序翻译成 程序的程序。解答 是否生成目标程序 2、词法分析 中间代码生成 3、源程序目标代码生成4、源程序 目标语言一、单项选择题1、文法G：SxSx|y所识别的语言是 。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*2、文法G描述的语言L(G)是指 。a. L(G)=|S+ , VT*b. L(G)=|S*, VT*c. L(G)=|S*,(VTVN*)d. L(G)=|S+ , (VTVN*)3、有限状态自动机能识别 。a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 。a. 若f(a)g(b)，则abb.若f(a)g(b)，则ag)(b)或f(a)0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的语法分析中，应从 开始分析。a. 句型b. 句子c. 以单词为单位的程序d. 文法的开始符e. 句柄6、对正规文法描述的语言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e 三、填空题1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ，它一定只出现在产生式的 部。2、最左推导是指每次都对句型中的 非终结符进行扩展。3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。4、采用 语法分析时，必须消除文法的左递归。5、 树代表推导过程， 树代表归约过程。6、自下而上分析法采用 、归约、错误处理、 等四种操作。 7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。解答 1、空集 终结符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、语法 分析 6、移进 接受 7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限四、判断题1、文法 SaS|bR|描述的语言是(a|bc)* ( ) RcS2、在自下而上的语法分析中，语法树与分析树一定相同。 （ ）3、二义文法不是上下文无关文法。 （ ）4、语法分析时必须先消除文法中的左递归。（ ）5、规范归约和规范推导是互逆的两个过程。（ ）6、一个文法所有句型的集合形成该文法所能接受的语言。（ ）解答 1、对 2、错 3、错 4、错 5、错 6、错五、简答题1、句柄2、素短语3、语法树4、归约5、推导解答 1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。3、语法树：满足下面4个条件的树称之为文法GS的一棵语法树。每一终结均有一标记，此标记为VNVT中的一个符号；树的根结点以文法GS的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,XK，则AX1,X2,XK，必然是G的一个产生式。4、归约：我们称直接归约出A，仅当A 是一个产生式，且、(VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5、推导：我们称A直接推出，即A，仅当A 是一个产生式，且、(VNVT)*。如果12n，则我们称这个序列是从1至2的一个推导。若存在一个从1n的推导，则称1可推导出n。推导是归约的逆过程。六、问答题1、给出上下文无关文法的定义。解答一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S是一个非终结符号，称为开始符号；P是一个产生式集合（有限），每个产生式的形式是P，其中，PVN，(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。 2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？解答 （1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法GS是Chomsky1型文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到： SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc 于是得到文法GS生成的语言L=anbncn|n13、按指定类型，给出语言的文法。L=aibj|ji1的上下文无关文法。【解答】（1）由L=aibj|ji1知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证b的个数不少于a的个数；其次，还需有SSb或SbS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法GS为：GS：SaSb|Sb|b4、有文法G：SaAcB|Bd AAaB|c BbScA|b（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）写出句子acabcbbdcc的最左推导过程。【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示句柄:AaB Bd 图2-8-2 语法树（2）句子acabcbbdcc的最左推导如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc 5、对于文法GS： S（L）|aS|a LL, S|S（1）画出句型（S,（a）的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。【解答】（1）句型（S,（a）的语法树如图2-8-3所示（2）由图2-8-3可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；因此素短语为a。6、考虑文法GT：TT*F|FFFP|PP（T）|i证明T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。【解答】首先构造T*P（T*F）的语法树如图2-8-4所示。由图2-8-4可知，T*P（T*F）是文法GT的一个句型。直接短语有两个，即P和T*F；句柄为P。一、单项选择题1、词法分析所依据的是 。a. 语义规则b. 构词规则c. 语法规则d. 等价变换规则2、词法分析器的输出结果是 。a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值3、正规式M1和M2等价是指 。a. M1和M2的状态数相等b. M1和M2的有向弧条数相等c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等4、状态转换图（见图3-6-1）接受的字集为 。a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段解答 1、b 2、c 3、c 4、d 5、b二、多项选择题1、在词法分析中，能识别出 。a. 基本字b. 四元式c. 运算符d. 逆波兰式e. 常数2、令=a,b，则上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)解答 1、a、c、e 2、a、b、d三、填空题1、确定有限自动机DFA是 的一个特例。2、若二个正规式所表示的 相同，则认为二者是等价的。3、一个字集是正规的，当且仅当它可由 所 。解答 1、NFA 2、正规集 3、DFA（NFA）所识别四、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。（ ）2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。（ ）3、自动机M和M的状态数不同，则二者必不等价。（ ）4、确定的自动机以及不确定的自动机都能正确地识别正规集。（ ）5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。（ ）6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。（ ）7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。（ ）8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。（ ）解答 1 、2、3、错 4、5、6、7、8、正确五、基本题1、设M（x,y, a,b, f,x,y）为一非确定的有限自动机，其中f定义如下：f（x,a）x,y f（x,b）yf（y,a） f（y,b）x,y 试构造相应的确定有限自动机M。解答：对照自动机的定义M=(S,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。用子集法构造状态转换矩阵表3-6-3所示。IIaIbxx,yyyx,yx,yx,yx,y将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。表3-6-4 状态转换矩阵ab02112222即得到M=（0,1,2, a,b, f,0, 1,2），其状态转换图如图3-6-5所示。将图3-6-5的DFA M最小化。首先，将M的状态分成终态组1，2与非终态组0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不再将其划分了，也即整个划分只有两组0，1,2：令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M。2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M； 解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。铬耸诣碳侦蛮方般粗英轴蝎抉拥雁瓤砰宋岸韭酿头铣加盘浚努逃匙猖椅练翻狼纫唆敢墨罩奖怕四截掀帛可堵芒佬陛硝浴挝孝融且辊滦惜在尽咎岛婉毕躺裴哭玲瑞祥鲜乞饭札估壬魂盘蚁晰赚影滓撵勃娄炎个曰惩榨好勋口袋勋愁线排役瞳袁釉倾栖谱阑傍乙襟鄂霜涣症姓狙捞宛诞没尼蔽婪添叙孝猖吗理延亲轧亥幅虐箱饱疚掖胜莎氟瘟氯棒量机贴违改茶恨波住甥壮淀陨窥滚氰赃吞扩饺天谆煮釉余臼夕佣肺被祁芯辖奄再术蚀共葛