当前位置：文档之家 › 西电编译原理_复习与试题讲解

西电编译原理_复习与试题讲解

  • 格式：ppt
  • 大小：499.00 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

（完整版）编译原理复习题

（完整版）编译原理复习题

（完整版）编译原理复习题《编译原理》常见题型一、填空题1、编译程序的工作过程一般可以划分为词法分析，语法分析，语义分析，中间代码生成，目标代码生成等几个基本阶段。

2、若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。

3、编译方式与解释方式的根本区别在于是否生成目标代码。

5、对编译程序而言，输入数据是源程序，输出结果是目标程序。

7、若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。

8、一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。

其中，词法分析器用于识别单词。

10、一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。

12、产生式是用于定义语法成分的一种书写规则。

13、设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为L(G)＝{x│S*x，x∈V T*} 。

14、设G是一个给定的文法，S是文法的开始符号，如果S*x（其中x∈V*），则称x是文法的一个句型。

15、设G是一个给定的文法，S是文法的开始符号，如果S*x (其中x∈V T*)，则称x是文法的一个句子。

16、扫描器的任务是从源程序中识别出一个个单词符号。

17、语法分析最常用的两类方法是自上而下和自下而上分析法。

18、语法分析的任务是识别给定的终结符串是否为给定文法的句子。

19、递归下降法不允许任一非终结符是直接左递归的。

20、自顶向下的语法分析方法的关键是如何选择候选式的问题。

21、递归下降分析法是自顶向下分析方法。

22、自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

23、自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

(完整版)编译原理复习题及答案

(完整版)编译原理复习题及答案

编译原理复习题及答案一、选择题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．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(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)上。

(完整word版)编译原理复习题(word文档良心出品)

(完整word版)编译原理复习题(word文档良心出品)

编译原理复习一、简述题1、简述编译程序的工作过程编译程序的工作，即从输入源程序开始到输出目标程序为止的整个过程是非常复杂的。

通常，编译程序的工作过程可以划分为5个阶段：第1阶段，词法分析。

词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如保留字（基本字）、标识符、算符、界符等。

依循的原则：构词规则描述工具：有限自动机第2阶段，语法分析。

语法分析的任务是在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如语句、程序块、函数等，判断整个输入串是否是一个语法上正确的“程序”。

依循的原则：语法规则描述工具：上下文无关文法第3阶段，语义分析与中间代码产生。

这一阶段的任务是对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

通常的中间代码有三元式、四元式、间接三元式、逆波兰式等。

依循的原则：语义规则第4阶段，优化。

优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生更为高效（省时间和空间）的目标代码。

优化的主要方法有公共子表达式的提取、循环优化等。

依循的原则：程序的等价变换规则第5阶段，目标代码生成。

这一阶段的任务是把中间代码（或经优化处理之后的中间代码）变换成特定机器上的低级语言代码。

目标代码三种形式:绝对指令代码: 可直接运行可重新定位指令代码: 需要连接装配汇编指令代码: 需要进行汇编2、编译程序在分析语言程序的过程中将源语言程序的各种信息都保留在各种表格中，同时，在源语言程序出错时，编译程序要帮助进行错误判断、错误定位等，因此表格管理及出错处理和编译程序的各个阶段都有关联。

编译程序的结构图如图所示。

其中词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

语法分析器，简称分析器，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

编译原理复习重点含答案

编译原理复习重点含答案

编译原理复习重点含答案编译原理复习重点编译原理是计算机科学中的一门重要课程，它研究的是如何将高级语言程序转化为机器语言的过程。

在编译原理的学习中，我们需要掌握一些重要的概念和技术，以便能够理解和应用编译器的工作原理。

本文将重点介绍编译原理的几个重要主题，并提供相应的答案供参考。

一、词法分析词法分析是编译器的第一个阶段，它的任务是将输入的字符序列划分为一个个有意义的词素（token）。

词法分析器通常使用有限自动机（DFA）来实现，其工作原理是将输入字符序列逐个读入，并根据事先定义好的词法规则进行匹配和识别。

