《语法分析》PPT课件

,第5章语法分析,语法分析是编译的第二阶段；其任务是识别和处理比单词更大的语法单位，如：程序设计语言中的表达式、各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。,5.1语法分析的基本概念5.2递归子程序法5.3LL(1)分析法5.4LR()分析法5.5简单优先分析法,5.1语法分析的基本概念,5.1.1语法分析的定义与分类,【定义】形式上说，语法分析是指对给定的符号串（），判定其是否是某文法G(Z)的句子。即,1.自顶向下法（推导法）,2.自底向上法（归约法）,从开始符号出发，采用推导运算，试图自顶向下构造语法树。,从给定的符号串出发，采用归约运算，试图自底向上构造语法树。,或,通常采用“最左推导法”。,通常采用“最左归约法”,给定：=a*(b+c)，是否是表达式？,(接上页),5.1.2算法设计分析1,【例5.1】G(E)：E-T|E+T|E-TT-F|T*F|T/FF-i|(E),最左推导分析过程：,=T*F,=F*F,=a*F,=a*(E),=a*(E+T),=a*(T+T),=a*(F+T),=a*(b+T),=a*(b+F),=a*(b+c),-自顶向下法:,E,=T,为了清楚每次归约的是什麽？我们观察语法树的,5.1.2算法设计分析2,-自底向上法,a*(b+c),即,【结论】自底向上分析的关键技术是如何确定当前句型的句柄！,最左归约分析过程：,构造过程：,5.2.1递归子程序法的设计原理：,语法分析的核心技术是“文法”的机内表示问题；递归子程序法直接把文法变成程序。,对每一个非终结符，构造一个子程序，用以识别该非终结符所定义的符号串。每个子程序以产生式左部非终结符命名，以产生式右部构造子程序内容。,例如：设有如下产生式：,则有：递归子程序A:,递归子程序法属于自顶向下语法分析方法。故又名递归下降法。,y,n,NEXT(w),NEXT(w),NEXT(w),n,c?,遇时,y,NEXT(w),A-aBeD|bAc|,判断当前单词是否是c即w=c?,调用子程序A,(接上页),读单词函数,5.2.2递归子程序的构造算法,扩展文法：增设一个产生式，作为主程序：Z-Z，入出口约定：子程序入口时，其首符号已经读来！子程序出口时，其后继符应该读来！子程序内容设计：遇终结符，判定之，确认后读下一单词；遇非终结符,调用之,返回后不读下一单词；遇空串()，直接出口；,【例5.2】G(S):,令Z-S,则递归子程序:,子程序A,主程序,S-aAb|bS,A-cd|,实际上，上述两点可归纳为同一个条件，即：递归子程序要求文法应是：,5.2.3递归子程序法对文法的要求：,递归子程序是根据文法各产生式的首符号与当前所读单词进行匹配，以决定候选产生式的；这就要求文法：,具有相同左部的各产生式，首符号不同；,文法不能有左递归！,如：A-a|a(首符号相同，)；A-A|(直接左递归，)。,LL(1)文法!（见5.3节）。,5.2.4递归子程序的构造例：,.消除左递归后的文法1:,G(E):,【提示】根据文法变换：,A-A|A-,【例5.3】G(E)：E-T|E1TT-F|T2FF-i|(E)其中：1(+,-),2(*,/),i(变量或常数),主程序,子程序E,令Z-E,子程序T,(接上页),子程序F,(接上页),.消除左递归后的文法2:,G(E):,文法G(E)消除花括号后可得：,令Z-E，则可构造递归子程序如下：（主程序省略）,子程序E,子程序E,(接上页),1.什麽是LL(1)分析法？,5.3.1LL(1)分析法基本概念,5.3LL(1)分析法,LL(1)分析法的基本要点有三：利用一个分析表，登记如何选择产生式的知识；利用一个分析栈，记录分析过程；此分析法要求文法必须是LL(1)文法。,LL(1)分析法是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的1）之意；LL(1)分析法又称预测分析法，与递归子程序法同属于自顶向下确定性语法分析方法;,2.LL(1)分析过程示例,选择推导产生式后，为什麽要逆序压栈?,当栈顶为A,当前单词为c时，为什么选择A?,讨论,逆序压栈,#,#,#cA,#c,#cA,#c,#,cAb,Aa,b,ac#,选择ZbAc,b,ac#,匹配b,a,c#,选择AaA,a,c#,匹配a,c,#,选择A,c,#,匹配c,#,正确结束,Z,查分析表,对符号串：=bac#的分析过程：,分析表：,设有文法G(Z),#栈底标记和结束标记;,栈,结束：,若栈顶符=a且当前符为a；则pop,NEXT(w);,；当前符w=#,重复执行、，直到栈中只剩#为止：,即：栈调整：,即：栈调整：,3.LL(1)分析法算法概要,若栈顶符=A且当前符w=a且有产生式：Aa，则POP,PUSH(a)R;,逆序压栈!,否则，错误处理！,5.3.2LL(1)文法及其判定,1.首符号集合、后继符集合与选择符集合,设G(Z)=(VN,VT,Z,P)，A-P，则,【注】求follow(A)要点：查所有右部含有A的产生式:B-A若不空时,则first()follow(A)；若取空时,则follow(B)follow(A)；若=时,则follow(B)follow(A)。,select()=first(dAZ)=dselect()=first(bcA)=bselect()=first(aA)=aselect()=first()follow(A)=b,d，#,G(Z)：Z-dAZ|bcAA-aA|,【例5.4】求文法产生式的选择集合:,则有：,产生式序号,select()=d；,2.LL(1)文法及其判定,LL(1)文法可确保递归子程序法和LL(1)分析法的正确运用。,【例5.5】G(Z)：Z-dAZ|bcA,A-aA|,select()=b,select()=a；,即：db=又ab,d,#=,select()=b,d，#,G(Z)是LL(1)文法。,LL(1)分析法示例：,【例5.6】G(Z)：Z-Zb|a,【注】上述文法可进行等价变换，消除左递归得：,具有左递归的文法，一定不是LL(1)文法！,G(Z)是LL(1)文法，可以用LL(1)分析法。,G(Z)：Z-aA,A-bA|,5.3.3LL(1)分析器设计(实现),应用时，可用下列函数查表，获取相应产生式：L(栈顶符，当前符）=产生式序号,【结构设计】,.LL(1)分析表的构造:,LL(1)控制程序,LL(1)分析表,LL(1)分析表是存储文法选择集合的知识表。,行：非终结符,表项：产生式序号,如G(Z)：Z-aAb|AcA,select()=a;,【算法设计】,A-dA|,A-,求文法选择集合，确认LL(1)文法；,依次取产生式：,select()=d;,select()=c,d;,select()=b,c,#;,是LL(1)文法,LL(1)分析表：,不相交,不相交,若aselect(),NEXT(w),y,n,err,n,y,n,n,err,PUSH(#),PUSH(Z),POP(x),y,开始,结束,xVT,n,err,y,xVN,w=#,x=w,y,查LL(1)分析表:L(x,w)=?,.LL(1)分析法控制程序：,PUSH(iR）,把产生式i右部逆序压栈,把栈顶符弹入到变量x中!,LL(1)分析法综合示例：,【例5.7】G(E)：E-T|E1TT-F|T2FF-i|(E),此文法含左递归，不是LL(1)文法;经文法变换（消除左递归）后可得：,G(E):E-TEE-1TE|T-FTT-2FT|F-i|(E),其中：1(+,-),2(*,/),这是LL(1)文法吗?,select()=first(TE)=i,(,1.求G(E)的选择集合：,三对选择集合两两不相交，,select()=first(1TE)=1,select()=follow(E)=),#,select()=first(FT)=i,(,select()=first(2FT)=2,select()=follow(T)=1,),#,select()=first(i)=i,select()=first(E)=(,G(E)是LL(1)文法。,(接上页),2.构造LL(1)分析表：,花括号内是求得的选择集合！,T-2FT2|1,),#,F-ii|(E)(,E-TEi,(,E-1TE1|),#,T-FTi,(,G(E):,(接上页),符号串a+b#的LL(1)分析过程：,#,(+匹配成功),b#,+,1,#ET1,:PUSH(ET1),b#,+,E,#E,:PUSH(),+b#,+,T,#ET,:PUSH(i),+b#,a,F,TF,(a匹配成功),+b#,a,i,i,:PUSH(TF),+b#,a,T,ET,：PUSH(ET),a+b#,a,E,#E,:PUSH(TF),b#,b,T,#ET,ok,#,#,#,:PUSH(),#,#,T,#ET,:PUSH(),#,E,#E,(b匹配成功),#,b,i,i,:PUSH（i）,#,b,F,TF,#E,#ET,#E,#ET,分析表,控制程序,LR()分析法是指从左到右扫描、最左归约(LR)之意；它属于自底向上分析方法。常用的算法有LR(0)和LR(1)等，其中括号内的数是指不查看(0)或只查看一个当前符号(1)，即可确定当前句型的句柄。,5.4LR()分析法,利用一个分析表，登记选择句柄产生式的知识；利用一个分析栈，记录分析过程；【分析算法】依次读取单词，并进行如下操作：当栈顶出现句柄时，规约之，否则移进。,5.4.1.LR()分析法基本概念,LR()分析法的基本要点有三：,1.什么是LR（）分析法？,【例5.8】G(Z):Z-aBAd,A-bc|c,B-bB|c,2.LR()分析法分析过程示例：,符号串abccd最左归约过程:,符号串abccd的语法树：,abccd的语法树,abccd,B,B,A,Z,归约过程的句柄：,c,bB,c,aBAd,abccd,abBcd,aBcd,aBAd,Z,移进,NEXT,d#,c,#a,归约，,A-c,#,d,#aB,移进,NEXT,#,d,#aB,归约，,Z-aBAd,#,#aBA,OK,#,#,B-bB,B-c,移进,NEXT,cd#,c,#a,移进,NEXT,bccd#,a,#,归约，,d#,c,#ab,归约，,d#,c,#ab,移进,NEXT,ccd#,b,#,B,B,Z,A,a,b,c,c,d,句柄,(接上页),利用分析栈记录行分析过程：,【注】,何时栈顶出现句柄？怎样求当前句柄产生式？,设待分析的符号串:abccd#,语法树,3.有限自动机用作句柄识别器：,如何确认首次出现的c的父亲是B,而不是A？,句柄一定出现于某一个产生式的右部；,归约过程中如何确认句柄？,是否是句柄，还要看其所在符号串中的位置。,怎样判断栈顶出现的句柄不是bc,而是c?,显然是错误的(从文法中可判定：aA不能相邻!),若用bc归约，则有abccdaAcd(),若用A作父亲，则有abccdabAcd(),显然是错误的(从文法中可判定：Ac不能相邻!,语法树,我们讨论如下两个问题：,分析栈,扩展文法，使文法符号附有位置信息：,增设一个产生式(如：Z-Z)，,带有位置编码的文法符号，称为文法出现。,G(Z),并把产生式右端符号顺序编码，作为位置(状态)信息:,【注】由于文法出现比文法符号多了一个位置信息，在分析时，如果用文法出现代替文法符号，是否有助于句柄的确认呢？,句柄识别器的构造方法,利用扩展文法构造句柄识别器：,若把扩展文法中的位置号看成状态，那么就可用有限自动机描述如下：,对每个产生式，构造自动机，用以识别自己的符号串；,(0,Z)=1;,预见某个非终结符，也就预见其所有产生式的头符号;于是各产生式的子自动机可并接在一起。,【表示】:0状态预见Z后变换为1状态！,设编码0作为自动机的开始状态，,第二个产生式，构造自动机：,则第一个产生式，构造自动机：,(0,a)=2;,(2,B)=3;,(3,A)=4;,(4,d)=5;,句柄识别器的自动机构造示例：,移进状态：,归约状态：,G(Z),+,Z,a,B,b,b,B,c,c,A,d,b,c,OK,r(3),r(1),r(2),r(4),r(5),c,由扩展文法到句柄识别器的构造过程如右图所示：,【例5.8】,分析结束(OK)。,接受状态：,根据句柄识别器进行LR分析过程：,根据句柄识别器，abccd#识别过程：,(#0,a),=(#0a2b9B10,c),=(#0a2B3A4,d),=(#0a2,b),=(#0a2b9,c),=(#0a2b9c11,c),=(#0a2B3,c),=(#0a2B3c8,d),=(#0a2B3A4d5,#),=(#0Z1,#)=0k,句柄识别器又称“活前缀图”:意思是在最左归约过程中，识别了句柄，实际上也就识别了以句柄为后缀的该句型(规范句型)的前部符号串。,注,句柄,【例5.8】文法的句柄识别器:,LR(0)分析器的基本组成：,LR(0)分析法要求文法应是LR(0）文法。,LR(0)分析表LR(0)控制器,LR(0)中的0,是指不必查看当前符号就可确认句柄之意；,5.4.2LR(0)分析器设计,1.LR(0)文法及其判定,句柄识别器中，移进和归约不冲突；即移进和归约不同时发生！,满足下述特点的文法称为LR(0)文法。,例5.8文法，就是LR(0)文法，请看：,归约时不必查看当前符号；,【算法】,根据句柄识别器，填写LR(0)分析表：,若(i,x)=k,x(VN+VT),则R(i,x):=xk;,若状态i标记有（-，r(j),则对任何a(VT+#），R(i,a):=r(j);,R(1,#):=OK。,2.LR(0)分析表构造,扩展文法，构造句柄识别器；,LR()分析表是LR()分析法的知识表,是句柄识别器的一种机内表示形式：,R(_,_):,ak,OK,Zk,r(j),r(j),B10,c11,b9,r(4),r(4),r(4),r(4),r(4),Z1,A4,OK,r(1),r(1),r(1),r(1),r(1),a2,d5,r(3),r(3),r(3),r(3),r(3),r(5),r(2),r(5),r(2),c7,r(2),r(2),r(2),r(5),r(5),r(5),c8,b6,B3,b9,c11,3.LR(0)控制程序设计,PUSH(#0),NEXT(w),查LR(0)分析表R(Xk,w)=?,Y,err,R=OK,R=r(j),R=Wi,PUSHWi,Xk栈顶文法出现；,归约,移进,LR()控制器,n,LR(0)分析法小结示例,【例5.8】文法:,扩展文法，使文法符号附有位置信息：,由扩展文法构造句柄识别器：,+,Z,a,B,b,b,B,c,c,A,d,b,c,OK,r(3),r(1),r(2),r(4),r(5),c,B10,c11,b9,r(4),r(4),r(4),r(4),r(4),Z1,A4,OK,r(1),r(1),r(1),r(1),r(1),a2,d5,r(3),r(3),r(3),r(3),r(3),r(5),r(2),r(5),r(2),c7,r(2),r(2),r(2),r(5),r(5),r(5),c8,b6,B3,b9,c11,由句柄识别器构造LR(0)分析表：,LR(0)分析法分析过程示例：,#0a2b9,B10,PUSH(c8),NEXT(w),d#,c,#0a2,REDUCE(3),#,d,#0a2B3,PUSH(d5),NEXT(w),#,d,#0a2B3,REDUCE(1),#,#0a2B3A4,OK,#,#0,d#,d#,cd#,ccd#,bccd#,PUSH(c11),NEXT(w),c,#0a2,PUSH(a2),NEXT(w),a,#0,REDUCE(4),c,REDUCE(5),c,#0a2b9,PUSH(b9),NEXT(w),b,#0,a2,b9,c11,B3,c8,A4,d5,Z1,查分析表,查产生式,控制程序,符号串：abccd#,【例5.9】LR(0)分析法示例1：,构造下述文法的LR(0)分析表：G(Z)：Z-aAb,A-cA|d,构造句柄识别器：,扩展文法：G(Z)Z-Z1(0)Z-a2A3b4(1)A-c5A6(2)|d7(3),设计LR(0)分析表：,【例5.10】左递归文法的LR(0)分析表构造：,+,Z,a,A,d,b,c,OK,r(1),r(2),r(3),G(Z),【注】为了使句柄识别器是确定机，左递归产生式(2)中的A要与(1)中的A编码相同!?,r(3),r(2),r(1),d6,Z1,A3,OK,r(2),r(2),r(2),r(2),a2,r(1),r(1),r(1),r(1),r(3),r(3),r(3),r(3),c5,b4,【例5.11】LR(0)分析法示例1,构造下述文法的LR(0)分析表：G(Z)Z-aAb,A-Ac|d扩展文法：G(Z)Z-Z1(0)Z-a2A3b4(1)A-A5c6(2)|d7(3)构造可归前缀图：,(接上页),（2，A)=3,5,是个非确定机；,确定化的可归前缀图：,LR(0)分析表：,(接上页),5.4.3LR(0)分析法的扩展,LR()分析法的关键技术是句柄识别器的设计问题；如果句柄识别器发生了冲突：,此时，LR(0)分析法失效!需要改进句柄识别器的构造方法，于是出现了各种不同的LR()分析法。,【注】下面仅通过实例探讨LR(0)分析表的简单扩展问题-称为SLR(1)分析法。,移进/归约冲突,归约/归约冲突,【例5.9】G(Z):Z-aAb；A-cd|,扩展文法，构造句柄识别器：,Z-Z1(0);Z-a2A3b4(1)A-c5d6(2)|7(3),G(Z):,经确定化(消边)：,句柄识别器出现冲突：,解决办法：,求：follow(A)=b,若w=c则c5;若w=b则r(3)。,通过查看当前单词，是否可以解决？为此：,r(3),-,SLR(1)分析表,b,r(3),SLR(1)句柄识别器：,扩展句柄识别器，构造SLR(1)分析表,r(2),d6,r(1),Z1,A3,OK,a2,r(1),r(1),r(1),r(1),r(2),r(2),r(2),r(2),b4,c5,r(3),注意与LR(0)分析表的区别！,-,如此可以解决冲突的文法，称为SLR(1)文法。,S-S1(0)S-A2a3|B4c5A-d6;B-d7,【例5.10】G(S):S-Aa|Bc；A-d;B-d;,扩展文法，构造句柄识别器：,G(S):,即若w=a则r(3);若w=c则r(4)。,求：follow(A)=a,；follow(B)=c,+,S,A,a,c,OK,r(1),r(4),d,r(3),r(2),B,d,确定化,非确定机,扩展句柄识别器，构造SLR(1)分析表,r(2),r(1),OK,A2,B4,r(2),r(2),r(2),S1,d6,c5,r(4),r(3),r(1),r(1),r(1),a3,注意与LR(0)分析表的区别！,SLR(1)分析表,通过查看当前单词，解决冲突：,SLR(1)句柄识别器,a,r,r,c,简单优先分析法是一种从左到右扫描、最左归约分析法；它属于自底向上分析方法。该方法利用文法符号之间的优先关系来确定待归约的句柄，即可确定当前句型的句柄。,5.5简单优先分析法,利用一个分析表，登记选择句柄产生式的知识；利用一个分析栈，记录分析过程；【分析算法】依次读取单词，并进行如下操作：当栈顶出现句柄时，规约之，否则移进。,5.5.1.简单优先分析法基本概念,简单优先分析法的基本要点有三：,1.什么是简单优先分析法？,2.简单优先分析过程示例,符号串：=abbeae#,S,a,A,e,B,S,b,b,a,A,e,移进,NEXT,ae#,e,#a,移进,NEXT,e#,a,#aA,移进,NEXT,#,e,#aAe,归约,A-e,#,#aAea,归约,B-aA,#,#aAea,A-Sb,S-b,归约,eae#,b,#a,移进,NEXT,bbeae#,a,#,归约,ae#,e,#aS,移进,NEXT,eae#,b,#a,移进,NEXT,beae#,b,#,A,A,a,a,b,e,e,句柄,(接上页),利用分析栈记录行分析过程：,【注】,何时栈顶出现句柄？怎样求当前句柄产生式？,设待分析的符号串:abbeae#,#S,b,#aAe,#,#B,句柄,S-aAeB,归约,#,#,S,OK,语法树,同时归约者为相等关系，记作；,3.文法符号之间的优先关系,归约过程中如何确认句柄？,是否是句柄，还要看其所在符号串中的位置。,语法树,从语法树上，找出优先关系（指相临符号之间）如下：,Sb，,aA，,Ae，,eB,如：,左后归约者为小于关系，记作；,如：,ab,ab,be,当把优先关系纳入待分析的符号串时，有如下关系：,#be#,#e#,#,#,#,结论：一个句型的句柄，位于第一次（自左至右）出现在之间的符号串！,从文法中获取优先关系!,设si，sj是两个文法符号;,如：aA，Ae，eB，Sb；,sisj，当且仅当有Usisj；,优先关系的定义,sisj，当且仅当有UsiW，且Wsj；,如：ae，aS，aa，ab，Bb，Ab，eb。,(3)头符号集合和尾符号集合,设AVN，si，sj是两个文法符号;则:,FIRSTVT(A)=si|Asi,LASTVT(A)=sj|Asj。,【例5.12】,头符号集合尾符号集合,优先矩阵,表项=空表示两个符号不可能相临。,简单优先分析器的基本组成：,优先分析法要求文法应是简单优先文法。,优先矩阵分析表优先分析控制器,分析中只查看当前符号就可确认句柄；,5.5.2简单优先分析器设计,1.简单优先文法及其判定,文法产生式没有相同的右部；如A，B，,满足下述特点的文法称为简单优先文法。,例5.12文法，就是简单优先文法，请看：,文法符号之间至多有一种优先关系！,【算法】,sisj，当且仅当有Usisj；,sisj，当且仅当有UVsj，且siLASTVT(V)。,2.简单优先分析矩阵分析表构造,设W,VVN,si，sj是两个文法符号;,简单优先分析表是优先分析法的知识表,是文法的一种机内表示形式：,优先关系符号,终结符+非终结符+#,3.简单优先控制程序设计,PUSH(#),NEXT(w),查优先分析表R(Xk,w)=?,n,err,(#S#),PUSHW,POP(sj)，POP(sj-1)，POP(si)；PUSH(A)。,从sj（栈顶符）开始，往栈内查找，找到第一个使si-1bAc=baAc=bac=bac,bac是文法G(Z)的一个句子。,注,.构造递归子程序法：,证明G(Z)是LL(1)文法：,select()=first(dAZ)=d,求选择集合：,select()=first(bAc)=b,select()=first(aA)=a,select()=first(c)=e,select()=follow(A)=d,b，c,两组选择集合,皆不相交，,G（Z）是LL(1)文法！,即递归子程序法可用！,Z子程序,主程序,构造递归子程序(框图)：,NEXT(w),遇时,n,y,A子程序,NEXT(w),y,n,NEXT(w),n,y,err0,d,err3,NEXT(w),n,n,y,c,NEXT(w),y,err2,n,y,NEXT(w),分析过程示意：,bac#,设待分析的符号串：,b,b,a,a,c,c,c,c,#,#,.LL(1)分析法：,证明G(Z)是LL(1)文法：,select()=first(dAZ)=d,求选择集合：,select()=first(bAc)=b,select()=first(aA)=a,select()=first(c)=e,select()=follow(A)=d,b，c,两组选择集合,皆不相交，,G（Z）是LL(1)文法！,即递归子程序法可用！,2.构造LL(1)分析表：,LL(1)分析表：,G(Z)：Z-dAZd|bAcbA-aAa|ee|b,c,d,带有选择集合的文法：,逆序压栈,#,#,#cA,#c,#cA,#c,#,cAb,Aa,b,ac#,pop,push(cAb),b,ac#,pop,next,a,c#,pop,push(Aa),a,c#,pop,next,c,#,c,#,#,Z,对符号串：=bac#的分析过程：,分析过程示意：,G(Z)：Z-dAZd|bAcbA-aAa|ee|b,c,d,pop,push(),pop,next,正确结束,查分析表,.LR(0)(SLR(1)分析法：,扩展文