下载文档原格式
编译原理期末考试试题及答案一、选择题（每题2分，共20分）1. 编译器的前端主要负责以下哪项工作？A. 代码优化B. 目标代码生成C. 词法分析和语法分析D. 运行时支持2. 词法分析器的主要任务是什么？A. 识别语法结构B. 识别词法单元C. 构建语法树D. 代码优化3. 语法分析中，使用哪种方法可以避免回溯？A. 递归下降分析B. LR分析C. LL分析D. 自顶向下分析4. 下列哪个选项不是中间代码的形式？A. 三地址代码B. 四元组C. 抽象语法树D. 汇编语言5. 代码优化的目标不包括以下哪项？A. 提高代码执行速度B. 减少程序占用的内存C. 增加程序的可读性D. 减少程序的执行时间二、简答题（每题10分，共30分）1. 简述编译器的主要组成部分及其功能。
2. 解释什么是语法制导翻译，并举例说明其在编译过程中的应用。
3. 描述静态作用域规则和动态作用域规则的区别。
三、计算题（每题15分，共30分）1. 给定一个简单的算术表达式 `3 + (4 * 5) - 2`，请使用逆波兰表示法表示，并说明其转换过程。
2. 假设有一个简单的文法如下：```S -> A BA -> a A | εB -> b B | ε```请写出使用该文法生成字符串 "ab" 的所有派生树。
四、论述题（每题20分，共20分）1. 论述编译器中代码优化的重要性，并举例说明常见的优化技术。
参考答案一、选择题1. C2. B3. B4. D5. C二、简答题1. 编译器的主要组成部分包括前端、中端和后端。
前端负责词法分析和语法分析，中端进行语义分析和中间代码生成，后端则负责代码优化和目标代码生成。
2. 语法制导翻译是一种基于文法规则的翻译技术，它将源程序的语法结构映射到相应的语义操作上。
例如，在编译过程中，语法制导翻译可以用于将源代码中的条件语句转换为中间代码中的跳转指令。
3. 静态作用域规则是指变量的作用域在编译时确定，而动态作用域规则是指变量的作用域在运行时确定。
编译原理期末试卷1．给出LL(1)分析方法的总控流程图。
（5分）2．按指定类型给出下列语言的文法。
（10分）(1) L1={ ca n b m| n≥0,m>0 } 用正规文法。
S→cA A→aA|aB|a B→bB|b(2) L2={ 0n a 1n b m| n>0，m ≥0} 用二型文法。
S→0S1B|0a1 B→bB|c3．文法G[S]为：（10分）S→SdT | T T→T<G | G G→(S) | a试给出句型adT<(S)的短语、简单(直接)短语、句柄和最左素短语。
短语：a, T, (S), T<(S), adT<(S) 直接短语：a, (S) 句柄：a 最左素短语：a 4．将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。
（5分）S→[A A→B]|AS B→aB|+aS→[A A→B]A’A’→SA’|εB→aB|+a5．判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表，并写出aabbb 的分析过程。
（10分）S→aD D→STe|ε T→bM M→bH H→M|ε6．简述编译程序概念及构成。
（10分）编译程序是现代计算机系统的基本组成部分.从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序.7．设G=（V N，V T，P，<S>）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？（10分）2型（上下文无关）：规则形式：A→βA ∈VN，β∈ (VT⋃VN)*3型（右线性）：A→aB或A→a（右线性）A→Ba或A→a （左线性）a ∈VT⋃{ε}8．为文法G[E]：（10分）V → N | N[E] E → V | V+E N → i构造递归下降识别程序E( ){ V( ); if symbol = ‘+’E( ); }V( ){ N(); if symbol = ‘[’ { E(); if symbol != ‘]’error(); }N( ){ if symbol != ‘i ’ error(); }/* 这样的写法很简化，当文法提取左公因子后，需要计算相关非终结符的Follow 集，才能确定什么时候用空串规则推导。
湖北第二师范学院2014－2015学年度第二学期《编译原理》课程考试答案(A卷) 院系：计算机学院专业班级：学生姓名：学号：考试方式：闭卷………………………………………………………………………………………………………………一、填空题（每空1分，共10分）1．词法分析程序是逐个识别（字符），形成单词级别的（字符）串，词法分析程序输出的数据是（2 ）个，它们分别是（种别编码）和（自身值）。
2．语法分析程序是逐个识别（单词），形成语句级别的（单词）串。
3．一遍扫描的编译方法，是以语法分析程序为主，调用（词法分析）程序、语义分析程序，再由语义程序调用中间代码生成、中间代码优化等。
4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配）方案和（动态存储分配）方案。
二、综合题（共90分）1．（5分）将下面文法改写成3型文法：G=（｛S,A,B｝,{a,b,c,d,e},P,S）其中：P={S→abcA|edB,A→beB,B→d}答案：改写后的3型文法是（5分）G=（｛S,A,B,C,D,E,F｝,{a,b,c,d,e},P,S）其中：P={S→aC|eF, C→bD,D→cA,A→bE,E→eB,F→dB,B→d}2．（5分）给出下面表达式的四元式形式：a*b+(c-d)/e答案：四元式形式（5分）（*，a，b，t1）（-，c，d，t2）（/，t2，e，t3）（+，t1，t3，t4）3．（30分）给定文法 G[E] ：E → E+T | E-T | TT → T*F | T/F | FF → (E) | i该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。
无论改造前还是改造后的文法，如果是LL（1）文法，则给出（i+i）*i的分析过程（要求给出详细过程，并给出LL（1）的分析表）答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归（2分）（2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是（3分）E → TE’E’→ +TE’ | -TE’ | εT → FT’T’→ *FT’ | /FT’ |εF → (E) | i证明改造后的文法是LL（1）文法的过程A.求可达ε的非终结符（1分）可达的是E’,T’B.求每个非终结符的First集合（3分）First(E)={ (,i}First(E’)={+,-}First(T)={ (,i}First(T’)={*,/}First(F)={ (,i}C.求每个产生式右部字符串的First集合（3分）First(TE’)={ (,i}First(+TE’)={+}First(-TE’)={-}First(FT’)={ (,i}First(*FT’)={*}First(/FT’)={/}First((E))={ ( }First(i)={ i }First(ε)={ ε}D.求每个非终结符的Follow集合（3分）Follow(E)={$,)}Follow(E’)= Follow(E)={$,)}Follow(T)=First(E’) ∪ Follow(E)={$,+,-,)}Follow(T’)= Follow(T)={$,+,-,)}Follow(F)= First(T’) ∪ Follow(T)={$,+,-, *,/,)}E.求每个非终结符的Select集合（5分）Select(E → TE’)=First(TE’)={ (,i }Select(E’→ +TE’)=First(+TE’)={ + }Select(E’→ -TE’)=First(-TE’)={ - }Select(E’→ε)=First(ε)-{ ε} ∪ Follow(E’)={ $,) }Select(T → FT’)=First(FT’)={ (,i }Select(T’→ *FT’)=First(*FT’)={ * }Select(T’→ /FT’)=First(/FT’)={ / }Select(T’→ε)=First(ε)-{ ε} ∪ Follow(T’)={ $,+,-,) }Select(F → (E))=First((E))={ ( }Select(F → i)=First(TE’)={ i }F.求有多个产生式的非终结符Select集合的交集（2分）显然有Select(E’→ +TE’)∩Select(E’→ -TE’) ∩Select(E’→ε)=ΦSelect(T’→ *FT’) ∩Select(T’→ /FT’) ∩Select(T’→ε)= ΦSelect(F → (E))= ∩Select(F → i)= Φ所以改造后的文法是LL（1）文法4．（10分）对下面的NFA进行确定化答题：第1第25．（15分）给定文法 G[E] ：E → E+T | E-T | TT → T*F | T/F | F该文法是算符优先文法吗？是，则构造该文法的算符优先关系矩阵，并给出（i+i）*i的分析过程（要求给出详细过程）答案：（1）该文法是算符优先文法（1分）（2）构造该文法的算符优先矩阵A.求各非终结符的FirstVT集合（3分）FirstVT（E）=｛+，-，*，/，（，i｝FirstVT（T）=｛*，/，（，i｝FirstVT（F）=｛（，i｝B.求各非终结符的LasttVT集合（3分）LastVT(E)={ +，-，*，/，)，i }LastVT(T)={ *，/，)，i }LastVT(F)={ )，i }C.构造优先关系表（4分）6．（25分）给定文法 G[E] ：T → T*F | FF → (E) | i该文法是LR（0）文法吗？是，则构造该文法的LR（0）分析表，并给出（i+i）*i的分析过程，不是的，是SLR（1）文法吗，是，则构造该文法的SLR（1）分析表，并给出（i+i）*i的分析过程。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。
(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。
(×)3．一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4．语法分析时必须先消除文法中的左递归。
(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
(√)6．逆波兰表示法表示表达式时无须使用括号。
(√ )7．静态数组的存储空间可以在编译时确定。
(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。
(× )10．一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。
A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。
A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。
《编译原理》考试试卷A适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1.解释系统与编译系统的区别在于和。
2.在编译过程中始终伴随着管理和出错处理过程。
3.语法分析的方法为和两大类。
4.LL(1)文法中不能有和。
5.词法分析器中单词的描述工具是 ,单词的识别工具。
6.算符优先语法分析，在符号栈栈顶出现时，进行规约处理。
二、单选题（每小题2分，共10分）1.词法分析器的加工对象是（）A.中间代码B.单词C.源程序D.元程序2.同正则表达式a*b*等价的文法是（）A. G1:S→aS|bS|εB. G2: S→aSb|εC. G3:S→aS|Sb|εD. G4: S→abS|ε3.文法G[A]:A→bH H→BA B→Ab H→a 不是（）A. 2型文法B. 3型文法C. 0型文法D.1型文法4.算符优先分析每次都是对（）进行规约。
A.短语B.最左素短语C.素短语D.句柄5.( )不是DFA的成分。
A.有穷字母表B. 初始状态集合C.终止状态集合D.有限状态集合三、问答题（第1,5小题每题15分，其余每小题10分，共80分）1. （15分）解释下列术语：（1）编译程序（2）句柄（3）上下文无关文法2.编译程序主要有哪些构成成分？（10分）3.给出描述语言L={a n b2n c m|n,m≥0}的cfg。
（10分）4.（10分）将下图中的DFA M最小化。
5. （15分）判断文法G[S]:S→aHH→aMd|dM→Ab|εA→aM|e是否为LL(1)文法？给出判断过程。
6. （10分）改写文法G[E]：E → E+T|TT →T*F|FF →(E)| a为无左递归文法。
7. （10分）已知文法G[S]为：S→VV→T|ViTT→F|T+FF→)V*|(请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。
《编译原理》考试试卷A参考答案适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1. 边翻译边执行和不生成目标代码。
期末考试试卷（A）卷一、填空题（每小题2分，共20分）1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。
2、设z=abc，则z的固有头是①。
3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫①。
4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为①5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。
6、LR分析是按规范句型的①为可归约串。
7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。
8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算①。
9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。
10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk的一条通路。
如果n1=nk，则称该通路为①。
二、单项选择（每小题2分，共14分）1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。
其中3型文法也称为（）。
A．上下无关文法 B.正规文法C．上下文有关文法 D.无限制文法2、生成非0开头的正偶数集的文法是（）。
A． Z::=ABC B. Z::=ABCC::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|ε B::=BA|B0|0A::=1|2|3|…|9 A::=1|2|3|…|9C. Z::=ABC|2|4|6|8D. Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|0 B::=BA|B0|εA::=1|2|3|…|9 A::=1|2|3|…|93、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。
A.素短语B.直接短语C.句柄D.最左素短语4、同心集合并有可能产生新的（）冲突。
《编译原理》期末试题（一）一、是非题（请在括号，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。
(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。
(×)3．一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4．语法分析时必须先消除文法中的左递归。
(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
(√)6．逆波兰表示法表示表达式时无须使用括号。
(√ )7．静态数组的存储空间可以在编译时确定。
(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。
(× )10．一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。
A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式 M 1 和 M 2 等价是指_____。
A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。
A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。
参考答案一、填空题（每空1分，共10分）1编译程序（编译器）；解释程序（解释器）2 e, h, he, hel, hell3回退4正规文法（3型文法）5自顶向下；自底向上6左递归7归约.归约，移进.归约二、选择题(每小题2分，共20分)1 A 2D 3B 4B 5B6D 7C 8B 9A 10 C三、应用题(共46分)l(l)E=>E + TnT + TnF + Tni + Tni + T*Fni + F*Fni + i*Fni + i*(E) n i + i * (E — T) n i + i * (T — T) n i + i * (F — T) n i + i * (i — T) n i + i * (i — F) n i + i * (i — i)(2)i + i * (i — i) u F + i * (i — i) u T + i * (i — i) u E + i * (i — i) u E + F * (i — i)uE + T*(i - i)uE + T*(F - i)uE + T*(T - i)uE + T*(E - i)uE + T*(E - F) <=E + T*(E —T)uE + T*(E)<=E + T*F<=E + T<=E(3)(4)短语：il + i2 * (13 - 14), ib 12 * (13 - 14), 12, (13 - iQ, 13 - U, k, U直接短语：ii, ^2,13, U句柄：ii素短语：ii, i2,13,142对句子auab有两个不同的最左推导R n RuR n auR n auRR n auaR n auabR n RR n RuRR n aoRR n auaR n aoab所以该文法是二义性文法3 (ID, “int"), (ID, “main"), (LR_BRAC, _), (RR_BRAC, _)(LC.BRAC, _),(ID, “int”)，(ID, “a”)，(SEMIC, _),(ID, “a”)，(ASSIGN, _), (INT, 1), (SEMIC, _),(IF, _), (LR_BRAC, _), (ID, “a”), (EQ, _), (INT, 1), (RR_BRAC, _),(ID, “printf'), (LR_BRAC, _), (STRING, “Hello world!\n”)，(RR_BRAC, _), (SEMIC, _), (RETURN, _), (INT, 0), (SEMIC, _),(RC_BRAC, _)45(1)A T Aab I db I Aa I c ArdbA'IcA'A* T abA' I aA' I £⑵A — dbA'IcA'A't aB I £B r bA' I A'6(1)(2) 3 2 + 5 -7 100 (+, a, b,tl)101(uminus, tl, t2)102(+, c, d, t3)103(*, t2, t3, t4)四、综合题(共24分)1.(1) FISRT(S) = {(, a} FIRST(L) = FISRT(S) = {(, a} FIRST(M) = {b,e) FOLLOW(L) = ()} FOLLOW(M) = FOLLOW(L) = ()}(0) S' T S(1)S->aS(2)S->bA(3)A-> aA⑷A T £。
编译原理期末试题及答案一、选择题（每题2分，共20分）1. 编译器的主要功能是将（）代码转换成（）代码。
A. 高级语言，低级语言B. 高级语言，机器语言C. 汇编语言，机器语言D. 机器语言，汇编语言答案：B2. 编译过程中，词法分析的输出是（）。
A. 语法树B. 语法分析表C. 词法单元D. 抽象语法树答案：C3. 在编译原理中，语法分析通常采用（）方法。
A. 递归下降分析B. 动态规划C. 贪心算法D. 回溯算法答案：A4. 语义分析的主要任务是（）。
A. 检查语法错误B. 生成中间代码C. 检查语义错误D. 优化代码答案：C5. 编译器的优化通常发生在（）阶段。
A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D6. 编译器的前端主要负责（）。
A. 代码生成B. 代码优化C. 语法分析D. 目标代码生成答案：C7. 编译器的后端主要负责（）。
A. 代码生成B. 代码优化C. 语法分析D. 词法分析答案：A8. 编译原理中，LL(1)分析方法的特点是（）。
A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B9. 编译原理中，LR(1)分析方法的特点是（）。
A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B10. 编译原理中，语法制导翻译的主要思想是（）。
A. 根据语法树的结构进行翻译B. 根据词法单元进行翻译C. 根据语法分析表进行翻译D. 根据语义分析表进行翻译答案：A二、填空题（每题2分，共20分）1. 编译器中，用于表示语法规则的产生式通常由非终结符、产生符号和（）组成。
答案：产生式右侧2. 在编译原理中，一个文法是（）的，如果它的任何两个产生式都不会导致相同的句柄。
答案：无二义性3. 编译器的词法分析阶段通常使用（）算法来识别和分类词法单元。
答案：有限自动机4. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。
<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题1．将编译程序分成若干个“遍”是为了_b__。
a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2．构造编译程序应掌握__d__。
a.源程序b.目标语言c.编译方法d.以上三项都是3．变量应当c＿。
a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4．编译程序绝大多数时间花在_d___上。
a.出错处理b.词法分析c.目标代码生成d.管理表格5．词法分析器的输出结果是_c___。
a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值6．正规式MI和M2等价是指__c__。
a.MI和M2的状态数相等b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等 d.Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—c。
a．语法规则b．词法规则c．语义规则d．等价变换规则8．后缀式ab+cd+/可用表达式__b_来表示。
a．a+b/c+d b．(a+b)/(c+d)c．a+b/(c+d)d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。
a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守___d____＿原则。
a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。
2.已知文法G[E]:E→ET+|T T→TF*|F F→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b)*a(a|b)构造一个确定的有限自动机。
4．设文法G(S)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。
编译原理考试卷A 答案一大题：1. 答：词法分析阶段：读源程序，对字符流进行扫描和分解，识别出一个个单词。
语法分析阶段：将单词分解成各类语法短语。
语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。
中间代码生成阶段：半源程序变成一种内部表示形式。
代码优化阶段：对中间代码进行变换或改造，使生成的目标代码更为高效。
目标代码生成阶段：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。
2. 答：文法是一个四元组（V N ,V T ,P,S ），其中V N 为非终结符号集，V T 为终结符号集，P为产生式集，S 为开始符号。
按乔姆斯基分类，把文法分成四种类型：0型（短语文法）、１型（上下文有关文法）、２型（上下文无关文法）、３型（正规文法）。
3. 答：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。
4. 答：符号表的功能：收集符号属性；上下文语义的合法性检查的依据；作为目标代码生成阶段地址分配的依据。
5. 答：优化就是对代码进行等价变换，使得变换后的代码运行把那间与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。
优化技术有：删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知量与复写传播、删除无用赋值。
二大题：解： EE +TT * F短语：T*F , E+T*F 直接短语：T*F 句柄：T*F 素短语： T*F 三大题： 解：得DFA ＝>院系： 专业班级： 姓名： 学号：装 订 线四大题： 解：Select(S →)={a} select()={b} select()={（}Select(T→S T ′)={a,b,（} select(T′→，ST ′ )={，} select(T′→ε)={）} ∵改写后文法中，相同左部非终结符对应的两条不同产生式的select 集交集均为空 ∴改写后文法是LL （1）文法 （五大题： 解：（1）拓广文法为:(0)A '→A (1)A →aAb (2)A →aA d (3)A→ε 构造LR(0)识别活前缀的DFA ：=>∵在I 0、I 2 项目集中，存在移进归约冲突，故不是LR （0）文法。
一、单选题1、编译程序是一种( )。
A.汇编程序B.目标程序C.翻译程序D.解释程序正确答案：C2、若文法G定义的语言是无限集，则文法必然是( )。
A.二义性的B.上下文无关的C.递归的D.无二义性的正确答案：C3、一个上下文无关文法G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组( )。
A.句子B.单词C.产生式D.句型正确答案：C4、文法G：S →x xS | y 所识别的语言是( )。
A.xxy∗B. xx∗yxC.(xxy)∗D.(xx)∗y正确答案：D5、文法G：S →xS | y 所识别的语言是( )。
A.(xy)∗B.xy∗C.x∗yD. xx∗yx正确答案：C6、在自上而下的语法分析中，应从( )开始分析。
A.句型B.句子C.文法开始符号D.句柄正确答案：C7、语法分析器的输入是（）。
A.符号表B.目标程序C.源程序D.Token序列正确答案：D8、LL（1）分析法中“1”的含义是在输入串中查看一个输入符号，其目的是（）。
A.确定最左推导B.确定是否推导C.确定句柄D.确定使用哪一个产生式进行展开正确答案：D9、同正规式(a|b)∗等价的正规式为( )。
A.a∗|b∗B.(a|b)+C.(ab)∗D.(a∗|b∗)+正确答案：D10、已知文法G[S]:S→A1，A→A1|S0|0，与G等价的正规式是( )。
A.1∗|0∗1B.0(1|10)∗1C.0(0|1)∗D.1(10|01)∗0正确答案：B11、与(a|b)∗(a|b)等价的正规式是( )。
A.a∗|b∗B.(ab)∗(a|b)C.(a|b)(a|b)∗D.(a|b)∗正确答案：C12、如果一个正规式所代表的集合是无穷的，则它必含有的运算是( )。
A.接运算“·”B.或运算“|”C.括号“（”和“）”D.闭包运算“* ”正确答案：D13、在语法分析处理中，FIRST集合、FOLLOW集合均是( )。
一、填空题| (每题4分，共20分)1.乔母斯基定义的3型文法(线性文法)产生式形式A Ba|a,或A aB|a, A, B € Vn, a,b € Vt 。
2.语法分析程序的输入是单词符号，其输出是语法单位。
3型为B .aB的LR(0)项目被称为移进项目，型为B a.B的LR (0) 项目被称为待约项目，4. 在属性文法中文法符号的两种属性分别为继承属性和综合属性。
5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。
二.已知文法G(S)⑴ E T | E+T⑵ T F | F*F⑶ F (E) | i(1)写出句型(T*F+i)的最右推到并画出语法树。
(4分)(2)写出上述句型的短语，直接短语和句柄。
(4分)答：(1)最右推到(2分)E ==> T ==>F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i)(2)语法树(2分)IS/|\7i\E+T(3)(4 分)短语：(T*F+i ) ，T*F+i ，T*F，i直接短语：T*F，i句柄：T*F三.证明文法G(S) : S SaS | £是二义的。
(6分) 答：句子aaa对应的两颗语法树为：因此，文法是二义文法四.给定正规文法G( S):(1) S Sa | Ab |b ⑵A Sa请构造与之等价的DFA ( 6分) 答：对应的NFA 为： (6分)a b {F}① {S} {S}{S,A} ①{S,A} {S,A} {S}五•构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。
(15分) 答：(1)对应的NFA(5分)a b{0}{1 , 3} {0} {1,3} ① {2 , 3} {2,3} {1,3}{2,3}六.已知文法G(S):(1) S A | a | (T)⑵ T T,S | S试：(1)消除文法的左递归；(4分)(2) 构造相应的first 和follow 集合。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。
(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。
(×)3．一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4．语法分析时必须先消除文法中的左递归。
(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
(√)6．逆波兰表示法表示表达式时无须使用括号。
(√ )7．静态数组的存储空间可以在编译时确定。
(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。
(× )10．一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。
A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。
A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。
A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。
黄冈师范学院
2012—2013学年度第一学期期末试卷参考答案
考试课程：编译原理考核类型：考试A卷
考试形式：闭卷出卷教师：牛冀平
考试专业：计算机科学与技术，软件工程
考试班级：计科201001班，软件201001班
一、填空（每空0.5分，共 10分）
1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。
2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。
另外还有表格管理和（出错处理）。
3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。
4、设G是一个给定的文法，S是文法的开始符号，如果S=> x（其中x∈V*），则称x 是文法的一个（句型）。
5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。
6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。
（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可）
7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。
8、表达式（a+b)*c的后缀表达式为（ab+c*）。
9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。
分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找）
10、代码优化的目的是（减少代码的时空开销）。
11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。
12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。
二、选择题（每题1分，共10分）
1、文法的开始符号经多步推导产生的文法符号序列(仅包含终结符)是文法的（D ）。
A.短语
B.句柄
C.句型
D.句子
2、构造编译程序应掌握（D）。
A.源程序
B.目标语言
C.编译方法
D.以上三项都是
3、不属于循环优化的主要方法的是（B）。
A.强度削弱
B.删除无用赋值
C.删除归纳变量
D.代码外提
4、使用（A）可以定义一个程序的含义。
A.语义规则
B.词法规则
C.产生规则
D.左结合规则
5、优化可生成（D）的目标代码。
A．运行时间较短 B．占用存储空间较小
C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小
6、有文法G：E→E*T|T， T→T+i|i ,则输入串1+2*8+6按该文法G归约,其值为（B）。
A.23
B.42
C.30
D.17
7、编译技术中描述单词符号的形成规则的常用工具有（D）。
A．正规文法 B．正规式 C．有穷自动机 D．以上都是
8、编译技术中常用（ B ）描述程序语言的语法。
A．正规文法 B．上下文无法文法 C．属性文法 D．上下文有关文法
9、词法分析器的输出结果是( C )。
A．单词的种别编码 B．单词在符号表中的位置
C．单词的种别编码和自身值 D．单词自身值
10、以下( B )不是DFA的组成部分。
A．有穷字母表 B．初始状态集合 C．终止状态集合D．有限状态集合
三、简答题（每题10分，共50分）
1、有文法G[S]：S→SA|A A→a|b 写出句子aba的最左推导和最右推导。
解：句子aba的最左推导为：S=>SA=>SAA=>AAA=>aAA=>abA=>aba （5分）句子aba的最右推导为：S=>SA=>Sa=>SAa=>Sba=>Aba=>aba （5分）
2、一正规表达式为：b（b|a）| a（b|a（b|a）），写出上述正规式对应的DFA和状态装换矩阵。
解答：正规式对应的DFA为：（5分）
状态矩阵为： （5分）
状态\字符
a b X 1 3 1 2 Y 2 Y Y 3 Y Y Y
-
-
3、设G[E]: E->T|E+T|E-T, T->F|T*F|T/F , F->(E)|i 证明E+T*i*i+i 是该文法的句型
解答：
E => E+T => E+T+T => E+T*F+T => E+T*F*F+T => E+T*i*F+T => E+T*i*i+T => E+T*i*i+
F => E+T*F*i+i （5分） 或E => E+T => E+F => E+i =>E+T+i=> E+T*F+i => E+T*i+i => E+T*F*i+i => E+T*i*i+i （5分） 即，E=>* E+T*i*i+i ，所以是该文法的句型。
4、下面的文法是否是左递归的？如果是，该如何消除？ E →E+T|T T →T*F|F F →(E)|id
解答：E T 存在左递归， 可以用以下等价文法消除左递归
E →TE ’ （2分）
Y
X 1
2
3 a a
a b
b b b
a
DFA
E’→+TE’|ε（2分）
T→FT’（2分）
T’→*FT’|ε（2分）
F→(E)|id （2分）
5、设有文法G[S]：S→S/S|S-S|(S)|a，该文法是否有二义性？为什么？
解答：有.
该文法存在句子: a/a-a。
（5分）
该句子存在两颗不同的语法树，如图：（5分）
四、解答题（共30分）
1、对于下面的程序：
Program main
procedure p(x,y,z)
begin
y:=y+1;
z:=z+x;
end;
begin
a:=2; b:=3;
p(a+b,a,a);
write(a);
end.
请分别按照（1）传值(call by value)（2）传地址(call by reference) （3）传名（call by
name）(4)传结果(call by result)的参数传递方式给出程序执行时的输出结果。
解：（1）传名（call by name）输出结果为：2 （5分）（2）传地址(call by reference) 输出结果为：8 （5分）
（3）传值(call by value) 输出结果为：9 （5分）
(4) 传结果(call by result) 输出结果为：7 （5分）
2、对于文法G(S):
S-->bMb
M-->（L|a
L-->Ma)
1. 写出句型b(Ma)b的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语和句柄。
答：
1. (5分)
b
Ma
b
Lb
b
bMb
S)
(
(⇒
⇒
⇒
2. (5分)
短语: Ma)，(Ma)，b(Ma)b
直接短语: Ma)
句柄: Ma)
S
b M
( T
M a
b
L
)。
