第08讲-语法分析-III

本讲纲要回顾重点：FIRST集、FOLLOW集LL(1)文法自上而下分析实现递归函数法非递归的预测分析方法构造预测分析表1FIRST集和FOLLOW集FIRST(

)={a|

*a…,a

VT}计算满足的句子的所有可能开头字符特殊情况：当

*时，规定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT}计算语言的句型中所有可能跟在A后面的字符特殊情况：如果A是某个句型的最右符号，那么$属于FOLLOW(A)2FIRST集合及FOLLOW集合的计算方法FIRST集合计算方法若Xa..，则将终结符ａ加入FIRST(X)中若X，则将加入FIRST(X)中若XY…，且Y属于非终结符，则将FIRST(Y)\{}加入到FIRST(X)中若XY1Y2..YK,且Y1,Y2,..Yi-1(2≤i≤k)都是非终结符，且Y1,Y2,..Yi-1的FIRST集合中均包含，则将FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特别地，若Y1~YK均有产生式，则将加到FIRST(X)中。3SBAABS|dBaA|bS|cFIRST(S)=FIRST(B)FIRST(A)=FIRST(B)∪

{d}FIRST(B)={a,b,c}步骤1：FIRST集和FOLLOW集FIRST(

)={a|

*a…,a

VT}计算满足的句子的所有可能开头字符特殊情况：当

*时，规定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT}计算语言的句型中所有可能跟在A后面的字符特殊情况：如果A是某个句型的最右符号，那么$属于FOLLOW(A)4A的FOLLOW集合，是从开始符号可以导出的所有含A的文法符号序列中紧跟A之后的终结符。α的FIRST集合是从α开始可以导出的文法符号序列中的开头终结符。FOLLOW集合的计算方法FOLLOW集合计算方法对文法开始符号S,置$于FOLLOW(S)中。若有AB，则将FIRST()\{}加入FOLLOW(B)中。（此处可以为空）若AB或AB,且*（即属于FIRST()）,则将

FOLLOW(A)加入FOLLOW(B)中（此处可以为空）。5SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(S)=?FOLLOW(A)=?FOLLOW(B)=?FOLLOW集计算文法6SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={$}FOLLOW(A)={}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW集计算文法7SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={$}FOLLOW(A)={a,b,c,d}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(B)中的所有元素都可以加到FOLLOW(A)中FOLLOW集计算文法8SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={a,b,c,d,$}FOLLOW(A)={a,b,c,d}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(B)中的所有元素都可以加到FOLLOW(A)中FOLLOW(B)中的所有元素都可以加到FOLLOW(S)中FOLLOW集计算文法9SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={a,b,c,d,$}FOLLOW(A)={a,b,c,d,$}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(B)中的所有元素都可以加到FOLLOW(A)中FOLLOW(B)中的所有元素都可以加到FOLLOW(S)中FOLLOW(S)中的所有元素都可以加到FOLLOW(A)中102023/2/2

目录自上而下的语法分析First集合、Follow集合LL（1）文法自上而下的预测分析方法构造非递归预测分析表语法分析112023/2/2

句子

主语谓语宾语主语

名词谓语

动词

宾语

数词|名词

空调|导航动词

设为|开数词25度|A

|

(1)FIRST(

)FIRST()=(2)若

*，那么FIRST()FOLLOW(A)=FOLLOW(宾语)=FOLLOW(数词)={$}{$}LL(1)文法2.FIRST(数词)={25度，}FIRST(25度)={25度

}LL(1)文法LL(1)文法 任何两个产生式A

|都满足下列条件：FIRST(

)FIRST()=若

*，那么FIRST()FOLLOW(A)=LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归12LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|id该文法是LL(1)文法吗？13E

+TE|和T

*FT

|是判断的重点！LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|idFIRST(+TE

)={+}FOLLOW(E)={),$}FIRST(*

FT

)={*}FOLLOW(T)={+,),$}14结论：该文法是LL(1)文法！LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|id15结论：该文法是LL(1)文法！FIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}FOLLOW(F)={+,*,),$}162023/2/2

自上而下的语法分析自上而下的语法分析First集合、Follow集合LL（1）文法自上而下的预测分析方法构造非递归预测分析表语法分析172023/2/2

预测分析方法—递归3.句子

主语谓语宾语主语

名词谓语

动词

宾语

数词|名词

空调|导航动词

设为|开数词25度|句子(){主语();

谓语();

宾语();}主语(){名词();}名词(){ if(lookahead==“空调”){

match(“空调”);

}else{match(“导航”);}}句子

主语谓语宾语主语

