西安电子科技大学编译原理复习

《西安电子科技大学编译原理复习》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《编译原理》复习西安电子科技大学软件工程研究所刘坚课程内容要求（希望）牢固掌握基本概念灵活使用基本方法归纳总结所学内容一、引言二、词法分析三、语法分析四、语义分析—语法制导翻译生成中间代码学习不能走捷径，付出多少劳动就有多少收获掌握正确的学习方法，提高自学能力2第一章引言<1>语言的翻译不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译翻译方法：3<2>编译器的基本组成4<3>编译器的分析－综合模式<4>编译器的扫描遍数与编译器的编写5第二章词法分析构词规则与词法分析：首先规定单词形成的规则，称为构词规则；然后根据构词规则识别输入序列，称为词法分析。主

2、要内容：<1>记号、模式与单词<2>记号的说明－模式的形式化描述（正规式与正规集）<3>记号的识别－有限自动机<4>从正规式到词法分析器词法分析器的作用：滤掉源程序中的无用成分；处理与具体操作系统或机器有关的输入；识别记号并交给语法分析器；调用符号表管理器和出错处理器进行相关处理。6<1>记号、模式与单词模式（pattern）：规定单词识别的规则记号（token）：按照某模式识别出的一类单词（记号种类）单词（lexeme）：被识别出的字符串本身词法分析器的输出：记号=记号种类+记号属性<2>记号的说明－模式的形式化描述正规式与正规集正规式与正规集的定义(

3、基本正规式、三个运算)正规式的等价(描述相同的集合)利用正规式的等价对正规式进行化简(正规式的代数性质)用正规式形式化描述模式如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等正规式的简化形式以及辅助定义与规则7<3>记号的识别－有限自动机（FA）NFA与DFA的定义：FA=(S,Σ,move,s0,F)；NFA与DFA的表示：定义表示、状态转换图、状态转换矩阵；NFA与DFA的关键区别：NFA的不确定性：有ε状态转移；当前状态下，对同一字符有多于一个的下一状态转移；用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收

4、、回溯带来的问题；模拟DFA的算法（算法2.1）：用DFA识别记号。8<4>从正规式到词法分析器构造NFA的Thompson算法(算法2.2)：与正规式的对应关系；模拟NFA的“并行”算法（算法2.3）；从NFA构造DFA－子集法（算法2.5）：smove(S,a)与ε-闭包(T)的计算；DFA的最小化－可区分的概念：所有不可区分的状态看作是一个状态（算法2.6）；灵活运用各种方法构造DFA(正规式化简、状态转换图等)，特别是手工构造和算法构造的区别（考虑(a

5、b)*abb的NFA）。第三章语法分析语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译

6、模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即语法规则；根据语法规则识别输入序列（记号流）中的语言结构，即语法分析。语法分析的分析对象是组成语言的句子，句子具有层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法。主要内容<1>程序设计语言与文法<2>有关推导的基本概念<3>自上而下分析<4>自下而上分析10<1>程序设计语言与文法正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号(终结符)；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力；上下文

7、无关文法(CFG=(N,T,S,P))：CFG用于描述层次结构，如构成程序的句子；识别CFL的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；文法的分类：0型、1型、2型和3型文法词法分析器与语法分析器：FA与PDA11<2>有关推导的基本概念CFG产生语言的基本方法－推导：从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；（定义3.2、3.3、3.4）分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程(含有非终

8、结符)；(定义3.5、3.6)文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。(定义3.7)二义性的消除：改写二义文法为非二义文法；（两个关键步骤）对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。12<3>自上而下分析分析方法：推导，从上到下构造分析树，是一种预测的、试探的方法；对文法的要求：没有公共左因子和左递归左递归与直接左递归（定义3.9）消除直接左递归与左递归（算法3.1、3.2）提取公共左因子（类似于提取公因式）递归下降子程序方法：匹配终结符，展开非终结符（子程序

9、调用）13<3>自上而下分析（续）预测分析表方法:工作方式与过程：PDA（DPD