程序语言的语法分析

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

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

2、开始，往下构造语法树，直到建立每个叶的分析方法。4.1语法分析程序的功能2.自下而上的分析法从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法开始符号的一种方法；或者说，从语法树的未端开始，步步向上归约，直至根结点的分析方法。4.2自上而下语法分析法非确定的自上而下分析法的基本思想是：对任何输入串W试图用一切可能的办法，从文法的开始符号出发，自上而下地为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成功，则W为相应文法的一个句子，否则W就不是文法句子。4.2.1非确定的自上而下分析法的思想

3、也就是说，这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。试探发生回溯。4.2.1非确定的自上而下分析法的思想例设有文法G[S]：S→aAbA→de

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

5、dSaAb输入串W=adb4.2.1非确定的自上而下分析法的思想上述自上而下为输入串W建立语法树的过程，实际也是设法为输入串建立一个最左推导序列：SaAbadb。由于对输入串从左向

6、右进行扫描，使用最左推导，才能保证按从左到右扫描顺序匹配输入串。4.2.1非确定的自上而下分析法的思想根据以上分析，不难看出，非确定的自上而下分析法即是带回溯的自上而下分析法,实际上是一种穷举的试探方法，其分析效率极低，代价很高，在实用的编译程序中是不常用的。我们通常使用确定的自上而下分析法进行语法分析。4.2.1非确定的自上而下分析法的思想但确定的自上而下分析法对语言的文法有一定的限制条件，那就是要求描述语言的文法是无左递归的和无回溯的。4.2.2文法的左递归性和回溯的消除文法左递归的消除当一个文法是左递归文法

7、时，采用自上而下分析法会使分析过程进入无穷循环之中。文法左递归是指文法中的某个非终结符A存在推导AAα+4.2.2文法的左递归性和回溯的消除用非终结符A去匹配输入串时,使当前句型的最左非终结符仍然为A。也就是说，在没有读进任何输入符号的情况下，又重新要求A去进行新的匹配。于是，造成无穷循环。4.2.2文法的左递归性和回溯的消除对含直接左递归的规则进行等价变换，消除左递归引进一个新的非终结符，把含左递归的规则改写成右递归。设关于非终结符A的直接左递归的规则为4.2.2文法的左递归性和回溯的消除对A的规则可改写成如

8、下右递归形式：A'→αA'

9、εA→βA'A→Aα

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

11、Aα2

12、…

13、Aαm

14、β1

15、β2

16、…

17、βn其中每个α都不等于ε，而每个都不以A开头，消除直接左递归后改写为:A'→α1A'

18、α2A'

19、…

20、αmA'

21、εA→β1A'

22、β2A'

23、…

24、βnA'4.2.2文法的左递归性和回溯的消除

25、例1设有文法G[E]：E→E+T

26、E–T

27、TT→T*F

28、T/F

29、FF→(E)

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

31、idE→TE'E'→+TE'

32、–TE'

33、εT→FT'T'→*FT'

34、/FT'

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

36、Aad

37、bd

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

39、adA'

40、εA→bdA'

41、eA'4.2.2文法的左递归性和回溯的消除(2)采用扩充BNF表示法改写含直接左递归的规则：在扩充的BNF表示中使用花括号{α}

42、表示符号串α的出现可0次或多次，即表示α*4.2.2文法的左递归性和回溯的消除例如定义标识符的文法(b)使用方括号[α]表示α的出现可有可无，它用来表示可供选择的符号串。<标识符>l<标识符>l<标识符>d使用扩充BNF表示可改写成<标识符>l{l

43、d}4.2.2文法的左递归性和回溯的消除例如，定义C语言中条件语句的文法是<条件语句>if<布尔表达式><语句>