下载文档原格式
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
编译原理期末考试试题及答案一、选择题（每题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. 静态作用域规则是指变量的作用域在编译时确定，而动态作用域规则是指变量的作用域在运行时确定。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
一． 填空题（每空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中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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. 请简要解释编译原理的定义和作用。
编译原理是研究将高级语言源程序转化为等价的目标程序的一门学科。
它的主要作用是将高级语言的源代码翻译为计算机能够执行的目标代码，从而实现程序的运行。
2. 请列举并解释编译过程的各个阶段。
- 词法分析：将源代码划分为一个个词法单元，如变量、关键字等。
- 语法分析：根据语法规则，将词法单元组合为语法树，检查语法结构是否正确。
- 语义分析：对语法树进行语义检查，如类型匹配、作用域等。
- 中间代码生成：将语法树转化为中间代码表示形式，方便后续优化。
- 代码优化：对中间代码进行优化，提高程序执行效率。
- 目标代码生成：将优化后的中间代码转化为目标机器代码。
3. 请解释符号表在编译过程中的作用。
符号表是编译器在编译过程中用来管理变量、函数、类型等标识符的数据结构。
它的主要作用是记录标识符的相应属性，如类型、作用域等，以便在后续的语法、语义分析以及代码生成过程中进行查找、检查等操作。
4. 请简要解释LL(1)文法的定义和特点。
LL(1)文法是一种上下文无关文法，它具有以下特点：- 对于给定的非终结符，它的产生式右部的首符号不相同。
- 对于给定的产生式右部的首符号，它的产生式右部不相同。
- 通过向前查看一个符号，就能确定所选用的产生式。
5. 请简要解释词法分析器的作用和实现方式。
词法分析器的主要作用是将源代码分解为一个个词法单元，如变量名、关键字等。
它的实现方式一般采用有限自动机，通过定义正则表达式描述各个词法单元的模式，然后根据模式匹配的结果生成相应的词法单元。
答案仅为参考，请以实际考试为准。
第八节习题一、单项选择题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．目标代码生成解答1．b、c 2. a、b、c、e三、填空题1、解释程序和编译程序的区别在于。
编译原理期末试题及答案一、选择题（每题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. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。
第八节习题一、单项选择题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．目标代码生成解答1．b、c 2. a、b、c、e三、填空题1、解释程序和编译程序的区别在于。
<编译原理>历年试题及答案一．（每项选择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)构造预测分析表。
一、填空题（每空2分，共20分）1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。
2．编译器常用的语法分析方法有自底向上和自顶向下两种。
3．通常把编译过程分为分析前端与综合后端两大阶段。
词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。
4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。
5．对编译程序而言，输入数据是源程序，输出结果是目标程序。
1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。
2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。
4．一个LL（1）分析程序需要用到一张分析表和符号栈。
5．后缀式abc-/所代表的表达式是a/(b-c)。
二、单项选择题（每小题2分，共20分）1．词法分析器的输出结果是__C。
A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值2．正规式 M 1 和 M 2 等价是指__C_。
A． M1和M2的状态数相等B． M1和M2的有向边条数相等C． M1和M2所识别的语言集相等 D． M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_C____。
A． xyx B． (xyx)* C．xnyxn(n≥0) D． x*yx*4．如果文法G是无二义的，则它的任何句子α_A____。
A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。
A．源程序B．目标语言 C．编译方法 D．以上三项都是6．四元式之间的联系是通过__B___实现的。
A．指示器B．临时变量C．符号表 D．程序变量7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。
A．┐AB∨∧CD∨B．A┐B∨CD∨∧C． AB∨┐CD∨∧ D．A┐B∨∧CD∨8. 优化可生成__D___的目标代码。
A．运行时间较短B．占用存储空间较小C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小9．下列___C___优化方法不是针对循环优化进行的。
A. 强度削弱 B．删除归纳变量C．删除多余运算 D．代码外提10．编译程序使用_B_区别标识符的作用域。
A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次C．说明标识符的过程或函数的动态层次 D. 标识符的行号三、判断题（对的打√，错的打×，每小题1分，共10分）2．一个有限状态自动机中，有且仅有一个唯一的终态。
x3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。
X4．语法分析时必须先消除文法中的左递归。
X6．逆波兰表示法表示表达式时无须使用括号。
R9．两个正规集相等的必要条件是他们对应的正规式等价。
X1．编译程序是对高级语言程序的编译执行。
X2．一个有限状态自动机中，有且仅有一个唯一的初始态。
R3．一个算符优先文法的每个非终结符号间都不存在优先关系。
R4．LL（1）语法分析时必须先消除文法中的左递归。
R5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
R6．逆波兰表示法表示表达式时根据表达式会使用括号。
X7．静态数组的存储空间可以在编译时确定。
X8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
X9．两个正规集相等的必要条件是他们产生的符号串是相同的。
R10．一个语义子程序描述了一个文法所对应的翻译工作。
X1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？S-属性文法是只含有综合属性的属性文法。
（2分）L-属性文法要求对于每个产生式A X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1,X2…Xj-1的属性；（2）A的继承属性。
（2分）S-属性文法是L-属性文法的特例。
（１分）２．什么是LＬ（１）分析器２．什么是LＲ（０）分析器所谓LR(０)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。
五、综合题（共40分）1．（10分）对于文法 G[S] ：S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB⑴ (3 分 ) 请写出三个关于 G[S] 的句子；⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。
⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。
答：（1）三个 0 和 1 数量相等的串（每个1分）（2） S => 1A => 11AA => 11A 0S（3）2.（10分）设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。
⑵３分）试写出描述 L 的正规表达式；⑵（７分）构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NFA 、 DFA 的状态转换图，以及最小DFA的状态转换图 ) 。
答：（ 1 ）（３分）正规表达式： 1(0|1) * 00（ 2 ）（７分）第一步（３分）：将正规表达式转换为 NFA第二步（２分）：将 NFA 确定化为 DFA ：（１分）状态输入I 0 I 1 t 0 1[S] —[A,D,B] q 0 —q 1[A,D,B] [D,B,C] [D,B] 重新命名q 1 q 2 q 3[D,B,C] [D,B,C,Z] [D,B] q 2 q 4 q 3[D,B] [D,B,C] [D,B] q 3 q 2 q 3[D,B,C,Z] [D,B,C,Z] [D,B] q 4 q 4 q 3DFA 的状态转换图（１分）第三步（２分）：将DFA 最小化：（１分）将状态划分终态与非终态两个集合：Ａ＝｛ｑ０，ｑ１，ｑ２，ｑ３｝，Ｅ＝｛ｑ４｝根据Ａ、Ｅ集合的情况，对Ａ集合进行划分状态输入I 0 I 1ｑ０—Ａｑ１ＡＡｑ２ＥＡｑ３ＡＡ将状态集Ａ划分为两个集合：Ａ＝｛ｑ０，ｑ１，ｑ３｝，Ｂ＝｛２｝根据Ａ、Ｂ集合的情况，对Ａ集合进行划分状态输入I 0 I 1ｑ０—Ａｑ１ＢＡｑ３ＢＡ将状态集Ａ划分为两个集合：Ａ＝｛ｑ０｝，Ｃ＝｛ｑ１，ｑ３｝根据Ａ、Ｃ集合的情况，对Ｃ集合进行划分状态输入I 0 I 1ｑ１ＢＡｑ３ＢＡ最小DFA 的状态转换图（１分）３．（20分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是 LL(1) 文法吗？（要求给出详细过程，如果是LL（1），给出分析表）答：（1）该文法不是LL（1）文法，因为有左递归，消除左递归可获得一个LL（1）文法（2分）（2）消除左递归，得新文法 (3分)E → TE’E’→ +TE’| εT → FT’T’→ *FT’ |εF → (E) | i(3)求产生式右部的First集分)First(TE’) = First(T)= First(F)={(,i}First(+TE’) = {+}First(FT’) = First(F)={(,i}First(*FT’) = {*}First((E)) = {(}First(i) = {i}（4）求所有非终结符的Follow集分)Follow(E) = {$,)}Follow(E’) = Follow(E) = {$,)}Follow(T) = First(E’)∪Follow(E)={+} ∪{$,)}={$,+,)}Follow(T’) = Follow(T) ={$,*,)}Follow(F) = First(T ’)∪Follow(T) ∪Follow(T ’)= {$,*,)} （5） 求所有产生式的Select 集 分)Select （E → TE ’）=First(TE ’)= {(,i} Select （E ’→ +TE ’）=First(+TE ’)= {+} Select （E ’→ ε）= Follow(E ’) = {$,)} Select （T → FT ’）=First(FT ’)= {(,i} Select （T ’ → *FT ’）=First(*FT ’)= {*}Select （T ’→ ε）= Follow(T ’) ={$,+,)} Select （F → (E)）=First((E))= {(} Select （F → i ）=First(i)= {i} （6）对相同左部的所有Select 即求交集分) Select （E ’→ +TE ’）∩Select （E ’→ ε）= Φ Select （T ’ → *FT ’）∩Select （T ’→ ε）=Φ Select （F → (E)）∩Select （F → i ）=Φ 所以，改造后的文法是LL （1）文法，其分析表如下 （7） LL(1) 分析表（ 5 分）V NV T+ * i ( ) $E E → TE ’ E → TE ’ E ’ E ’→ +TE ’ E ’→ ε E ’→ ε T T → FT ’ T → FT ’ T ’ T ’→ ε T ’ → *FT ’ T ’→ ε T ’→ εF F → (E) F → i 1．（10分）对于文法G ：S aSbS|aS|d证明该文法是二义性文法。
答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。
（5分） 句子aadbd 有两棵语法树（5分，划一棵树给3分）。
如下图：（６分） (1) (2)由此可知，S aSbS|aS|d 定义的文法是二义性文法。
３．（20分）给定一个简单的算术表达式文法 G[E] ： E → E+T | T T → T*F | F F → (E) | iSSabSS adSaSS abS dd该文法是 SLR(1) 文法吗？（要求给出详细过程，如果是SLR文法，给出分析表）答：(1) 该文法的拓广文法是： (2分)E’→E （1）E → E+T （2）E → T （3）T → T*F （4）T → F （5）F → (E) （6）F → i （7）（2）相应的LR（0）的DFA：（10分）（3）冲突与解决 (3分）① I1状态中有移进—规约冲突Follow(E’)={ $ } 不含{ + }可解决移进—规约冲突② I2状态中有移进—规约冲突Follow(E)={ +，），$ } 不含{ * }可解决移进—规约冲突③ I8状态中有移进—规约冲突Follow(E)={ +，），$ } 不含{ * }可解决移进—规约冲突(4) SLR分析表 (5分)ACTION GOTO+*i（）$E T F0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、单项选择题（每小题2分，共20分）1．语言是____C_A．终结符与非终结符的符号串的集合 B．非终结符符号串的集合 C．终结符符号串的集合 D．产生式的集合2．编译程序分两阶段工作，前阶段完成的工作是__C___A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化3．一个句型中称为句柄的是该句型的最左CA．句型 B．短语 C．直接短语 D．最左直接短语4．自动机识别的语言是 DA．0型语言 B．1型语言 C．2型语言 D．3型语言5．自动机所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 BA．字符 B．单词 C．句子 D．句型6．对应Chomsky四种文法的四种语言之间的关系是BA．L0L1L2L3 B．L3L2L1L0 C．L3=L2L1L0 D．L0L1L2=L37．词法分析的任务是AA．识别单词 B．分析句子的含义 C．识别句子 D．生成目标代码8．常用的中间代码形式不含DA．三元式 B．四元式 C．逆波兰式 D．语法树9．代码优化的目的是CA．节省时间 B．节省空间 C．节省时间和空间 D．把编译程序进行等价交换10．代码生成阶段的主要任务是CA．把高级语言翻译成汇编语言 B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言。
