五自顶向下的语法分析

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

1、编译原理§5.1语法分析概述§5.2自顶向下的分析法概述§5.3递归子程序法§5.4LL(1)分析法第五章自顶向下的语法分析§5.1语法分析概述词法分析器记号取下一个记号源程序语法树前端的其余部分语法分析器中间表示符号表一、语法分析的功能功能：是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。二、语法分析方法的种类§5.1语法分析概述语法分析方法自顶向下分析法自底向上分析法递归下降分析法预测分析法(LL(1)分析)算符优先分析法LR分析法LR(0)分析法SLR(1)分析法LR(1)分析法LALR(1)分析法三、语法分析的错误处理§5.1语法分析概述1、程序

2、出错的种类词法错误：如标识符、关键字或操作符的拼写错误；语法错误：如算术表达式的括号不匹配；语义错误：如操作符作用于不相容的操作数；逻辑错误：如无限的递归调用。三、语法分析的错误处理§5.1语法分析概述2、常见语法错误的处理例：x:=)a+b)*c;10:=(a+b)*c：①语句①的“)”错误②语句②的赋值语句的左部的第一个单词“10”错误③第②句的单词“:”错误语法分析器在发现错误时，将有关的错误单词的位置、错误类别和错误性质等信息显示给用户。一、基本思想§5.2自顶向下分析法概述从句型推导的角度看从语法树角度看从实现技术角度看例：考虑下述文法和输入串w=cad，

3、ScAdAab

4、aScAd二、遇到的问题§5.2自顶向下分析法概述c匹配例：考虑下述文法和输入串w=cad，ScAdAab

5、aScAd二、遇到的问题§5.2自顶向下分析法概述例：考虑下述文法和输入串w=cad，ScAdAab

6、aScAd二、遇到的问题§5.2自顶向下分析法概述ab匹配？例：考虑下述文法和输入串w=cad，ScAdAab

7、aScAd二、遇到的问题§5.2自顶向下分析法概述ab匹配？例：考虑下述文法和输入串w=cad，ScAdAab

8、aScAd二、遇到的问题§5.2自顶向下分析法概述a匹配？例：考虑下述文法和输入串w=cad，ScA

9、dAab

10、aScAd二、遇到的问题§5.2自顶向下分析法概述a匹配？成功！例：考虑下述文法和输入串w=cad，ScAdAab

11、a二、遇到的问题§5.2自顶向下分析法概述存在形如A→αβ1

12、αβ2的产生式，即有多个候选式的前缀相同（称为公共左因子，或左因子），则可能造成虚假匹配，使得在分析过程中可能需要进行大量回溯。分析例2：文法G[S]：SSaSb和输入串baaaaSSa二、遇到的问题§5.2自顶向下分析法概述当输入符为b时，用Sb来推导，就推不出后边的部分；用SSa来推导，又无法确定何时用Sb来替换。陷入死循环。SaSa…二、遇到的问题§5.2自顶

13、向下分析法概述存在左递归（文法中有形如A→Aα的产生式），分析过程又使用最左推导，就会使分析过程陷入死循环。分析例2：文法G[S]：SSaSb和输入串baaaa三、解决方法§5.2自顶向下分析法概述1.消除左递归直接左递归：A→A…间接左递归：A→Bβ，B→Aα即AA…潜在左递归：A→αAβ，且αε+*间接左递归举例A→aB①A→Bb②B→Ac③B→d④若有输入串为adbcbcbc，则分析过程的语法树如图这时B若用产生式(4)替换，则推导到此终止，不能推出adbcbcbc，而若选用(3)则有图(b)，形成死循环。§5.2自顶向下分析法概述1.消除直接左递归消

14、除方法：假定关于A的全部产生式是：A→Aα1

15、Aα2

16、…

17、Aαm

18、β1

19、β2

20、…

21、βn其中，αi(1≤i≤m)不等于ε,βj(1≤j≤n)不以A开头，消除直接左递归后改写为：A→β1A′

22、β2A′

23、…

24、βnA′A′→α1A′

25、α2A′

26、…

27、αmA′

28、ε例：文法G[S]：SSaSbS→bS′S′→aS′

29、ε可改写为：消除文法中的直接左递归练习例：文法G[E]:EE+T

30、TTT*F

31、FF(E)

32、i解：引进新符号E’,T’∈VN则改写成新文法G’[E]：ETE’E’+TE’

33、εTFT’T’*FT’

34、εF(E)

35、i假定关于A的全部产生式是：A→Aα1

36、A

37、α2

38、…

39、Aαm

40、β1

41、β2

42、…

43、βn消除直接左递归后改写为：A→β1A′

44、β2A′

45、…

46、βnA′A′→α1A′

47、α2A′

48、…

49、αmA′

50、ε§5.2自顶向下分析法概述2.消除间接左递归消除方法：去除那些从开始符号出发永远无法到达的非终结符号的产生规则，为非终结符号编号，再采用代入法将间接左递归变为直接左递归，从而消除直接左递归。算法89页消除文法中的左递归举例例：文法G[E]:S→Qc

51、c①Q→Rb

52、b②R→Sa

53、a③解：若非终结符排序为S、Q、R,左部为S的产生式①无直接左递归，②中右部不含S，所以把①右部代入③得：R→Qca

54、ca

55、a④再将②的右部代入④得