自上而下语法分析

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

1、自上而下语法分析编译技术之四主讲鲁斌高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法21语法分析器功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则下图表明了语法分析器在编译程序中的地位按照语法分析树的建立方法，我们可以粗略地把语法分析方法分为两类：一类是自上而下分析法，另一类为自下而上分析法源程序词法分析器单词符号取下一单词符号语法分析器语法分析树后续部分

2、符号表3例：自顶向下构造最左推导（aabbaa)SaASaASbASSbaASaSbSAaabaaSbASaabASaabbaSaabbaaaASS42自上而下分析面临的问题自上而下分析的一般方法：对任何输入串，用一切可能的方法从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树，或寻找一个最左推导这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程5例4.1：假定有文法(4.1)S→xAyA→**

3、*分析输入串x*y（记为α）。SxAySxAy***SxAy(a)(b)(c)

4、6由上例看到，自上而下分析法存在许多困难和缺点文法的左递归性PPα使分析陷入无限循环回溯的不确定性，要求我们将已经完成工作推倒重来虚假匹配问题难于知道出错位置效率低，代价高，实践价值不大因此，为解决这些问题我们要消除左递归和回溯+73LL(1)分析法3.1左递归的消除3.2消除回溯、提左因子3.3LL（1）分析条件83.1左递归的消除一般而言，假定P关于的全部产生式是PP1

5、P2

6、…

7、Pm

8、1

9、2

10、…

11、n其中，每个都不等于，而每个都不以P开头，那么，消除P的直接左递归性就是把这些规则改写成：P

12、1P’

13、

14、2P’

15、…

16、nP’P’1P’

17、2P’

18、…

19、mP’

20、9例4.2：文法E→E+T

21、TT→T*F

22、FF→(E)

23、i消去直接左递归：E→TE’E’→+TE’

24、εT→FT’（4.2）T’→*FT’

25、εF→(E)

26、i直接左递归和非直接左递归的消除方法均在必须掌握之列10若一个文法不含回路（PP），也不含以ε为右部的产生式，则消除一切左递归的算法是：把文法G的所有非终结符排序：P1,P2,…,PnFORi:=1TOnDOBEGINFORj:=1TOi-1DO{把形如Pi→Pjγ的规则改写成Pi→δ1γ

27、δ2γ

28、…

29、δkγ其

30、中Pj→δ1

31、δ2

32、…

33、δk是关于Pj的所有规则；}消除关于Pi规则的直接左递归性END化简上述文法*11例4.3：考虑文法：SQc

34、cQRb

35、bRSa

36、a消除左递归。解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入到Q中有关的候选式：QSab

37、ab

38、b现在Q同样不含直接左递归，把它带入S的有关候选式：SSabc

39、abc

40、bc

41、c经消除S的直接左递归后我们们得到整个文法SabcS’

42、bcS’

43、cS’S’abcS’

44、QSab

45、ab

46、bRSa

47、a由于关于Q,R的规则式多余的则可化简得到：Sabc

48、S’

49、bcS’

50、cS’S’abcS’

51、123.2消除回溯、提左因子令G是一个不含左递归的文法，对G的所有的非终结符号的每个候选定义它的终结首符集FIRST()为：FIRST()={a

52、*a…,aVT}若*，则规定FIRST()。换句话说FIRST()是的所有可能推导的开头终结符或可能的13如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同的候选i和jFIRST(i)FIRST(j)=那么，当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某个候选前去执

53、行任务。这个候选就是那个终结首符集含a的14如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢？其办法是提取公共左因子假定关于A的规则是A1

54、2

55、…

56、n

57、1

58、2

59、…

60、m（其中每个不以开头）那末，可以把这些规则改写成：AA’

61、1

62、2

63、…

64、mA’1

65、2

66、…

67、n15例：有产生式BbBcA

68、b由于FIRST(bBcA)FIRST(b)={b}，则需要提取公共左因子，将产生式改写成：BbCCBcA

69、163.3LL（1）分析条件问题例4.4：考虑文法4.2，对输入串i

70、+i进行自上而下分析EFE’T’T(b)i+iIPi+iIP(a)E’TEi+iIP(c)FT’TEE’iEFE’T’T(d)i+iIPiεEi+iFE’IPT’T(e)iε+E’TεεiFT’E→TE’E’→+TE’

71、εT→FT’T’→*FT’

72、εF→(E)

73、i17假定S是