常见的词法单元包括关键字、标识符、常量、运算符等。

常见的词法规则包括：1. 关键字：例如if、while、for等。

2. 标识符：由字母、数字和下划线组成，且以字母或下划线开头。

3. 常量：包括整数常量、浮点数常量、字符常量和字符串常量等。

4. 运算符：例如加法运算符+、减法运算符-等。

5. 分隔符：例如逗号、分号等。

词法分析的结果是一个个词法单元，每个词法单元包含一个词素和对应的词法单元类型。

例如，对于输入程序"int a = 10;"，词法分析的结果可能是[("int", "关键字"), ("a", "标识符"), ("=", "运算符"), ("10", "整数常量"), (";", "分隔符")]。

二、语法分析语法分析是编译器的第二个阶段，它的任务是将词法分析器输出的词法单元序列转化为抽象语法树（AST）。

语法分析器通常使用上下文无关文法（CFG）来描述语言的语法结构，并使用递归下降、LL(1)分析、LR分析等算法进行分析。

常见的语法规则包括：1. 表达式：例如算术表达式、布尔表达式等。

西电编译原理_第二章习题解答

西电编译原理_第二章习题解答
(3) 再考虑：仅由1组成的串，或 若干1打头的串。
最终的正规式： 1* | 1*(01|0)* = 1*(01|0)*
© 西安电子科技大学 · 软件学院
5
1. 根据模式写出正规式
习题2.4 (2) 所有不含有子串 011 的01串 思路2：考虑包含 011 的串，然后构造没有011的串 ① 含有 子串 011 的最简单的串：
© 西安电子科技大学 · 软件学院
？
| (01|10) (00|11)* (01|10) )*
4
1. 根据模式写出正规式
习题2.4 (2) 所有不含有子串 011 的01串 思路1：简单例子，观察规律 (1) 最简单的串： 0 , 1, 11, 00, 10, 01, 010, …
(2) 上述各串重复： (0 | 00 | 01 | 010 )* = (01 | 0)*
© 西安电子科技大学 · 软件学院
7
2.依据NFA/DFA，给出正规式
思路1： 回顾“正规式 与 FA的关系”
正规集 描述 正规式 识别 有限自动机
正规式、FA是从两个不同的侧面表示一个集合(即正 规集)。所以，根本的方法是以正规集为桥梁， - 先分析清楚 FA 识别的集合之结构特征， - 然后再设计此集合的正规式。
© 西安电子科技大学 · 软件学院
2
1. 根据模式写出正规式
一般思路：（1）分析题意 （2）列举一些最简单的例子 （3）寻找统一规律*,考虑所有可能情况**
习题2.4 (1) 由偶数个0和奇数个1构成的01串
解：① 最简单的串有 0个0和1个1组成的串： 1 2个0和1个1组成的串：010 ，001，100 ② 在上述串的中间、两头添加偶数个0和/或偶数个1，即可 得到满足题意的其他串。 设偶数个0/偶数个1组成的串，可用正规式 A 表示，则最 终正规式： A1A | A0A1A0A

7西安电子科技大学《编译原理》

