自顶向下语法分析方法

《自顶向下语法分析方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章自顶向下语法分析方法确定的自顶向下分析思想LL(1)文法的判别某些非LL(1)文法到LL(1)文法的等价变换不确定的自顶向下分析思想确定的自顶向下分析方法返回目录确定的自顶向下分析思想文法G1[S]:S→pAS→qBA→cAdA→aB→dBB→bW=pccadd自顶向下的推导过程：SpApcAdpccAddpccadd语法树：SpASpAcAdSpAcAdcAdSpAcAdcAda这个文法的特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。文法G1[S]:S→p

2、AS→qBA→cAdA→aB→dBB→b文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBW=ccap自顶向下的推导过程：SApcApccApccap语法树：SApSApcASApcAcASApcAcAa这个文法的特点：每个产生式的右部不全是由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。文法G1[S]:S→ApS→BqA→aA→cAB→bB→dB定义：设G=(VT,VN,S,P)是上下文无关文法，FIRST(α)={a

3、αaβ,a∈VT,α∈V+

4、,β∈V*,}若αε，则规定ε∈FIRST(α)**调用返回FIRST(Ap)={a,c}FIRST(Bq)={b,d}文法G2[S]:S→ApS→BqA→aA→cAB→bB→dB文法G3[S]:S→aAS→dA→bASA→εW=abd试图推导的过程：SaAabASabSabd定义：设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始符号。FOLLOW(A)={a

5、SA且a∈FRIST(),∈VT*,∈V+}若SA,且ε，则规定#∈FOLLOW(A)即：FOLLOW(A)={a

6、S…Aa…

7、,a∈VT}若S…A，则规定#∈FOLLOW(A)#作为输入串的结束符，或称为句子括号，如：#输入串#*****调用返回对A→α，A→β其中A∈VN,α,β∈VN*，当α和β不同时推导出空时（设α不推导出空，β推导出空），则当FIRST(α)∩(FIRST(β)∪FOLLOW(A))=Φ时，对于非终结符A的替换仍可唯一地确定候选。定义：给定上下文无关文法的产生式A→α，A∈VN,α∈V*，若αε，则SELECT(A→α)=FIRST(α)如果αε，则SELECT(A→α)=FIRST(α)∪FOLLOW(A)**调

8、用返回定义：一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的两个不同产生式A→α和A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ其中α,β不同时能ε。*LL(1)文法的含义：第一个L表示：自顶向下分析是从左向右扫描输入串。第二个L表示：分析过程中将用最左推导。1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。类似也可以有LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。文法G[S]是否是LL(1)文法:S→aAS→dA→bASA→εSELECT(S→aA)={a}

9、SELECT(S→d)={d}SELECT(A→bAS)={b}SELECT(A→ε)={a,d,#,ε}SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=ΦSELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,#,ε}=Φ所以该文法是LL(1)文法。设文法G[S]为:S→aASS→bA→bAA→εSELECT(S→aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)={a,b,ε}SELECT(S→aAS)∩SELECT(S→b)={a}∩{

10、b}=ΦSELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b,ε}≠Φ所以该文法不是LL(1)文法。G[S]:S→aASS→bA→bAA→ε对输入串W=ab进行推导：SaASabASabS出错SaASaSabLL(1)文法的判别求出能推出ε的非终结符计算FIRST集计算FOLLOW集计算SELECT集判别是否是LL(1)文法例：设文法G[S]为:S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c判断它是否是LL(1)文法。1.求出能推出ε的非终结符S→ABS→bCA→εA→bB→εB

11、→aDC→ADC→bD→aSD→c非终结符SABCD初值未定未定未定未定未定第一次扫描是是否第二次扫描是否2.计算FIRST集1.若XV,则FIRST(X)={X}2.若XVN,且有产生式Xa…，则a∈FIRST(X);若X也是一条产