编译原理课件04(2)语法分析.ppt

《编译原理课件04(2)语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4.2.4递归下降分析法递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。4.2.4递归下降分析法基本思想对文法中的每个非终结符编写一个函数(或子程序),每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。4.2.4递归下降分析法构造递归下降分析程序的方法:为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写。A→α

2、1α2…αnαi∈VTαi∈VNα1α2…αn=ε4.2.4递归下降分析法(1)当遇到终结符a时，则编写语句if(当前读来的输入符号==a)读下一个输入符号；(2)当遇到非终结符A时，则编写语句调用A()；(4)当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导。(3)当遇到规则A→ε时，则编写语句4.2.4递归下降分析法if(当前读来的输入符号FOLLOW(A))error()；E→E+T

3、TT→T*F

4、FF→(E)

5、id例设有文法G[E]：试构造一个识别该文法句子的递归下降分析程序。4.2.4递

6、归下降分析法分析首先消去文法左递归，得到文法G'[E]E→TE'E'→+TE'

7、εT→FT'T'→*FT'

8、εF→(E)

9、idE→E+T

10、TT→T*F

11、FF→(E)

12、id4.2.4递归下降分析法无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符E',T',F有：E→TE'E'→+TE'

13、εT→FT'T'→*FT'

14、εF→(E)

15、id4.2.4递归下降分析法ETE'ETE'TFT'F(E)(TE')ETE'TFT'+ETE'FT'+TE'+ETE'(FT')SELECT(E'→+TE'

16、)∩SELECT(E'→ε)=FIRST(+TE')∩{FIRST(ε)∪FOLLOW(E')}={+}∩{ε,),$}=ΦSELECT(T'→*FT')∩SELECT(T'→ε)=FIRST(*FT')∩{FIRST(ε)∪FOLLOW(T')}={*}∩{ε,),$,+}=Φ4.2.4递归下降分析法SELECT(F→id)∩SELECT(F→(E))=FIRST(id)∩FIRST((E))={id}∩{(}=Φ所以文法G'[E]是LL(1)文法。4.2.4递归下降分析法分析程序中定义两个函数：(1)函数Scaner()功能:读进源程

17、序的下一个单词符号并将它放在全程变量sym。(2)函数error()功能:出错处理程序。4.2.4递归下降分析法对文法G'[E]可写出相应的递归下降分析程序如下：E→TE'E'→+TE'

18、εT→FT'T'→*FT'

19、εF→(E)

20、idmain(){Scaner();E();if(sym==‘$’)printf(“success”);elseprintf(“fail”);}4.2.4递归下降分析法E(){T();E'();}E'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sy

21、m!=‘$’))error();}4.2.4递归下降分析法E→TE'E'→+TE'

22、εT→FT'T'→*FT'

23、εF→(E)

24、idT(){F();T();}E→TE'E'→+TE'

25、εT→FT'T'→*FT'

26、εF→(E)

27、idT(){if(sym==‘*’){Scaner();F();T();}elseif(symfollow(T'))error();}4.2.4递归下降分析法F(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();

28、elseerror();}elseerror();}E→TE'E'→+TE'

29、εT→FT'T'→*FT'

30、εF→(E)

31、id4.2.4递归下降分析法4.2.4递归下降分析法main(){Scaner();E();if(sym==‘$’)printf(“success”);elseprintf(“fail”);}id+id$E(){T();E'();}T(){F();T();}见F见E'见T'返回下一页F(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)S

32、caner();elseerror();}elseerror();}4.2.4递归下降分析法返回T4.2.4递归下降分析法T(){if(sym==‘*’){Scaner();F();T()