编译原理 第4章-自顶向下语法分析方法ppt课件.ppt

《编译原理 第4章-自顶向下语法分析方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析本章讨论程序语言的语法分析方法，以及语法分析程序的设计原理和实现技术。语法分析程序的功能和语法分析方法自顶向下语法分析法自底向上算符优先分析法LR分析法4.1语法分析程序的功能语法分析程序的功能语法分析器词法分析后的单词串语法成分构成的语法树或错误表语法分析的方法自顶向下语法分析法(自上而下语法分析法)自底向上语法分析法(自下而上语法分析法)4.1语法分析程序的功能1.自上而下的分析法从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。4.1语法分析程序的功能2.自下而上的分析法从给定的输入串开

2、始，根据文法规则逐步进行归约，直至归约到文法开始符号的一种方法；或者说，从语法树的未端开始，步步向上归约，直至根结点的分析方法。4.2自上而下语法分析法非确定的自上而下分析法的基本思想是：对任何输入串W试图用一切可能的办法，从文法的开始符号出发，自上而下地为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成功，则W为相应文法的一个句子，否则W就不是文法句子。4.2.1非确定的自上而下分析法的思想也就是说，这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。试探发生回溯。4.2.1非确定的自上而下分析法的思想例设有文法G[S]：S→aAbA→d

3、e

4、d输入串W=adbSaAbde匹配失败、这时应回溯,选择A的其它可能的规则重新匹配。4.2.1非确定的自上而下分析法的思想d匹配成功S→aAbA→de

5、dSaAb输入串W=adb4.2.1非确定的自上而下分析法的思想上述自上而下为输入串W建立语法树的过程，实际也是设法为输入串建立一个最左推导序列：SaAbadb。由于对输入串从左向右进行扫描，使用最左推导，才能保证按从左到右扫描顺序匹配输入串。4.2.1非确定的自上而下分析法的思想根据以上分析，不难看出，非确定的自上而下分析法即是带回溯的自上而下分析法,实际上是一种穷举的试探方法，其分析效率极低，代价很高，在实用的编译程序中

6、是不常用的。我们通常使用确定的自上而下分析法进行语法分析。4.2.1非确定的自上而下分析法的思想但确定的自上而下分析法对语言的文法有一定的限制条件，那就是要求描述语言的文法是无左递归的和无回溯的。4.2.2文法的左递归性和回溯的消除文法左递归的消除当一个文法是左递归文法时，采用自上而下分析法会使分析过程进入无穷循环之中。文法左递归是指文法中的某个非终结符A存在推导AAα+4.2.2文法的左递归性和回溯的消除用非终结符A去匹配输入串时,使当前句型的最左非终结符仍然为A。也就是说，在没有读进任何输入符号的情况下，又重新要求A去进行新的匹配。于是，造成无穷循环。4.2.2文法的左递归性

7、和回溯的消除对含直接左递归的规则进行等价变换，消除左递归引进一个新的非终结符，把含左递归的规则改写成右递归。设关于非终结符A的直接左递归的规则为4.2.2文法的左递归性和回溯的消除对A的规则可改写成如下右递归形式：A'→αA'

8、εA→βA'A→Aα

9、β其中α、β是任意的符号串,α不等于ε,β不以A开头4.2.2文法的左递归性和回溯的消除改写以后的形式和原来形式是等价的。也就是说，从A推出的符号串的集合是相同的。4.2.2文法的左递归性和回溯的消除一般情况下，设文法中关于A的规则为A→Aα1

10、Aα2

11、…

12、Aαm

13、β1

14、β2

15、…

16、βn其中每个α都不等于ε，而每个都不以A开头，消除直接

17、左递归后改写为:A'→α1A'

18、α2A'

19、…

20、αmA'

21、εA→β1A'

22、β2A'

23、…

24、βnA'4.2.2文法的左递归性和回溯的消除例1设有文法G[E]：E→E+T

25、E–T

26、TT→T*F

27、T/F

28、FF→(E)

29、id消去非终结符E,T的直接左递归后，文法G[E]改写为：F→(E)

30、idE→TE'E'→+TE'

31、–TE'

32、εT→FT'T'→*FT'

33、/FT'

34、ε4.2.2文法的左递归性和回溯的消除例2设有文法G[A]:A→Ac

35、Aad

36、bd

37、e消去直接左接左递归后文法G[A]改写为A'→cA'

38、adA'

39、εA→bdA'

40、eA'4.2.2文法的左递归性和回溯的消除2.回溯的消除在自上而下分

41、析过程中，由于回溯，需要推翻前面的分析，包括已做的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效率，因此，需要消除回溯。4.2.2文法的左递归性和回溯的消除我们分析发现引起回溯的原因是:在文法中,当某个非终结符A有多个候选式时:遇到用A去匹配当前输入符号a时，无法确定选用唯一的一个候选式，而只能逐一进行试探，从而引起回溯。具体表现在下面两种情况。A→α1

42、α2

43、α3

44、∙∙∙∙∙∙

45、αn4.2.2文法的左递归性和回溯的消除第一种情况:文法中相同左部的规