西安交通大学《编译原理》第十一章 期末考试拓展学习 3

编译原理期末考试试题及答案一、选择题（每题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. 静态作用域规则是指变量的作用域在编译时确定，而动态作用域规则是指变量的作用域在运行时确定。

编译原理第六章到第十一章课后习题答案p116/1.已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 计算FIRSTVT -- LASTVT表(2) 构造算符优先关系表（OPERATER PRIORITY RELATION TABLE），说明是否为算符优先文法。

=: #=#, (=)<: (< FIRSTVT(T) , ,<firstvt(s)<="" ,="" p="">>:LASTVT(S)># , LASTVT(T)>), LASTVT(T)> ,表中无多重人口所以是算符优先（OPG）文法。

（3）计算G[S]的优先函数。

收敛（4）对输入串（a,a）#的算符优先分析过程为Success!3.有文法G（S）：s->Vv->T/ViTT->F/T+FF->)V*|((1)(+(i(的规范推导S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)F+Fi（的短语、句柄、素短语。

短语S: F+Fi（T1:F+F （素短语）T2:F （句柄）F:( （素短语）(3) G(S)是否为OPG？若是，给出（1）中句子的分析过程！S’->#S# S->V V->T/ViT T->F/T+F F->)V*|(算符优先关系表（OPERATER PRIORITY RELATION TABLE）对输入串(+(I(的算符优先分析过程为:p152/2文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→SI3若产生式排序为：0 S' →S1 S →L.L2 S →L3 L →LB4 L →B5 B →06 B →1由产生式知：First (S' ) = {0,1}First (S ) = {0,1}First (L ) = {0,1}First (B ) = {0,1}Follow(S' ) = {#}Follow(S ) = {#}Follow(L ) = {.,0,1,#}Follow(B ) = {.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：I5B →.0和B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。

(6分)解：G[S]：S—>ABA—>aAb |εB—>aBb |ε2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。

解：G[S]：S—>1S0 | AA—>0A1 |ε3.P48 第6题（5）、（6）.画语法树6、已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i（５）i+(i+i) （６）i+i*i解：(5)语法树：（6）语法树：4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：a ε bP102例题6.1及其分析.( 后加画语法树)例6.1 设文法G[S]为：(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。

步骤符号栈输入符号串动作（1）# abbcde# 移进（2）#a bbcde# 移进（3）#ab bcde# 归约（A—>b）（4）#aA bcde#移进（5）#aAb cde# 归约（A—>Ab）（6）#aA cde# 移进（7）#aAc de# 移进（8）#aAcd e# 归约（B—>d）（9）#aAcB e# 移进（10）#aAcBe # 归约（S—>aAcBe）（11）#S # 接受一、计算分析题（60%）1、正规式→ NFA→ DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0|1)*101解：先构造NFA0 1S AA A ABAB AC ABAC A ABZABZ AC AB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以0 1S AA A BB C BC A DD C B(4) b((ab)*|bb)*ab解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：a b0 01 101 01 11 0、{1}，其中A为初态，A，B为终态，因此有：a bA B CB B CC A最小化：：初始分划得终态组{A,B}，非终态组{C}Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。

《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。

西交《编译原理》第三章自上而下语法分析一、自上而下分析方法的原理自顶向下语法分析方法(即推导法)就是从文法开始符S出发，逐步进行推导，以证实Sα的推导过程是否存在的方法S→二、文法G：xAyA→aab若输入串为xay，其分析过程为：①先建立根结点，输入串的指针指向x； S②由于S产生式只有一个，从S构造如图推导树的待匹配为x，输入串指针为x匹配， x A y指针下移，推导树待匹配为A。

S③ A有两个产生式，选用第一个得树如图，此时匹配结点为a，匹配成功，指针为y， x A y 推导树待匹配为b。

a b④谋求第三次匹配时不成功，证明上一步选择的产生式不适合，故注销A子树，指针回到第二次匹配前，即上一步之前状态。

S⑤选A的第二产生式如图，这时第二次匹配成功，指针后移。

⑥第三次匹配成功，且输入串结束，推导树待匹配结点结束， x A y分析结束，故xay是合法的句子。

该例中第④步的过程就称为回溯，此时生成的子树要注销，以匹配的指针要回避，以便选取其他候选产生式另作试探，这样势必影响到分析效率，而且实现分析的过程也将复杂化。

事实上，若在对候选产生式的选择时，若能针对输入串指针的终结符，可以有选择的进行，如：qBpASG→:acAdA→bdBB→对输入串pccadd Sp Ac A da又如：BqApS→acAA→bdBB→对于输入串ccap SA pc Ac Aa由此可见，分析回溯的原因：① 候选产生式有公有的左因子。

21αβαβ→A当输入串待匹配的前缀可以与α匹配时，很难选择。

若没有公有左因子，那么只要选择推导出的首字符能与输入串匹配的那个候选式即可。

② 左递归文法产生式存在将导致分析陷入困境。

αA A →。

第 0 页共 16 页一．填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。

2. 规范规约是最（3）规约。

3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。

另外还有（6）和出错处理。

4．表达式x+y*z/(a+b)的后缀式为（7）。

5．文法符号的属性有综合属性和（8）。

6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。

7．局部优化是局限于一个（10）范围内的一种优化。

二．选择题（1-6为单选题，7-8为多选题，每问2分，共20分）1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（），以及一组（）。

A ．字符串B ．产生式C ．开始符号D ．文法2.程序的基本块是指（）。

A ．一个子程序B ．一个仅有一个入口和一个出口的语句C ．一个没有嵌套的程序段D ．一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。

A ．自左向右 B ．自顶向下 C ．自底向上 D ．自右向左 4．在通常的语法分析方法中，（）特别适用于表达式的分析。

A ．算符优先分析法 B ． LR 分析法 C ．递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（）。

A ．四元式序列B ．间接三元式序列C ．二元式序列D ．机器语言程序或汇编语言程序 6．一个文法所描述的语言是（）；描述一个语言的文法是（）。

A ．唯一的 B ．不唯一的 C ．可能唯一，也可能不唯一7．如果在文法G 中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。

编译原理期末考试题(含答案)1. 请简要解释编译原理的定义和作用。

编译原理是研究将高级语言源程序转化为等价的目标程序的一门学科。

它的主要作用是将高级语言的源代码翻译为计算机能够执行的目标代码，从而实现程序的运行。

2. 请列举并解释编译过程的各个阶段。

- 词法分析：将源代码划分为一个个词法单元，如变量、关键字等。

- 语法分析：根据语法规则，将词法单元组合为语法树，检查语法结构是否正确。

- 语义分析：对语法树进行语义检查，如类型匹配、作用域等。

- 中间代码生成：将语法树转化为中间代码表示形式，方便后续优化。

- 代码优化：对中间代码进行优化，提高程序执行效率。

- 目标代码生成：将优化后的中间代码转化为目标机器代码。

3. 请解释符号表在编译过程中的作用。

符号表是编译器在编译过程中用来管理变量、函数、类型等标识符的数据结构。

它的主要作用是记录标识符的相应属性，如类型、作用域等，以便在后续的语法、语义分析以及代码生成过程中进行查找、检查等操作。

4. 请简要解释LL(1)文法的定义和特点。

LL(1)文法是一种上下文无关文法，它具有以下特点：- 对于给定的非终结符，它的产生式右部的首符号不相同。

- 对于给定的产生式右部的首符号，它的产生式右部不相同。

- 通过向前查看一个符号，就能确定所选用的产生式。

5. 请简要解释词法分析器的作用和实现方式。

词法分析器的主要作用是将源代码分解为一个个词法单元，如变量名、关键字等。

它的实现方式一般采用有限自动机，通过定义正则表达式描述各个词法单元的模式，然后根据模式匹配的结果生成相应的词法单元。

答案仅为参考，请以实际考试为准。

编译原理期末试题(含答案+大题集+重要知识点)《编译原理》期末试题一、是非题 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所识别的语言是_____。

第1页共6页A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。

西交《编译原理》在线作业试卷总分:100 得分:100一、单选题 (共 30 道试题,共 60 分)1. 许多广为使用的语言，如Fortran、C、Pascal等，属于（）。

A. 强制式语言B. 应用式语言C. 基于规则的语言D. 面向对象的语言答案:A2.在编译方法中，动态存储分配的含义是( )。

A. 在运行阶段对源程序中的数组.变量.参数等进行分配B. 在编译阶段对源程序中的数组.变量.参数进行分配C. 在编译阶段对源程序中的数组.变量.参数等进行分配，在运行时这些数组.变量.参数的地址可根据需要改变D. 其他都不正确答案:A3.现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程序。

A. 重定位程序；B. 解释程序；C. 连接装配程序；D. 诊断程序；答案:C4.语法分析应遵循（）。

A. 语义规则B. 语法规则C. 构词规则D. 等价变换规则答案:C5.（）是指源程序中不符合语法或词法规则的错误，这些错误一般在词法分析或语法分析时能检测出来。

A. 语义错误B. 语法错误C. 短语错误D. 短句错误答案:B6.在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分( )错误。

A. 语法B. 语义C. 语用D. 运行答案:A7.下列关于标识符和名字叙述中，正确的是( )。

A. 标识符有一定的含义B. 名字是一个没有意义的字符序列C. 名字有确切的属性D. 都不正确答案:C8.编译程序是一种( )A. 汇编程序B. 翻译程序C. 解释程序D. 目标程序答案:B9.代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个（）把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程序。

编译原理试题计算机学院2001级班学号姓名一选择题（12分）【】1．词法分析器的输入是。

A．符号串B．源程序C．语法单位D．目标程序【】2．两个有穷自动机等价是指它们的。

A．状态数相等B．有向弧数相等C．所识别的语言相等D．状态数和有向弧数相等【】3．文法G：S → xSx | y 所识别的语言是。

A．xy*x B．(xyx)* C．xx*yxx* D．x*yx*【】4．设a,b,c为文法的终结符，且有优先关系a≡b和b≡c，则。

A．必有a≡c B．必有c≡aC．必有b≡a D．选项A、B和C都不一定成立【】5．若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的语法分析方法是。

A．ALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法【】6．生成中间代码时所依据的是。

A．语法规则B．词法规则C．语义规则D．等价变换规则【】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为。

A．┐ab∨∧cd∨B．a┐b∨cd∨∧C．ab∨┐cd∨∧D．a┐b∨∧cd∨【】8．基本块。

A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句C．有多个入口语句和一个出口语句D．有多个入口语句和多个出口语句二判断题（6分。

认为正确的填“T”，错的填“F”）【T】1．同心集的合并有可能产生“归约/归约”冲突。

【T】2．一个文法所有句子的集合构成该文法定义的语言。

【】3．非终结符可以有综合属性，但不能有继承属性。

【T】4．逆波兰表示法表示表达式时无需使用括号。

【】5．一个有穷自动机有且只有一个终态。

【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。

三填空题（8分）1．最常用的两类语法分析方法是自顶向下和自低向上分析法。

2．对于文法G[E]：E→T|E+T T→F|T*F F→P↑F|P P→(E)|i,句型T+T*F+i 的直接短语为，句柄为。

西交《编译原理》第二章词法分析C# 语言规范输入产生式定义 C# 源文件的词法结构。

C# 程序中的每个源文件都必须符合此词法文法产生式。

input:（输入：）input-sectionopt（输入节可选）input-section:（输入节：）input-section-part（输入节部分）input-section input-section-part（输入节输入节部分）input-section-part:（输入节部分：）input-elementsopt new-line（输入元素可选新行）pp-directive（pp 指令）input-elements:（输入元素：）input-element（输入元素）input-elements input-element（输入元素输入元素）input-element:（输入元素：）whitespace（空白）comment（注释）token（标记）C# 源文件的词法结构由五个基本元素组成：行结束符、空白、注释、标记和预处理指令。

在这些基本元素中，只有标记在 C# 程序的句法文法中具有重要意义。

对C# 源文件的词法处理就是将文件缩减成标记序列，该序列然后即成为句法分析的输入。

行结束符、空白和注释可用于分隔标记，预处理指令可导致跳过源文件中的某些节，除此之外这些词法元素对 C# 程序的句法结构没有任何影响。

当有若干词法文法产生式与源文件中的一个字符序列匹配时，词法处理总是构成尽可能最长的词法元素。

例如，字符序列 // 按单行注释的开头处理，这是因为该词法元素比一个 / 标记要长。

行结束符行结束符将 C# 源文件的字符划分为行。

new-line:（新行：）回车符 (U+000D)换行符 (U+000A)回车符 (U+000D) 后跟换行符 (U+000A)行分隔符 (U+2028)段落分隔符 (U+2029)为了与添加文件尾标记的源代码编辑工具兼容，并能够以正确结束的行序列的形式查看源文件，下列转换按顺序应用到 C# 程序中的每个源文件：如果源文件的最后一个字符为 Control-Z 字符 (U+001A)，则删除此字符。

一、填空题|（每题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)(1) E → T | E+T(2) T → F | F*F(3) 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分）（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(2) 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}（5分）六. 已知文法G(S) :(1) S → ^ | a | (T)(2) T → T,S | S试：（1）消除文法的左递归；（4分）（2）构造相应的first 和 follow 集合。