名词谓语

动词

宾语

数词|名词

空调|导航动词

设为|开数词25度|182023/2/2

主语谓语

名词动词

空调设为设为25度宾语$$空调

数词输入:X=a$Xa,XVNXa,XVTX=a=$25度句子预测分析方法3.递归的分析程序19SBAABS|dBaA|bS|cS(){B();A();}A(){if(lookahead==‘a’|’b’|’c’){B();S();}elsematch(‘d’);}B(){if(lookahead==‘a’){match(‘a’);A();}elseif(lookahead==‘b’){match(‘b’);S();}elsematch(‘c’);}递归下降的预测分析递归下降的预测分析为每一个非终结符写一个分析过程这些过程可能是递归的例： type

simple

|id

|array[simple]oftype simpleinteger

|char

|numdotdotnum20递归下降的预测分析一个辅助过程procedurematch(t:token);begin iflookahead==tthen lookahead:=nexttoken() elseerror()end;21递归下降的预测分析proccduretype;begin iflookaheadin{integer,char,num}then simple() elseiflookahead=thenbegin match();match(id) end elseiflookahead=arraythenbegin match(array);match([);simple(); match(]);match(of);type() end elseerror()end;22type

simple |id |array[simple]oftype递归下降的预测分析proceduresimple;begin iflookahead=integerthen match(integer) elseiflookahead=charthen match(char) elseiflookahead=numthenbegin match(num);match(dotdot);match(num) end elseerror()end;23simpleinteger |char |numdotdotnum242023/2/2

目录自上而下的语法分析First集合、Follow集合LL（1）文法自上而下的预测分析方法构造非递归预测分析表语法分析252023/2/2

空调导航开设为25度$动词

宾语数词句子主语谓语

名词句子

主语谓语宾语主语

名词名词

空调|导航谓语

动词

动词

设为|开宾语

数词|数词

25度|句子

主语谓语宾语句子

主语谓语宾语主语

名词主语

名词名词

空调

名词

导航谓语

动词谓语

动词动词

设为动词

开宾语

数词宾语数词25度数词构造预测分析表4.262023/2/2

对每个产生式A

FIRST()的每个a，把A加入M[A,a]FOLLOW(A)的b（包括$）把A

加入M[A,b]M的其它没有定义的条目都是error在FIRST()NY构造预测分析表4.272023/2/2

First集合、Follow集合LL（1）文法自上而下的预测分析方法构造非递归预测分析表递归下降预测分析非递归的预测分析A|满足下列条件：1、FIRST()FIRST()=2、若

*，那么FIRST()FOLLOW(A)=总结实现first集合、follow集合程序设计实现非递归的预测分析程序针对非LL（1）文法，如何实现自上而下的语法分析？282023/2/2习题3.3

自上而下分析3.3.4非递归的预测分析29a+b$输入预测分析程序分析表M输出

XYZ$栈预测分析表用于驱动分析的全过程3.3

自上而下分析30非终结符输入符号id+*...EETE

E

E

+TE

TTFT

T

T

T

*FTFFid书上57页表3.13.3

自上而下分析31栈输入输出

…

…预测分析器接受输入id*id+id的动作

$Eid*id+id$E

TE$E’Tid*id+id$T

FT$E’T’Fid*id+id$F

id$E’T’idid*id+id$一个符号被消耗*id+id$$E’T’Match(id)T’

*FT’$E’T’F**id+id$Match(*)id+id$$E’T’F预测分析表的构建（1）对文法的每个产生式A

，执行(2)和(3)。（2）对FIRST()的每个终结符a，把A

加入M[A,a]（即加入表中A行a列）。（3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）,把A

加入M[A,b]。（4）M的其它没有定义的条目都是error。32文法S->ACDA->a|C->cD->d33FIRST(S)={a,c}FIRST(A)={a,}FIRST(C)={c}FIRST(D)={d}FOLLOW(S)={$}FOLLOW(A)={c}FOLLOW(C)={d}FOLLOW(D)={$}预测分析表的构建非终结符输入符号acd$SACD

34FIRST(S)={a,c}FIRST(A)={a,}FIRST(C)={c}FIRST(D)={d}FOLLOW(S)={$}FOLLOW(A)={c}FOLLOW(C)={d}FOLLOW(D)={$}S->ACDS->ACDA->aA->C->cD->dERRORERRORERRORERRORERRORERROR文法S->ACDA->a|C->cD->dERRORERRORERRORERROR上下文无关文法自上而下自下而上LL(1)文法2个函数递归下降预测分析非递归的预测分析最左推导任何两个产生式A