发布时间 : 星期日 文章(整理完)编译原理网上作业题参考答案20121101更新完毕开始阅读
东北农业大学网络教育学院 编译原理作业题参考答案
第一章 编译概述
多项选择题：
1.编译程序各阶段的工作都涉及到（BC）。（﹡﹡）
A.语法分析 B.表格管理 C.出错处理 D.语义分析E.词法分析 2.编译程序工作时，通常有（ABCE）阶段。 （﹡）
A.词法分析 B.语法分析 C.中间代码生成 D.语义检查 E.目标代码生成
填空题：
1．解释程序和编译程序的区别在于（是否生成目标程序）。（﹡）
2．编译过程通常可分为5个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、（代码优化）和（目标代码）生成。（﹡）
3．编译程序工作过程中，第一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。（﹡） 4．编译程序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。（﹡）
综合题：
1.画出编译程序的总体结构图，简述各部分的主要功能。（﹡﹡﹡） 解答：编译程序的总体结构如下图所示：
词法分析程序：输入源程序，进行词法分析，输出单词符号。
语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。
中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一定形式的中间代码，比如说四元式。
优化程序：对中间代码进行优化处理。
目标代码生成程序：把中间代码翻译成目标语言程序。
表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格打交道。
出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理程序对发现的错误都及时进行处理。
第二章 文法和语言的基本知识
多项选择题：
1. ABC 2. ACE 3. BCD 4. AC 5. 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|abQ QP→PQ bP→bb bQ→bc cQ→cc
*
（1）它是Chomsky哪一型文法？ （2）它生成的语言是什么？（﹡﹡﹡） 解答：
（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到： S S SaaabbQQQ ……
于是得到文法G[S]生成的语言L={abc|n≥1}
3．按指定类型，给出语言的文法。
L={ab|j＞i≥1}的上下文无关文法。（﹡﹡） 解答：
由L={ab|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为： G[S]：S→aSb|Sb|b
4．有文法G：S→aAcB|Bd A→AaB|c B→bScA|b
（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄； （2）写出句子acabcbbdcc的最左推导过程。（﹡﹡﹡） 解答：
（1）分别画出对应两句型的语法树，如下图所示 句柄:AaB Bd
ijij
nnn
abQaSPQaSPQ
abc aabQPQaaSPQPQ
aabPQQ
aabbQQ
aabbcQ
aabbcc aaabPQPQQ
aaaPPQQQ
aaabbPqqq
aaabQPQPQaaabPQQPQ
aaabbbcQQaaabbbccQaaabbbccc