7西安电子科技大学《编译原理》
1
3.5.1 自下而上分析的基本方法
思路：从句子ω开始，从左到右扫描ω，反复用产生式的左部替换 产生式的右部、谋求对ω的匹配，最终得到文法的开始符号，或者 发现一个错误。
3.5.1.1 规范归约与“剪句柄”
定义3.13 设αβδ是文法G的一个句型， 若 存在S =*>αAδ，A =+>β， 则 称β是句型αβδ相对于A的短语， 特别的，若 有A→β， A→β 则 称β是句型αβδ相对于产生式A→β的直接短语。 一个句型的最左直接短语被称为句柄。 ■ ① 直观上，句型是一个完整结构，短语是句型中的某部分(针对 某非终结符)。S是一个句型，而不是一个短语(树根不是短语)。 ② 短语形成的两个要素： 1．从S可以推导出A，即S=*>αAδ； 2．从A至少一次推导出β，即A=+>β。
13
结
束
上节主要内容： 1. 自下而上分析的基本方法：归约（短语、直接短语、句柄、规 范（最左）归约） 2. 规范归约的形象表示－剪句柄； 3. 移进-归约分析工作模式：格局与格局变换 4. LR分析与LR文法： <1> 分析表：动作表与转移表 <2> 模拟算法：改变格局的两个重要动作－移进与归约 <3> LR分析器的实例分析 <4> LR文法
5
3.5.1.2 移进-归约分析器工作模式
移进-归约分析器的工作模式：
输入记号流 ip top 符 号 状 态 栈 驱动器 移进-归约 分析表 输出
与预测分析对比：
输入记号流 符 top 号 栈 ip 输出
驱动器 预测分析表 (b) 预测分析器模型
预测分析器： 移进-归约分析器： 1.分析方法：格局与格局变换 1. 分析方法：格局与格局变换 2.分析表 2. 分析表 3. 驱动器（模拟算法） 3. 驱动器（模拟算法） 4. LR（文法、语言、分析器） 4. 预测分析表的构造 5. LL（文法、语言、分析器） 5. SLR分析表的构造

编译原理全复习(完整版)

1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

（4）优化器，对中间代码进行优化处理。

（5）目标代码生成器，把中间代码翻译成目标程序。

（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。

（7）出错管理，把错误信息报告给用户。

编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。

（2）。

语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。

（3）语义分析与中间代码产生。

任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

（4）优化。

任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

（5）目标代码生成。

任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。

2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。

b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。

西安电子科技大学编译原理 (23)

• 标识符initial形成的记号是<id,2> • 加号形成的记号是<+> • 标识符rate形成的记号是<id,3> • 乘号*形成的记号是<*> • 60形成的记号是<60>

其他面向特定应用领域的语言 计算机辅助设计：MATLAB 集成电路设计：VHDL、Verilog 虚拟现实与人机交互：VRML ……
21
程序设计语言的发展
计算机语言举例
[例1]通用程序设计语言与汇编语言（包括机器 指令） Pascal语句： x := a+b； C++语句： x = a+b； 汇编指令： 十六进制代码 汇编指令 A10002 MOV AX, [A] 8B1E0202 MOV BX, [B] 01D8 ADD AX, BX A30402 MOV [X], AX 22
输出
特点
编译器：工作效率高，即时间快、省空间；交互性与动 态特性差、可移植性差。被大多数PL的翻译所采用； 解释器：工作效率低，即时间慢、费空间；交互性与动 态特性好、可移植性好。早期的Basic和现在的Java等。 基本功能：二者相同； 采用技术：从翻译的角度来讲，两种方式所涉及的原理、 方法、技术相似。
26
1.3 编译器与解释器
语言翻译的两种基本形态 先翻译后执行
源程序 输入数据
边翻译边执行
源程序 输入数据
编译器 目标程序
目标程序
输出
解释器
输出
[例5]假设有源程序P：x=3;
P 编译器 目标程序 目标程序
P
解释器
x=3
27
3
x=3
3
1.3 编译器与解释器

西电编译原理_第二章习题解答

