语法分析和语法分析.ppt

《语法分析和语法分析.ppt》由会员分享，可在线阅读，更多相关《语法分析和语法分析.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编编译译原原理理第第四四章章语法分析及语法分析程序语法分析及语法分析程序东华大学计算机学院本章内容本章内容v自顶向下分析和自底向上分析自顶向下分析和自底向上分析v围绕分析器的自动生成展开围绕分析器的自动生成展开东华大学计算机学院难难重重点点语法分析是编译程序的核心部分。语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的出的单词符号序列是否是给定文法的正确句子（程序）正确句子（程序）目前语法分析常用的方法有自顶向下目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下（自上而下）分析和自底向上（自下而上）分析两

2、大类。而上）分析两大类。东华大学计算机学院v自顶向下分析法：自顶向下分析法：从文法的开始符号出发，反复使从文法的开始符号出发，反复使用文法的产生式，寻找与输入符用文法的产生式，寻找与输入符号串匹配的推导。号串匹配的推导。v自底向上分析法：自底向上分析法：从输入符号串开始，逐步进行归约，从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。直至归约到文法的开始符号。东华大学计算机学院自底向上的语法分析自底向上的语法分析例：文法例：文法G：ScAdAabAa识别输入串识别输入串w=cabd是否是该文法的是否是该文法的句子句子 S AA c a b d c a b d c a b dv关键：句柄

3、的确定关键：句柄的确定东华大学计算机学院自顶向下分析的语法分析自顶向下分析的语法分析例：例：文法文法SaCbCcd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc试探试探的过程的过程v问题：会产生回溯问题：会产生回溯东华大学计算机学院自自顶向顶向下分析法的另一问题下分析法的另一问题若有文法若有文法G6S:(1)SSa(2)Sb推导推导baa#v问题：左问题：左递归递归SbSSaSSabSSaSaSSaSab东华大学计算机学院自自顶向下分析法需要解决的问题顶向下分析法需要解决的问题左递归左递归对文法进行改造对文法进行改造回溯回溯如何唯一地确定所采用的产生式？如何唯

4、一地确定所采用的产生式？LL(1)文法文法当拒绝当拒绝w时时,只能知道只能知道w不是句子不是句子,不知不知出何错及出在何处出何错及出在何处东华大学计算机学院4.1自顶向下的语法分析自顶向下的语法分析消除文法的左递归消除文法的左递归带回溯的递归子程序带回溯的递归子程序回溯的消除及回溯的消除及LL(1)文法文法东华大学计算机学院4.1.1消除文法的左递归消除文法的左递归例：例：AA|A的解是：的解是：*引入新的非终结符引入新的非终结符A,令其产生令其产生*,则有则有:A AA A|对于对于AA1|A2|An|1|m消除直接左递归消除直接左递归A1A|mA及及A1A|nA|东华大学计算机学院消除文法

5、左递归消除文法左递归的矩阵方法的矩阵方法设文法的非终结符为设文法的非终结符为X1,X2,Xn,Xi的产生的产生式分为以式分为以VN符和符和VT符打头的两类符打头的两类.将将|改改写为写为+,有有Xi=X1 1i+X2 2i+Xn ni+i其其中中,i是以是以VT符打头的产生式之和符打头的产生式之和,ki可以为可以为 这样这样,文法文法G可表示为可表示为X=XA+B。东华大学计算机学院消除文法左递归消除文法左递归的矩阵方法的矩阵方法该方程有解该方程有解:X=BA*为得到为得到A*,由于由于则有则有:X=BZ，Z=I+AZ其中其中X的产生式以的产生式以VT符打头符打头,而而Z的产生式的产生式以以

6、ijij V*打头打头,因此将不含左递归因此将不含左递归.注意注意,由此所得的文法含有无用符号和无用由此所得的文法含有无用符号和无用产生式产生式,需化简需化简东华大学计算机学院消除文法左递归消除文法左递归的的例子例子例例4.1SSa|Ab|aASc相应的矩阵为相应的矩阵为展开矩阵展开矩阵,得得SSaZ11aZ11 AAaZ12aZ12Z11Z11aZ11|cZ21|aZ11|cZ21|Z12Z12aZ12|cZ22aZ12|cZ22Z21Z21bZ11bZ11Z22Z22|bZ12|bZ12消除文法中无用产生式消除文法中无用产生式SaZ11Z11aZ11|cZ21|Z21bZ11东华大学计算机

7、学院消除回溯的条件消除回溯的条件候选式的候选式的终结首符集终结首符集FIRST()=a|*a,a VT,V*时时,FIRST()若若A-产生式的各产生式的各候选式候选式 i(i=1,2,m)都都推不出推不出，且，且FIRST(i)互不相交，则互不相交，则当扫描当前输入符号当扫描当前输入符号ai FIRST(j)时时,唯唯一可用于推导的产生式只能是一可用于推导的产生式只能是Aj。东华大学计算机学院消除回溯的条件消除回溯的条件存在某候选式存在某候选式 i i,i i*,即即FIRST(FIRST(i),i),有有两种选择两种选择匹配当前扫描符号匹配当前扫描符号a a：存在某存在某 j j,使使 j

