编译技术-学习总结

1、编译技术第2章 ：词法分析1、 字符串的相关运算连接：x=”abc” y=”208” xy=”abc208”方幂：s=“a”， t=“b” (st)5(st)(st)(st)(st)(st)=“ababababab”2、 语言的运算LM（并）：L=a,b , M=1,6 , 求LM = a,b,1,6 LM（连接）：L=a,b , M=1,6 , 求LM = a,b1,6=a1, a6,b1,b6 L的方幂：L=a,bL3=a,ba,ba,b=aa,ab,ba,bba,b=aaa,aab,aba,abb,baa,bab,bba,bbbL的闭包：L的星闭包=> L* = L0L1L2Ln=

2、eLLLLLLLLLLL的正闭包=>L+ = L1L2Ln=LLLLLLLLLL LLLLL结论：L的星闭包表示零个或多个L连接的并集 ，L的正闭包表示一个或多个L连接的并集。3、 正规试定义：又称正规表达式，是字母表中字符串的集合，用来表示简单的语言，也叫做正规集。说明：一个正规式r 表示一个语言(r)正规式运算约定：优先级高到低依次为=>闭包>连接运算>选择运算，都为左结合如(a)(b)*)|(c )可以简化写成ab*|c 。正规式定义：设是字母表， r1 、r2 . ri是上的正规式，则正规定义是指将形式为d1 = r1 , d2 = r2 dn = rn 的正规

3、， d1 r1 ( 表示d1定义为r1的形式， d1是正规式的名字)， 读作“定义为”。 约定：正规定义中，用黑体字表示名字4、 状态图含义：又称转换图，用来识别源程序中各词法单元组成：一个开始状态-用圆圈表示；一个或多个终止状态(也称接受状态)-用双圆圈表示；连接各状态的边-用箭头表示；待识别的输入串中的符号-标于各边上。5、有限自动机含义：是一种数学模型，表现为状态转换图的形式，用来识别正规式所表达的语言，即用来识别正规式的识别器。不确定有限自动机(NFA)：确定有限自动机(DFA)：NFA到DFA的转换：（子集构造法）=> 令所构造的DFA在接受某输入字符串后所到达的状态是原NFA

