第4章_语法分析和语法分析

编译原理第四章语法分析及语法分析程序东华大学计算机学院本章内容自顶向下分析和自底向上分析围绕分析器的自动生成展开东华大学计算机学院难重点语法分析是编译程序的核心部分。•语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）•目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。东华大学计算机学院自顶向下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自底向上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。东华大学计算机学院自底向上的语法分析•例：文法G：S→cAdA→abA→a识别输入串w=cabd是否是该文法的句子SAAcabdcabdcabd关键：句柄的确定东华大学计算机学院自顶向下分析的语法分析•例：文法SaCbCcd|c为输入串w=acb建立分析树SSSaCbaaCCbbcdc试探的过程问题：会产生回溯东华大学计算机学院自顶向下分析法的另一问题•若有文法G6[S]:(1)S→Sa(2)S→b推导baa#问题：左递归SbSSaSSabSSaSaSSaSab东华大学计算机学院自顶向下分析法需要解决的问题•左递归–对文法进行改造•回溯–如何唯一地确定所采用的产生式？－LL(1)文法•当拒绝w时,只能知道w不是句子,不知出何错及出在何处东华大学计算机学院4.1自顶向下的语法分析•消除文法的左递归•带回溯的递归子程序•回溯的消除及LL(1)文法东华大学计算机学院4.1.1消除文法的左递归•例：AA|A的解是：*引入新的非终结符A’,令其产生*,则有:AA’A’A’|对于AA1|A2|…|An|1|…|m消除直接左递归A1A’|…|mA’及A’1A’|…|nA’|东华大学计算机学院消除文法左递归的矩阵方法•设文法的非终结符为X1,X2,…,Xn,Xi的产生式分为以VN符和VT符打头的两类.将‘|’改写为‘+’,有Xi=X11i+X22i+…+Xnni+i其中,i是以VT符打头的产生式之和,ki可以为这样,文法G可表示为X=XA+B。),,,(),,,(),,,(212122221112112121nnnnnnnnnXXXXXX东华大学计算机学院消除文法左递归的矩阵方法该方程有解:X=BA*为得到A*,由于nnnnZZZZAIAAIAAAIA111132*,,**令其中则有:X=BZ，Z=I+AZ其中X的产生式以VT符打头,而Z的产生式以ijV*打头,因此将不含左递归.注意,由此所得的文法含有无用符号和无用产生式,需化简东华大学计算机学院消除文法左递归的例子•例4.1SSa|Ab|aASc•相应的矩阵为22211211222112112221121122211211*),(),(,),(),(),(ZZZZbcaZZZZZZZZaASZZZZbcaZabcaASAS则令展开矩阵,得SaZ11AaZ12Z11aZ11|cZ21|Z12aZ12|cZ22Z21bZ11Z22|bZ12消除文法中无用产生式SaZ11Z11aZ11|cZ21|Z21bZ11东华大学计算机学院消除回溯的条件•候选式的终结首符集FIRST()={a|*a,aVT,V*}*时,FIRST()•若A-产生式的各候选式i(i=1,2,…,m)都推不出，且FIRST(i)互不相交，则当扫描当前输入符号aiFIRST(j)时,唯一可用于推导的产生式只能是Aj。东华大学计算机学院消除回溯的条件•存在某候选式i,i*,即FIRST(i),有两种选择匹配当前扫描符号a：–存在某j,使j推导出以a打头的符号串–选择i,让跟随在后的符号串推导出以a打头的符号串。东华大学计算机学院消除回溯的条件•若两种选择都可行,则回溯不可避免。因此,要求当i*时,跟在后的符号串不能推导出其它j所能推导出的首终结符符号串。定义：A后的所有终结符之集FOLLOW(A)={a|S#*Aa,aVT{#},,V*}当A为一句型的尾符号时,#FOLLOW(A)。东华大学计算机学院消除回溯的条件•无回溯的条件为:若i*,则FOLLOW(A)与其它j互不相交FOLLOW(A)FIRST(j)=.东华大学计算机学院First&Follow•文法为：–0）S→MH1）S→a–2）H→LSo3）H→ε–4）K→dML5）K→ε–6）L→eHf–7）M→K8）M→bLM非终结符FIRST集FOLLOW集S{a,d,b,ε,e}{#,o}M{d,ε,b}{e,#,o}H{ε,e}{#,f,o}L{e}{a,d,b,e,o,#}K{d,ε}{e,#,o}东华大学计算机学院LL(1)文法•消除回溯的条件：对G中每个AVT,A-产生式中任何两个候选式i,j,均满足:(1)FIRST(i)FIRST(j)=(ij1i,jm)(2)i,j中,至多有一个能推导出;(3)若j*,则FIRST(i)FOLLOW(A)=(i=1,2,…,mij)•注:条件(2)可省略.即(1)(2)•满足上述条件的文法称为LL(1)文法东华大学计算机学院关于LL(1)的一些结论•能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性,主要有:–(1)任何LL(1)文法都是无二义性的;–(2)左递归文法是非LL(1)的;–(3)存在一种算法,它能判定任意文法是否为LL(1)的;–(4)存在一种算法,它能判定任意两个LL(1)文法是否等价;–(5)CFL是否是LL(1)语言是不可判定的;–(6)非LL(1)语言是存在的.•若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.此法极少用,故从略.东华大学计算机学院4.2自底向上的语法分析•优先分析法及LR分析法•问题：–如何确定句型的句柄–如何正确地选择产生式进行归约•建立语法树东华大学计算机学院4.2.4LR分析法•LR分析:自左至右扫描的自底向上的分析•LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最广泛使用的方法;一般用CFG描述的语言均可用LR分析法•先介绍LR分析器的逻辑结构及工作原理,再分别介绍几种LR分析器(即LR(0),SLR(1)和LR(1))的构造东华大学计算机学院（一）LR分析器的逻辑结构及工作原理•LR分析器=输入符号串+分析栈+总控程序+分析表•例：文法G[L]:1.LE,L2.LE3.Ea4.Eb•分析表状态ACTIONGOTOab，#LE0s3s4121acc2s5r23r3r34r4r45s3s4626r1例：a,b,a分析过程分析动作：移进、归约、接受、报错东华大学计算机学院对符号串“a,b,a”的分析过程步骤状态栈中符号余留符号分析动作下一状态10#a,b,a#s33203#a,b,a#r3GOTO[0,E]=2302#E,b,a#s554025#E,b,a#s4450254#E,b,a#r4GOTO[5,E]=260252#E,E,a#s55702525#E,E,a#s338025253#E,E,a#r3GOTO[5,E]=29025252#E,E,E#r2GOTO[5,L]=610025256#E,E,L#r1GOTO[5,L]=6110256#E,L#r1GOTO[0,L]=11201#L#东华大学计算机学院（二）LR(0)分析表的构造•一些术语–规范句型的活前缀(viableprefix)•将栈内符号与未扫描的输入串拼接起来,可得一规范句型.即栈内符号串总是规范句型的前缀,且不含句柄右侧的符号.•把具有上述性质的符号串称为规范句型的活前缀–LR(0)项目（看详细内容）东华大学计算机学院LR(0)项目•活前缀：–包含全部句柄，则：进行归约:A,记为A;–部分句柄，则：应移进(句柄的后半部分),A12–不含句柄，则：期望移进一产生式的右部:A•我们把右部添加了一个“”的产生式,称为LR(0)项目•LR(0)项目：–归约项目：A→–接受项目：S’→S–移进项目：AX,(XVT,可以是空串)–待约项目：AX,(XVN,可以是空串)东华大学计算机学院识别所有规范句型全部活前缀的DFA•例：文法G[S]：S→A|BA→aAb|c,B→aBb|d•LR(0)分析表的构造–DFA的状态由若干LR(0)项目组成的集合表示–构造整个项目集为求基本项目的闭包过程,即整个项目集称为基本项目集的闭包。东华大学计算机学院I0:S’→·SS→·AS→·BA→·aAbA→·cB→·aBbB→·dI1:S’→S·SI2:S→A·AI3:S→B·BI4:A→a·AbA→·aAbA→·cB→a·BbB→·aBbB→·daI5:A→c·ccI6:B→d·ddaI7:A→aA·bI9:B→aB·bI8:A→aAb·I10:B→aBb·BAbb识别G[S]全部活前缀的DFAS→A|BA→aAb|c,B→aBb|d东华大学计算机学院LR(0)分析表的构造•有了全部活前缀的DFA，就可构造相应的LR(0)分析表.•项目集代表了分析过程中各状态，且分析动作相关。因此要求每个项目集的各项目相容，即在同一项目集中不出现:–移进项目与归约项目并存;–多个归约项目并存.•若文法G满足上述条件,即不含上述冲突项目,则称G为LR(0)文法.•显然,只有当一文法是LR(0)文法时,才能构造出无冲突动作的分析表来.东华大学计算机学院G[S]的LR(0)分析表ACTIONGOTOabcd#SAB0s4s5s61231acc2r1r1r1r1r13r2r2r2r2r24s4s5s6795r4r4r4r4r46r6r6r6r6r67s88r3r3r3r3r39s1010r5r5r5r5r5东华大学计算机学院习题•文法G[B]是否是LR(0)文法？如果是，请画出LR(0)分析表；如果不是，请说明原理：B→bD;SeD→D;d|dS→s;S|sSLR(1)分析表的构造东华大学计算机学院习题•文法G[S]是否是SLR(1)文法？如果是，请画出SLR(1)分析表；如果不是，请说明原理：S→CbBAA→Aab|abB→C|DbC→aLR(1)分析表的构造东华大学计算机学院I0:S’→·S,#S→·CbBA,#C→·a,bI1:S’→S·,#SI3:C→a·,#aI2:S→C·bBA,#CI4:S→Cb·BA,#B→·C,aB→·Db,aC→·a,aD→·a,bbI5:S→CbB·A,#A→·Aab,#/aA→·ab,#/aI6:B→C·,#BCI8:C→a·,aD→a·,baI7:B→D·b,aI9:B→Db·,aDbI11:A→a·b,#/aI12:A→ab·,#/aabI10:S→CbBA·,#A→A·ab#/aAI13:A→Aa·b,#/aI14:A→Aab·,#/aab文法G[S]的LR(1)项目集及DFA东华大学计算机学院分析表实例状态ACTIONGOTOabcSABCD0s3121acc2s43r64s85675s11106r47s98r6r79r510s13r111s1212r3r313s1414r2r2