编译原理复习 (2).ppt

《编译原理复习 (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理期末总复习考试题型一．单项选择(2'×10=20')二．简答题(6'×3=18')三．自动机转换题(15')四．中缀式转化后缀式和四元式(6'×2=12')五．用DAG进行局部优化(10')六．综合题(25')编译原理总复习——知识要点第1章编译程序:compiler能将一种计算机高级语言程序(源语言程序)转换成另一种等价的计算机低级语言程序(目标语言程序)编译原理总复习编译程序工作过程的各个阶段：词法分析器语法分析器语义分析器源程序中间代码生成器代码优化器目标代码生成器目标程序出错管理器符号表管理器编译原理总复习第3

2、章文法G=（VN，VT，P，Z）VN：非终结符号集VT：终结符号集P：产生式或规则的集合Z：开始符号（识别符号）Z∈VN规范推导：即最右推导——若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最右非终结符进行替换。编译原理总复习文法G[Z]所产生的所有句子的集合文法G[Z]（1）句型：x是句型Zx,且x∈V*；**（2）句子：x是句子Zx,且x∈VT*；*（3）语言：L（G[Z]）={x

3、Zx，x∈VT*}；即：句型是由文法开始符号推导出来的由终结符和非终结符组成的符号串。即：句子是由文法开始符号推导出

4、来的由终结符组成的符号串。编译原理总复习给定文法，判断给定输入串是否为该文法的句子或句型。并指出该句子或句型的：短语简单短语句柄编译原理总复习第4章词法分析程序的主要任务：对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符，按照构词规则切分成一个一个具有独立意义的单词，并识别其正确性，再交给下一阶段进行语法分析。描述词法的机制是正则表达式识别机制是有穷状态自动机编译原理总复习为正规式(0

5、1)*0(0

6、1)构造一个等价的有穷自动机。将此自动机转换为确定自动机DFA。例：编译原理总复习SABCZ01εε001第5章语法

7、分析的主要工作：识别由词法分析给出的单词序列是否为给定文法的正确句子（程序）。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。编译原理总复习三个重要集合：First集Follow集Select集注：三种集合均为终结符集编译原理总复习SELECT(A→α)=(FIRST(α)－{ε})∪FOLLOW(A)，否则FIRST(α)，当αε时﹨*确定的自顶向下语法分析：要求文法必须是LL(1)文法LL(1)文法的判别若非终结符A的两个不同产生式，A→α,A→β；满足：SELECT(A→α)∩SELECT(A→β)=

8、Ф编译原理总复习第7章LR分析法前缀：一个符号串的前缀是指该串的任意首部（包括）。可归前缀：是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。活前缀：可归前缀的任意首部。编译原理总复习移进项目：A→.bβ其中b为终结符，可为待约项目：A→.Bβ其中B为非终结符，可为归约项目：A→.接受项目：S'→S.LR(0)分析和SLR(1)分析编译原理总复习分析法过程步骤：拓广文法G'：引起一个新的开始符号S'，且将S'→S作为第0个产生式添加到文法G中，并对所有产生式进行编号。构造识别活前缀的DFA。判断

9、是否存在移进－归约冲突或归约－归约冲突。若无冲突，则为LR(0)文法，构造LR(0)分析表；若有冲突，判断是否为SLR(1)文法编译原理总复习SLR(1)文法判定：存在如下项目集(状态)I:I={X→.b,A→.,B→.}其中b∈VTI中含有移进－归约和归约－归约冲突。若满足：FOLLOW(A)∩FOLLOW(B)∩{b}=Ф则为SLR(1)文法。编译原理总复习SLR(1)分析表的构造规则：(1)项目集Ii中若有形如A.X的项目，且有GO(Ii,X)=Ij,若X为一终结符号a时，则置ACTION[I,a]=Sj;若X为

10、一非终结符号时，则置GOTO[i,X]=j；(2‘)若有归约项目A→.属于Ii,设A→为文法第j个行产生式，则对任何属于FOLLOW(A)的输入符号a，置ACTION[i,a]=Rj；(3)若有接受项目S'→S.属于Ii,则置ACTION[i,#]=acc。(4)在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。编译原理总复习第8章语义分析的任务对于所写的源程序，在词法分析和语法分析的基础上，进一步分析其含义，在理解含义的基础上，为生成相应的目标代码做好准备或直接生成目标代码。语义描述方法——属性文法语义的处理方法

11、——语法制导翻译编译原理总复习属性文法——属性文法形式的定义为一个三元组AG，AG=（G，V，E）。其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描