chap4-1自顶向下语法分析

2020/4/111检查由扫描器输出的单词符号序列是否符合该语言的文法——句子扫描器分析器语义处理单词符号分析树源程序分析器的输入：Token序列分析器的输出分析树出错处理分析方法自顶向下（递归下降、预测分析)自底向上（算符优先、LR分析器）第四章语法分析2020/4/1124.1自顶向下的分析方法基本思想寻找输入符号串最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树2020/4/1131、重要概念推导:αＡβαγβ(依据：Ａ→γ)最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Right-most)推导——最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）自顶向下语法分析要解决的问题是?2020/4/114候选式的确定给定文法S→cAdA→ab|a?句子cad是该文法定义语言的句子SScAdcAdaba产生式(候选式)的选择：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。2020/4/115带回溯的自顶向下分析思想给定文法G[S]和输入串W,从S出发自顶向下构造语法树:若存在某条推导路径,使得S=*W,则W语法正确;若尝试所有推导路径,都无法得到S=*W,则W语法错误.不确定的自顶向下分析需作回溯,效率很低.2020/4/1162.确定的自顶向下分析思想基本思想：每一步根据当前输入符号可唯一确定某条规则用于推导.由根向下构造语法树.构造最左推导.推导出的终结符是否与当前输入符匹配2020/4/117确定的自顶向下分析思想例1:S–pA[1]|qB[2]A–cAd[3]|a[4]输入串：Ｗ＝pccadd分析结论：Ｗ语法正确且分析过程的每一步都唯一原因：本文法的非终结符（Ｓ，Ａ）的候选都以终结符开头，且两两不同．Ｓ：p≠qA:c≠a2020/4/118例2:S–Ap[1]|Bq[2]A–a[3]|cA[4]B–b[5]|dB[6]输入串：Ｗ＝ccap分析结论:Ｗ语法正确且分析过程的每一步都唯一原因：本文法的A和B的候选以终结符开头，且两两不同．A：a≠cB:b≠d;并且对于S:FIRST（Ａp）∩FIRST(Bq)={a,c}∩{b,d}=定义：FIRST（）={a|=*a,a∈VT,,∈V*}若=*ε则规定ε∈FRIST()2020/4/119例3:S–aA[1]|d[2]A–bAS[3]|[4]输入串：Ｗ＝abd分析结论：W语法正确且分析过程的每一步都唯一原因：S：a≠dA:{b}∩FOLLOW（A）={b}∩{a,d}=定义：FOLLOW（A）={aS=*A且a∈FRIST（），∈V*，∈V+}2020/4/1110我们希望：从左到右扫描输入串——寻找它的一个最左推导对于G的每个非终结符A的任何两个不同的候选式A→α|β1)FIRST(α)∩FIRST(β)=φ2)如果β*ε，则FISRT(α)∩FOLLOW(A)=φ——文法Ｇ是LL(1)的充要条件第一个L:从左到右扫描输入串第二个L:生成的是最左推导1:向前看一个输入符号2020/4/11113.LL(1)文法的判别1.对于A∈Vn,计算First(A)2.对于A∈Vn,计算Follow(A)3.对于A–|β,计算FIRST()∩FIRST(β)FIRST(β)∩follow(A)(若=*成立)2020/4/11121.若Ａ=*，则∈First(A)2.若A–B…,则FIRST(A)=FIRST(A)∪(FIRST(B)-{ε})若A–a…,则FIRST(A)=FIRST(A)∪{a}3.若A–B…及A–a…,且=*，则类似于步骤2处理求FIRST(A)的算法2020/4/1113FIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(（)={（}FIRST(）)={）}FIRST(id)={id}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id例2020/4/1114例:S–AＢ|bCA–|bB–|aDC–AD|bD–aS|cNFirst(N)Sa,b,Ab,Ba,Ca,b,cDa,c2020/4/1115求FOLLOW(A)的算法对于所有非终结符,重复进行以下计算1)将#加入到FOLLOW(S)#为句子的结束符2)若A→αBβ，则FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}3)如果A→αB或A→αBβ，且β*ε，A≠B，则FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)2020/4/1116FOLLOW(E)={),#}FOLLOW(E')=FOLLOW(E)={),#}FOLLOW(T)={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)={*,+,),#}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id例2020/4/1117NFollow(N)S#Aa,c,#B#C#D#例:S–AＢ|bCA–|bB–|aDC–AD|bD–aS|c2020/4/1118对于A–|β∈Ｐ，计算交集S–AＢ|bCA–|bB–|aDC–AD|bD–aS|cNFirst(N)Sa,b,Ab,Ba,Ca,b,cDa,cFollow(N)#a,c,####First(AB)=First(A)∪First(B)∪{b}={b,a,}First(bC)={b}∵{b,a,}∩{b}={b}≠∴G[Ｓ]不是LL(1)文法2020/4/11194.非LL(1)文法到LL(1)文法的变换LL(1)文法的性质：LL(1)文法是无二义的LL(1)文法不含左递归LL(1)文法不含公共左因子2020/4/1120(1)消除左递归直接左递归A→Aα间接左递归A+Aα例:S→AaA→Sb无法根据左递归文法进行自顶向下的分析左递归的消除方法将A→Aα|β替换为A→βA’和A’→αA’｜ε2020/4/1121例：表达式文法直接左递归的消除E→E+T｜TT→T*F｜FF→(E)｜idE→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜id2020/4/1122间接左递归的消除S→Ac|cA→Bb|bB→Sa|a将B的定义代入A产生式得：A→Sab|ab|b将A的定义代入S产生式得:S→Sabc|abc|bc|c消除直接左递归：S→abcS’|bcS’|cS’S’→abcS’|ε删除“多余的”产生式：A→Sab|ab|b和B→Sa|a结果：S→abcS’|bcS’|cS’S’→abcS’|ε2020/4/1123消除左递归的一般方法已知左递归产生式组A→Aα1|Aα2|…|Aαn|β1|β2|…|βm替换为产生式组Aβ1B|β2B|…|βnBBα1B|α2B|…|αnB|ε其中：B为新变量，相当于A’2020/4/1124将产生式Ａβ|变换为：ＡBBβ|例:S→ifCtS|ifCtSeSC→b提左因子得:S→ifCtSAA→eS|C→b(2)提取左因子2020/4/1125左因子提取方法将形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm的规则改写为A→αA’|γ1|γ2|…|γm和A'→β1|β2|…|βn2020/4/1126注意!文法G[S]中消除了左递归和公共左因子后并不能保证其一定变换为LL(1)文法.需进行判别后才能下结论.2020/4/1127G’[E]:(1)E–TE’(2)E’–+TE’(3)E’–(4)T–FT’(5)T’–*FT’(6)T’–(7)F–(E)(8)F–i例:G[E]:E→E+T｜TT→T*F｜FF→i｜(E)G[E]是否为LL(1)文法？2020/4/1128G’[E]:(1)E–TE’(2)E’–+TE’(3)E’–(4)T–FT’(5)T’–*FT’(6)T’–(7)F–(E)(8)F–i·各非终结符的FIRST集合如下：FIRST(E)=｛(,i｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,i｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,i｝·各非终结符的FOLLOW集合为：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}2020/4/1129G’[E]:(1)E–TE’(2)E’–+TE’(3)E’–(4)T–FT’(5)T’–*FT’(6)T’–(7)F–(E)(8)F–aE’–+TE’|FIRST(+TE’)=｛+｝FOLLOW(E′)=｛)，＃｝T’–*FT’|FIRST(*FT’)=｛*｝FOLLOW(T′)=｛+,)，＃｝F–(E)|aFIRST((E))=｛(｝FIRST(a)=｛a｝所以G’[E]是LL（1）的2020/4/1130习题：1、改写以下文法，消除左递归并判断改写后的文法是否LL(1)文法。M→MaH|HH→b(M)|(M)|b2、判断以下文法是否LL(1)文法,求该文法中各非终结符的FIRST集和FOLLOW集,并构造预测分析表。a.A→baB|b.S→bA|aB→Abb|aA→bBB→bB|3、判断该文法是否LL(1)文法？如不是，请将其改写为LL(1)文法。a.S→A|BA→aA|aB→bB|bb.S→i|(E)E→E+S|E-S|SC.E→E+T|TT→T*F|FF→（E）|i2020/4/1131确定的自顶向下分析方法递归子程序法预测分析方法2020/4/11324.1.2递归子程序法方法:对于每一A∈Vn,构造一个子程序.设A→α,对α中各个符号X:若X∈Vt,则匹配当前输入符号a,判断Ｘ=a?;若X∈Vn,则转而调用Ｘ所对应的子程序．语法分析开始时，调用开始符号Ｓ对应的子程序2020/4/1133递归子程序法例：G’[E]:E–TE’E’–+TE’｜T–FT’T’–*FT’｜F–(E)F–iProcedureE;{T;E’}ProcedureT;{F;T’}ProcedureE’;{ifsym=‘+’then{advance;T;E’}}ProcedureT’;{ifsym=‘*’then{advance;F;T’}}2020/4/1134递归子程序法例：G’[E]:E–TE’E’–+TE’｜T–FT’T’–*FT’｜F–(E)F–iProcedureF;{ifsym=‘i’thenadvanceelseifsym=‘(’then{advance;E;ifsym=‘)’thenadvanceelseerror1}elseerror2}2020/4/1135递归子程序法ProcedureF;{ifsym=‘i’thenadvanceelseifsym=‘(’then{advance;E;ifsym=‘)’thenadvanceelseerror1}elseerror2}ProcedureE;{T;E’}ProcedureT;{F;T’}ProcedureE’;{ifsym=‘+’then{advance;T;E’}}ProcedureT’;{ifsym=‘*’then{advance;F;T’}}i1+i2*i3的分析过程2020/4/1136语法图和递归子程序法例表达式文法