自顶向下语法分析.ppt

1、2020年10月10日,S.P,O.P,2020年10月10日,知识结构,2020年10月10日,任务：根据文法规则，从源程序单词符号串中识别出语法 成分，并进行语法检查。,两大类分析方法：,自顶向下分析,自底向上分析,语法分析的任务,2020年10月10日,存在主要问题: 回溯问题,左递归问题,主要方法：递归子程序法、 LL分析法,自顶向下分析算法的基本思想为：,自底向上分析算法的基本思想为：,存在主要问题:“可归约串”的识别问题,主要方法：算符优先分析法、 LR分析法,2020年10月10日,5.1自顶向下分析法,自顶向下分析的一般过程,从S出发采用最左推导，试图逐步推出输入串,L(GS)

2、? S作为语法树的根，试图自上而下地为构造一棵语法树 若叶结点从左向右排列恰好，则表示是文法的句子，而这棵语法树就是句子的语法结构 若构造不出语法树，则不是文法的句子,2020年10月10日,自顶向下分析方法分类,确定的,不确定的,回溯,2020年10月10日,【例】 G1S: S pA |qB A cAd|a B d B |c 识别输入串w= pccadd是否是G1S的句子,试探推导过程： S pA pcAd pccAdd pccadd 试探成功,这个文法的特点： 1、每个产生式的右部都由终结符号开始 2、如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始,2020年10月10日,

3、【例】 G2S: S Ap |Bq A a|cA B b|dB 识别输入串w= ccap是否是G2S的句子,试探推导过程： S Ap cAp ccAp ccap 试探成功,这个文法的特点： 1、产生式的右部不全是由终结符开始 2、如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始 3、文法中无空产生式,2020年10月10日,1. FIRST集,FIRST()：从可能推导出的所有开头终结符号或,对于文法G的所有非终结符的每个候选式，其终结首符号集称为FIRST集，定义如下：,【例】 SaAb Acd|c,【例】 SAa Aa|,2020年10月10日,（1）若=a ，且aVT

