编译原理语法分析 从上至下.ppt

编译原理语法分析 从上至下.ppt

ID:51593431

大小:144.00 KB

页数:32页

时间:2020-03-25

编译原理语法分析 从上至下.ppt_第1页
编译原理语法分析 从上至下.ppt_第2页
编译原理语法分析 从上至下.ppt_第3页
编译原理语法分析 从上至下.ppt_第4页
编译原理语法分析 从上至下.ppt_第5页
资源描述:

《编译原理语法分析 从上至下.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、编译方法中国人民大学信息学院陈文萍1第四章语法分析——自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL(1)分析中的错误处理24.1语法分析器的功能语法分析器的地位分类自上而下分析自下而上分析词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析树34.2自上而下分析定义:也称面向目标的分析方法,从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子。主旨:对任何输入串,试图用一切可能的办法,从文法开始符号着

2、手,自上而下地为输入串构造一棵语法树。本质上是一个试探过程,反复使用不同的产生式谋求匹配输入串的过程。4自上而下分析的问题(1)左递归例:例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想,选用产生式(1)来推导SSa,语法树末端结点最左符号为非终结符,所以选用(1)继续推导SSaSaa此时语法树末端结点最左符号为非终结符,所以选用(1)继续推导SSaSSaSSSa试图用S匹配输入串时,出现:在没有识别任何输入符号的情况下,又得重新要求S去进行新的匹配,分析过程陷入无限循环5

3、自上而下分析的问题(2)回溯例:G[S]:S→xAy,A→ab|a若当前输入串为xay,首先构造的推导SxAy匹配进一步推导对A可选择A→ab替换,得SxAyxabyxayxaby匹配xa都已匹配,当前面临输入符为y与b不能匹配,所以将输入串指针退回到a,对A的替换重新选用下一个产生式A→a进行试探,SxAyxay输入串中当前符a得到匹配,指针向前移动到y,与语法树中y匹配,匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。6自上而下分析的问题(3)分析过程中,匹配成功可能是暂时的。最终分析不成功,很

4、难知道输入串中出错的确切位置。带回溯,效率低,代价高74.3LL(1)分析法左递归的消除消除回溯LL(1)分析条件8直接左递归的消除左递归:一个文法是含有左递归的,如果存在非终结符P,P=>+Pα形如:P→Pα

5、β,其中α不为,β不以P打头消除直接左递归改写为:P→βP’,P’→αP’

6、一般来说,若P→Pα1

7、Pα2

8、…

9、Pαm

10、β1

11、β2

12、…

13、βn,αi不为,βi不以P打头,消除直接左递归就把规则改写为:P→β1P’

14、β2P’

15、…

16、βnP’P‘→α1P’

17、α2P’

18、…

19、αmP’

20、例:E→E+T

21、T,T→T*F

22、F,F→

23、(E)

24、i消除直接左递归后变为:E→TE’E’→+TE’

25、T→FT’T’→*FT’

26、F→(E)

27、i9文法左递归的消除消除一个文法左递归:对文法的要求无回路()不含以为右部的产生式消除左递归算法:(1)以某种顺序将文法非终结符排列P1,P2……Pn(2)fori:=1tondobeginforj:=1toi-1do用Pi-->1r

28、2r…

29、kr替代形如Pi-->Pjr的规则其中Pj-->1

30、2…

31、k是关于Pj的全部产生式;消除Pi规则的直接左递归;end(3)化简由2得到的文法10左递归的消除例,文法S→Qc

32、c

33、,Q→Rb

34、b,R→Sa

35、a1,非终结符排序为:S,Q,R2,替换规则对于S,无需替换,S→Qc

36、c对于Q,无需替换,Q→Rb

37、b关于R,替换为,R→Rbca

38、bca

39、ca

40、a,消除直接左递归为R→bcaR’

41、caR’

42、aR’,R’→bcaR’

43、非终结符的顺序不同,文法的形式可能不同,但都是等价的11消除回溯不回溯,对文法的要求设G是一个不含左递归的文法,对G的所有非终结符的每个候选,它的终结首符集FIRST()为FIRST()={a

44、=>*a…,a∈VT},若=>*ε则规定ε∈FIRST()若非终结符A的所有候选

45、首符集两两不相交,即A的任何两个不同候选α和β,FIRST(α)∩FIRST(β)=,则可消除回溯改造文法的方法:提左公因子将产生式Aβ1

46、…

47、βn

48、1

49、…

50、m变换为:AB

51、1

52、…

53、mBβ1

54、…

55、βn12LL(1)分析条件例如:文法:E→TE’,E’→+TE’

56、,T→FT’,T’→*FT’

57、,F→(E)

58、i输入串i+i,语法分析树FIRST(TE’)={(,i}FIRST(+TE’)={+}FIRST(FT’)={(,i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)={i}

59、ETE’iTE’+T’FFT’εiεε13LL(1)分析条件S是文法G的开始符号,对G的任何非终结,定义FOLLOW(A)={aS=>*…Aa…且a∈VT},若S=>*…A,则#∈FOLLOW(A)一个文法G是LL(1)的,当且仅当对于G的每一个非终结符A的任

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。