自顶向下语法分析.ppt

S.P,O.P,知识结构,任务：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。,两大类分析方法：,自顶向下分析,自底向上分析,语法分析的任务,存在主要问题:回溯问题,左递归问题,主要方法：递归子程序法、LL分析法,自顶向下分析算法的基本思想为：,自底向上分析算法的基本思想为：,存在主要问题:“可归约串”的识别问题,主要方法：算符优先分析法、LR分析法,5.1自顶向下分析法,自顶向下分析的一般过程,从S出发采用最左推导，试图逐步推出输入串,L(GS)?S作为语法树的根，试图自上而下地为构造一棵语法树 若叶结点从左向右排列恰好，则表示是文法的句子，而这棵语法树就是句子的语法结构 若构造不出语法树，则不是文法的句子,自顶向下分析方法分类,确定的,不确定的,回溯,【例】G1S:S pA|qBA cAd|aB d B|c识别输入串w=pccadd是否是G1S的句子,试探推导过程：S pA pcAd pccAdd pccadd试探成功,这个文法的特点：1、每个产生式的右部都由终结符号开始2、如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始,【例】G2S:S Ap|BqA a|cA B b|dB识别输入串w=ccap是否是G2S的句子,试探推导过程：S Ap cAp ccAp ccap试探成功,这个文法的特点：1、产生式的右部不全是由终结符开始2、如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始3、文法中无空产生式,1.FIRST集,FIRST()：从可能推导出的所有开头终结符号或,对于文法G的所有非终结符的每个候选式，其终结首符号集称为FIRST集，定义如下：,【例】SaAbAcd|c,【例】SAaAa|,（1）若=a，且aVT，则aFIRST()；例：FIRST(i)=i FIRST(+TE)=+,ETEE+TE|TFTT*FT|F(E)|i,构造FIRST集的算法,（2）若=X，XVN，且有产生式Xb，则把b加入到FIRST()中；例：FIRST(FT)=(,i?,（3）若=X1X2 Xn，其中XiVN,1in；,将FIRST(X1)中的一切非的终结符加进FIRST()；若FIRST(X1),则将FIRST(X2)中的一切非的终结符加进FIRST()；若FIRST(X1)且FIRST(X2),则将FIRST(X3)中的一切非的终结符加进FIRST()；依此类推，若对于一切1in,FIRST(Xi)，则将加进FIRST()。,ETEE+TE|TFTT*FT|F(E)|i,例：FIRST(FT)=,FIRST(F)-=(,i,【例】G2S:S Ap|BqA a|cA B b|dB识别输入串w=ccap是否是G2S的句子,试探推导过程：S Ap cAp ccAp ccap试探成功,FIRST（Ap）a，cFIRST（Bq）b，d,FIRST(F)=(,iFIRST(T)=*,FIRST(T)=FIRST(F)-=(,iFIRST(E)=+,FIRST(E)=FIRST(T)-=(,i,【例】GEETEE+TE|TFTT*FT|F(E)|i,计算文法中非终结符的First集合,【例】G3S:S aA|dA bAS|识别输入串w=abd是否是G3S的句子,试探推导过程：S aA abAS abS abd试探成功,这个文法的特点：1、含有空产生式2、非空产生式右部首符号集合两两不相交3、紧跟该非终结符右边可能出现的终结符集合也不相交,2.FOLLOW集,FOLLOW(A)：是所有句型中紧接A之后的终结符号或#,对于文法G的非终结符的后继符号集称为FOLLOW集，定义如下：,构造集合FOLLOW的算法,（1）若A为开始符号，则把“#”加入FOLLOW(A)中；,（2）若BA()，则把FIRST()-加入FOLLOW(A)中；,注：FOLLOW集合中不含有,ETEE+TE|TFTT*FT|F(E)|i,#FOLLOW(E),由F(E)可知，)FOLLOW(E),由ETE，应把FOLLOW(E)加入FOLLOW(E)由E+TE 且E，应把FOLLOW(E)加入FOLLOW(T),【例】GEETEE+TE|TFTT*FT|F(E)|i,FOLLOW(E)=#,)E是开始符号#FOLLOW(E)又F(E)FOLLOW(E)FOLLOW(E)=#,)E TE FOLLOW(E)加入 FOLLOW(E)FOLLOW(T)=+,),#E+TE FIRST(E)-加入FOLLOW(T)又E，FOLLOW(E)加入FOLLOW(T)FOLLOW(T)=FOLLOW(T)=+,),#T FT FOLLOW(T)加入FOLLOW(T)FOLLOW(F)=*,+,),#T FT FOLLOW(F)=FIRST（T）-又T FOLLOW(T)加入FOLLOW(F),FIRST(F)=(,iFIRST(T)=*,FIRST(T)=(,iFIRST(E)=+,FIRST(E)=(,i,求FOLLOW集合,LL的含义自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则,5.2 LL(1)文法的判别,要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法。,一个文法G是LL(1)的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立：,FIRST()FIRST()=,也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出.假若=，那么，FIRST（)FOLLOW（A）.也就是，若=,则所能推出的串的首符号不应在FOLLOW(A）中,*,*,若=，则 SELECT(A)=First()若=，则SELECT(A)=(First()-)Follow(A),*,*,一个文法是LL(1)的充要条件：对于每个形如 的产生式，满足 Select()Select()=其中：、不能同时推出,LL(1)文法的判别条件,求出能推出的非终结符计算First集合计算Follow集合计算Select集合不满足Select()Select()=的不是LL(1)文法，否则是LL(1)文法。,LL(1)文法的判别步骤,【例】GE：ETEE+TE|TFTT*FT|F(E)|i判别该文法是否为LL(1)文法？,FIRST(F)=(,iFIRST(T)=*,FIRST(T)=(,iFIRST(E)=+,FIRST(E)=(,i,FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，#FOLLOW(F)=*,，),#,E+TE|FIRST(+TE)=+FOLLOW(E)=)，T*FT|FIRST(*FT)=*FOLLOW(T)=+,)，F(E)|i FIRST(E)=(FIRST(i)=i所以GE是LL（1）的,【例】GE：ETE E+TE|TFTT*FT|F(E)|i,例1：设有文法(1)S-xAy(2)A-*|*现有输入串：x*y 其分析过程如下：,失败，需要退回，重新选取A的侯选式这时使得分析器的动作不稳定,产生的原因？,自顶向下分析面临的问题,问题1：回溯,1.回溯问题,什么是回溯（backtracking）?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件：,文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。,回溯带来的问题：,严重的低效率：语法分析要重做、语义处理工作要推倒重来,自顶向下分析存在的主要问题,迷宫求解,消除回溯的途径：,改写文法,对具有多个右部的规则反复提取左因子,【例】对下述两个产生式，提取公共左因子改造文法。if E then S1 else S2 if E then S1,if E then S1 U U else S2|,A1|2|n,如果1n中还有几个首符号相同，可反复提取引入了许多非终结符和产生式,1.递归规则：规则右部有与左部相同的符号 左递归规则：AA 右递归规则：AA 自嵌入递归规则：AA,递归文法,2.递归文法：含有递归规则的文法，为直接递归文法,ABaBAb,递归文法的优点：可用有穷条规则，定义无穷语言,例：对于前面给出的无符号整数的文法是有递归文法，用12条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？,!,GS：SSD|DD0|1|2|3|4|5|6|7|8|9,左递归文法的缺点：不能用自顶向下的方法来进行语法分析,会造成死循环,GE：Ei+i|i*i|(i+i)*i,该文法所描述的语言为L(G)=i+i,i*i,(i+i)*i，无法表示无穷的表达式语言,2.左递归问题,【例】文法GE：EE+T|TTT*F|FF(E)|i给出i*i+i自顶向下的分析过程。,要实行自顶向下分析，必须要消除文法的左递归,从左向右扫描源程序，同时实施最左推导,失败：由于使用最左推导，对左递归文法进行自顶向下分析时，会导致死循环。,将左递归规则改为右递归规则,AA|,【例】文法GE：EE+T|TTT*F|F F(E)|i,ETEE+TE|TFTT*FT|F(E)|i,（1）消除直接左递归,消除直接左递归课内练习,文法G:P PaPb|BaP转化为：,P BaPPP aPbP|,注：只有最左边的P参加变换。,(2)消除间接左递归（了解自学）,先通过产生式进行非终结符置换将间接左递归变为直接左递归消除直接左递归把置换的产生式加入,详例见书文法G6，P89,5.3 某些非LL(1)文法到LL(1)文法的等价转换,消除左递归和提取公共左因子,【例】GS:SaSb|AAbAc|bBcBBa|a,【例】GS:SaSb|AAbAc|bBcBBa|a,不确定的自顶向下分析思想,当文法不满足LL(1)时，不能用确定的自顶向下分析，但可用不确定的自顶向下分析，也就是带回溯的自顶向下分析法（试探）。,由于相同左部的产生式的右部First集交集不为空引起由于相同左部非终结符的右部存在能推导出的产生式，且该非终结符的Follow集中含有其他产生式右部First集的元素文法含左递归,确定的自顶向下分析方法,递归子程序法,对文法中的每个非终结符（语法成分）编写一个子程序，而子程序的代码结构由相应非终结符的产生式右部所决定：产生式右部的终结符与输入符号相匹配 非终结符与相应的子程序调用对应,构造方法非常简单 程序结构清晰 递归调用较多，占用内存多、速度慢 如果所采用的高级语言不允许递归，则不能使用此方法,特点,自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式,基本思想：,LL(1)分析法,使用下推自动机的方式实现。使用一个二维分析表和栈联合进行控制来实现分析。,确定的自顶向下分析方法,预测分析法,LL(1)分析器的逻辑结构：分析栈、分析表、总控程序,文法符号,根据栈顶符号X和当前输入符号a来决定分析器的动作,在实际语言中，每一种语法成分都有确定的左右界符，为研究问题方便，统一以表示输入串结束,ETEE+TE|TFTT*FT|F(E)|i,第1列为非终结符,第1行为终结符+#,每个元素为产生式或空,分析表中的元素表示：在分析时需要将A展开，如果当前符号为a时，应该选择元素MA,a中存放的产生式。如果MA,a为空，表示出现语法错误。,预测分析表构造算法,1.对每个终结符aSelect()，把加至A,a中；2.把所有无定义的A,a标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的,如果文法是LL(1)文法，其预测分析表中没有多重定义的元素，可以进行确定的分析。,ETEE+TE|TFTT*FT|F(E)|i,请按照上述算法构造分析表,总控程序算法描述,将#压入堆栈中，将开始符号S压入堆栈中读取下一个符号到a；每次执行下述动作：栈顶符号弹出放入X中；如果X为终结符号：如果X=a=#，分析结束，接受句子。如果X=a!=#，表明成功匹配;X出栈,a 取下一个符号如果 X!=a，出错处理。如果X为非终结符号,则查分析表M:如果MX,a为空，出错处理。如果MX,a=X1 X2Xn,则:X 出栈;将右部Xn X2 X1反序压入S中。,步骤 符号栈 读入符号剩余符号串 使用产生式,1.Ei+i*i#ETE,2.ETi+i*i#TFT,3.ETFi+i*i#Fi,4.ET i i+i*i#,5.ET+i*i#T,6.E+i*i#E+TE,7.ET+i*i#,输入串为:i+i*i#,ETEE+TE|TFTT*FT|F(E)|i,步骤 符号栈读入符号剩余符号串 使用产生式,8.ET i*i#TFT,9.ETF i*i#Fi,10.ET i i*i#,11.ET*i#T*FT,12.ETF*i#,13.ETF i#Fi,14.ET i i#,15.ET#T,16.E#E,17.#accept,例题1已知文法GS:S aHH aMd|dM Ab|A aM|e1.判断GS是否为LL（1）文法，若是，请构造相应的LL（1）预测分析表2.若GS是LL（1）文法，请给出对输入串aaabd#的预测分析过程，并说明该输入串是否是GS的句子,5.6典型例题及解答,确定的自顶向下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。要求通过本章的学习后，能够对一个给定的文法判断是否是LL(1)文法；能构造预测分析表；能用预测分析方法判断给定的输入符号串是否是该文法的句子；对某些非LL(1)文法做等价变换后可能变成LL(1)文法。,小结,