欢迎来到天天文库
浏览记录
ID:56153851
大小:172.00 KB
页数:10页
时间:2020-03-17
《四川大学编译原理复习要点.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、四川大学编译原理复习要点2013版一、编译器各个阶段的功能,输入、输出,前端、后端1)词法分析:将字符序列收集到称作记号(token)的有意义单元中扫描程序 输入:源代码输出:记号2) 语法分析:从扫描程序中获取记号形式的源代码,并完成定义程序结构的语法分析,语法分析定义了程序的结构元素及其关系。输入:记号输出:语法树3)语义分析程序:分析程序的静态语义,包括声明和类型检查。输入:语法树输出:注释树4)源代码优化程序:编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完成的,而此时代码改进可能只依赖于源代码。【对源代码进行优化,并产生中间代码】 输入:注释
2、树输出:中间代码5)目标代码生成:得到中间代码,生成目标机器的代码代码生成器输入:中间代码输出:目标代码6)目标代码优化程序:编译器改进由代码生成器生成的目标代码。输入:目标代码输出:目标代码扫描程序、分析程序和语义分析程序是前端,代码生成器是后端,前后端分开的好处:可以给编译器带来更方便的可移植性,此时的编译器既能改变源代码,又能改变目标代码。【遍】编译器发现,在生成代码之前多次处理整个源程序很方便,这些重复就是遍。首遍是从源中构造一个语法树或中间代码,在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成二、 解释器和编译器的区别与联系? 读入源语言后,解释器和编
3、译器都要进行词法分析、语法分析和语义分析,之后,二者开始有所分别。解释器在语义分析后选择了直接执行语句;编译器在语义分析后选择将将语义存储成某一种中间语言,之后通过不同的后端翻译成不同的机器语言(可执行程序)编译器是把源语言(如C,Pascal,java等高级语言)转换为目标语言(汇编语言、机器语言等低级语言),要产生目标代码。解释器是以一个源语言(C,Pascal,java等高级语言)为输入,一边解释一边执行源程序,但不产生目标代码。三、算法描述(伪代码)p41构造一个扫描程序的自动过程:正则表达式→NFA→DFA→程序1、正则表达式→NFA(1) 建立字母表。输入的正则表达式由于一
4、般不输入“与”操作符,因此首先给表达式加入 .作为与操作。再利用逆波兰式的堆栈操作,把操作符与字母分开,便得到了字母表。 (2) Thompson构造法。首先将构成正则表达式的各个元素分解,对于每一个元素,按照下述规则1和规则2生成NFA。 注意:如果r中记号a出现了多次,那么对于a的每次出现都需要生成一个单独的NFA。2、NFA→DFA从单个输入字符的某个状态中去除ε-转换和多重转换。(1)利用ε-closure规则即闭包规则,把NFA状态划分成集合,而后把每个集合作为DFA的状态。详细描述:从NFA的状态S开始经过ε到达的状态存储下,然后再把存储结果中的状态有经过ε到达的新状态也存
5、储在一起,这样通过闭包规则就可以这些集合,再把集合作为DFA的状态。(2)子集构造3、DFA→程序DFA状态最小化取出DFA状态中的不可达的状态。构造最小状态的等价DFA的算法是通过创建统一到单个状态的状态集来进行。构造NFA(使用Thompson结构):1)基本正则表达式基本正则表达式格式a或ε,其中a表示字母表中单个字符的匹配,ε表示空串的匹配。与正则表达式a等同的NFA(即在其语言中准确接受)的是:与ε等同的NFA是:2)并置我们希望构造一个与正则表达式rs等同的NFA,其中r和s都是正则表达式。可将与rs对应的NFA构造如下:3)在各选项中选择我们希望在与前面相同的假设下构造一
6、个与r
7、s相对应的NFA。如下进行:4)重复我们需要构造与r*相对应的机器,现假设已有一台与r相对应的机器。那么就如下进行:构造NFA的一个例子:例:根据Thompson结构将正则表达式ab
8、a翻译为NFA。首先为正则表达式a和b分别构造机器:接着再为并置ab构造机器:现在再为a构造另一个机器复件,并利用它们组成ab
9、a完整的NFA,如下图:将NFA转换成DFA(最小子集法):ε-闭包(ε-closure)是可由ε转换从某状态或某些状态达到的所有状态集合,它总是包含状态本身子集构造 相关题目:2.1,2.12,2.16四、提左因子和消除左递归1、在建立LL(1)语法分析器的时候,
10、提左因子和消除左递归的目的、原因 目的:提取左因子---避免程序回溯;消除左递归---消除无限循环原因:当有公因子存在时,不能立即区分出文法规则右边的选择;当有左递归时,将导致一个无限循环。2、提左因子和消除左递归的算法描述消除左递归伪代码P119fori:=1tomdoforj:=1toi-1doreplaceeachgrammerrulechoiceoftheformAi→AjβbytheruleAi→α1β
11、α2β
12、....
13、αkβ,wh
此文档下载收益归作者所有