编译原理重点

1、编译原理什么是编译程序？编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。编译的各个阶段什么是文法？文法是以又穷的集合刻画无穷的集合的一个工具。1、字母表:它是非空有穷集。 例如：=a,b,c或=1,2,32、符号：字母表中的元素称为符号。3、符号串：符号的有穷序列，符号串也称为字。用来表示空符号串。例如：a,ab,abc4、长度：符号串的长度是指该串所包含的符号个数。用|x|表示符号串x的长度。例如：|a|=1，|abn|=35、连结：设x和y为符号串，则称xy 为他们的连结。 例如：x=aa,y=bb,则xy=aabb6、空集：不含任何元素的集合,记为

2、F。7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。A=a,b,B=c,d,则AB=ac,ad,bc,bd8、方幂：设A为符号串集，则定义 A0= A1=A An=An-1 A 例如：A=a,b 则有： A0= A1=a,b A2=aa,ab,ba,bb9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下： A+=A1A2A3¼ 例如：A=a,A+=a,aa,aaa,10、星闭包：设A为一集合，则定义A的星闭包为A* ，其具体定义如下A*=A0A+ 例如：A=a,A*=,a,aa,aaa, 文法G定义为四元组(VN，VT，P，S )其中VN为非终结符号(或语法实

3、体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合； VN，VT和P是非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表例 文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号推导：用若干次产生式可从x串导出y串，则称y为x的推导，记为xy。直接推导：用一次产生式可从x导出y，则称y为x的直接推导，并记为xÞy。星推导:x y(当且仅当x=y或xy)。句型：由初始符推出的任意符号集合。

4、句子：不包含非终结符的句型。最左推导：推导的每一步都是对最左非终结符进行替换。最右推导（规范推导）：推导的每一步都是对最右非终结符进行替换。所得句型称为规范句型。0型文法(短语结构文法):产生式为：，其中和是符号串。1型文法(上下文有关文法)：产生式：Au，其中AVN，u为非空串。 2型文法(上下文无关文法): A，其中AVN，为非空串。3型文法(正则文法):产生式为：Aa,AbB,其中A,BVN, #a,bVT是符号串。四种文法包含关系：0型文法1型文法2型文法3型文法二义性文法:一个文法存在某个句子使得它有两棵语法树。例G:EE+E|E*E|(E)|i 将词法分析从语法分析部分独立出来的原

5、因1、使整个编译程序的结构更简洁、清晰、条例化2、改进编译效率3、增加编译系统的可移植性 例4.2.1: 令S=a,b,则S上的正规式和相应正规集为(1) a(1) a(2) a½b(2) a,b(3) ab(3) ab(4) (a½b)(a½b)(4) aa,ab,ba,bb(5) a *(5) e ,a,aa, 任意个a的串(6) (a½b)*(6) e ,a,b,aa,ab,bb 所有由 a和b组成的串(7) (a½b)*(aa½bb)(a½b)* (7) S*上所有含有两个相继的a或两个相继的b组成的串正规式正规文法

6、、正规文法正规式转换规则：正规产生式正规文法正规文法正规产生式A=xyAxB, ByAxB, ByA=xyA=x*yAxB, Ay, BxB, ByAxA|yA=x*yA=x|yAx, AyAx, AyA=x|y例4.2.4:将GS转换为正规式SaASaAaAAdAAaAd解：由文法GS得S=aA|aA=(aA|dA)|(a|d)则S= a(a|d)*(a|d)|a = a(a|d)*(a|d)| e) = a(a|d)*一个确定的有穷自动机（DFA）M是一个五元组: M= (K, f, S, Z), 其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个

7、输入符号，也称为输入符号表；3. f是转换函数，是在K×K上的单值映射，即如存在f(ki, a)=kj, (kiK,kjK) ，则当前状态为ki且输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4. SK是唯一的一个初态；5. ZÌ K是一个终态集，终态也称可接受状态或结束状态。1. 状态集合I的-闭包，记为-closure(I)，定义为一状态集，是由状态集I中的任何状态S经任意条弧而能到达的状态所构成的集合。状态集合I的任何状态都属于-closure(I)。2. 状态集合I的a弧转换，记为move(I,a)，是所有那些可从I中的某一状态经过一条a弧