4、在接受该输入字符串后能到达的所有状态的集合。(PPT-73)例：步骤：等价DFA的开始状态A，它等于原NFA的开始状态“0”经过转换后所得到的状态的集合 即 A = -closure(0)=0,1,2,4,7标记A：先计算A中的每个状态经过a 转换后所得到的状态的集合: move(A,a) ；再对该集合中每个状态求其转换后所得到的状态的集合，它们的并集就是DFA的新状态，设该新状态为B，move(A,a)=3,8 B= -closure(move(A,a)=-closure(3,8)=-closure(3)-closure(8)=1,2,3,4,6,78=1,2,3,4,6,7,8再计算A中的

5、每个状态经过b 转换后所得到的状态的集合: move(A,b) ；再对该集合中每个状态求其转换后所得到的状态的集合，它们的并集就是DFA的新的状态，设该新状态为C，同上，则C=1,2,4,5,6,7 C = -closure(move(A,b)接下来应对状态B、C进行标记，并分别计算它们在接受输入符号a、b后所能到达的状态集合，直到求得的DFA的所有状态都已标记过。标记B：move(B,a)=3,8，则其它同标记A 。e=> -closure(move(B,a) = B-closure(move(B,b) ，move(B,b)=5,9 D=-closure(5)-closure(9) =

6、1,2,4,5,6,79=1,2,4,5,6,7,9标记C:move(C,a)=3,8，同标记A。 e=> -closure(move(C,a) = B-closure(move(C,b) ，move(C,b)=5 move(C,b)= move(A,b) , C= -closure(move(A,b) 不必计算其转换，即：e-closure(move(C,b)=C标记D：move(D,a)=3,8，同上-closure(move(D,a)=B move(D,b)=5，同上-closure(move(D,b)=C说明：所有状态均已标记，再没有新的状态产生，到此构造过程结束。D含有原NFA

7、的一个接受状态“9”，因此，它是转换后DFA的终止状态-即新的DFA的状态集为A,B,C,D,其中，A为开始状态，D为接受状态。状态输入符号abABCBBDCBCDBC结论：识别一种语言的自动机有多个。第三章：语法分析1、上下文无关文法定义：上下文无关文法G是一个四元组(VT ,VN ,S,P )VT :终结符的集合；VN :非终结符的集合，且VT VN =Ø；S :是非终结符，称为开始符号；P :产生式的集合，产生式的形式 : A其中，AVN , (VT VN )* 终结符：是源语言的不可再分的基本符号，代表最小的语法单位-即词法记号非终结符：也称语法变量，代表一个语法概念产生式：

8、是定义语法变量构成元素的规则。(指定一个语法变量是由哪些元素构成的规则)文法的开始符号至少出现在某个产生式的左部2、 推导含义：指把文法符号串中的非终结符用其产生式右部的串来代替。表示方法：符号 “=>”表示直接推导例：文法符号串：A，将非终结A用其产生式：A中的右部符号串来替换，从而得到：，这个替换过程称为推导，表示为：A=。例：EE + E | E * E | (E ) |E | id ，写出句子(id + id)的推导过程E=>E=>(E)=>(E + E)=>(id + E)=>(id + id)符号“=>”表示“一步推导”， “=>*”

9、表示“零步或多步推导”，“=>+ ”表示“一步或多步推导”最左推导：指推导过程中每步都是替换句型中最左边的非终结符，记作=>lm 最右推导：也叫规范推导，指推导过程中每步都是替换句型中最右边的非终结符，记作=>rm 3、 相关概念上下文无关语言：指由上下文无关文法产生的语言。如文法G产生的语言记为L(G)。等价的文法：指两个能产生同样语言的文法。句型：对于开始符号为S的文法G，若：S=>*，可能含有非终结符，则叫做文法G的句型。句子：对于开始符号为S的文法G，若：S=>+w 且w是终结符串(wL(G)，则串w叫做文法G的句子。4、 语法分析树含义：指推导的图形表示

10、-其中每个内部结点由非终结符标记，它的子结点由该非终结符的这次推导所用的产生式的右部各符号从左到右依次标记。分析树的叶子结点由非终结符或终结符标记，所有叶子结点从左到右构成一个句型。二义性：指文法的一些句子存在不止一棵分析树，即这些句子存在不止一种最左或最右推导。说明=>可以通过重写产生式消除其二义性。5、 正规式上下文无关文法A，画出正规式的NFA 有正规式(a|b)*abB，将NFA按如下规则构造为上下文无关文法确定终结符集合：由上图可得a,b为每个状态i引入非终结符Ai:得A0, A1 , A2如果状态i有一个a转换到状态j,则引入产生式：Aia Aj ,若a =，则引入产生式：

11、AiAj 如果状态 i 是接受状态，则引入Ai=左递归文法：设A是文法的非终结符，对某个字符串a，若存在推导 A=>+Aa ，则该文法称为左递归文法。由产生式AAa 引起的左递归称为直接左递归消除左递归的方法：引入新的非终结符A，将左递归形式改写成右递归的形式即对于左递归产生式 AAa |b ，用下面两个产生式： Ab A，Aa A|来替换非直接左递归：SAa | b (1) ASd | (2)其中，非终结符是左递归的，但不是直接左递归，而是经两步推导得出的。消除非直接左递归：先变换成直接左递归，再消除。即用产生式(1)的右部代替产生式(2)右部的符号S，则得到： SAa | b AAa

12、d | bd | 再按消除直接左递归的方法来消除提左因子：是一种文法变换，用于将文法变成适于自上而下分析的文法例：A1|2，提出公因子，提左因子后变换为：AA A|6、形式语言的种类0型文法：也称短语文法，其产生式为:，其中,，(VN VT)*, 并且 a至少含1个非终结符1型文法：它是型文法的特例，即要求|，但S可以例外，且不得出现在产生式的右部 说明： 1型文法也称为上下文有关文法，其产生式的一般形式为：A，表示当A的上文为且下文为时才能把A替换成，因此称为上下文有关文法2型文法：它是型文法的特例，即要求产生式的左部是一个非终结符。其产生式的形式为：A，其中AVN ,(VN VT)* 说明

13、：也称为上下文无关文法，它不管A的上下文如何，就可以把A替换成，因此称为上下文无关文法3型文法：它是2型文法的特例，即其产生式的右部最多有两个符号，且具有下面形式之一：AaB 或Aa，其中，A, BVN , aVT 说明： 3型文法也称为正规文法 ，它与自动机等价。在程序设计中，通常用来描述词法单元7、 自上而下分析一般方法：对任何输入串，试图用一切可能的办法，从文法的开始符号，最左地推导出该输入串-即为输入串寻找最左推导 说明：通常，以文法的开始符号为根结点，自上而下，从左到右为输入串建立分析树。如果分析树的叶子结点从左到右恰好组成输入串，则表明分析成功缺点：不能处理左递归：使分析过程陷入无

14、限循环；当非终结符的选择出错时，需要使用复杂的回溯技术；由于回溯，导致已做好的语义工作推倒重来；由于回溯，分析串难以报告输入串出错的确切位置。FIRST ()：指文法的符号串的开始符号的集合。符号串的开始符号指组成的第一个符号，它是终结符。FIRST集合构造方法： 若有产生式Xa，且aVT ，则把a加入到FIRST(X)中；若存在X，则将也加入到FIRST(X)中 若有XY，且YVN，则将FIRST(Y)中的所有非元素(记为“”)都加入到FIRST(X)中；若有XY1Y2Yk，且Y1Yi1都是非终结符，而Y1Yi1的候选式都有存在，则把FIRST(Yj)的所有非元素都加入到FIRST(X)中(

15、j=1,2,i)；特别是当Y1Yk均含有产生式时，应把也加到FIRST(X)中FOLLOW(A) ：指产生式右部非终结符A的后继符号a的集合，它是紧接在非终结符A后面的一个终结符。若S=>* A，则FOLLOW(A)，是输入串结束符。FOLLOW集合的构造方法： 对文法开始符号S，置#于FOLLOW(S)中(由语句括号“#S#”中的S#得到)。若有AB(可为空)，则将FIRST()加入到FOLLOW(B)中。 若有AB或AB，且=>* (即 FIRST()，则把FOLLOW(A)加到FOLLOW(B)中(此处的也可为空)。8、 递归下降的预测分析法含义：指为每一个非终结符编写一个确

16、定用哪个选择的分析程序，由于文法的定义是递归的，因此这些分析程序也是递归的（预测：指根据当前的输入符号，为非终结符确定用哪一个选择）。9、 非递归的预测分析法基本思想：根据输入串的当前输入符号，确定用哪个产生式推导：即当此输入符号是某产生式右部的第一个符号时，就选用该产生式；然后再取输入串的下一个符号，继续用此方法选择应该用的产生式，如此重复，直到推导出被分析的输入串为止。组成：一个输入缓冲区：存放待分析的输入串；一个栈：存放文法的符号串，栈底符号是$；分析表：对某个非终结符，当面临特定输入符号时，决定选择哪个产生式；预测分析程序：根据当前的栈顶符号和所面临的输入符号，决定分析器的动作。预测分

17、析程序的构造方法：（1）若栈顶符号X=a=$，则说明分析成功并停机；（a是当前输入符）（2）若栈顶符号X=a$,则分析器弹出栈顶符号X，并推进输入指针指向下一个输入符号。（3）若栈顶符号X是终结符但不等于a , 则说明当前产生式的选择是错误的。因此，分析器报告出错，并调用错误管理程序。(4) 若栈顶符号X是非终结符, 则访问分析表M，若MX,a是X的产生式，例如，MX,a=XUVW,则从栈中弹出X，再依次将W、V、U压栈，并让U在栈顶，且输入指针不移动。若MX,a为空白，则表明出错，即非终结符X不能面临输入符号a ，则调用错误管理程序。(5)重复此过程，至栈中只剩符号$ 。预测分析表的构造：（

18、1）对文法的每个产生式A，执行(2)和(3)；（2） 对FIRST(）的每个终结符a，把A加入到MA, a中。（3） 如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A加入 到MA, b中。（4）M中没有定义的条目都是error，用空白表示。10、 自下而上分析说明：又称为移进归约分析。常用的分析方法是LR分析法，其中指从左向右扫描输入串即移进；指构造输入串最右推导的逆过程- 即最左归约，也称规范归约，简称归约。句型：对于开始符号为S的文法G，若： S=>*且可能含有非终结符，则叫做G的句型。规范句型：指用最右推导得出的句型，也称右句型句子：对于开始符号为S的文法G，若 S=>+ w且w是终结符串(wL(G)，则串w叫做文法G