《编译原理》复习要点

1、学习好资料欢迎下载考试安排：7月13日（20周周三），15:00-17:00,20208填空10X1分、选择10X2分、简答4X5分、大题5X10分考试大题：循环优化LL（1）.定义之类的算符优先算法自下而上分析法（20分，选择、填空、大题）第一章引论一.编译程序（compiler）:（如汇编语言或机器语言程序）把某一种高级语言程序等价地转换成另一种低级语言程序的程序.编译程序的工作的五个阶段：1.词法分析、语法分析、中间代码产生、优化、目标代码产生词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机FOR I1 TO 100 DO2.保留字标识符等符整常数保留字整常数保留字语法分析任务：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。3.依循的原则：语法规则述工具：上下文无关文法语义分析与中间代码产生任务：对各类不同语法范畴按语言的语义进行初步翻译。（变量是否定义、类型是否正确等）依循的原则：语义规则中间代码：三元式，四元式，逆波兰记号，树形结构等。是一种独立于具体硬件的记号系统。例:Z:=

2、X + 0.618 * Y(2)0.618XT1(3):=T2翻译成四元式为T1T24.优化任务:对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则FORK:=1TO100DOBEGINM:=I+10*K;N:=J+10*K;END4.目标代码产生任务：把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式：a） b）c）编译程序结构编译程序总框绝对指令代码：可直接运行可重新定位指令代码：需要连接装配（简答题5分）汇编指令代码：需要进行汇编2.1.1 语法词法规则：单词符号的形成规则。a）单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。b）描述工具：正规式和有限自动机语法规则：语法单位的形成规则。a）语法单位通常包括：表达式、语句、分程序、过程、函数、程序等；c）描述工具：上下文无关文法2.1.2 语义语义:一组规则，用它可以定义一个程序的意义。描述方法：a）自然语言描述：隐藏错误、二义性和不完整性b）形式描述：无二义性完整性多数语言中，算符的优先顺序如下：乘

3、哥（*或T）一元负（-）乘、除力口、减关系符（,=,）非（？，not）与（A,&,and）或（？,）隐含（或imp）等值（或epui,或2.3程序语言的语法描述1.几个概念：优先级由高自低不同的语言对算符优先级的规定有差异，甚至差异很a）考虑一个有穷字母表汇字符集b）其中每一个元素称为一个空跳c）汇上的空（也叫字符串）是指由汇中的字符所构成的一个有穷序列d）不包含任何字符的序列称为空字，记为e）用汇*表示汇上的所有字的全体，包含空字例如：设汇=a,b,则汇=e,a,b,aa,ab,ba,bb,aaa,f）汇*的子集U和V的连接（积）定义为UV=ab|aWU&bV例如：设：U=a,aa,V=b,bb那么：U=ab,abb,aab,aabbg）V自身的n次积记为V=W-Vh）规定V0=3，令V*=V0uVuV2uMu称v*是v的闭包；记v+=vV,称V是v的正规闭包。例如：设：U=a,aa*那么：U=z,a,aa,aaa,aaaa,U=a,aa,aaa,aaaa,i）0型（短语文法，图灵机）：产生式形如：atP其中：心（Vt=Vn）*且至少含有一个非终结符；Pw（VtuVn）*任彳510型

4、语言都是递归可枚举的。j）1型（上下文有关文法，线性界限自动机）：产生式形如：3TB其中：|豆|和，仅ST8例外。意味着对非终结符进行替换时务必考虑上下文,并且，一般不允许替换成空k） 2型（上下文无关文法，非确定下推自动机产生式形如：AtP其中：AWVn；pw（Vt2Vn）*。非终结符的替换可以不必考虑上下文。l） 3型（正规文法，有限自动机）：产生式形如：Ato（B或Ata其中：aWVt*;aB三Vn右线性文法左线性文法产生式形如：ATBot或At其中：值wVt*;aBeVn正规文法的能力要比上下文无关文法弱得多。四种类型描述能力比较m)上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(Vt,Vn,S,P),其中Vt：终结符集合(非空)VN：非终结符集合(非空)，且VteV诲S:文法的开始符号，SVnP:产生式集合(有限)，每个产生式形式为*P-jot,PEVn,a(Vt=Vm)开始符S至少必须在某个产生式的左部出现一次。例：文法G(A):Atc|AbG(A)的语言？解：L(Gi)=c,cb,cbb,以c开头，后继若干个bn)定义：如果一个文法存在某个句子对应两颗不同的语