8、而到达的状态的全体。右图中D、E、F、G为等价状态，可化简为一个状态。通过正规式构造NFA：例4.4.1构造出与正规式R=(a)*(|bb)(a|b)*等价的NFA。正规文法和又穷自动机的等价性：计算FIRST集：1、 若xVT，则FIRST（x）=x2、 若XVN，且有产生式Xa.，aVT则把a加入FIRST（X）集中；若X是一条产生式，则把也加入到FIRST（X）集中3、 若XY.是一条产生式且YVT，则把FIRST（Y）中所有非元素加入到FIRST（X）集中4、 若XVN；Y1，Y2，YiVN，且有产生式XY1 Y2 Yn；当Y1 Y2 Yi-1都时，(其中1in)，则FIRST(Y1)

9、、FIRST(Y2)、FIRST(Yi-1)的所有非空元素和FIRST(Yi)都包含在FIRST(X)中。当(4)中所有Yi,(i=1,2,n)，则FIRST(X)=(FIRST(Y1) ） （FIRST(Y2) ）（FIRST(Yn) ） 5、反复使用上述(2)(5)步直到每个符号的FIRST集合不再增大为止。计算FOLLOW集：对文法中每一 AVN 计算 FOLLOW(A)1、 设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#” 为句子括号)。2、 若AB是一个产生式，则把FIRST()的非空元素加入FOLLOW(B)中。如果则把 FOLLOW(A)也加入FOLLOW(B)中。

10、反复使用2直到每个非终结符的FOLLOW集不再增大为止LL(1) 文法的定义:一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A, A,满足SELECT(A)SELECT(A)= ，其中，不同时能例1：判断下列文法是否是LL(1)文法G：SaA Sd AbAS A解： select(SaA)=a； select(Sd)=d ；select (SaA) select(Sd)=Ø select(AbAS)=b；select(A) =First()-Follow(A) =Follow(A)=a,d,#； select (AbAS) select(A )

11、=Ø所以，该文法是LL（1）文法。例2：非LL(1)文法到LL(1)文法的等价转换：1、提取左公共因子2、消除左递归例 G：SSaSb可改写为：SbSSaS|LR(0)文法：例 GS: S ®a A c B e A ®b A ®Ab B ®d 1)构造识别活前缀的DFA 2)构造它的LR(0)分析表。 3)分别给出对输入符号串abbcde和Abbce的LR(0)分析步骤。解：GS拓广为: S ® S S ®a A c B e A ®b A ®Ab B ®d对输入串abbcde#的分析过程对输入串

12、abbce#的分析过程SLR(1)文法：例1：SAa.bBc设：FOLLOW(A)=a，FOLLOW(B)c Ad. 所以：FOLLOW(A)FOLLOW(B)=f, Be. FOLLOW(A)b=f； FOLLOW(B)b=f所以本文法是SLR(1)文法。例2：文法缩写后并拓广为G如下： 1.SS 2.SrD 3.DD,i 4.Di得图如右图：follow(S)=follow(S)=#follow(S),=#,=满足上述条件则可利用SLR(1)方法。转化情况如下：LR（1）文法：例子：若文法GS为： SS0 SBB1 BaB2 Bb3则其转换图和分析表如下： 几种文法分析方法的比较：LR（0

13、）有冲突时SLR(1)follow集有交集LR(1) 优化后LALR（1）语法分析自顶向下递归子程序法LL(1)方法自底向上简单优先方法算符优先法LR方法LR(0)SLR(1)LR(1)LALR(1)第1 题已知文法AaAd|aAb|判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。答案：文法：AaAd|aAb|拓广文法为G，增加产生式SA若产生式排序为：0 S' A1 A aAd2 A aAb3 A 由产生式知：First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = #Follow(A ) = d,b,#G的LR(0)项目集族及识别活前缀的DFA 如上图