(3) 再考虑：仅由1组成的串，或 若干1打头的串。
最终的正规式： 1* | 1*(01|0)* = 1*(01|0)*
© 西安电子科技大学 · 软件学院
5
1. 根据模式写出正规式
习题2.4 (2) 所有不含有子串 011 的01串 思路2：考虑包含 011 的串，然后构造没有011的串 ① 含有 子串 011 的最简单的串：
然后据上，考查每条从初态到终态的路径，综合正规式即可。
© 西安电子科技大学 · 软件学院 9
2.依据NFA/DFA，给出正规式
习题2.10 (2) 用正规式描述 DFA 所接受的语言；
0 b,c 2 b,c a b a a,c 1
该DFA从初态到终态有三条路径：0b2，0c2，0a1b2 用正规式表示为： b | c | a(a|c)*b， 而且是这三条路径均至少重复一次， 故最终的正规式为：(b|c|a(a|c)*b)+
© 西安电子科技大学 · 软件学院 13
其它
习题2.9 构造 10*1 的最小DFA 解： 活用 Thompson 算法 (1) 分解为三部分：1，0*，1； (2) 画出三者的状态转换图：
0 1 0 1 2 3 1 4
(3) 连接运算：子图首尾相连
0
1
0 1 1
1
4
这已经是最小的DFA
© 西安电子科技大学 · 软件学院
© 西安电子科技大学 · 软件学院
11
其它
关于：正规式 -> NFA -> DFA -> DFA最小化：
说明：（一般）逐步计算 正规式->NFA： （1）呆板Thompson算法: 自上而下分解正规式—— 语法树， 自下而上构造NFA —— 后续遍历; 特点：每个运算对应一次构造，繁琐！ （2）活用Thompson算法： 分解正规式：得到若干规模适中的子正规式； 为每个子正规式：画出其最简的状态转换图（子图）； 按Thompson算法，将子图组合，得到完整的图。

编译原理期末考试复习整理(详细列出考试重点+重点例题)