D． 文法
D． 自右向左
C． 该句子有两个不同的最右推导 D． 该句子有两棵不同的语法树
E． 该句子对应的语法树唯一
8． 下面（ ）语法制导翻译中，采用拉链—回填技术。
A. 赋值语句 B. 布尔表达式的计算 C. 条件语句
得分
三． 解答题（共 60 分）
1． （共 15 分）已知文法 G[E]:
E→ETE|（E）|i
④ bc10
D．①②③④
D． 自右向左
D. ④②
(4) 语法分析
(5) 目标代码生成
(6) 表格管理
(7) xyz*ab+/+
(8) 继承属性
(9) a+(i-1)*20+j-1
(10) 基本块 一、选择题（每问 2 分，共 20 分） 1.C B 2.D 3.B 4.A 5.D 6.A,C
7.BCD,选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止。
得 二． 选择题（1-6 为单选题，7-8 为多选题，每问 2 分，共 20 分）
分
1. 一个上下文无关文法 G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一
组（ ）。
A． 字符串
2.程序的基本块是指（ ）。
A． 一个子程序
B． 产生式
C． 开始符号
B． 一个仅有一个入口和一个出口的语句
得分
一． 填空题（每空 2 分，共 20 分）
1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种： 静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。
2. 规范规约是最（3）规约。
3. 编译程序的工作过程一般划分为 5 个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式 x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组 a[1..15,1..20]某个元素 a[i，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。

1、试为表达式 w+（a+b)＊（c+d/(e-10）+8) 写出相应的逆波兰表示。

