您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 其它文档 > 四川大学编译原理复习要点
学习好资料欢迎下载四川大学编译原理复习要点2013版一、编译器各个阶段的功能,输入、输出,前端、后端1)词法分析:将字符序列收集到称作记号(token)的有意义单元中扫描程序输入:源代码输出:记号2)语法分析:从扫描程序中获取记号形式的源代码,并完成定义程序结构的语法分析,语法分析定义了程序的结构元素及其关系。输入:记号输出:语法树3)语义分析程序:分析程序的静态语义,包括声明和类型检查。输入:语法树输出:注释树4)源代码优化程序:编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完成的,而此时代码改进可能只依赖于源代码。【对源代码进行优化,并产生中间代码】输入:注释树输出:中间代码5)目标代码生成:得到中间代码,生成目标机器的代码代码生成器输入:中间代码输出:目标代码6)目标代码优化程序:编译器改进由代码生成器生成的目标代码。输入:目标代码输出:目标代码扫描程序、分析程序和语义分析程序是前端,代码生成器是后端,前后端分开的好处:可以给编译器带来更方便的可移植性,此时的编译器既能改变源代码,又能改变目标代码。【遍】编译器发现,在生成代码之前多次处理整个源程序很方便,这些重复就是遍。首遍是从源中构造一个语法树或中间代码,在它之后的遍是由处理中间表示、向它增加信息、更换结构或生成不同的表示组成二、解释器和编译器的区别与联系?读入源语言后,解释器和编译器都要进行词法分析、语法分析和语义分析,之后,二者开始有所分别。解释器在语义分析后选择了直接执行语句;编译器在语义分析后选择将将语义存储成某一种中间语言,之后通过不同的后端翻译成不同的机器语言(可执行程序)编译器是把源语言(如C,Pascal,java等高级语言)转换为目标语言(汇编语言、机器语言等低级语言),要产生目标代码。解释器是以一个源语言(C,Pascal,java等高级语言)为输入,一边解释一边执行源程序,但不产生目标代码。学习好资料欢迎下载三、算法描述(伪代码)p41构造一个扫描程序的自动过程:正则表达式→NFA→DFA→程序1、正则表达式→NFA(1)建立字母表。输入的正则表达式由于一般不输入“与”操作符,因此首先给表达式加入.作为与操作。再利用逆波兰式的堆栈操作,把操作符与字母分开,便得到了字母表。(2)Thompson构造法。首先将构成正则表达式的各个元素分解,对于每一个元素,按照下述规则1和规则2生成NFA。注意:如果r中记号a出现了多次,那么对于a的每次出现都需要生成一个单独的NFA。2、NFA→DFA从单个输入字符的某个状态中去除ε-转换和多重转换。(1)利用ε-closure规则即闭包规则,把NFA状态划分成集合,而后把每个集合作为DFA的状态。详细描述:从NFA的状态S开始经过ε到达的状态存储下,然后再把存储结果中的状态有经过ε到达的新状态也存储在一起,这样通过闭包规则就可以这些集合,再把集合作为DFA的状态。(2)子集构造3、DFA→程序DFA状态最小化取出DFA状态中的不可达的状态。构造最小状态的等价DFA的算法是通过创建统一到单个状态的状态集来进行。构造NFA(使用Thompson结构):1)基本正则表达式基本正则表达式格式a或ε,其中a表示字母表中单个字符的匹配,ε表示空串的匹配。与正则表达式a等同的NFA(即在其语言中准确接受)的是:与ε等同的NFA是:2)并置我们希望构造一个与正则表达式rs等同的NFA,其中r和s都是正则表达式。可将与rs对应的NFA构造如下:3)在各选项中选择我们希望在与前面相同的假设下构造一个与r|s相对应的NFA。如下进行:学习好资料欢迎下载4)重复我们需要构造与r*相对应的机器,现假设已有一台与r相对应的机器。那么就如下进行:构造NFA的一个例子:例:根据Thompson结构将正则表达式ab|a翻译为NFA。首先为正则表达式a和b分别构造机器:接着再为并置ab构造机器:现在再为a构造另一个机器复件,并利用它们组成ab|a完整的NFA,如下图:将NFA转换成DFA(最小子集法):ε-闭包(ε-closure)是可由ε转换从某状态或某些状态达到的所有状态集合,学习好资料欢迎下载它总是包含状态本身子集构造相关题目:2.1,2.12,2.16四、提左因子和消除左递归1、在建立LL(1)语法分析器的时候,提左因子和消除左递归的目的、原因目的:提取左因子---避免程序回溯;消除左递归---消除无限循环原因:当有公因子存在时,不能立即区分出文法规则右边的选择;当有左递归时,将导致一个无限循环。2、提左因子和消除左递归的算法描述消除左递归伪代码P119fori:=1tomdoforj:=1toi-1doreplaceeachgrammerrulechoiceoftheformAi→AjβbytheruleAi→α1β|α2β|....|αkβ,whereAj→α1|α2|.....|αkisthecurrentruleforAjremove,ifnecessary,immediateleftrecursioninvolvingAia)把直接左递归改写为右递归【简单直接左递归】设有文法产生式:A→Aβ|γ。其中β非空,γ不以A打头。可写为:A→γA'A'→βA'|ε一般情况下,假定关于A的产生式是【普遍的直接左递归】A→Aα1|Aα2|…|Aαm|β1|β2|…|βn其中,αi(1≤i≤m)均不为空,βj(1≤j≤n)均不以A打头。则消除直接左递归后改写为:A→β1A'|β2A'|…|βnA'A'→α1A'|α2A'|…|αmA'|ε例4.12:有文法G(E):E→E+T|TT→T*F|FF→i|(E)消除该文法的直接左递归。解:按转换规则,可得:E→TE'E'→+TE'|ε学习好资料欢迎下载T→FT'T'→*FT'|εF→i|(E)b)消除间接左递归【一般的左递归,不带有ε产生式且不带有循环的文法】对于间接左递归的消除需要先将间接左递归变为直接左递归,然后再按a)清除左递归。例4.13:以文法G6为例消除左递归:(1)A→aB(2)A→Bb(3)B→Ac(4)B→d解:用产生式(1),(2)的右部代替产生式(3)中的非终结A得到左部为B的产生式:(1)B→aBc(2)B→Bbc(3)B→d消除左递归后得到:B→aBcB'|dB'B'→bcB'|ε再把原来其余的产生式A→aB,A→Bb加入,最终得到等价文法为:(1)A→aB(2)A→Bb(3)B→(aBc|d)B'(4)B'→bcB'|εc)消除文法中一切左递归的算法设非终结符按某种规则排序为A1,A2,…,An。Fori﹕=1tondobeginForj﹕=1toi-1dobegin若Aj的所有产生式为:Aj→δ1|δ2|…|δn替换形如Ai→Ajγ的产生式为:Ai→δ1γ|δ2γ|…|δnγend消除Ai中的一切直接左递归学习好资料欢迎下载end提取左因子伪代码P122当两个或更多文法规则选择共享一个通用前缀时,需要提取左因子:A→αβ|αγ按如下规则提取左因子:A→αA’A’→β|γ五、first集合follow集合算法伪代码P126P131具体看书上的例子First集合求法:1.直接收取:对形如U-a…的产生式(其中a是终结符),把a收入到First(U)中2.反复传送:对形入U-P…的产生式(其中P是非终结符),应把First(P)中的全部内容传送到First(U)中。Follow集合求法:1.直接收取:注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到Follow(U)中。2.直接收取:对形如“…UP…”(P是非终结符)的组合,把First(P)除ε直接收入到Follow(U)中。3.反复传送:对形如P-…U的产生式(其中U是非终结符),应把Follow(P)中的全部内容传送到Follow(U)中。(或P-…UB且First(B)包含ε,则把First(B)除ε直接收入到Follow(U)中,并把Follow(P)中的全部内容传送到Follow(U)中)学习好资料欢迎下载六、写递归下降子程序伪代码P106递归下降:将一个非终结符A的文法规则看作将识别A的一个过程的定义一个if语句(简化了的)文法规则是:if-stmt→if(exp)statement|if(exp)statementelsestatement伪代码:procedureifstmt;beginmatch(if);match(();exp;match());statement;iftoken=elsethenmatch(else);statement;endif;endifstmt;给出基于DFA进行词法分析的表驱动的实现算法p44state:=1;ch:=nextinputcharacter;whilenotaccept[state]andnoterror(state)donewstate:=T[state,ch];ifadvance[state,ch]thench:=nextinputchracter;State:=newstate;endwhile;ifaccept[state]thenaccpet;学习好资料欢迎下载七、上下文无关文法BNFEBNF最左最右推导1、定义:上下文无关文法G是一个四元组G=(N,T,P,S),其中N是非终结符的有限集合;T是终结符或单词的有限集合,它与N不相交;P是形如A→α的产生式的有限集合,其中A∈N,α∈V﹡,V=T∪NS是N中的区分符号,称为开始符号或句子符号。V中的符号称为文法符号,包括终结符和非终结符。2、Backus-Naur符号(就是众所周知的BNF或Backus-NaurForm)是描述语言的形式化的数学方法,由JohnBackus(也许是PeterNaur)开发,用于描述Algol60编程语言的语法。3、EBNF(扩展的BNF)使用花括号{…}表示重复,方括号[...]表示可选EBNF中注意重复和可选的表示方法,语法图【可视的表示EBNF规则的图形表示法】上下文无关文法说明程序设计语言的语法结构,利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别在于上下文无关文法的规则是递归的(recursive)最左推导(leftmostderivation)是指它的每一步中最左的非终结符都要被替换的推导最右推导(rightmostderivation)则是指它的每一步中最右的非终结符都要被替换的推导。最左推导和与其相关的分析树的内部节点的前序编号相对应;最右推导则和后序编号相对应最右推导的一个例子:文法规则:exp→expopexp|(exp)|numberop→+|-|*分析树与抽象语法树有什么不同?对一个串按照某种文法进行推导的过程,可以用一颗树表示出来,这棵树就是分析树。分析树是表示记号串结构的一种十分有用的方法。抽象语法树是真正的源代码记号序列的抽象表示,包含了转换所需的所有信息,而且比分析树效率更高。学习好资料欢迎下载分析程序可以通过一个分析树表示所有步骤,但却通常只能构造出一个抽象的语法树(或与它等同的)。八、记号类型1、保留字,如IF何THEN,它们表示字符串“if”和“then”2、特殊符号,如算数符号加(PLUS)和减(MINUS),它们表示“+”“—”3、表示多字符串的记号,如NUM和ID,它们分别表示数字和标识符九、语言、句子、句型【语言】由推导从exp中得到的所有记号符号的串集是被表达式的文法定义的语言【句型】从文法起始符号出发经过任意有限次推导出来的串【句子】------------------------------------------------------------的只有终结符的串十、自顶向下(第4章)自底向上(第5章)区别:自顶向下语法分析:从文法的开始符号出发,从顶部开始构造语法分析树。自底向上语法分析:从构成语法分析树的叶子节点的终结符号串开始,从底部开始构造语法分析树。1、自顶向下的分析算法通过在最左推导中描述出各步骤来分析记号串输入从文法的开始符号出发,从顶部
本文标题:四川大学编译原理复习要点
链接地址:https://www.777doc.com/doc-5467659 .html