5、法树，则说这个文法是二义的。G(E):Eti|E+E|E*E|(E)是二义文法。o)语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G,一个为二义的，一个为无二义的。但L(G尸L(G)2.状态转换图a)概念：状态转换图是一张有限方向图。b)结点代表状态，用圆圈表示。c)状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。d)一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态3 .正规运算符优先顺序在不致混淆时，括号可以省去，但规定算符的优先顺序为:*(闭包).(连接)|(或)4 .3型文法-正规式G的任何产生式为AttxB或Ata其中：“WVt*；aB三Vn3型文法等价于正规式，所以也称正规文法。3.3.2 确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,f,So,F),其中:a) S：有穷状态集，b) I：输入字母表(有穷)，c) f:状态转换函数，为SmtS的单值部分映射，f(s,a尸s表示：当现行状态为s,输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继

6、状态。d) SoWS是唯一的一个初态；e) F三S:终态集(可空)。例如：DFAM=(0,1,2,3,a,b,f,0,3),其中：f定义如下：f(0,a)=1f(0,b)=2f(1,a)=3f(1,b)=2f(2,a)=1f(2,b)=33.3.3 非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,工f,So,F)，其中：1 S:有穷状态集；2工：输入字母表(有穷)；3 f:状态转换函数，为SxfT2s的部分映射(非单值)；4 S0=S是非空的初态集；5 F=S:终态集(可空)。从状态图中看NFA和DFA的区别：1 弧上的标记可以是工中的一个字，而不一定是单个字符；2 同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。定义：对于任何两个有限自动机M和M,如果L(M)=L(M),则称M与M等价。自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。对于每个NFAM存在一个DFAM,使得L(M尸L(M)。亦即DFA与NFA描述能力相同。把上述NFA确定化一一采用子集法.设I是M的状态集的一个子集，定义I的*闭包&closure(I)

7、为：i) 若sI,贝Usw&-closure(I);ii) 若sWI,则从s出发经过任意条源而能到达的任何状态s都属于-closure(I)即&closure(I)=I=s|从某个s=I出发经过任意条飙能到达s例：设a是工中的一个字符，定义Ia=&closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。XA1544匿乩1(5S4A1A)5,241,6,Y)0,6,1,5,3,115,2J,6,Y5315434AV爆 363Y(5361Y)(SJJ.IAVIMJJ- 5.4,1. (524,1,A,Y) 5d,1小E&L&J041,6.V；“1V)13136630 12 3 4 5 63.3.4正规文法与有限自动机的等价性定理：1. 对每一个右线T正规文法G或左线性正规文法G,都存在一个有限自动机(FA)M,使得L(M)=L(G)。2.对每一个FAM,都存在一个右线性正规文法号和左线性正规文法G,使得L(M)=L(Gr)=L(Gl)。3.3.5 正规式与有限自动机的等价性定理：1 .对任何FAM,都存在一个正规式r,使得L(r尸L(M)。2 .对任何正规式r,都存在

8、一个FAM,使得L(M)=L(r)。对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)3.3.6 确定有限自动机的化简对DFAM的化简：寻找一个状态数比M少的DFAM,使得L(M)=L(M)假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字而停止于终态，那么同样，从t出发也能读出a而停止于终态；反之亦然。两个状态不等价，则称它们是可区别的。对一个DFAM最少化的基本思想：把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。1(1) =0, 1,2 I 出=3, 4, 5, 6Ia(1) =1,3I(11)=0,2I(12)=1I平,4,5,6I(11)=0,2Ia(11)=1Ib(11)=2,5I(111)=0I(112)=2I(12)=1I出=3,4,5,6Ia(2)=3,6I2出=4,5第四章语法分析一一自上而下分析语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。3.3.7 LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯4.3.1 左递归的消除P的规则为直接消除见诸于产生式中的左递归：假定关于非终结符P*-P|:其中P不

《《编译原理》复习要点》由会员壹****1分享，可在线阅读，更多相关《《编译原理》复习要点》请在金锄头文库上搜索。