8、 j推导出以推导出以a a打头的符打头的符号串号串选择选择 i i,让跟随在后的符号串推导让跟随在后的符号串推导出以出以a a打头的符号串。打头的符号串。东华大学计算机学院消除回溯的条件消除回溯的条件若两种选择都可行若两种选择都可行,则回溯不可避免。则回溯不可避免。因此因此,要求当要求当 i i*时时,跟在后的符号串不跟在后的符号串不能推导出其它能推导出其它 j j所能推导出的首终结符所能推导出的首终结符符号串符号串。定义：定义：A A后的所有终结符之集后的所有终结符之集FOLLOW(A)=a|S#FOLLOW(A)=a|S#*AaAa,a,a V VT T T T#,#,V V*当当A A为

9、一句型的尾符号时为一句型的尾符号时,#,#FOLLOW(A)FOLLOW(A)。东华大学计算机学院消除回溯的条件消除回溯的条件无回溯的无回溯的条件条件为为:若若 i i*,则则FOLLOW(A)FOLLOW(A)与其它与其它 j j互不相交互不相交FOLLOW(A)FOLLOW(A)FIRST(FIRST(j)=j)=.东华大学计算机学院First&Follow文法为：文法为：0 0 0 0）SM H 1SM H 1SM H 1SM H 1）Sa Sa Sa Sa 2 2 2 2）HL S o 3HL S o 3HL S o 3HL S o 3）HHHH 4 4 4 4）Kd M L 5Kd

10、M L 5Kd M L 5Kd M L 5）KKKK 6 6 6 6）Le H f Le H f Le H f Le H f 7 7 7 7）MK 8MK 8MK 8MK 8）Mb L MMb L MMb L MMb L M非终结符非终结符 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(

11、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)存在一种算法,它能判定任意文法是否为L

12、L(1)的;(4)存在一种算法,它能判定任意两个LL(1)文法是否等价;(5)CFL是否是LL(1)语言是不可判定的;(6)非LL(1)语言是存在的.若在分析过程中若在分析过程中,每步向前扫描每步向前扫描k个符号来确定选用的产生式个符号来确定选用的产生式,此分析方法称为是此分析方法称为是LL(k)分析分析.此法极少用此法极少用,故从略故从略.东华大学计算机学院4.2自底向上的语法分析自底向上的语法分析优先分析法及优先分析法及LR分析法分析法问题：问题：如何确定句型的句柄如何确定句型的句柄如何正确地选择产生式进行归约如何正确地选择产生式进行归约建立语法树建立语法树东华大学计算机学院4.2.4LR

