06自上而下分析

复习文法推导语法树二义文法3.1上下文无关文法上下文无关文法是四元组（VT,VN,S,P）VT:终结符集合VN:非终结符集合S:开始符号，非终结符中的一个P:产生式集合，产生式形式:A→α例({id,+,∗,−,(,)},{expr,op},expr,P)expr→expropexprexpr→(expr)expr→−exprexpr→idop→+op→∗推导把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替例E→E+E|E∗E|(E)|−E|idE⇒−E⇒−(E)⇒−(E+E)⇒−(id+E)⇒−(id+id)记号S⇒*α、S⇒+w例E→E+E|E∗E|(E)|id句子id*(id_id)最左推导E⇒lmE*E⇒lmid*E⇒lmid*(E+E)⇒lmid*(id+E)⇒lmid*(id+id)最右推导（规范推导）E⇒rmE*(E)⇒rmE*(E+E)⇒rmE*(E+id)⇒rmE*(id+id)⇒rmid*(id+id)3.1上下文无关文法G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE二义性E⇒E∗EE⇒E+E⇒id∗E⇒E∗E+E⇒id∗E+E⇒id∗E+E⇒id∗id+E⇒id∗id+E⇒id∗id+id⇒id∗id+id两个不同的最左推导G(E)：Eid|E+E|E-E|E*E|E/E|(E)适当的表达式文法用一种层次观点看待表达式id∗id∗(id+id)+id∗id+id文法expr→expr+term|termterm→term∗factor|factorfactor→id|(expr)expr→expr+term|termterm→term∗factor|factorfactor→id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id∗id分析树id∗id∗id分析树自上而下的分析自上而下分析面临的问题递归下降分析程序构造预测分析程序LL(1)文法语法分析的任务对任一给定w∈VT*，判断w∈L（G）语法分析器：是一个程序，它按照P，做识别w的工作词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析1、主旨：从文法开始符号出发，自上而下的为输入串建立一棵语法树语法分析的分类：自下而上自上而下例文法G1：ScAdAab|a输入串：w=cad，为它建立语法树ScAdabaS→cAdA→abA→a输入串w:文法G:IP分析过程：1）w——输入串；IP—‘c’S——扩充；cad2）α=cAd；与IP—‘c’匹配；3）IP—‘a’A扩展，第一式ab,IP—‘a’与ab匹配；IP—‘d’,但d与b不匹配;4）报告失败，撤销A的子树，回到A;指针回退到IP—‘a’;A还有替换式未试过，而又可能匹配；语法树的形成文法的左递归回溯用替换符的顺序会影响所接受的语言如：A→ab|a改为A→a|ab难以报告出错的确切位置穷举试探法——低效的分析方法自上而下分析面临的问题三、自上而下分析的问题解决消除文法的左递归克服回溯问题1、区分三种类型的左递归-直接左递归即形如：N→Nα-间接左递归即形如：N→AαA→BβB→Nγ-潜在左递归即形如：N→αN而αε2、直接左递归的消除候选式：A→Aα|βββαβααβααα……A→βA’A’→αA’|ε消除方法：若：A→Aα|β，其中β不以A开头则修改规则为：A→βA′A′→αA′|ε消去直接左递归后：E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→（E）|i例4.2文法：E→E+T|TT→T*F|FF→（E）|i消除方法：若：A→Aα|β，(β不以A开头)则修改规则为：A→βA′A′→αA′|ε非直接左递归S→Aa|bA→Sd|ε先变换成直接左递归S→Aa|bA→Aad|bd|ε再消除左递归S→Aa|bA→bdA′|A′A′→adA′|ε消除方法：若：A→Aα|β，(β不以A开头)则修改规则为：A→βA′A′→αA′|ε如果是非直接左递归，先代入，后消除。5、消除回溯、提左因子回溯原因若当前符号=a，对A展开，而A→α1|α2|…|αm，那么，要知道哪一个αi是获得以a开头的串的唯一替换式。即：选择哪一个αi，亦即通过查看第一个（当前）符号来发现合适的替换式αi。怎样选择αi？①以a为头的αi②如有多个αi以a为头的，这是文法的问题消除回溯目的：非终结符A的所有侯选式的首符集两两不相交方法：提取公共左因子若：A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm(其中,每个γ不以δ开头)那么,可以把这些规则改写成A→δA′|γ1|γ2…|γmA′→β1|β2|…|βn例悬空else的文法stmt→ifexprthenstmtelsestmt|ifexprthenstmt|other若：A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm(其中,每个γ不以δ开头)那么,可以把这些规则改写成A→δA′|γ1|γ2…|γmA′→β1|β2|…|βn提左因子stmt→ifexprthenstmtoptional_else_part|otheroptional_else_part→elsestmt|εE→TE′E′→+TE′|εT→FT′T′→*FT′|εF→（E）|i每个非终结符所对应的递归子程序如下所示：intE(char*sym){T(sym);E′(sym);}intT(char*sym){F(sym);T′(sym);}intE′(char*sym){if((*sym)==‘+’){ADVANCE;T(sym);E′(sym);};E→TE′E′→+TE′|εT→FT′intT′(char*sym)if(*sym==‘*’){ADVANCE;F(sym);T′(sym);}T′→*FT′|εintF(char*sym){if(*sym==‘i’){ADVANCE}elseif(*sym==‘(’){ADVANCE;E;if(*sym==‘)’){ADVANCE}elsereturnERROR}elsereturnERROR;}F→（E）|i对文法加什么样的限制可以保证没有回溯？例S→ABA→ab|εB→aCC→…定义两个与G有关的集合：FIRST(α)和FOLLOW(A)；1）定义：若G，α∈V*，S，A∈VNFOLLOW(A)={a|SαAaβ，a∈VT，α,β∈V*}FIRST(α)={a|αa…,a∈VT}若αε，规定ε∈FIRST(α)若一个A∈VN，A→α1|α2|…|αm就有许多FIRST(αi)，如果A的任何两个候选式αi和αj，均有FIRST(αi)∩FIRST(αj)=意味着，A的每一候选式α推导后所得的字符串第一个VT均不同。于是，对输入符号a，如果a∈FIRST(αi)，则aFIRST(αj)，(j≠i)，因此，对A的展开无疑应选候选式αi，才有可能命中。先构造FIRST(X),X∈V连续使用以下规则，直至再无终结符，或ε加入任一FIRST集为止①若X∈VT，则FIRST(X)是{X}②若X∈VN,且X→aα，则{a}∪FIRST(X)X→ε，则{ε}∪FIRST(X)③若X∈VN,X→Y…,Y∈VN,则FIRST(Y)\{ε}∪FIRST(X)X→Y1Y2…Yi-1Yi…Yk,Yj∈VN,k=1,那么对于某个i,a在FIRST(Yi)中，且ε在所有的FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)，即Y1Y2…Yi-1ε，则把a加入到FIRST(X)中。如果ε在所有的FIRST(Yj)中，那么把则{ε}∪FIRST(X)再进而构造FIRST(X1X2…Xn)①FIRST(X1)的非ε终结符加入FIRST(X1X2…Xn)②若ε∈FIRST(X1)，则FIRST(X2)的所有非ε终结符加入FIRST(X1X2…Xn)③若ε∈FIRST(X1),ε∈FIRST(X2)，则FIRST(X3)的所有非ε终结符加入FIRST(X1X2…Xn)最后，若ε∈FIRST(Xi),i=1..n，则{ε}加入FIRST(X1X2…Xn)4）例已知文法G：E→TE′T′→*FT′|εE′→+TE′|εF→（E）|iT→FT′求它的FIRST(α),FOLLOW(A)FIRST集的构造：FIRST(E)=FIRST(E’)=FIRST(T’)=FIRST(T)=FIRST(F)={(,i}{+,ε}{*,ε}定义两个与G有关的集合：FIRST(α)和FOLLOW(A)；1）定义：若G，α∈V*，S，A∈VNFOLLOW(A)={a|SαAaβ，a∈VT，α,β∈V*}构造FOLLOW(A)应用下列规则，直到再没有什么加进任一FOLLOW为止①$属于FOLLOW(S)②若存在A→αBβ，则FIRST(β)FOLLOW(B)，除ε外③若有A→αB，或A→αBβ且ε∈FIRST(β)，则FOLLOW(B)FOLLOW(A)E→TE′T′→*FT′|εE′→+TE′|εF→（E）|iT→FT′求它的FIRST(α),FOLLOW(A)4）例已知文法G：E→TE′T′→*FT′|εE′→+TE′|εF→（E）|iT→FT′求它的FIRST(α),FOLLOW(A)FIRST集的构造：FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}①$属于FOLLOW(S)②若存在A-αBβ，则FIRST(β)FOLLOW(B),除ε外由①得：FOLLOW(E)={$}由②得：E→TE′则FIRST(E’)\{ε}∈FOLLOW(T)，即FOLLOW(T)={+}T→FT′则FIRST(T’)\{ε}∈FOLLOW(F),即FOLLOW(F)={*}F→（E）则FIRST())∈FOLLOW(E),即FOLLOW(E)={$,)}FOLLOW集的构造：FIRST(T’)={*,ε}FIRST(E’)={+,ε}E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→（E）|i即FOLLOW(F)={*,,,}③若有A→αB，或A→αBβ且ε∈FIRST(β),则FOLLOW(B)FOLLOW(A)FOLLOW(E)={),$}FOLLOW(T)={+}FOLLOW(F)={*}由③得：即FOLLOW(E’)={,})$即FOLLOW(T)={+,,})$即FOLLOW(T’)={,,})$+)$+E→TE′且E’→ε得FOLLOW(E)FOLLOW(T)，T→FT′得FOLLOW(T)FOLLOW(T’),T→FT′且T’→ε得FOLLOW(T)FOLLOW(F),E→TE′得FOLLOW(E)FOLLOW(E’)，FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}FOLLOW(E)=FOLLOW(E’)={),$}FOLLOW(T)=FOLLOW(T’)={+，)，$}FOLLOW(F)={*,+,),$}最终构造结果：注意：FIRST集针对终结符，非终结符，候选式而构造；FOLLOW集只对非终结符构造。任何两个产生式A→α|β都满足下列条件：1.FIRST(α)∩FIRST(β)=∅2.若β⇒*ε(如果ε在FIRST(β)中)，那么FIRST(α)∩FOLLOW(A)=∅。3.3.2LL(1)文法例S→ABA→ab|εB→aCC→…LL（1）文法LL：第一个L表示从左到右扫描输入串，第二个L表示最左推导（1）：表示分析时每一步只需向前查看一个符号LL(1)文法任何两个产生式A→α|β都满足下列条件：FIRST(α)∩FIRST(β)=∅若β⇒*ε，那么FIRST(α)∩FOLLOW(A)=∅LL(