下载文档原格式
编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 程序设计B. 程序翻译C. 程序调试D. 数据处理答案：B2. 下列哪一项不是编译器的前端处理过程？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，词法分析器的主要作用是什么？A. 识别程序中的关键字和标识符B. 将源代码转换为中间代码C. 检查程序的语法结构D. 确定程序的运行环境答案：A4. 语法分析通常采用哪种方法？A. 自顶向下分析B. 自底向上分析C. 正则表达式匹配D. 直接解释执行答案：B5. 语义分析的主要任务是什么？A. 检查程序的语法结构B. 检查程序的类型安全C. 识别程序中的变量和常量D. 将源代码转换为机器代码答案：B二、简答题1. 简述编译器的工作原理。
答案：编译器的工作原理主要包括以下几个步骤：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。
词法分析器将源代码分解成一系列的词素；语法分析器根据语法规则检查词素序列是否合法；语义分析器检查程序的语义正确性；中间代码生成器将源代码转换为中间代码；代码优化器对中间代码进行优化；最后，目标代码生成器将优化后的中间代码转换为目标机器代码。
2. 什么是词法分析器，它在编译过程中的作用是什么？答案：词法分析器是编译器前端的一个组成部分，负责将源代码分解成一个个的词素（tokens），如关键字、标识符、常量、运算符等。
它在编译过程中的作用是为语法分析器提供输入，是编译过程的基础。
三、论述题1. 论述编译器中的代码优化技术及其重要性。
答案：代码优化是编译过程中的一个重要环节，它旨在提高程序的执行效率，减少资源消耗。
常见的代码优化技术包括：常量折叠、死代码消除、公共子表达式消除、循环不变代码外提、数组边界检查消除等。
代码优化的重要性在于，它可以显著提高程序的运行速度和性能，同时降低程序对内存和处理器资源的需求。
四、计算题1. 给定一个简单的四则运算表达式，请写出其对应的逆波兰表达式。
编译原理考试题一、选择题。
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.将目标代码转换成中间代码。
二、填空题。
1. 词法分析的输出是（）。
2. 语法分析的输出是（）。
3. 语义分析的输出是（）。
4. 目标代码生成的输入是（）。
5. 目标代码生成的输出是（）。
三、简答题。
1. 请简要说明编译过程中词法分析的作用和实现方法。
2. 请简要说明编译过程中语法分析的作用和常用的语法分析方法。
3. 请简要说明编译过程中语义分析的作用和常见的语义分析任务。
4. 请简要说明编译过程中目标代码生成的作用和常用的目标代码生成方法。
5. 请简要说明编译过程中优化的作用和常见的优化方法。
四、分析题。
1. 请分析词法分析器的设计和实现方法，并给出一个具体的例子。
2. 请分析语法分析器的设计和实现方法，并给出一个具体的例子。
3. 请分析语义分析器的设计和实现方法，并给出一个具体的例子。
4. 请分析目标代码生成器的设计和实现方法，并给出一个具体的例子。
5. 请分析编译器优化的方法和实现过程，并给出一个具体的例子。
五、综合题。
1. 请设计一个简单的编译器，包括词法分析器、语法分析器、语义分析器和目标代码生成器，并给出相应的实现代码。
2. 请分析该编译器的设计思路和实现方法，并说明其优缺点。
编译原理复习题及答案一、选择题1．一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2．文法G[A]：A→εA→aB B→Ab B→a是(A)A 正规文法B 二型文法3．下面说法正确的是(A)A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A 必要条件B 充分必要条件5．下面说法正确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A)A 归约速度快B 对文法限制少7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B)A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A)A Lex是一个词法分析器的生成器B Yacc是一个语法分析器9．下面说法正确的是(A)A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。
A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．(A)是一种典型的解释型语言。
A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。
A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。
A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。
A．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。
编译原理考试试卷一、选择题（每题2分，共20分）1. 编译器的主要功能是将源代码转换成目标代码，以下哪个不是编译器的基本组成部分？A. 词法分析器B. 语法分析器C. 代码优化器D. 运行时环境2. 词法分析器通常不负责以下哪项任务？A. 识别关键字B. 识别标识符C. 进行语义分析D. 去除空白字符3. 语法分析中，递归下降分析是一种：A. 确定性分析方法B. 非确定性分析方法C. 基于语法制导的分析方法D. 基于语法树的分析方法4. LR分析器是用于处理：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. 所有选项都是二、简答题（每题10分，共30分）1. 简述编译原理中词法分析器的作用及其实现方式。
2. 描述语法分析中自顶向下分析和自底向上分析的区别。
3. 解释编译优化的重要性，并给出一个优化的例子。
三、计算题（每题25分，共50分）1. 给定一个简单的算术表达式 "3 + 4 * 2 - 1"，请说明如何使用递归下降分析器来解析这个表达式，并给出相应的语法树。
2. 假设你有一个简单的编译器后端，需要将四元式 "(a, b, +, c)" 转换成目标代码。
编译原理考试题及答案汇总一、选择1．将编译程序分成若干个“遍”是为了 _B__。
A . 提高程序的执行效率 B. 使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D. 利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指 __C__。
A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。
C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等3．中间代码生成时所依据的是 _C_。
A.语法规则 B •词法规则 C •语义规则 D •等价变换规则 4.后缀式ab+cd+/可用表达式__B_来表示。
A. a+b/c+d B . (a+b)/(c+d) C a+b/(c+d) D a+b+c/d6． 一个编译程序中，不仅包含词法分析， _A _______ ，中间代码生成，代码优化，生成等五个部分。
A ．( ) 语法分析B ．( ) 文法分析C ．( ) 语言分析D ．( ) 解释分析 7． 词法分析器用于识别 __C___。
A ．( ) 字符串B ．( ) 语句C ．( ) 单词D ．( ) 标识符 8． 语法分析器则可以发现源程序中的 ___D__。
A ．( ) 语义错误B ．( ) 语法和语义错误C ．( ) 错误并校正D ．( ) 语法错误 9． 下面关于解释程序的描述正确的是 __B___。
(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的A ．( ) (1)(2)B ．( ) (1)C ．( ) (1)(2)(3)D ．( ) (2)(3) 10． 解释程序处理语言时 , 大多数采用的是 __B___方法。
A ．( ) 源程序命令被逐个直接解释执行B ．( ) 先将源程序转化为中间代码 , 再解释执行C ．( ) 先将源程序解释转化为目标程序 , 再执行D ．( ) 以上方法都可以11． 编译过程中 , 语法分析器的任务就是 (1) 分析单词是怎样构成的 (2) (3) 分析语句和说明是如何构成程序的 A ．( ) (2)(3) B ．( ) (2)(3)(4)C ．( ) (1)(2)(3) D ．( ) (1)(2)(3)(4) 12． 编译程序是一种 ___C__。
编译原理考试题
1. 编译器的作用是什么？简述编译器的基本工作流程。
2. 解释什么是词法分析。
描述词法分析器的基本工作原理。
3. 什么是语法分析？描述语法分析器的基本工作原理。
4. 解释语义分析的概念。
语义分析器的基本工作原理是什么？
5. 请简要解释编译器的前端和后端分别是做什么的。
6. 什么是中间代码？为什么编译器要生成中间代码？
7. 解释什么是符号表。
符号表在编译过程中起到什么作用？
8. 简述优化在编译过程中的作用。
列举并解释两种常见的优化技术。
9. 解释静态链接和动态链接的区别。
10. 请解释解释器和编译器之间的区别。
描述它们各自的工作
原理。
11. 解释冲突解析算法中的"移进-归约"冲突和"归约-归约"冲突。
12. 简述LL(1)文法和LR(1)文法的特点及区别。
13. 解释编程语言中的数据类型检查和类型推导的概念。
14. 简要描述语法制导翻译的概念和基本原理。
15. 请解释正则表达式和有限自动机之间的关系。
注意：以上为编译原理考试相关的问题，文中不含有标题相同的文字。
<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题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．正规式MI和M2等价是指____。
a. MI和M2的状态数相等b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—。
a．语法规则 b．词法规则 c．语义规则 d．等价变换规则8．后缀式ab+cd+/可用表达式___来表示。
a．a+b/c+d b．(a+b)/(c+d) c．a+b/(c+d) d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为_____＿管理技术。
a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守_______＿原则。
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) 构造预测分析表。
编译原理试题及答案一、选择题1. 下列哪个不是编译器所需的基本处理步骤？A. 词法分析B. 语法分析C. 语义分析D. 目标代码优化答案：D2. 编译器的主要功能是将高级语言程序翻译成什么形式？A. 汇编语言B. 机器语言C. 中间代码D. 高级语言答案：B3. 下列哪个不属于编译器的后端阶段？A. 代码优化B. 目标代码生成C. 词法分析D. 目标程序优化答案：C二、填空题1. 编译器的输入是源程序，输出是目标程序。
2. 目标代码生成阶段的任务是将中间代码翻译成汇编语言或机器语言。
3. 语法分析阶段的输出是抽象语法树。
三、简答题1. 请简述编译器的工作原理。
编译器的工作原理主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段。
词法分析阶段将源程序分解成单词（也称为词法单元），语法分析阶段根据语法规则将词法单元组织成一个语法树，语义分析阶段对语法树进行语义检查，中间代码生成阶段将语法树转化为中间代码，代码优化阶段对中间代码进行优化，最后目标代码生成阶段将中间代码转化为机器语言或汇编语言。
2. 请说明词法分析的作用是什么，如何实现？词法分析的作用是将源程序中的字符序列转化为单词序列，也就是将一段代码切分成不同的词法单元。
实现词法分析可以通过有限状态自动机来处理输入字符序列，并根据一系列规则将字符序列划分为词法单元。
常用的方法有手写分析器和使用词法分析生成器等。
3. 简要介绍一下代码优化的目的和方法。
代码优化的目的是通过对程序的中间代码或目标代码进行调整，以达到提高程序性能、减小程序的空间占用或减小程序的执行时间等目的。
代码优化的方法主要包括局部优化和全局优化两种。
局部优化主要针对某个代码块进行优化，如常量折叠、公共子表达式消除等。
全局优化则考虑整个程序，对程序的整体结构进行优化，如循环优化、函数内联等。
总结：编译原理试题及答案主要涵盖了选择题、填空题和简答题三个部分。
其中选择题主要考察对编译器基本处理步骤和功能的理解。
编译原理考试题及答案一、选择题（每题5分，共20分）1. 编译器的主要功能是什么？A. 代码优化B. 代码翻译C. 代码调试D. 代码运行答案：B2. 下列哪个选项不属于编译器的前端部分？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，文法的产生式通常表示为：A. A -> αB. A -> βC. A -> γD. A -> δ答案：A4. 下列哪个算法用于构建语法分析树？A. LL(1)分析B. LR(1)分析C. SLR(1)分析D. LALR(1)分析答案：A二、填空题（每空5分，共20分）1. 编译器的前端通常包括词法分析、语法分析和________。
答案：语义分析2. 编译器的后端主要负责________和目标代码生成。
答案：代码优化3. 编译器中的词法分析器通常使用________算法来识别单词。
答案：有限自动机4. 语法分析中，________分析是一种自顶向下的分析方法。
答案：递归下降三、简答题（每题10分，共30分）1. 简述编译器的作用。
答案：编译器的主要作用是将高级语言编写的源代码转换成计算机能够理解的低级语言或机器代码，以便执行。
2. 解释一下什么是语法制导翻译。
答案：语法制导翻译是一种翻译技术，它利用源语言的语法信息来指导翻译过程，使得翻译过程能够更好地理解源代码的语义。
3. 什么是词法分析器？答案：词法分析器是编译器前端的一部分，它的任务是将源代码文本分解成一系列的标记（tokens），这些标记是源代码的最小有意义的单位。
四、计算题（每题10分，共30分）1. 给定一个简单的文法G(E)：E → E + T | TT → T * F | FF → (E) | id请计算文法的非终结符号E的FIRST集和FOLLOW集。
答案：E的FIRST集为{(, id}，FOLLOW集为{), +, $}。
2. 假设编译器在进行语法分析时，遇到一个语法错误的代码片段，请简述编译器如何处理这种情况。
第一章引论1. 解释下列术语：编译程序、编译程序的前端和后端答：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。
（2）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。
通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。
（3）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。
2.一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。
答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下：（1）词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
（2）语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
（3）语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
（4）中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。
（5）中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。
（6）目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
（7）表格管理程序：负责建立、填写和查找等一系列表格工作。
表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。
可以说整个编译过程就是造表、查表的工作过程。
需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。
（8）错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。
当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。
4.对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
（1）else 没有匹配的if（2）数组下标越界（3）使用的函数没有定义（4）在数中出现非数字字符答案：（1）语法分析（2）运行时或者语义分析（3）语法分析（4）词法分析第三章文法和语言1.文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。
答案：L(G[S])={abc}2.文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案：长度至少为 1 的任意的数字串。
3.为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。
答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|94.已知文法G[Z]：(1)Z：：= aZb(2)Z：：= ab写出L(G[Z])的全部元素。
答案：L(G[Z]) = { a n b n | n≥1 }5.写一文法，使其语言是偶正整数的集合。
要求：(1) 允许0 打头；(2)不允许0 打头。
答案：(1)允许0 开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|08.文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答案：由于对于文法 G[S] 的一个句子abc ，存在以下两个不同的最右推导：最右推导 1：最右推导 2：所以该文法为二义文法。
11.令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答案：按照句型的定义，由于存在推导，所以是该文法的一个句型。
通过构造该句型的语法树，可以直观地看出句型的所有的短语、直接短语和句柄。
该句型的语法树如下：所有的短语：所有的直接短语：句柄：13.一个上下文无关文法生成句子abbaa 的推导树如下：(1)给出串abbaa 最左推导、最右推导。
(2)该文法的产生式集合P 可能有哪些元素？(3)找出该句子的所有短语、直接短语、句柄。
(1)最左推导：最右推导：(2) 该文发的产生式集合 P 可能的元素：、、、、、。
(3) 所有短语：abbaa、a、bb、aa、ε、b；所有直接短语：a、ε、b；句柄：a。
第四章词法分析2.已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。
答案：先构造其矩阵用子集法将NFA 确定化：将x、z、xz、y、xy、xyz 重新命名，分别用A、B、C、D、E、F 表示。
因为B、C、F中含有z，所以它为终态。
DFA 的状态图：3.将下图确定化：答案：用子集法将NFA 确定化：0 1S VQ QUVQ VZ QUQU V QUZVZ Z ZV Z -QUZ VZ QUZZ Z Z重新命名状态子集，令VQ 为A、QU 为B、VZ 为C、V 为D、QUZ 为E、Z 为F。
0 1-S A BA C BB D E+C F FD F -+E C E+F F FDFA 的状态图：7.给文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b构造相应的最小的DFA。
答案：相应的 NFA 为：a b-S A QA A B,ZB Q DQ Q D,ZD A BE B FF E D,Z+Z - -确定化：a b-S A QA A BZQ Q DZ+BZ Q D+DZ A BD A BB Q DM = {S,A,Q,D,B} ∪ {BZ,DZ}{S,A,Q,D,B}按照 b 可划分为 {S,D,B}∪{A,Q} M = {S,D,B} ∪ {A,Q} ∪ {BZ,DZ}{S,D,B}按照 b 可划分为 {S}∪{D,B}M = {S} ∪ {D,B} ∪ {A,Q} ∪ {BZ,DZ}已不能再划分，所以，状态 D与 B、A 与 Q、BZ 与 DZ 分别为等价状态。
删除D、Q 和 DZ：a b-S A Q→AA A BZQ Q DZ+BZ Q→A D→B+DZ A BD A BB Q→A D→B8.给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：11.一种证明两个正则表达式等价的方法，那就是构造它们的最小 DFA，表明这两个 DFA 是一样的（当然状态名可以不同）。
使用此方法，证明下面的正则表达式是等价的。
(1) (a|b)*(2) (a*|b*)*(3) ((|a)b*)*解：（1）（2）a b±SAB SAB SAB（3）a b±SA SA SA第五章自顶向下语法分析方法例题1 已知文法 G[S]：S → aHH → aMd | dM → Ab | εA → aM | e①判断 G[S] 是否为 LL(1) 文法，若是，构造相应的预则分析表。
②若 G[S] 为 LL(1) 文法，给出输入串 aaabd# 的分析过程，并说明该串是否为 G[S] 的句子。
解：①【第 1 步】求出能推导出ε的非终结字符。
非终结字符S H M A能否推导出ε不可不可可不可【第 2.1 步】计算每一个终结或非终结字符 X 的 FIRST 集合：First(S) = {a}First(H) = {a,d}First(M) = first(A)∪{ε} = {a,e,ε}First(A) = {a,e}【第 2.2 步】计算每一个产生式右部的 FIRST 集合：First(aH) = {a}First(aMd) = {a}First(d) = {d}First(Ab) = first(A) = {a,e}First(ε) = {ε}First(aM) = {a}First(e) = {e}【第 3 步】计算每一个非终结字符 X 的 FOLLOW 集合：Follow(S) = {#}Follow(H) = follow(S) = {#}Follow(M) = {d}∪follow(A) = {b,d}Follow(A) = {b}【第 4 步】计算每一个产生式的 SELECT 集合：Select(S→aH) = {a}Select(H→aMd) = {a}Select(H→d) = {d}Select(M→Ab) = first(Ab) = {a,e}Select(M→ε) = follow(M) = {b,d}Select(A→aM) = {a}Select(A→e) = {e}【第 5 步】判别是否为 LL(1) 文法：由于：Select(H→aMd) ∩ Select(H→d) = ΦSelect(M→Ab) ∩ Select(M→ε) = ΦSelect(A→aM) ∩ Select(A→e) = Φ所以，该文法为 LL(1) 文法。
a b d e #S S→aHH H→aMd H→dM M→Ab M→εM→εM→AbA A→aM A→e ②步骤分析栈剩余输入串（第 1 个字符为当前输入字符）推导所用的产生式或匹配1 #S aaabd# S→aH2 #Ha aaabd# 匹配 a3 #H aabd# H→aMd4 #dMa aabd# 匹配 a5 #dM abd# M→Ab6 #dbA abd# A→aM7 #dbMa abd# 匹配 a8 #dbM bd# M→ε9 #db bd# 匹配 b10 #d d# 匹配 d11 # # 接受（分析成功）例题2.文法 G[S]：①试对 G[S] 进行改写，并判断改写后的文法是否为 LL(1) 文法？②通过这个例子，能够说明什么？解：①文法存在间接左递归，应该先将间接左递归转换为直接左递归。
有以下两种转换方法：转换方法 1：将代入中的 A，将间接左递归转换为直接左递归后，文法转换为：消除关于 S 的直接左递归后，文法转换为：由于所以，改写以后的文法为 LL(1) 文法。
