编译原理复习ppt课件.ppt

《编译原理复习ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译原理》复习西安电子科技大学软件工程研究所刘坚课程内容一、引言二、词法分析三、语法分析四、语法制导翻译生成中间代码五、运行环境要求①牢固掌握基本概念②灵活使用基本方法③善于归纳总结（抽象能力）2第一章引言<1>语言的翻译不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译翻译方法：3<2>编译器的基本组成4<3>编译器的分析－综合模式<4>编译器的扫描遍数与编译器的编写5第二章词法分析对于单词的识别，首先应该有单词形成的规则，称为构词规则，然后根据构词规则识别输入序列，称为词法分析。主要内容<1

2、>记号、模式与单词<2>记号的说明－模式的形式化描述（正规式与正规集）<3>记号的识别－有限自动机<4>从正规式到词法分析器滤掉源程序中的无用成分；处理与具体操作系统或机器有关的输入；识别记号并交给语法分析器；调用符号表管理器和出错处理器进行相关处理。词法分析器是编译器与源程序打交道的唯一阶段，可以被认为是编译器的预处理阶段，它有以下几个重要作用：6<1>记号、模式与单词模式（pattern）：规定单词识别的规则记号（token）：按照某模式识别出的一类单词（记号种类）单词（lexeme）：被识别出

3、的字符串本身词法分析器的输出：记号=记号种类+记号属性<2>记号的说明－模式的形式化描述①正规式与正规集：正规式与正规集的定义（基本正规式、三个运算）；正规式的等价（描述相同的集合）；利用正规式的等价对正规式进行化简（正规式的代数性质）。②用正规式对模式进行形式化描述：如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等；正规式的简化形式以及辅助定义与规则。7<3>记号的识别－有限自动机（FA）NFA与DFA的定义：M=(S,Σ,move,s0,F)；NFA与DFA的表示：定义

4、直接表示、状态转换图、状态转换矩阵；NFA与DFA的关键区别：NFA的不确定性（当前状态下，对同一字符可能有多于一个的下一状态转移）；用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收、回溯带来的问题；模拟DFA的算法（用DFA识别记号）。<4>从正规式到词法分析器构造NFA的Thompson算法（与NFA定义的对应关系）；模拟NFA的“并行”算法；从NFA构造DFA－子集法：smove(S,a)与ε-闭包(T)的计算；DFA的最小化－可区分的概念：所有不可区分的状态看作是一个状态；灵

5、活运用各种方法构造DFA（正规式化简、状态转换图等）8第三章语法分析语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即语法规则；根据语法规则识别输入序列（记号流）中的语言结构，即语法分析。语法分析的分析对象是组成语言的句子，句子具有层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法。主要内容<1>程序设计语言与文法<2>有关推导的基本概念<3>自上而下分析<4>自下而

6、上分析9<1>程序设计语言与文法正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号（终结符）；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力；上下文无关文法（CFG=(N,T,S,P)）：CFG用于描述层次结构，如构成程序的句子；识别CFL的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；文法的分类：0型、1型、2型和3型文法词法分析器与语法分析器（FA与PDA）10<2>有关推导的基本概念CFG产生语言的基本方法－推导：推导的基本

7、思想是从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程（含有非终结符）；文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。二义性的消除：a.改写二义文法为非二义文法；b.对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。11<3>自上而下分析分析方法：推导，从上到下构

8、造分析树，是一种预测的、试探的方法；对文法的要求：没有公共左因子和左递归；递归下降子程序方法：匹配终结符，展开非终结符（子程序调用）预测分析表方法:a.工作方式与过程：PDA（DPDA）、格局与改变格局的动作；b.预测分析表的构造：FIRST集合与FOLLOW集合，FIRST与FOLLOW的计算；c.LL(1)文法及其判别：预测分析表中没有多重定义条目（推论3.2）。12<4>自下而上分析分析方法：归约（推导的逆过程），从叶子到根构造分析树；基本概念：短语、直接短语、