《编译原理》重点知识总结.docx

《《编译原理》重点知识总结.docx》由会员分享，可在线阅读，更多相关《《编译原理》重点知识总结.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理重点知识总结（编译原理）知识点总结目录第一章引论第二章高级语言及其语法描绘第三章语法分析自上而下分析第四章属性文法和语法制导翻译第五章语义分析和中间代码产生第六章优化第一章引论一编译程序(compiler):把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序二编译程序的工作的五个阶段:词法分析、语法分析、中间代码产生、优化、目的代码产生1.词法分析任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描绘工具：有限自动机FORI:=1TO100DO保留字标识符等符整常数保留字整常数保留字2.语法分析任务:在词法

2、分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则述工具：上下文无关文法3.语义分析与中间代码产生任务:对各类不同语法范畴案语言的语义进行初步翻译。变量能否定义、类型能否正确等依循的原则：语义规则中间代码:三元式，四元式，逆波兰记号，树形构造等。是一种独立于详细硬件的记号系统。例：将Z:=X+0.618*Y翻译成四元式为(1)*0.618YT1(2)+XT1T2(3):=T2_Z4.优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目的代码。依循的原则：程序的等价变换规则FORK:=1TO100DOBEGINM:=I+10*K;N:=J

3、+10*K;END4.目的代码产生任务:把中间代码变换成特定机器上的目的代码。依靠于硬件系统构造和机器指令的含义目的代码三种形式:a)绝对指令代码:可直接运行b)可重新定位指令代码:需要连接装配c)汇编指令代码:需要进行汇编第二章高级语言及其语法描绘2.1.1语法词法规则：单词符号的构成规则。a)单词符号是语言中具有独立意义的最基本构造。一般包括：常数、标识符、基本字、算符、界符等。b)描绘工具：正规式和有限自动机语法规则：语法单位的构成规则。a)语法单位通常包括：表达式、语句、分程序、经过、函数、程序等;c)描绘工具：上下文无关文法2.1.2语义语义：一组规则，用它能够定义一个程序的意义。描

4、绘方法：a)自然语言描绘：隐藏错误、二义性和不完好性b)形式描绘：?无二义性?完好性多数语言中，算符的优先顺序如下：乘幂*或一元负-乘、除加、减关系符,=,非?，not与(，&，and)或(?,|,or,)隐含(或imp)等值或epui，或2.3程序语言的语法描绘1.几个概念:a)考虑一个有穷字母表字符集b)其中每一个元素称为一个字符c)上的字(也叫字符串)是指由中的字符所构成的一个有穷序列d)不包含任何字符的序列称为空字，记为e)用*表示上的所有字的全体,包含空字例如:设=a，b，则*=,a,b,aa,ab,ba,bb,aaa,.f)*的子集U和V的连接积定义为UVb|U&bV例如:设：Ua

5、,aa,Vb,bb那么：UV=ab,abb,aab,aabbg)V本身的n次积记为Vn=VVVh)规定V0=，令V*=V0V1V2V3称V*是V的闭包;记VVV*，称V+是V的正规闭包。例如:设：Ua,aa那么：U*=,a,aa,aaa,aaaa,U=a,aa,aaa,aaaa,i)0型(短语文法，图灵机)：产生式形如：其中：(VT?VN)*且至少含有一个非终结符；(VT?VN)*任何0型语言都是递归可枚举的。j)1型(上下文有关文法，线性界线自动机)：产生式形如：其中：|，仅S例外。意味着对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成空串。k)2型(上下文无关文法，非确定下推自动

6、机)：产生式形如：A其中：AVN；(VT?VN)*。非终结符的替换能够不必考虑上下文。l)3型(正规文法，有限自动机)：产生式形如：AB或A其中：VT*；A，BVN产生式形如：AB或A其中：VT*；A，BVN正规文法的能力要比上下文无关文法弱得多。四种类型描绘能力比拟m)上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT?VN=?S：文法的开场符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VT?VN)*开场符S至少必须在某个产生式的左部出现一次。例：文法G1(A)：Ac|AbG1(

7、A)的语言?解：L(G1)=c，cb，cbb，?，以c开始，后继若干个bn)定义：假如一个文法存在某个句子对应两颗不同的语法树，则讲这个文法是二义的。G(E)：Ei|E+E|E*E|(E)是二义文法。o)语言的二义性：一个语言是二义性的，假如对它不存在无二义性的文法。可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G)2.状态转换图a)概念：状态转换图是一张有限方向图。b)结点代表状态，用圆圈表示。c)状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。d)一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态3.正规运算符优先顺序在不致混

