《编译原理》复习要点

1、学习好资料欢迎下载考试安排：7月13日（20周周三），15:00-17:00,20208填空10X1分、选择10X2分、简答4X5分、大题5X10分考试大题：循环优化LL（1）.定义之类的算符优先算法自下而上分析法（20分，选择、填空、大题）第一章引论一.编译程序（compiler）:（如汇编语言或机器语言程序）把某一种高级语言程序等价地转换成另一种低级语言程序的程序.编译程序的工作的五个阶段：1.词法分析、语法分析、中间代码产生、优化、目标代码产生词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机FOR I1 TO 1

2、00 DO2.保留字标识符等符整常数保留字整常数保留字语法分析任务：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。3.依循的原则：语法规则述工具：上下文无关文法语义分析与中间代码产生任务：对各类不同语法范畴按语言的语义进行初步翻译。（变量是否定义、类型是否正确等）依循的原则：语义规则中间代码：三元式，四元式，逆波兰记号，树形结构等。是一种独立于具体硬件的记号系统。例:Z:=X + 0.618 * Y(2)0.618XT1(3):=T2翻译成四元式为T1T24.优化任务:对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规

3、则FORK:=1TO100DOBEGINM:=I+10*K;N:=J+10*K;END4.目标代码产生任务：把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式：a） b） c） 编译程序结构编译程序总框绝对指令代码：可直接运行可重新定位指令代码：需要连接装配汇编指令代码：需要进行汇编（简答题5分）第二章高级语言及其语法描述2.1.1 语法词法规则：单词符号的形成规则。a）单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。b）描述工具：正规式和有限自动机语法规则：语法单位的形成规则。a）语法单位通常包括：表达式、语句、分

4、程序、过程、函数、程序等；c）描述工具：上下文无关文法2.1.2 语义语义:一组规则，用它可以定义一个程序的意义。描述方法：a）自然语言描述：隐藏错误、二义性和不完整性b）形式描述：无二义性完整性多数语言中，算符的优先顺序如下：乘哥（*或T）一元负（-）乘、除力口、减关系符（<,=,>,<=,>=,<>）非（？，not）与（A,&,and）或（？,®）隐含（或imp）等值（或epui,或2.3程序语言的语法描述1.几个概念：优先级由高自低不同的语言对算符优先级的规定有差异，甚至差异很a）考虑一个有穷字母表汇字符集b）其中每一个元素称为一个空

5、跳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

6、,aaaa,i）0型（短语文法，图灵机）：产生式形如：atP其中：心（Vt=Vn）*且至少含有一个非终结符；Pw（VtuVn）*任彳510型语言都是递归可枚举的。j）1型（上下文有关文法，线性界限自动机）：产生式形如：3TB其中：|豆|<|和，仅ST8例外。意味着对非终结符进行替换时务必考虑上下文,并且，一般不允许替换成空k） 2型（上下文无关文法，非确定下推自动机产生式形如：AtP其中：AWVn；pw（Vt2Vn）*。非终结符的替换可以不必考虑上下文。l） 3型（正规文法，有限自动机）：产生式形如：Ato（B或Ata其中：aWVt*;aB三Vn右线性文法左线性文法产生式形如：ATBot

7、或At其中：«Vt*;aBeVn正规文法的能力要比上下文无关文法弱得多。四种类型描述能力比较m)上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(Vt,Vn,S,P),其中Vt：终结符集合(非空)VN：非终结符集合(非空)，且VtCV诲S:文法的开始符号，SVnP:产生式集合(有限)，每个产生式形式为*P-jot,PEVn,a(Vt=Vm)开始符S至少必须在某个产生式的左部出现一次。例：文法G(A):Atc|AbG(A)的语言？解：L(Gi)=c,cb,cbb,以c开头，后继若干个bn)定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E):Et

8、i|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型文

9、法等价于正规式，所以也称正规文法。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的一个后继状态。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,

10、b)=2f(2,a)=1f(2,b)=33.3.3 非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,I,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等价。自动机理论中一个重要的结论：判定两个

