语法分析和语法分析.ppt
编 译 原 理,第 四 章语法分析及语法分析程序,东华大学计算机学院,本章内容,自顶向下分析和自底向上分析围绕分析器的自动生成展开,东华大学计算机学院,难 重 点,语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。,东华大学计算机学院,自顶向下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。,自底向上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,东华大学计算机学院,自底向上的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否是该文法的句子,关键：句柄的确定,东华大学计算机学院,自顶向下分析的语法分析,例：文法S aCb C cd|c 为输入串w=acb建立分析树,试探的过程,问题：会产生回溯,东华大学计算机学院,自顶向下分析法的另一问题,若有文法G6S:(1)SSa(2)Sb推导baa#,问题：左递归,东华大学计算机学院,自顶向下分析法需要解决的问题,左递归对文法进行改造回溯如何唯一地确定所采用的产生式？LL(1)文法当拒绝w时,只能知道w不是句子,不知出何错及出在何处,东华大学计算机学院,本节将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。本节主要介绍内容为：LL(1)文法的定义和判别 非LL(1)文法的等价变换 确定的自顶向下分析方法 递归子程序法 预测分析方法,东华大学计算机学院,4.1 自顶向下的语法分析,消除文法的左递归带回溯的递归子程序回溯的消除及LL(1)文法,东华大学计算机学院,4.1.1 消除文法的左递归,例：AA|A的解是：*引入新的非终结符A,令其产生*,则有:A A A A|对于 AA1|A2|An|1|m消除直接左递归 A1A|mA 及 A 1A|nA|,东华大学计算机学院,消除文法左递归的矩阵方法,设文法的非终结符为 X1,X2,Xn,Xi的产生式分为以VN符和VT符打头的两类.将|改写为+,有Xi=X11i+X22i+Xnni+i 其中,i 是以VT符打头的产生式之和,ki 可以为 这样,文法G可表示为X=XA+B。,东华大学计算机学院,消除文法左递归的矩阵方法,该方程有解:X=BA*为得到A*,由于,则有:X=BZ，Z=I+AZ其中X的产生式以VT符打头,而Z的产生式以ijV*打头,因此将不含左递归.注意,由此所得的文法含有无用符号和无用产生式,需化简,东华大学计算机学院,消除文法左递归的例子,例4.1 SSa|Ab|a ASc相应的矩阵为,展开矩阵,得S aZ11A aZ12Z11aZ11|cZ21|Z12 aZ12|cZ22Z21 bZ11Z22|bZ12消除文法中无用产生式S aZ11Z11aZ11|cZ21|Z21 bZ11,东华大学计算机学院,消除回溯的条件,候选式的终结首符集FIRST()=a|*a,aVT,V*时,FIRST()若A-产生式的各候选式i(i=1,2,m)都推不出，且 FIRST(i)互不相交，则当扫描当前输入符号aiFIRST(j)时,唯一可用于推导的产生式只能是Aj。,东华大学计算机学院,消除回溯的条件,例如,文法G1S:SAAAaAb|*,A-产生式有两个候选式,两集不相交FIRST(aAb)=aFIRST(*)=*设输入串为aa*bb*,最左推导 SAA(a)aAbA(a)aaAbbA(*)aa*bbA(*)aa*bb*(#)无回溯的条件:FIRST(i)FIRST(j)=,东华大学计算机学院,消除回溯的条件,存在某候选式i,i*,即FIRST(i),有两种选择匹配当前扫描符号a：存在某j,使j推导出以a打头的符号串选择i,让跟随在后的符号串推导出以a打头的符号串。,东华大学计算机学院,消除回溯的条件,若两种选择都可行,则回溯不可避免。因此,要求当i*时,跟在后的符号串不能推导出其它j所能推导出的首终结符符号串。定义：A后的所有终结符之集FOLLOW(A)=a|S#*Aa,aVT#,V*当A为一句型的尾符号时,#FOLLOW(A)。,东华大学计算机学院,消除回溯的条件,无回溯的条件为:若i*,则FOLLOW(A)与其它j互不相交FOLLOW(A)FIRST(j)=.,东华大学计算机学院,First&Follow,文法为：0）SM H 1）Sa 2）HL S o 3）H 4）Kd M L 5）K 6）Le H f 7）MK 8）Mb 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中每个AVT,A-产生式中任何两个候选式i,j,均满足:(1)FIRST(i)FIRST(j)=(ij 1i,jm)(2)i,j中,至多有一个能推导出;(3)若j*,则FIRST(i)FOLLOW(A)=(i=1,2,m ij)注:条件(2)可省略.即(1)(2)满足上述条件的文法称为LL(1)文法,东华大学计算机学院,4.1.4 某些非LL(1)文法的改造,方法：消除左递归反复提取左因子例：EE+T|TT(E)|a(E)|a 经改造后可得文法：ETEE+TE|TaT|(E)T(E)|这是一个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.1 优先文法,（略）,东华大学计算机学院,4.2.4 LR分析法,LR分析:自左至右扫描的自底向上的分析LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最广泛使用的方法;一般用CFG描述的语言均可用LR分析法先介绍LR分析器的逻辑结构及工作原理,再分别介绍几种LR分析器(即LR(0),SLR(1)和LR(1)的构造,东华大学计算机学院,（一）LR分析器的逻辑结构及工作原理,LR分析器=输入符号串+分析栈+总控程序+分析表例：文法GL:1.LE,L 2.LE 3.Ea 4.Eb分析表,例：a,b,a分析过程,分析动作：移进、归约、接受、报错,东华大学计算机学院,GL:1.LE,L 2.LE 3.Ea 4.Eb,东华大学计算机学院,对符号串“a,b,a”的分析过程,东华大学计算机学院,（二）LR(0)分析表的构造,一些术语规范句型的活前缀(viable prefix)将栈内符号与未扫描的输入串拼接起来,可得一规范句型.即栈内符号串总是规范句型的前缀,且不含句柄右侧的符号.把具有上述性质的符号串称为规范句型的活前缀LR(0)项目（看详细内容）,东华大学计算机学院,LR(0)项目,活前缀：包含全部句柄，则：进行归约:A,记为A;部分句柄，则：应移进(句柄的后半部分),A12不含句柄，则：期望移进一产生式的右部:A我们把右部添加了一个“”的产生式,称为LR(0)项目LR(0)项目：归约项目：A接受项目：SS移进项目：AX,(XVT,可以是空串)待约项目：AX,(XVN,可以是空串),东华大学计算机学院,识别所有规范句型全部活前缀的DFA,例：文法GS：SA|B AaAb|c,BaBb|dLR(0)分析表的构造DFA的状态由若干LR(0)项目组成的集合表示构造整个项目集为求基本项目的闭包过程,即整个项目集称为基本项目集的闭包。,东华大学计算机学院,识别GS全部活前缀的DFASA|B AaAb|c,BaBb|d,东华大学计算机学院,LR(0)分析表的构造,有了全部活前缀的DFA，就可构造相应的LR(0)分析表.项目集代表了分析过程中各状态，且分析动作相关。因此要求每个项目集的各项目相容，即在同一项目集中不出现:移进项目与归约项目并存;多个归约项目并存.若文法G满足上述条件,即不含上述冲突项目,则称G为LR(0)文法.显然,只有当一文法是LR(0)文法时,才能构造出无冲突动作的分析表来.,东华大学计算机学院,GS的LR(0)分析表,东华大学计算机学院,习题,文法GB是否是LR(0)文法？如果是，请画出LR(0)分析表；如果不是，请说明原理：BbD;SeDD;d|d Ss;S|s,SLR(1)分析表的构造,东华大学计算机学院,习题,文法GS是否是SLR(1)文法？如果是，请画出SLR(1)分析表；如果不是，请说明原理：SCbBA AAab|ab BC|Db Ca,LR(1)分析表的构造,东华大学计算机学院,I0:S S,#SCbBA,#C a,b,I1:S S,#,S,I3:Ca,#,a,I2:S CbBA,#,C,I4:SCbBA,#BC,aB Db,aC a,aD a,b,b,I5:SCbBA,#AAab,#/aA ab,#/a,I6:BC,#,B,C,I8:Ca,aD a,b,a,I7:BD b,a,I9:BDb,a,D,b,I11:Aab,#/a,I12:Aab,#/a,a,b,I10:SCbBA,#A Aab#/a,A,I13:AAab,#/a,I14:AAab,#/a,a,b,文法GS的LR(1)项目集及DFA,东华大学计算机学院,分析表实例,
