编译原理4章4.

第四章自顶向下语法分析方法4.1语法分析器的功能：语法分析是整个编译过程的核心部分，它完成的任务是：按照文法从源程序单词串(符号串)中识别各类语法成分，判断所给出的单词串是否是给定文法的正确句子，并为语义分析和代码生成做准备。语法分析器词法分析器编译程序后续部分符号表源程序单词符号取下一单词符号语法分析树4.2不确定的自顶向下分析一、算法思想：对于任一输入符号串，试用一切可能的办法从树根结点出发根据文法自上向下的为输入串建立一棵语法树。二、举例：设有文法G[S]:(1)ScAd(2)Aab|a给定输入串w=cad,试给出分析过程Scad(1)据初始符号产生根结点S,并让读指针指向输入串首符号cScad(2)据S的产生式发展语法树cAdScad(3)用S的子结点(cAd)匹配输入串，首符号匹配，读指针向下移动cAdScad(4)A有两个选择，选择第一个进行试探，发展语法树。cAdabcScad(5)子树A的最左子结点与指针所指符号匹配，指针移动，与A的第二个结点匹配，失败！回溯。AdabScad(6)回溯要把A的第一个选择所生长的子树销掉，并把分析指针恢复到进入A时的值。cAdScad(7)用A的第二个选择生成语法树cAdaScad(8)A的子结点与当前符号匹配，指针移动，S的第三结点d进入工作，匹配成功cAda三、对应最左推导：以上为输入符号串建立语法树的过程，实际上也是一个建立最左推导序列的过程，显然有：ScAdcad，之所以使用最左推导，是因为我们对输入串是从左到右扫描的，只有使用最左推导，才能按扫描顺序去匹配输入串。四、存在问题：p681.左递归问题：自顶向下分析方法，在匹配过程中，假若用到非终结符号U去匹配输入串，而U为左递归的(例如：UU…)，那么为了用它的右部匹配输入串，又要用到非终结符号U，循环往复，没有终止。若文法存在间接递归，也有相同问题发生。2.回溯问题：对某个非终结符，当有多条规则时，需采用逐个选择的方法，若不能匹配需要回溯，代价高，效率低。4.3确定的自顶向下分析思想一、算法思想：对于任一输入符号串，从文法的识别符号出发，根据当前的输入符号，唯一的确定一个产生式，用产生式的右部的符号串替代相应的非终结符往下推导，或构造一棵语法树。若能推导出输入串或构造语法树成功则输入串是句子，否则不是。二、举例：(1)文法G[S]:SpA|qBAcAd|a输入串w=pccaddSpAAcdAcda对应最左推导：SpApcAdpccAddpccadd文法特点：(1)每个产生式的右部都由终结符号开始；(2)两个产生式若左部相同，则其右部以不同的终结符号开始；(3)无空产生式U方法：根据产生式右部的首符号选择产生式。(2)文法G[S]:SAp|BqAcA|aBdB|b输入串w=ccapSApcAcAa对应最左推导：SApcApccApccap文法特点：(1)每个产生式的右部并非都由终结符号开始；(2)两个产生式若左部相同，则其右部以不同的终结符号或非终结符号开始，且首符号集不相交；(3)无空产生式U方法：根据产生式右部的首符号选择产生式。(3)文法G[S]:SaA|dAbAS|输入串w=abdSaAAbSd对应最左推导：SaAabASabSabd文法特点：(1)有空产生式U；(2)两个产生式若左部相同，则其对应的首符号集不相交并且与其后继符号集也不相交；方法：根据产生式的可选集选择产生式。例题(1)(2)(3)的共同特点：1)没有左递归2)在每一步推导中，都可以根据输入串的当前符号唯一的确定一个产生式去匹配。4.3.2几个重要集合一、首符号集：设有文法G=(VT,VN,S,P)是上下文无关文法，则符号串x的首符号集合定义为：First(x)={a|x*ay,aVT,yV*}，*若x,则First(x).First(x)={a|x*a…,aVT}，例如：有如下文法G[E]：EE+T|TTT*F|FF(E)|i则有：First(E+T)={(,i}First(T)={(,i}First(i*i)={i}二、后继符号集：设有文法G=(VT,VN,S,P)是上下文无关文法，UVN,则非终结符号U的后继符号集定义为：*Follow(U)={a|S…Ua…,aVT}，*若S…U,则#Follow(U).#是指输入串的括号，如#abcd#例如：有文法G[E]：EE+T|TTT*F|FF(E)|i因有E*E所以有：#Follow(E)因有E*E+T所以有：+Follow(E)因有E*(E)所以有：)Follow(E)故，Follow(E)={#,+,)}因有E*T同理，所以有：#Follow(T)因有E*T+T所以有：+Follow(T)因有E*T*F所以有：*Follow(T)因有E*(T)所以有：)Follow(T)故，Follow(T)={#,+,*,)}1.构造文法符号X的FIRST集：(1)X∈VT，则FIRST(X)={X};(2)X∈VN，且有Xa…,则a加入FIRST(X)；若有Xε，则ε加入FIRST(X)；(3)若有XY…,且Y∈VN,则FIRST(Y)中非ε元素全部加入FIRST(X)；若有XY1Y2Y3…YK,且Yi∈VN,ε∈FIRST(Yj)则FIRST(Yi)中非ε元素加入FIRST(X)；若ε∈FIRST(Xj),1≤j≤k，则ε加入FIRST(X)2≤i≤k1≤j＜i2.构造符号串α的FIRST集:(α=X1X2…XN)(1)首先FIRST(α)=FIRST(X1)\{ε};(2)若ε∈FIRST(Xj),则FIRST(Xi)\{ε}加入FIRST(α);(3)若ε∈FIRST(Xj),则ε加入FIRST(α);1≤j＜i1≤j≤k三、FIRST集及FOLLOW集的构造例：设有文法G[E]:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i求非终结符号的First集：First(E)={(,i}First(E’)={+,ε}First(T)={(,i}First(T’)={*,ε}First(F)={(,i}3.构造非终结符X的FOLLOW集例：前述文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i非终结符的Follow集：Follow(E)={),#}Follow(E’)={),#}Follow(T)={+,),#}Follow(T’)={+,),#}Follow(F)={*,+,),#}(1)对文法开始符号S,#加入FOLLOW(S);(2)若有AαBβ,则FIRST(β)\{ε}加入FOLLOW(B);(3)若有AαB,或AαBβ且ε∈FIRST(β)，则FOLLOW(A)加入FOLLOW(B);LL(1)文法：如果一个文法满足以下条件：1、文法不含左递归。2、对文法中每一个非终结符A的各个产生式的候选首符集两两不相交。3、对文法中每一个非终结符A，若存在某个候选首符集包含，则First(A)Follow(A)=LL(1)中第一个L表明自左(Left)向右扫描输入串，第二个L表明分析过程采用最左(Left)推导，括号中的1表明只需向右看一个符号便可决定选择哪个产生式进行推导。4.3.1非LL(1)文法转换为LL(1)文法对某个语言来说其文法不一定是LL(1)文法，而非LL(1)文法将无法采用确定的自顶向下分析方法进行分析，但我们可以通过对文法进行等价变换，在有些情况下使其成为LL(1)文法。一、提取左公共因子：设文法中有Uxy|xw(UVN,x,y,wV*)形式的产生式，从而导致了:First(xy)First(xw)=First(x)Ф1.方法：若有产生式Uxy|xw|…|xz，则提取左公共因子并用EBNF表示为：Ux(y|w|…|z)再引入另一个非终结符号V，将产生式变为：UxVVy|w|…|zp71ex.若在y,w,…,z中仍然有左公共因子，可以再次提取。注意，若有：Uxy|x则提取后：Ux(y|)2.举例：设有产生式：S→ifBthenS1elseS2|ifBthenS1其中，S表示两种类型的条件语句。提取公因子，改成：S→ifBthenS1(elseS2|)引入非终结符号R：S→ifBthenS1RR→elseS2|ε文法中，if,then,elseVT3.说明：文法提取左公共因子后，只能使相同左部的产生式右部的First集不相交。文法提取左公共因子后，若文法中无空产生式，且无左递归，则改写后的文法为LL(1)文法。有些文法，不能在有限步骤内改写为无左公共因子的文法。二、消除左递归：左递归文法的分析程序可能进入死循环，可以证明，左递归文法不可能是LL(1)文法。1.消除直接左递归：若有产生式Ux|y|…|z|Uv,UVN,x,y,z,vV*,则改写并用EBNF表示为：U（x|y|…|z|){v}或改为右递归的形式：U（x|y|…|z|)U’U’vU’|举例：设有文法G[E]E→E+T|TT→T*F|FF→(E)|iE→T|E+TE→T{+T}E→TE’E’→+TE’|或T→F|T*FT→F{*F}T→FT’T’→*FT’|或2.消除间接左递归：先将间接左递归变为直接左递归，再按消除直接左递归的方法进行。举例：设有文法G[A](1)A→Bc(2)A→d(3)B→aA(4)B→Ab将(3)(4)带入(1)A→aAcA→AbcA→d直接左递归A→aAc|d|AbcA→(aAc|d)A’A’→bcA’|3.消除文法中全部左递归的算法：若文法中没有回路(AA),则：(1)把文法中的非终结符，按某种顺序进行排列(顺序任意)，如，A1,A2,…,An；(2)对每个非终结符号用排在它前面的其它非终结符号的产生式表示出来，并消除产生式中的直接左递归。fori:=1tondobeginforj:=1toi-1dobegin把形如Pi→Pjγ的产生式改成Pi→δ1γ|δ2γ|…|δkγ其中Pj→δ1|δ2|…|δk是关于Pj的所有产生式。end消除关于Pi产生式的直接左递归end(3)化简由(2)所得文法，即去掉多余产生式。消除一切左递归的方法：(1)把文法中的非终结符，按某种顺序进行排列(顺序任意)，如，A1,A2,…,An；举例：有文法G[S]:S→Qc|cQ→Rb|bR→Sa|a该文法无直接左递归，但，SQcRbcSabc,故有间接左递归，所以文法G[S]为左递归文法。(1)对非终结符号排序：R,Q,S(2)逐个消除直接左递归：R：R→Sa|a无直接左递归Q：将R带入Q中：Q→Sab|ab|b无直接左递归S：将R,Q带入S中：S→Sabc|abc|bc|c消除S的直接左递归：S→(abc|bc|c)S’S’→abcS’|Q→Sab|ab|bR→Sa|a所以文法成为：(3)去掉多余产生式：S→(abc|bc|c)S’S’→abcS’|注意：对非终结符号的排序是任意的(但要保证开始符号不变)，不同的排序最后所得文法得形式可能不同，但它们是等价的。文法G[E]：E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i4.4确定的自顶向下分析方法举例一、递归子程序法递归子程序法是比较简单直观易于构造的一种语法分析方法，其方法思想是对源程序中每个语法成分编制一个处理子程序，即对每个非终结符号编制一个递归过程，每个子程序的功能是识别由该非终结符号推出的串。它要求文法满足LL(1)文法，以便当某个非终结符号有多条产生式时，可以根据当前的输入符号唯一地确定选择某个产生式进行匹配。见P74ProgromE;BeginTWhilesym=“+”doBeginadvance;TendEndProgromT;BeginFWhilesym=“*”doBeginadvance;FendEndProgromF;Ifsym=“i”thenadvanceelseIfsy