13、分析法分析法LR分析:自左至右扫描的自底向上的分析自左至右扫描的自底向上的分析LR分析对文法要求很少分析对文法要求很少,效率极高效率极高,且能及且能及时发现错误时发现错误,是目前最广泛使用的方法是目前最广泛使用的方法;一一般用般用CFG描述的语言均可用描述的语言均可用LR分析法分析法先介绍先介绍LR分析器的逻辑结构及工作原理分析器的逻辑结构及工作原理,再分别介绍几种再分别介绍几种LR分析器分析器(即即LR(0),SLR(1)和和LR(1)的构造的构造东华大学计算机学院（一）（一）LR分析器的逻辑结构及工作原理分析器的逻辑结构及工作原理LR分析器分析器=输入符号串输入符号串+分析栈分析栈+总控程

14、序总控程序+分析表分析表例：文法例：文法GL:1.LE,L2.LE3.Ea4.Eb分析表分析表状态状态ACTIONGOTOab，#LE0s3s4121acc2s5r23r3r34r4r45s3s4626r1v例：例：a,b,a分析过程分析过程v分析动作分析动作：移进、归约、移进、归约、接受、报错接受、报错东华大学计算机学院对符号串对符号串“a,b,a”的分析过程的分析过程步骤步骤状态状态栈中符号栈中符号余留符号余留符号分析动作分析动作下一状态下一状态10#a,b,a#s33203#a,b,a#r3GOTO0,E=2302#E,b,a#s554025#E,b,a#s4450254#E,b,a#r

15、4GOTO5,E=260252#E,E,a#s55702525#E,E,a#s338025253#E,E,a#r3GOTO5,E=29025252#E,E,E#r2GOTO5,L=610025256#E,E,L#r1GOTO5,L=6110256#E,L#r1GOTO0,L=11201#L#东华大学计算机学院（二）（二）LR(0)分析表的构造分析表的构造一些术语一些术语规范句型的活前缀规范句型的活前缀(viableprefix)将栈内符号与未扫描的输入串拼接起来将栈内符号与未扫描的输入串拼接起来,可可得一得一规范句型规范句型.即栈内符号串总是即栈内符号串总是规范句型规范句型的前缀的前缀,且且不

16、含句柄右侧的符号不含句柄右侧的符号.把具有上述性质的符号串称为把具有上述性质的符号串称为规范句型的活规范句型的活前缀前缀LR(0)项目（看详细内容）项目（看详细内容）东华大学计算机学院LR(0)项目项目活前缀：活前缀：包含全部句柄，则：进行归约包含全部句柄，则：进行归约:A,记为记为A;部分句柄，则：部分句柄，则：应移进应移进(句柄的后半部分句柄的后半部分),A1 2不含句柄，则：不含句柄，则：期望移进一产生式的右部期望移进一产生式的右部:A 我们把右部添加了一个我们把右部添加了一个“”的产生式的产生式,称为称为LR(0)LR(0)项项项项目目目目LR(0)项目：项目：归约项目：归约项目：A

17、接受项目：接受项目：SS 移进项目：移进项目：A X,(X VT,可以是空串可以是空串)待约项目：待约项目：A X,(X VN,可以是空串可以是空串)东华大学计算机学院识别所有规范句型全部活前缀的识别所有规范句型全部活前缀的DFA例：文法例：文法GS：SA|BAaAb|c,BaBb|dLR(0)分析表的构造分析表的构造DFA的状态由若干的状态由若干LR(0)项目组成的集合项目组成的集合表示表示构造整个项目集为求基本项目的构造整个项目集为求基本项目的闭包过过程程,即整个项目集称为基本项目集的闭包。即整个项目集称为基本项目集的闭包。东华大学计算机学院I0:SSSASBAaAbAcBaBbBdI1:

18、SSSI2:SAAI3:SBBI4:AaAbAaAbAcBaBbBaBbBdaI5:AcccI6:BdddaI7:AaAbI9:BaBbI8:AaAbI10:BaBbBAbb识别识别GS全部活前缀的全部活前缀的DFASA|B AaAb|c,BaBb|d东华大学计算机学院LR(0)分析表的构造分析表的构造有了全部活前缀的有了全部活前缀的DFA，就可构造相应的，就可构造相应的LR(0)分析分析表表.项目集项目集代表了分析过程中各代表了分析过程中各状态状态，且分析动作相关。，且分析动作相关。因此要求每个项目集的各项目因此要求每个项目集的各项目相容，相容，即在同一项目即在同一项目集中不出现集中不出现:

19、移进项目与归约项目并存移进项目与归约项目并存;多个归约项目并存多个归约项目并存.若文法若文法G满足上述条件满足上述条件,即不含上述冲突项目即不含上述冲突项目,则称则称G为为LR(0)文法文法.显然显然,只有当一文法是只有当一文法是LR(0)文法时文法时,才能构造出无冲才能构造出无冲突动作的分析表来突动作的分析表来.东华大学计算机学院GS的的LR(0)分析表分析表ACTIONGOTOabcd#SAB0s4s5s61231acc2r1r1r1r1r13r2r2r2r2r24s4s5s6795r4r4r4r4r46r6r6r6r6r67s88r3r3r3r3r39s1010r5r5r5r5r5东华大

20、学计算机学院习题习题文法文法GB是否是是否是LR(0)文法？如果是，文法？如果是，请画出请画出LR(0)分析表；如果不是，请说分析表；如果不是，请说明原理：明原理：BbD;Se DD;d|d Ss;S|sSLR(1)分析表的构造分析表的构造东华大学计算机学院习题习题文法文法GS是否是是否是SLR(1)文法？如果是，文法？如果是，请画出请画出SLR(1)分析表；如果不是，请分析表；如果不是，请说明原理：说明原理：SCbBAAAab|abBC|DbCaLR(1)分析表的构造分析表的构造东华大学计算机学院I0:SS,#SCbBA,#Ca,bI1:SS,#SI3:Ca,#aI2:SCbBA,#CI4:SCbBA,#BC,aBDb,aCa,aDa,bbI5:SCbBA,#AAab,#/aAab,#/aI6:BC,#BCI8:Ca,aDa,baI7:BDb,aI9:BDb,aDbI11:Aab,#/aI12:Aab,#/aabI10:SCbBA,#AAab#/aAI13:AAab,#/aI14:AAab,#/aab文法文法GS的的LR(1)项目集及项目集及DFA东华大学计算机学院分析表实例分析表实例状态状态ACTIONGOTOabcSABCD0s3121acc2s43r64s85675s11106r47s98r6r79r510s13r111s1212r3r313s1414r2r2