11、自动机等价性的算法是存在的。对于每个NFAM存在一个DFAM,使得L(M尸L(M')。亦即DFA与NFA描述能力相同。把上述NFA确定化一一采用子集法.设I是M的状态集的一个子集，定义I的*闭包&closure(I)为：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弧而到达

12、的状态集合。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

13、 正规式与有限自动机的等价性定理：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的两个状态，称s和t笠化：如果从状态s出发能读出某个字a而停止于终态，那么同样，从t出发也能读出a而停止于终态；反之亦然。两个状态不等价，则称它们是可区别的。对一个DFAM最少化的基本思想：把M的状态集划分为一些不相交的子集，使得任何两个不同子集

14、的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。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)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配”的推导。递归下降分析法：对每一语法变量(非终结

15、符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。3.3.7 LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯4.3.1 左递归的消除P的规则为直接消除见诸于产生式中的左递归：假定关于非终结符P*-P|:其中P不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：左递归变右递归-PP,P;一般而言，假定P关于的全部产生式是PP|P停|.IPOtm|阳均Ipn其中，每个a都不等于&每个沸B不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P-

16、PlP1P|PnP*p“p|ei|sPs提取公共左因子：假定关于A的规则是(其中，每个Y不以M头)Af那1|郤2|邵n|71|飞2|臣那么，可以把这些规则改写成Z於'|X|丁2|YmA*1p1|p2|pn经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。4.3.3LL(1)分析条件假定S是文法G的开始符号，对于G的任何非终结符A,我们定义*FOLLOWA)=a|S=.Aa.,aVT*特别是，若s=,A,则规定#WFOLLOW(A)构造不带回溯的自上而下分析的文法条件1 .文法不含左递归，2 .对于文法中每一个非终结符A的各个产生式的候选首符集两两

17、不相交。即，若Za11a21,|an则FIRST(ai)nFIRST(o(j)=©(i却i=1,2,.,n3 .对文法中的每个非终结符A,若它存在某个候选首符集包含；，则FIRST(A)AFOLLOW(A)=如果一个文法G满足以上条件，则称该文法G为LL(1)文法。第五章语法分析一一自下而上分析语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：

18、规范归约5.1.2规范归约1 .定义：令G是一个文法，S是文法的开始符号，假定口的是文法G的一个句型，如果有*且SnaASA=P则称口是句型口的相对于非终结符A的短语。特别是，如果有,则称B是句型oP而寸于规则jp的直接短语。一个句型的最左直接短语称为该句型的句柄。2 .归约采用“移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出枝，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(组约_为)该产生式的左部符号。5.2算符优先分析四则运算的优先规则：先乘除后加减，同级从左到右考虑二义文法文法G(E):G(E):Eti|E+E|E-E|E*

19、E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系寻找“M归约串”和进行归约。5.2.1 算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR-则我们称该文法为算符文法。约定：a、b代表任意终结符；P、QR代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。假定G是一个不

20、含承产生式的算符文法。对于任何一对终结符a、b,我们说：1. a=b当且仅当文法G中含有形如ab或PaQb的产生式；+2. a<b当且仅当G中含有形如4aR的产生式，而R=b或产Qb；+3. a>b当且仅当G中含有形如4Rb的产生式，而R=-a或1-aCl如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一：a=b,a<b,a>bo则称G是一个算符优先文法。从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足a=b的终结符对。确定满足关系<和>的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRS

21、TVT(P)和LASTVT(P):+FIRSTVT(P)=a|P=a，P=Qa,aVTQVN+a<b当且仅当G中含有形如P一aR的产生式，而-b或Qb1+LASTVTP)=a|Pna,或PnaQ,awVT而QwVN+a>b当且仅当G中含有形如FRb的产生式，而R=-a或2-aCl有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和>的所有终结符对。假定有个产生式的一个候选形为aP-那么，对任何bwFIRSTVT(P)，有a<b。假定有个产生式的一个候选形为Pb-那么，对任何aWLASTVT(P),有a>b。按其定义，可用下面两条规则来构造集合FIRS

22、TVT(P):1 .若有产生式a或-Qa,则awFIRSTVT(P);2 .若aWFIRSTVT(Q),且有产生式-Q-,则aWFIRSTVT(P)。练习：P133-2计算它的FIRSTVT和LASTVT计算G的优先关系。并确定G是否是一个算符优先文法？唯一确定每一步工作LR分析器的核心是一张分析表：ACTIONS,a：当状态s面临输入符号a时，应采取什么动作GOTOS,X:状态s面对文法符号X时，下一状态是什么文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目例：如：AtXYZ有四个项目：a>.xyza-；x.yza-；xy.za_；xyz.f.称为"归约项目&quo

23、t;归约项目S'TX.称为“接受项目"i.aP(a三Vt)称为"移进项目"A-jot.BP(BWVn)称为"待约项目".例：文法G(S)SEE一aA|bBZcA|dB一cB|d该文法的项目有：1.SjE2.SE-3.E一aA4.EfaA5.aA6.KcA7.Zc-A8.ZcA9.Z-d10.Kd-11.EfbB12.bB13.E-bB14.BfcB15.BfcB16. BfcB-17.B-d18.B-d-构造识别文法所有活前缀的NFA方法1. 若状态i为XXXi-1.XiXn,状态j为-X1Xi-1X.Xi+1Xn,则从状态i画一条标志

24、为Xi的有向边到状态j;2. 若状态i为Xr.AP,A为非终结符，则从状态i画一条也到所有状态j工把识别文法所有活前缀的NFA确定化。4: A-c-A A*l<AA2: FAcAA * <13 Erb BAd0: £ jRE nAE-v bBt Si B- -c bB-k rB B-r-dA11: B-*(l 想别活前攀的构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。LR(0)分析表的构造假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况：1) 既含移进项目又含归约项目，2) 含有多个归约项目则称G是一

25、个LR(0)文法。分析表的ACTIONS口GOTO?表构造方法：1 .若项目A-口邛属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTIONk,a为“sj”。2 .若项目Afa属于屋，那么，对任何终结符a(或结束符#),置ACTIONk,a为“rj”(假定产生式A-a是文法G的第j个产生式)。3 .若项目S-S属于Ik,则置ACTIONk,#为“acc”。4 .若GO(Ik,A)=Ij,A为非终结符，则置GOTOk,A=j。5 .分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。M卬2)弁新在ACTIONgotc状恁Abc<1*EA(1s21_J1acc12s4sl(&

26、gt;63all7J4s4slO815s5slli6rlrlrlrlrl71r2r2r2r2r28i'3r3rJr3r39r5r5r5r-5f510r4r4r4r4r4111161-61616d1按上述方法构造出的ACTIONGOTOB口果不含多重入口，则称该文法为SLR文性。使用SLR表的分析器叫做一个SLR分析器。每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的.这个文嶷的LR0哪4臬机龟臻为;Io：S'E及FTE)I7：T-T*F豆E->E+T甘一HEE1，TEfTIFiI1、I2和I9都含有“移进归约”冲突。FOLLOW(E)=#,),+

27、I;:r一 I 25.3.4规范LR分析表的构造我们需要重新定义项目，使得每个项目都附带有k个终结符。每个项目的一般形式是A-crP,aia2-ak，这样的一个项目称为一个LR(k)项目。项目中的aia2叽称为它的向前搜索符串(或展望串)。向前搜索符串仅对归约项目A-ot,aia2”有意义。对于任何移进或待约项目A一ct,P,aia2ak,隹令,搜索符串aia2ak没有作用。按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。使用这种分析表的分析器叫做一个规范的LR分析器。具有规范的LR(1)分析表的文法称为一个LR(1)文法。LR

28、(1)状态比SLR多，LR(0)cSLR=LR(1)心无二义文法。第六章属性文法和语法制导翻译6.1属性文法属性文法(也称属性翻译文法)在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的“值”(称为星匡)。属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等属性可以进行计算和传递语义规则:对于文法的每个产生式都配备了一组属性的计算规则属性综合属性：“自下而上”传递信息继承属性：“自上而下”传递信息综合属性在语法树中，一个结点的综合属性的值由其子结点的属性值确定。使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值仅仅使用综合属性的属性文法称S-属性文法

29、继承属性在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下文依赖关系很方便6.2.3一遍扫描的处理方法一遍扫描的处理方法是在语法分析的同时计算属性值所采用的语法分析方法属性的计算次序L一属性文法适合于一遍扫描的自上而下分析S-属性文法适合于一遍扫描的自下而上分析6.4L-属性文法和自顶向下翻译通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值LL(1):自上而下分析方法，深度优先建立语法树第七章语义分析和中间代码产生静态语义检查类型检查控制流检查一致性检查相关名字检查名字的作用域分析7.1中间语言常用的中间语言：后缀式，

30、逆波兰表示图表示：DAG抽象语法树三地址代码四元式间接三元式逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。7.4布尔表达式的翻译布尔表达式的两个基本作用：用于逻辑演算，计算逻辑值；用于控制语句的条件式.产生布尔表达式的文法：Ef E or E | E andE |一E | (E) | i rop i | ia<borc<dande<f1OO(j%a,b,0)*101

31、也102)102(j<pc,d,104)1030.、0)104(j*aet£100)tru#list105Or103)Iselis第十章优化优化:对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。等价:指不改变程序的运行结果。有效:指目标代码运行时间短，占用的存储空间小。Ij,口:藕译者靖！*代码优化春*毓玲后端ijflI!_,_-_L一一i建制洗介析谨分析代科正兼2*10.1 概述优化的三个不同级别：局部优化循环优化全局优化优化的种类：删除多余运算（或称删除公用子表达式）代码外提强度消弱变换循环控制条件合并已知量复写传播删除无用赋值10.2 局部优化局限

32、于基本块范围内的优化称为基本块内的优化,或称局部优化。在一个基本块内通常可以实行下面的优化：删除公共子表达式删除无用赋值合并已知量临时变量改名交换语句的位置代数变换划分四元式程序为基本块的算法：1.求出四元式程序中各个基本块的入口语句：1）程序第一个语句，或2）能由条件转移语看或无条件转移语句转移到的语句，或附明|1) X由 ITHfl Y3）紧跟在条件转移语句后面的语句。（l）rrmlX（2）rea.YR:-XmodYifR=O|Mb（8）X:=V（4）Y:=R静1。（J）画vHteYhull10.3循环优化对循环中的代码，可以实行：代码外提强度消弱删除归纳变量（变换循环控制条件）循环展开循环合并10.3.1 代码外提循环不变运算：对四元式A:=BopC,若B和C是常数，或者到达它们的B和C的定值点都在循环外。所谓变量A在某点d的定值到达另一点u（或称变量A的定值点d到达另一点u）,是指流图中从d有一通路到达u且该通路上没有A的其它定值。d:A:=BopCu:D:=AopE把循环不变运算提到循环体外。PlI。）】尸】*=1r】的TM+TiTrflddr(A) IIT-