编译原理期末考试复习整理(详细列出考试重点+重点例题)本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March目录第一章 (3)词法分析： (3)语义法分析 (3)中间代码 (3)第二章 (3)1.根据语言写出文法 (4)2.根据文法写语，描述其特点(必考大题2-3类型) (4)3.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11） (6)第三章 (11)1.给出一个正规文法 (左线性、右线性方法），写出其状态转换图(必考) (11)1.1右线性文法写出状态转换图 (必考) (11)1.2状态转换图写出右线性文法G (12)1.3左线性文法写出状态转换图 (必考) (13)2.非确定自动机的确定化 (14)第四章 (15)第五章 (15)属性文法与属性翻译文法 (15)逆波兰式（大题） (16)四元式（大题） (16)第一章词法分析：分析源程序的结构，判断它是否是相应程序设计语言的合法程序语义法分析的任务是根据语言的语义规则对语法分析得到的语法结构进行静态的语义检查（确定类型、类型与运算合法性检查、识别含义等），并且转换成另一种内部形式（语义树）表示出来或者直接用目标语言表示出来。

中间代码是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是便于优化、移值；三是容易将它翻译成目标代码第二章文法G定义为四元组(V N，V→，P，S )其中V N为非终结符号(或语法实体，或变量)集；V→为终结符号集；P为产生式(也称规则)的集合； V N，V→和P是非空有穷集。

S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。

V N和V→不含公共的元素，即V N ∩V→ = φ,通常用V 表示V N∪ V→，V称为文法G的字母表或字汇表。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

三、计算题（3.4） 2．最小化DFA：(利用可区分概念) 原始划分(两个组)：1={A,B} 2={C,D} 考察所有状态转移： move(A,a) = A, move(B,a) = B move(A,b) = B, move(B,b) = C move(C,a) = D, move(D,a) = C move(C,b) = D, move(D,b) = C 根据可区分概念将1分割成两个组1和3，得到： 1={A} 2={C,D} 3={B} 由于状态 C 和D 不可区分，因此可将 C、D 合并为 一个状态且选C作代表，得到最小DFA如右。 对应的图形表示如下。
T F a T + F F b c
三、计算题（3.2）
E E * T F ( E ) T T + F
F d
T F id
(T+F)*id 的分析树
a*b+c*d的分析树
15
三、计算题（3.2） (d) E→E*T|T，T→T+F|F，F→id的识别活前缀的DFA：
E’→.E I0 E E’→E. I1 * E→E.*T E→.E*T E→.T T→.T+F T E→T. I2 T→.F T→T.+F F→.id F F T→F. I3 id id F→id. I4 id
复习什么？
1. 2. 3. 4. 概述 词法分析 语法分析 语法制导翻译生成中间代码 语法与语义、属性 语义规则的两种表现形式：语法制导定义、翻译方案 中间代码：特点，为什么需要中间代码，常见中间代码 形式（后缀式、树、三地址码） 符号表：作用 声明语句的翻译：查填符号表 变量声明 过程声明（左值、右值、作用域、参数传递） 可执行语句的翻译：生成中间代码 算术表达式与赋值语句； 数组元素的引用：地址计算（不变部分、可变部分） 布尔表达式的短路计算翻译； 拉链与回填； 4 控制语句的翻译
a
{0} A {0,1} B {0,1,2} C {0,2} D {0} A {0} A {0,2} D {0,2} D
三、计算题（3.4）
b {0,1} B {0,1,2} C {0,1,2} C
{0,1,2} C
A B C D
A A D D
B C C C
得到DFA如右（其中，C和D中含NFA的终态，故C和D是DFA的终态） 18
以阶段划分编译器
源程序 词法分析 语法分析 出 语义分析 中间代码生成 代码优化 目标代码生成 目标代码
1
符 号 表 管 理
错 处 理
基本情况
题型： • 简答题（30分） • 填空题（20分） • 计算题（50分） 内容分布： • 概述与词法分析（约30分） • 语法分析（约40分） • 语法制导翻译生成中间代码（约30分）
7
一、简答题（续2） 1.6 给出语句while (a<b) do if (c<d) then x:= y+z的中间 开始 代码序列。 解：程序流程图： 中间代码： 101 (j<, a, 102 (j, -, 103 (j<, c, 104 (j, -, 105 (+, y, 106 (:=, t1, 107 (j, -, 108 ...
（也可以先给出语句的分析树，然后剪句柄生成中间代码）
8
二、填空题 2.1 从程序运行的角度看，编译程序和解释程序的主要区别 是： 。 2.2 编译程序的基本组成有：词法分析、 、 、中间代码 生成、 、 、 和 。 2.3 正规式r和s等价说明 相同。 2.4 不含子串baa的所有a、b符号串的正规式是 。 2.5 规范规约(最左归约)和 是互逆的两个过程。 2.1 运行目标程序时控制权在解释程序而不在目标程序，或者 是否生成目标代码，或者是否与机器相关。 2.2 语法分析、语义分析、代码优化、目标代码生成、 符号表管理和出错处理 2.3 r和s表示的正规集 2.4 a*(b|ba)* 2.5 规范推导(或最右推导)
2.9 FIRST(S)= {e，d，ε，a，b} ，FIRST(D)= {a，b} FIRST(T)= {ε，a，b} ，FIRST(R)= {d，ε} 。 2.10 {ambncn|m≥0, n≥1}。 2.11 右值（或值）、左值（或地址）。
，
11
二、填空题（续3） 2.12 为数组声明a:array[1..4, 2..3]中a分配的存储空间的首 地址为base_a，且每个数组元素占据一个存储单元。若以行为 主存放，数组元素a[3, 3]在存储空间中相对base_a的偏移量 是 ；若以列为主存放，数组元素a[3, 3]在存储空间中相对 base_a的偏移量是 。 2.12 以行为主存放，数组元素a[3, 3]在存储空间中相对base_a 的偏移量是 5 ； 以列为主存放，数组元素a[3, 3]在存储空间中相对base_a 的偏移量是 6 。
a<b N 结束
b, -, d, -, z, -, -,
103) 108) 105) 101) t1) x) 101)
N
Y c<d Y x:=y+z
或：
101 102 103 104 105 106 107 108 if a<b goto 103 goto 108 if c<d goto 105 goto 101 t1 := y+z x := t1 goto 101 ...
13
三、计算题（3.2） 3.2 有文法G如下（注：G中终结符id仅由单个英文字母组成，如 a, b等）：E→E*T|T T→T+F|F F→(E)|id 和G的语法制导翻译如下：
E→E1*T | T T→T1+F | F F→(E) | id {E.place=newtemp; emit(*,E1.place,T.place,E.place;} {E.place=T.place;} {T.place=newtemp; emit(+,T1.place,F.place,T.place;} {T.place=F.place;} {F.place=E.place;} {F.place=;}
2
复习什么？
1. 概述：编译器、解释器，汇编，反编译，反汇编，交叉汇 编，编译阶段，编译前端（分析）、后端（综合） 2. 词法分析 • 基本概念：正规式、正规集、有限自动机，词法分析器 的构造 • 常见计算题类型：已知集合求正规式、DFA；已知正规 式求DFA、集合；已知NFA（DFA）求正规式、集合；NFA 的确定化、最小化。 3. 语法分析 • 基本概念：上下文无关文法（CFG）、语言，句子、句 型，最左推导、最右推导，句柄，下推自动机（PDA）， 自上而下分析（递归下降法、预测分析法）与自下而上 分析（移进-归约分析）； • 一些必要的定义和算法的核心思想等； • 常见的计算题类型：计算FIRST、FOLLOW集合，构造句 子的分析树（语法树），构造预测分析表，构造识别文 法活前缀的DFA。 3
12
三、计算题 3.1 有文法G：V→id|id(E), E→E+V|V (a) 说明G不是LL(1)文法； (b) 将G改写为LL(1)文法。 解：(解题思路：LL(1)文法不能有左递归和左因子) (a) 因为FIRST(id)∩FIRST(id(E))={id}，即非终结符L产生 式的两个候选项有公共左因子，所以G不是LL(1)文法。（或 答文法中有左递归） (b)消除左递归和提取左因子之后，得到G1'如下，它是LL(1) 文法。 V → id B B → ε|(E) E → V E' E' → + V E' |ε
试 题 讲 解
5
一、简答题 1.1 有哪些方法可以去除文法的二义性。 1.2 写出 -((a+b)*c)+d 的后缀式。 1.3 给出布尔表达式A or B、A and B和not B短路计算的控制 逻辑。
1.1 （1）改写文法 （2）规定文法符号的优先级和结合性 1.2 ab+c*@d+（或ab+c*-d+） 1.3 A or B： if A then true else B A and B： if A then B else false not A： if B then false else true
9
二、填空题（续1）
2.6 文法的终结符集和 的交集一定为 。词法分析器交 给语法分析器的文法符号一定是 ，它只能出现在产生式的 部。 2.7 主流程序设计语言均采用静态作用域和 原则，为此类语 言的编译器设计的符号表应具有 的性质。 2.8 LR(1)分析法中，L的含义是 ，R的含义是 ，1的含义 是 。 2.6 非终结符集、空、终结符、右 2.7 最近嵌套、后进先出 2.8 自左向右扫描输入、最右推导的逆、确定下一个动作向前 看1个终结符
E→E*.T T E→E*T.I7 T→T.+F T→.T+F T→.F I5 F→.id + +
T→T+.F F T→T+F. I8 F→.id I6
16
三、计算题（3.3） 3.5 设有文法G：S→aBc|bAB, A→aAb|b, B→b|ε。 <1> 计算非终结符S、A、B的FIRST和FOLLOW集合(算法 3.5，算法3.6)； <2> 构造G的LL(1)分析表（算法3.7）; <3> 分析输入序列baabbb（以格局的形式写出具体的分 析步骤）。 解： <1> FIRST(B) = {b,ε} FOLLOW(B) = {c,#} FIRST(A) = {a,b} FOLLOW(A) = {b,#} FIRST(S) = {a,b} FOLLOW(S) = {#} a S A b c # aBc bAB aAb b b ε ε
(a) 求句型(T+F)*id 的短语、直接短语以及句柄； (b) 根据语法制导翻译写出句子a*b+c*d的中间代码； (c) 若a=3，b=5，c=7，d=8，请给出中间代码计算结果； (d) 将文法G简化为：E→E*T|T，T→T+F|F，F→id。给出它的识 别活前缀的DFA（算法3.9）。