4、 ，则aFIRST()； 例： FIRST(i)= i FIRST(+TE)= + ,ETE E+TE| TFT T*FT| F(E)|i,构造FIRST集的算法,（2）若=X ，XVN，且有产生式Xb，则把b加入到FIRST()中； 例： FIRST(FT)= ( , i ?,2020年10月10日,（3）若=X1X2 Xn，其中XiVN , 1in；, 将FIRST(X1)中的一切非的终结符加进FIRST()； 若FIRST(X1),则将FIRST(X2)中的一切非的终结符加进FIRST()； 若FIRST(X1)且FIRST(X2),则将FIRST(X3)中的一切非的终结符加进FIRST

5、()； 依此类推，若对于一切1in,FIRST(Xi)，则将加进FIRST()。,ETE E+TE| TFT T*FT| F(E)|i,例：FIRST(FT)=,FIRST(F)-=(,i,2020年10月10日,【例】 G2S: S Ap |Bq A a|cA B b|dB 识别输入串w= ccap是否是G2S的句子,试探推导过程： S Ap cAp ccAp ccap 试探成功,FIRST（Ap）a，c FIRST（Bq）b，d,2020年10月10日,FIRST(F)=(,i FIRST(T)=*, FIRST(T)=FIRST(F)-=(,i FIRST(E)=+, FIRST(E)=

6、 FIRST(T)-=(,i,【例】 GE ETE E+TE| TFT T*FT| F(E)|i,计算文法中非终结符的First集合,2020年10月10日,【例】 G3S: S aA|d A bAS| 识别输入串w= abd是否是G3S的句子,试探推导过程： S aA abAS abS abd 试探成功,这个文法的特点： 1、含有空产生式 2、非空产生式右部首符号集合两两不相交 3、紧跟该非终结符右边可能出现的终结符集合也不相交,2020年10月10日,2. FOLLOW集,FOLLOW(A)：是所有句型中紧接A之后的终结符号或#,对于文法G的非终结符的后继符号集称为FOLLOW集，定义如下

7、：,2020年10月10日,构造集合FOLLOW的算法,（1）若A为开始符号，则把“#”加入FOLLOW(A)中；,（2）若BA ()，则把FIRST()-加入FOLLOW(A)中；,注：FOLLOW集合中不含有,ETE E+TE| TFT T*FT| F(E)|i,#FOLLOW(E),由F(E)可知， )FOLLOW(E),由ETE，应把FOLLOW(E)加入FOLLOW(E) 由E + TE 且E ，应把FOLLOW(E )加入FOLLOW(T),2020年10月10日,【例】 GE ETE E+TE| TFT T*FT| F(E)|i,FOLLOW(E)=#,) E是开始符号#FOLL

8、OW(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)=(,i FIRST(T)=*, FIRST(T) =(,i FIRST(E

9、)=+, FIRST(E)=(,i,求FOLLOW集合,2020年10月10日,LL的含义 自左向右扫描分析输入符号串 从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则 LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则,5.2 LL(1)文法的判别,要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法。,2020年10月10日,一个文法G是LL(1)的，当且仅当对于G的每一个非终结符的任何两个不同产生式 ，下面的条件成立：,FIRST()FIRST()= ,也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出 .假若

10、 = ，那么， FIRST（)FOLLOW（A）. 也就是， 若 = ,则所能推出的串的首符号不应在FOLLOW(A）中,*,*,2020年10月10日,若=，则 SELECT(A)=First() 若=，则 SELECT(A)=(First()-)Follow(A),*,*,一个文法是LL(1)的充要条件 ： 对于每个形如 的产生式，满足 Select() Select() = 其中： 、不能同时推出,LL(1)文法的判别条件,2020年10月10日,求出能推出的非终结符 计算First集合 计算Follow集合 计算Select集合 不满足Select() Select() = 的不是LL

11、(1)文法，否则是LL(1)文法。,LL(1)文法的判别步骤,2020年10月10日,【例】 GE： ETE E+TE| TFT T*FT| F(E)|i 判别该文法是否为LL(1)文法？,FIRST(F)=(,i FIRST(T)=*, FIRST(T) =(,i FIRST(E)=+, FIRST(E)=(,i,FOLLOW(E)=), FOLLOW(E)=)， FOLLOW(T)=，)， FOLLOW(T)=,)，# FOLLOW(F)=*,，),#,2020年10月10日,E +TE | FIRST(+TE)=+ FOLLOW(E)=)， T *FT | FIRST(*FT)=* FO

12、LLOW(T)=+,)， F (E) | i FIRST(E)=( FIRST(i)=i 所以GE是LL（1）的,【例】 GE：ETE E+TE| TFT T*FT| F(E)|i,2020年10月10日,例1：设有文法 (1) S - xAy (2) A - *|* 现有输入串：x*y 其分析过程如下：,失败，需要退回，重新选取A的侯选式 这时使得分析器的动作不稳定,产生的原因？,自顶向下分析面临的问题,问题1：回溯,2020年10月10日,1.回溯问题,什么是回溯（backtracking）?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件：,文法中，对于某个非终结符号的规则其右

13、部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。,回溯带来的问题：,严重的低效率：语法分析要重做、语义处理工作要推倒重来,自顶向下分析存在的主要问题,2020年10月10日,迷宫求解,2020年10月10日,消除回溯的途径：,改写文法,对具有多个右部的规则反复提取左因子,【例】对下述两个产生式，提取公共左因子改造文法。 if E then S1 else S2 if E then S1,if E then S1 U U else S2 |,2020年10月10日,A1|2|n,如果1n中还有几个首符号相同，可反复提取 引入了许多非终结符和产生式,2020年10月1

14、0日,1.递归规则：规则右部有与左部相同的符号 左递归规则：AA 右递归规则：AA 自嵌入递归规则：AA,递归文法,2.递归文法：含有递归规则的文法，为直接递归文法,ABa BAb,2020年10月10日,递归文法的优点：可用有穷条规则，定义无穷语言,例：对于前面给出的无符号整数的文法是有递归文法，用12条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？,!,GS： SSD|D D0|1|2|3|4|5|6|7|8|9,2020年10月10日,左递归文法的缺点：不能用自顶向下的方法来进行语法分析,会造成死循环,GE：Ei+i|i*i|(i+i)*i,该文法所描述的语言为

15、L(G)=i+i,i*i,(i+i)*i，无法表示无穷的表达式语言,2020年10月10日,2.左递归问题,【例】文法GE： EE+T|T TT*F|F F(E)|i 给出i*i+i自顶向下的分析过程。,要实行自顶向下分析，必须要消除文法的左递归,从左向右扫描源程序，同时实施最左推导,失败：由于使用最左推导，对左递归文法进行自顶向下分析时，会导致死循环。,2020年10月10日,将左递归规则改为右递归规则,AA|,【例】文法GE： EE+T| T TT*F| F F(E)|i,ETE E+TE| TFT T*FT| F(E)|i,（1）消除直接左递归,2020年10月10日,消除直接左递归课内

16、练习,文法G : P PaPb|BaP 转化为：,P BaPP P aPbP| ,注：只有最左边的P参加变换。,2020年10月10日,(2)消除间接左递归（了解自学）,先通过产生式进行非终结符置换 将间接左递归变为直接左递归 消除直接左递归 把置换的产生式加入,详例见书文法G6，P89,2020年10月10日,5.3 某些非LL(1)文法到LL(1)文法的等价转换,消除左递归和提取公共左因子,【例】 GS: SaSb|A AbAc|bBc BBa|a,【例】 GS: SaSb|A AbAc|bBc BBa|a,2020年10月10日,不确定的自顶向下分析思想,当文法不满足LL(1)时，不能用

17、确定的自顶向下分析，但可用不确定的自顶向下分析，也就是带回溯的自顶向下分析法（试探）。,由于相同左部的产生式的右部First集交集不为空引起 由于相同左部非终结符的右部存在能推导出的产生式，且该非终结符的Follow集中含有其他产生式右部First集的元素 文法含左递归,2020年10月10日,确定的自顶向下分析方法,递归子程序法,对文法中的每个非终结符（语法成分）编写一个子程序，而子程序的代码结构由相应非终结符的产生式右部所决定： 产生式右部的终结符与输入符号相匹配 非终结符与相应的子程序调用对应,构造方法非常简单 程序结构清晰 递归调用较多，占用内存多、速度慢 如果所采用的高级语言不允许递

18、归，则不能使用此方法,特 点,2020年10月10日,自左向右扫描分析输入符号串 从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式,基本思想：,LL(1)分析法,使用下推自动机的方式实现。 使用一个二维分析表和栈联合进行控制来实现分析。,确定的自顶向下分析方法,预测分析法,2020年10月10日,LL(1)分析器的逻辑结构：分析栈、分析表、总控程序,文法符号,根据栈顶符号X和当前输入符号a来决定分析器的动作,2020年10月10日,在实际语言中，每一种语法成分都有确定的左右界符，为研究问题方便，统一以表示输

19、入串结束,ETE E+TE| TFT T*FT| F(E)|i,第1列为非终结符,第1行为终结符+#,每个元素为产生式或空,分析表中的元素表示：在分析时需要将A展开，如果当前符号为a时，应该选择元素MA,a中存放的产生式。如果MA,a为空，表示出现语法错误。,2020年10月10日,预测分析表构造算法,1.对每个终结符aSelect()，把加至A,a中； 2.把所有无定义的A,a标上“出错标志”。 可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的,如果文法是LL(1)文法，其预测分析表中没有多重定义的元素，可以进行确定的分析。,2020年10月10日,ETE E+TE

20、| TFT T*FT| F(E)|i,请按照上述算法构造分析表,2020年10月10日,总控程序算法描述,将#压入堆栈中，将开始符号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中。 ,2020年10月10日,2020年10月10日,步