编译原理第三章语法分析.ppt

第三章 语法分析,语法分析器的作用,上下文无关文法（CFG）,定义：上下文无关文法是一个四元组G=(N,T,P,S) N是非终结符的有限集合； T是终结符的有限集合，且NT； P是产生式的有限集合； S是非终结符，是文法的开始符号。 例：定义上下文无关文法G=(N,T,P,S)如下： N=E T=+,*,(,),-,id S=E P: EE+E EE*E E(E) E-E Eid,缩写为： EE+E|E*E|(E)|-E|id,形式语言分类,定义：若文法G=(N,T,P,S)的每个产生式中，均有 (NT)*N(NT)*,且至少含有一个非终结符， (NT)*,则称G为0型文法（短语文法）。 1型文法（上下文有关文法）：G的任何产生式(S除外)均满足| | (|x|表示x中文法符号的个数)； 2型文法（上下文无关文法）：G的任何产生式形如A，其中AN，(NT)*； 3型文法（正规文法、线性文法）：G的任何产生式形如Aa或者AaB(或者ABa）,其中A,BN,aT*。,正规式与上下文无关文法,正规式所描述的语言结构均可以用CFG描述，反之不一定。 例：正规式r=(a|b)*abb的CFG描述如下 AHT H|aH|bH Tabb 往往采用正规式而不是CFG描述词法。 正规式适合描述线性结构； CFG适合描述具有嵌套（层次）性质的非线性结构。,CFG产生语言的基本方法推导,定义：将产生式A的右部代替文法符号序列A 中的A得到的过程，称为A直接推导 出，记作：A。 1n为零步或多步推导； 1n为零步推导； 任何文法符号序列可以推导出它自身，； 推导具有传递性，,则,*,*,*,*,*,定义：由CFG G所产生的语言 L(G)=|S and T*称为上下文无关语言，称为句子。若S,(NT)*,则称为G的一个句型。 只含终结符的句型是句子。 定义：在推导中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，产生的句型称为左句型。 最右推导也称为规范推导。,+,*,例： 已知G(E),EE+E|E*E|(E)|-E|id id+(id*id)的推导过程： 最左推导： E E+E id+E id+(E) id+(E*E) id+(id*E) id+(id*id) 最右推导： E E+E E+(E) E+(E*E) E+(E*id) E+(id*id) id+(id*id),定义： 设是上下文无关文法G的一个句型, 如果有S A, 并且A,则称是句型关于非终结符A的一个短语, 或称是句型的一个短语。 直接短语（简单短语）：A 句柄：一个句型的最左直接短语。 素短语:含有终结符的短语,但不存在也具有相同性质的真子串 短语：以非终结符为根的子树中所有从左到右排列的叶子； 直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）； 句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。 素短语:子树末端结点组成的符号串含终结符,且在该子树中不再有包含 含有终结符的更小子树,*,+,短语与语法树,例：G(E)：EE+T|T TT*F|F F(E)|i 句型：i*i+i的短语、直接短语、句柄和素短语 短语：i1*i2+i3,i1*i2,i1,i2,i3 直接短语：i1,i2,i3 句柄：i1 素短语: i1，i2，i3,分析树： 根由开始符号标记； 每个叶子由一个终结符、非终结符或标记； 每个内部结点由一个非终结符标记； 若AX1X2Xn是一个产生式，则标记为A的内部结 点从左到右有子结点X1，X2，Xn； 若A，则必是叶结点，且它是A的唯一子结点。 例：,E ,语法树： 根与内部结点由表达式中的操作符标记； 叶子由表达式中的操作数标记； 用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中； 例： 语法树只反映句型的结构，忽略了推导句型的过程。,二义性与二义性的消除,定义：若文法G对同一个句子产生不止一棵分析树，则称G是二义的。 例：id+id*id 原因是文法中缺少对文法符号优先级和结合性的规定,E,id + E,E * E,id id,E,E * E,E + E id,id id,自上而下语法分析,自上而下语法分析法：从文法开始符号出发,找最左推导；或从根开始,构造推导树。 1.回溯分析法：(不确定性) 例：SxAy Aaba 输入串为xay,说明分析过程,2.存在的问题 (1)回溯公共左因子的存在 A1| 2 (2)左递归 AA 或 AA 提取左因子，以避免回溯； 消除左递归，以避免陷入死循环。,消除左递归,(1)直接左递归的消除 AA 改写为：AA AA 一般地 AA1|A2|Am|1|2|n （i，j不以A开头） 改写为：A1A|2A. . .|nA A 1A|2A. . .|mA|,例：消除直接左递归 EE+T|T TT*F|F F(E)|-F|id 消除后 ETE E +TE| TFT T *FT| F(E)|-F|id,(2)间接左递归的消除 例： SQcc QRbb RSaa 按S,Q,R排列,或R,Q,S排列 按S、Q、R排列, 代入后 按R、Q、S排列, 代入后 SQcc RSaa QRbb QSababb R Rbcabcacaa SSabcabc bcc 消除R中的直接左递归 消除S中的直接左递归 R bcaRcaRaR SabcSbcScS R bcaR SabcS ,提取左因子(回溯),A1| 2| . |n| 改写为：AA| A 1| 2| . |n 例：SiCtS|iCtSeS|a Cb 消除左因子： SiCtSS|a SeS| Cb 当一个文法中既有左递归又含左因子时，先消除左递归。,文法3.2:,ETE E+TE| TFT T*FT| F(E)|i 输入串i*(i+i)的语法分析,递归下降程序:,void match(token t) if(lookahead= =t) lookahead=nexttoken; else error(); void E() T(); E(); void E() if(lookahead= =+) match(+); T(); E(); ,void T() F(); T(); void T() if(lookahead= =*) match(*); F(); T(); ,递归下降程序:,void F() if(lookahead= =i) match(i); else if(lookahead= =() match(); E(); if(lookahead= =) match(); else error(); else error(); ,匹配*,匹配( ),匹配+,预测分析器(LL(1)分析法),构成：下推栈,预测分析表,控制程序,输入串 分析方法： 初始时,和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作: x=a=, 成功 x=a, 匹配 xN, 查预测分析表,构造预测分析表,1FIRST集 (1)定义：文法符号序列A的FIRST集合 FIRST(A)a|A a. . . , aT,若A,则FIRST(A) 若x是终结符，则FIRST(x)=x; 若A是非终结符且A，则加入到FIRST(A); 若A是非终结符且AY1Y2Yk,并且Y1Yj-1都能推导出, 则对所有j(1jk),若aFIRST(Yj),加入a到FIRST(A)。,*,*,例：LE;L| ETE E+TE|-TE| TFT T*FT|/FT|modFT| F(E)|id|num 非终结符的FIRST集 FIRST(F)=(,id，num FIRST(T)=*,/,mod， FIRST(T)=FIRST(F)=(,id，num FIRST(E)=+,-, FIRST(E)=FIRST(T)=(,id，num FIRST(L)=,(,id，num,1FOLLOW集 (1)定义：非终结符A的FOLLOW集合 FOLLOW(A)a|SAa , aT,若SA, 则#FOLLOW(A),其中S为开始符号 #FOLLOW(S); ABC: 将FIRST(C)-加入FOLLOW(B); AB或ABC且FIRST(C),则将FOLLOW(A)加入FOLLOW(B)。,*,*,例：LE;L| ETE E+TE|-TE| TFT T*FT|/FT|modFT| F(E)|id|num 非终结符的FOLLOW集 FOLLOW(L)=# FOLLOW(E)=;,) FOLLOW(E)=;,) FOLLOW(T)=+,-,;,) FOLLOW(T)=+,-,;,) FOLLOW(F)=*,/,mod,+,-,;,),构造算法： 对每个产生式A 对FIRST( A )的每个终结符a，加入到MA,a； 若FIRST( A ),则对FOLLOW(A)的每个终结符b（包括#），加入到MA,b； M中其他没有定义的条目均为error。,例：id+id*id;的分析过程,LL(1)文法,例：SiCtSS|a SeS| Cb FIRST(C)=b FIRST(S)=e, FIRST(S)=i,a FOLLOW(S)=e,# FOLLOW(S)=e,# FOLLOW(C)=t 任何二义文法、含左递归和左因子的文法都不是LL(1)文法。,一个文法G是LL(1)文法，当且仅当G的任何两个产生式 A|,满足下列条件： 对任何终结符a，和不能同时推导出以a开始的串； 和最多有一个可以推导出； 若,则不能推导出以FOLLOW(A)中的终结符开始的任 何串。,*,自下而上语法分析法：从输入串开始,归约,直至 文法开始符。 定义：若是文法G的一个句子,序列n,n-1,0 满足下述条件时称为最左规约（规范归约）。 n=; 0为文法的开始符,即0=S; 对任何i(0in), i-1是从i经把句柄替换为相应产生式的左部非终结符而得到的。,自下而上语法分析,例1: G(E) EE+TT TT*FF F(E) i i+i*i的规范规约过程,i+i*i E+i*i E+T*i E+T*F E+T E,例2: G(S) SaAcBe AAb|b Bd abbcde的规范规约过程,abbcde aAbcde aAcde aAcBe S,算符优先分析法,适合于分析程序语言中的各类表达式。 所谓算符优先分析,就是依照算术表达式的四则运 算过程来进行语法分析,预先规定终结符之间的优先关 系和结合性质,以确定句型的”可规约串”来进行规约。 它不是一种规范规约,在整个过程中起决定作用的 是相继两个终结符的优先关系。,1. 算符文法 上下文无关文法G,没有形如P或P. . .QR. . .的产生式,则称G为算符文法 2. 终结符之间的优先关系 对算符文法G, a,bT 定义 (1)a=b: G中有P. . .ab. . .或P. . .aQb. . .的产生式 (2)ab: G中有P. . .Rb. . . 且R . . .a或R aQ 3. 算符优先文法 若算符文法G的任何终结符a,b之间的优先关系至多有 =、中的一个,则G为一算符优先文法。,构造优先关系表,(1)FIRSTVT集 FIRSTVT(P)=a|Pa,或PQa,aT,QN 若Pa或PQa, 则aFIRSTVT(P); 若PQ, 则FIRSTVT(Q)FIRSTVT(P); 直至FIRSTVT(P)不再增大。 (2)LASTVT集 LASTVT(P)=a|P.a,或PaQ,aT,Q N 若P.a或PaQ, 则aLASTVT(P); 若P.Q, 则LASTVT(Q)LASTVT(P); 直至LASTVT(P)不再增大。,FIRST(A)是推导出的第一个终结符集; FIRSTVT(A)是所有推导中首先遇到的终结符集; FOLLOW(A)是紧跟非终结符A后的终结符集; LASTVT(A)是所有推导中最后遇到的终结符集.,例： G(E) EE+TT TT*FF F(E) i,E,T,F,FIRSTVT,LASTVT,( i + *,( i,) i + *,) i *,) i,( i *,考察EE+T中的E和+ 、 +和T、#和# 、#和E 、E和# 考察TT*F中的T和* 、 *和F 考察F(E)中的(和E 、 (和) 、 E和),+,+,*,*,i,i,(,(,),),#,#,=,=,算符优先关系表,从上表可知: (1)相同终结符之间的优先关系未必是= (2)有aa (3)a、b之间未必一定有优先关系 故=、不同于关系运算符“等于”、“小于”、“大于”,算符优先分析方法 设a为栈顶终结符,i+i*i的算符优先分析过程,LR分析法,LR(K) 分析法： 自下而上的LR分析法是指从左向右扫描输入串,每 次分析由分析栈中符号及向前搜索K个输入符号,以确 定作为产生式右部的短语(句柄)是否已在分析栈的栈 顶形成,从而决定应采取的动作。这种分析方法称为 LR(K)分析法。一般只考虑K1的情况。,识别活前缀,活前缀：规范句型的不含句柄之后任何符号的一个前缀。 亦即:若A是文法的一个产生式,且有SA 则的任何前缀都是规范句型的活前缀。 项目:在产生式右部添加一个圆点,如A、A、A 归约项目：形如A 移进项目：形如Aa，aT 待约项目：形如AB，BN 接受项目：形如S，S为开始符 拓广文法：增加产生式SS，从而SS成为唯一的接受项目。,*,识别活前缀的DFA,项目集I的闭包closure(I)： 对iI,都有iclosure(I); 若ABclosure(I), B为非终结符，且B为文法G的一个产生式, 则Bclosure(I)； 重复直至closure不再增大。 定义：对所有属于项目集I、且形如AX的项目，令 XNT,则goto(I,X)是所有形如AX的项目。,LR分析器组成：分析栈,控制程序,分析表,输入串,输入串,分析栈,驱动程序,输出,action,goto,分析表,s0,. . .,sm-1,sm,a1,ai,#,.,.,分析栈： 存放状态;初始时,置初始状态s0;栈里的每一状态 概括了从分析开始到某一时刻已进行的分析工作。 分析表： 由actions,a和gotos,A两个子表组成。 actions,a定义了在状态s下, 当前输入符号为a时应 采取的分析动作：移进, 归约,接受, 出错。 goto表是一个状态及非终结符的二维矩阵, gotos,A定义了在状态s下, 面对文法符号A时的状态转换。,C=I0,I1,In, Ii对应状态i,I0=closure(SS)为唯一初态; 对每个Ii, 若AaIi, 且go (Ii,a)=Ij, 则actioni,a=sj; 若AIi, A为第j个产生式,则actioni,a=rj; 若SSIi, 则actioni,=acc; 若go(Ii,A)=Ij, 则gotoi,A=j; 凡不能用规则、登记的表项均为“错误”。,LR(0)分析表的构造,假定LR(0)文法规范族的每个项目集不含冲突项目，按 下述方法构造的分析表是一张LR(0)表，使用LR(0)表的分析 器叫做LR(0)分析器。,例：试构造该文法的LR(0)分析表 GS:SBB BaB|b 拓广为：GS: (0)SS (1)SBB (2)BaB (3)Bb 构造GS的LR(0)项目集规范族： 计算初态，I0closure(S.S) I0： S.S S.BB B.aB B.b 计算初态下的每个可能状态转移closure(goto(I0,x) I1： SS.,I2： SB.B I3： Ba.B I4： Bb. B.aB B.aB B.b B.b 计算下一状态的每个可能状态转移closure(goto(Ii,x) I5： SBB. I6： BaB. 构造DFA:,LR(0)分析表,例：为文法构造识别活前缀的DFA。 (0)EE (1)EE-T (2)ET (3)TT*F (4)TF (5)F-F (6)Fid 计算DFA初态，I0closure(E.E) I0:,E.E E.E-T E.T T.T*F T.F F.-F F.id,SLR分析表的构造,计算初态下的每个可能状态转移closure(goto(I0,x),E.E E.E-T E.T T.T*F T.F F.-F F.id,I0,EE. EE.-T,E,I1,ET. TT.*F,T,TF.,F,Fid.,I2,I3,I4,id,F-.F F.-F F.id,-,I5,计算下一状态的每个可能状态转移closure(goto(Ii,x),E.E E.E-T E.T T.T*F T.F F.-F F.id,I0,EE. EE.-T,E,I1,ET. TT.*F,T,TF.,F,Fid.,I2,I3,I4,id,F-.F F.-F F.id,-,I5,EE-.