8、淆时，括号能够省去，但规定算符的优先顺序为：*闭包.连接|或4.3型文法-正规式G的任何产生式为AB或A其中：VT*；A，BVN3型文法等价于正规式，所以也称正规文法。3.3.2确定有限自动机(DFA)对状态图进行形式化，则能够下定义：自动机M是一个五元式M=(S,f,S,F),其中：a)S:有穷状态集，b)：输入字母表(有穷)，c)f:状态转换函数，为S?S的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。d)SS是唯一的一个初态；e)F?S：终态集(可空)。例如：DFAM=(0，1，2，3，a，b，f，0，3)，其中

9、：f定义如下：f(0，a)=1f(0，b)=2f(1，a)=3f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3f(3，b)=33.3.3非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,f,S,F)，其中：1S:有穷状态集；2：输入字母表(有穷)；3f:状态转换函数，为S?*2S的部分映射(非单值)；4S?S是非空的初态集；5F?S：终态集(可空)。从状态图中看NFA和DFA的区别：1弧上的标记能够是*中的一个字，而不一定是单个字符；2同一个字可能出如今同状态射出的多条弧上。DFA是NFA的特例。定义：对于任何两个有限自动机M和M，假如L(M

10、)=L(M)，则称M与M等价。自动机理论中一个重要的结论：断定两个自动机等价性的算法是存在的。对于每个NFAM存在一个DFAM，使得L(M)=L(M)。亦即DFA与NFA描绘能力一样。把上述NFA确定化采用子集法.设I是M的状态集的一个子集，定义I的-闭包-closure(I)为:i)若sI，则s-closure(I)；ii)若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I)即-closure(I)=I?s|从某个sI出发经过任意条弧能到达s例：设a是中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。3.3.4正

11、规文法与有限自动机的等价性定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)L(G)。2.对每一个FAM，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。3.3.5正规式与有限自动机的等价性定理：1.对任何FAM，都存在一个正规式r，使得L(r)=L(M)。2.对任何正规式r，都存在一个FAM，使得L(M)=L(r)。对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)3.3.6确定有限自动机的化简对DFAM的化简:寻找一个状态数比M少的DFAM，使得L(M)=L(M)假设s和t为M的两个状态，称

12、s和t等价:假如从状态s出发能读出某个字而停止于终态，那么同样，从t出发也能读出而停止于终态；反之亦然。两个状态不等价，则称它们是可区别的。对一个DFAM最少化的基本思想:把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。I(1)=0,1,2I(2)=3,4,5,6Ia(1)=1,3I(11)=0,2I(12)=1I(2)=3,4,5,6I(11)=0,2Ia(11)=1Ib(11)=2,5I(111)=0I(112)=2I(12)=1I(2)=3,4,5,6Ia(2)=3,6Ia(2)=

13、4,5第三章语法分析自上而下分析语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开场符号出发，反复使用各种产生式，寻找匹配的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反应和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。4.3LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克制回溯4.3.1左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP|其中不以P开始。我们能够把P的规则等价地改写为如下的非直

14、接左递归形式：PPPP|一般而言，假定P关于的全部产生式是PP1|P2|Pm|1|2|n其中，每个都不等于，每个都不以P开始那么，消除P的直接左递归性就是把这些规则改写成：P1P|2P|nPP1P|2P|mP|提取公共左因子:假定关于A的规则是A1|2|n|1|2|m(其中，每个不以开始)那么，能够把这些规则改写成AA|1|2|mA1|2|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。4.3.3LL(1)分析条件假定S是文法G的开场符号，对于G的任何非终结符A，我们定义.,.|)(*TVaAaSaAFOLLOW?=十分是，若AS?*，则规定FOLL

15、OW(A)构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A1|2|n则FIRST(i)FIRST(j)(ij)i=1,2,.,n3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(A)FOLLOW(A)=假如一个文法G知足以上条件，则称该文法G为LL(1)文法。第四章语法分析自下而上分析语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开场，逐步进行“归约，直到文法的开场符号。即从树末端开场，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符

16、优先分析法：根据算符的优先关系和结合性质进行语法分析。合适分析表达式。LR分析法：规范归约5.1.2规范归约1.定义：令G是一个文法，S是文法的开场符号，假定是文法G的一个句型，假如有且AS*?，+?A则称是句型相对于非终结符A的短语。十分是，假如有A?,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。2.归约采用“移进归约思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶构成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。5.2算符优先分析四则运算的优先规则：先乘除后加减，同级从左到右考虑二

17、义文法文法G(E)：G(E)：Ei|E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。假如规定算符的优先次序，并按这种规定进行归约，则归约经过是唯一的。起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串和进行归约。5.2.1算符优先文法及优先表构造一个文法，假如它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们讲：1.a=b当且仅当文法G中含有形如Pab或PaQb的产生式；2.ab当且仅当G中含有形如PRb的产生式，而R+?a或R+?aQ。假如一个算符文法G中的任何终结符对(a，b)至多只知足下述三关系之一：a=b，ab。则称G是一个算符优先文法。从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有知足a=b的终结符对。确定知足关系的所有终结符对：