2、写出表达式a＋b＊(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=（b+c)＊e+(b+c)/f的逆波兰式和三元序列。

4、已知文法G(S)及相应翻译方案S→aAb ｛print “1”}S→a {print “2”｝A→AS {print “3”｝A→c ｛print “4"｝输入acab, 输出是什么？5、已知文法G（S)S→bAaA→(B | aB→A a)写出句子b（aa）b的规范归约过程.6、已知文法G［S］S→S*aF | aF ｜＊aFF→+aF | +a消除文法左递归。

1、设文法G（S）：S→^ ｜ a | （T）T→T,S ｜ S⑴ 消除左递归;⑵ 构造相应的FIRST和FOLLOW集合;⑶ 构造预测分析表2.语句 if E then S(1）改写文法，使之适合语法制导翻译；（2）写出改写后产生式的语义动作。

4。

设某语言的for语句的形式为for i：＝E（1) to E（2) do S其语义解释为i：＝E(1）LIMIT:＝E（2）again: if i＜＝LIMIT thenBeginS；i：＝i＋1goto againEnd；（1）写出适合语法制导翻译的产生式;（2)写出每个产生式对应的语义动作。

7。

已知文法G(S)S→a ｜ ^ | （T）T→T，S ｜ S（1) 给出句子(a，（a,a))的最左推导;（2) 给出句型（(T,S），a）的短语, 直接短语，句柄。

8。

对于 C 语言do S while E语句(1）改写文法，使之适合语法制导翻译;(2）写出改写后产生式的语义动作.9。

已知文法G(S）S→aAcBeA→Ab｜ bB→d（1)给出句子abbcde的最左推导及画出语法树；（2）给出句型aAbcde的短语、素短语。

10。

设文法G（S）:S→（T) | aS | aT→T,S ｜ S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。

西安交通大学智慧树知到“计算机科学与技术”《编译原理》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共15题)1.复写传播的目的是对某些变量的赋值变为无用。

()A.对B.错2.程序语言的单词符号一般可以分为5种，下面()不需要超前搜索。

A.关键字B.标识符C.常数D.算符和界符3.中间代码是独立于机器的，复杂性介于源语言和机器语言之间，便于进行与机器无关的代码优化工作。

()A.对B.错4.在运行空间的划分中有一个单独的区域叫堆，用来存放()。

A.目标代码B.静态数据C.动态数据D.过程参数5.非终结符只有综合属性，由词法分析器提供。

()A.对B.错6.Chomsky把文法分成四种类型，其中，()也称正规文法。

A.0型B.1型C.2型D.3型7.从左线性文法构造有限自动机时，通常自动机状态个数比文法非终结符号数多()A.4B.2C.0D.18.若一个程序语言的任何变量的存储空间大小和相互位置都能在编译时确定，则可采用静态分配策略。

()A.对B.错9.有文法G=({S}，{a}，{S→SaS，S→ε}，S)，该文法是()。

A.LL(1)文法B.二义性文法C.算符优先文法D.SLR(1)文法10.在编译过程中，既可以将几个不同的阶段合为一遍，也可以把一个阶段的工作分为若干遍。

()A.对B.错11.上下文无关文法可以用()来描述。

A.正则表达式B.正规文法C.扩展的BNFD.翻译模式12.Fortran语言的编译程序采用()分配策略。

A.静态B.最佳C.堆式动态D.栈式动态13.为了便于优化处理，三地址代码可以表示成()。

A.三元式B.四元式C.后缀式D.间接三元式14.自上而下分析面临的四个问题中，不包括()。

A.需消除左递归B.存在回朔C.虚假匹配D.寻找可归约串15.一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。

()A.对B.错第2卷一.综合考核(共15题)1.一个数据类型通常包括三种要素，下面()不是A.用于区别这种类型的数据对象的属性B.这种类型的数据对象可以具有的值C.对这种类型的数据对象的内存分配D.可以作用于这种类型的数据对象的操作2.一个二义性文法可以是SLR文法或LALR文法。