new第四章 语法分析2.ppt

1、编 译 原 理Compiler Principles,蒋凌云 南京邮电大学.计算机学院,第四章 语法分析,教材：编译技术原理及其实现方法王汝传 编著,第四章 语法分析,本章内容,4.1 引言 一、语法分析任务 二、语法分析方法 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法） 三、LL（1）分析法 4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用 4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,第四章 语法分析,本章内

2、容,4.1 引言 一、语法分析任务 二、语法分析方法 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法） 三、LL（1）分析法 4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用 4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析

3、3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,自底向上语法分析,自底向上语法分析，是从输入符号串出发，试图把它归约成识别符号。从图形上看，自

4、底向上分析过程是以输入符号串作为末端结点符号串，向着根结点方向往上构造语法树，使识别符号正是该语法树的根结点。自底向上分析是一个不断进行直接归约的过程。任何自底向上分析方法的关键是要找出这种句柄。 目前已有多种自底向上分析技术的实现方法。如简单优先分析法、算符优先分析法以及LR(K)分析法等。,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先

5、文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3

6、. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义

7、2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语

8、法分析,1.与文法有关的一些关系定义 一般说来，一集合上的（二目）关系就是指某一性质，此性质对集合中任意两个符号来说，或者满足或者不满足。如果在集合中两个元素c和d之间满足某一关系，就表示成cRd，如：33。所以可以把关系看成是有序偶的集合：即（c, d) R，当且仅当cRd。,一、简单优先文法分析法,一、简单优先文法分析法,关系R可以具有自反、非自反、对称、非对称 、传递性质外，还具有转置性质，即若cRd，则d(R)c称关系(R)是关系的转置 。如是） ,一、简单优先文法分析法,关系的同等关系记为，cd当且仅当c=d 关系的传递闭包定义为：aRb当且仅当对某个n0，aRnb，显然，如果aRb

9、，则aRb。若把关系看作有序对集合时，便有 关系自反传递闭包*定义为 aR*b 当且仅当a=b或aRb，所以 *,一、简单优先文法分析法,下面我们定义与任何文法有关的几个关系。 （1）上关系 设为已知文法的有穷字汇表，U是任一非终结符，上关系可定义为U L S当且仅当存在规则 U其中可以是终结符或非终结符。 或表示成 （U，）U,S(VTVN ),关系L的意思是由文法规则左部非终结符与右部首符号组成的有序偶集合,一、简单优先文法分析法,例4.5 设文法 f DdCDe e f 由定义求得,(,)，(,)，(,)，(C, e)，(,),（2）上关系传递闭包+ 上关系传递闭包+定义为：U + 当且

10、仅当存在一条规则序列（至少有一条规则），使得 U1，12，2 3，Sn 即 + （U，）U+, S(VTVN) 显然 + = L1 L2 L3,一、简单优先文法分析法,一、简单优先文法分析法,例4.5 设文法 f DdCDe e f (, ),(, ),(, ),(C, e),(, ) 因为 AB BD 所以增加 （A, D) BD DB 所以增加 （B, B) DB BD所以增加 （D, D) 所以 (,),(,),(,),(,), (, ),(, ),(, ),(, e) ,一、简单优先文法分析法,（3）上关系自反传递闭包L* 上关系自反传递闭包L*定义为： L* =I L+ I 为恒等关

11、系 即* （U，）U*,S(VTVN) 显然 L* = L0L1 L2 L3,一、简单优先文法分析法,例4.5 设文法 f DdCDe e f 因为 I= (,),(B,),(C, C),(D,),(d, d), (e,e),(f,f) *I L+ (，)，(，)，(，)，(，)， (，)，(，)，(，)，(，e) 所以*(,),(,),(,),(,), (e,e),(f,f),(d,d),(A,B),(A,D),(B,D),(C,e) ,一、简单优先文法分析法,(4)上关系R (用类似方法可以定义) U R S 当且仅当存在规则 U 所以 (U,S)U ， S(VTVN) (5)上关系R+

12、R+ =(U,S)|U +S， S(VTVN) R (6)上关系* * I * =(U,S)|U *S， S(VTVN) *R,关系R的意思是由文法规则左部符号与右部尾符号组成的有序偶集合,一、简单优先文法分析法,例4.5 设文法 f DdCDe e f 关系，和*同学可自行完成。,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2.

13、LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法,2. 构造文法关系传递闭包和自反传递闭包 根据定义可以直接构造L+，R+，但对于一些复杂文法实现较困难。 这时，可以通过布尔矩阵求得。 (1)布尔矩阵的概念 1)假定关系R是定义在n个符号

14、S1，S2，Sn的集合S上一个关系，可用n*n的布尔矩阵来表示，记为BR BRi，j=1,当且仅当 SiRSj 否则BR的元素BRi，j=0 可见，布尔矩阵中的元素只能取1或0。,一、简单优先文法分析法,设文法 f,DdCDe,e,f 由定义求得 (，)，(，)，(，)，(C,e)，(，) 根据关系L的值，可作出它的布尔矩阵 BL 如下所示：,A B C D e d f A 1 1 0 0 0 0 0 B 0 0 0 1 0 0 0 C 0 0 0 0 1 0 0 D 0 1 0 0 0 0 0 e 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 f 0 0 0 0 0 0 0,两

15、个n*n的布尔矩阵的加法和乘法可以模仿一般矩阵的加法和乘法进行，只是将对应元素的加、乘以及求和运算视为逻辑加、逻辑乘。,BL =,一、简单优先文法分析法,2)说明 设A是n个元素的集合，R是二元关系，于是有： RiR n 这是离散数学中一条十分重要定理，使我们十分方便求出传递闭包 如：A a, b, c, d n4 R4 关系的转置，可用表示的布尔矩阵转置给出。 在同一个字母表上两个关系的乘积，可由表示这两个关系的布尔矩阵乘积给出。 设字母表有n个元素，是上一个关系，而是表示的 nn布尔矩阵，则我们能用 n 所定义的矩阵表示的传递闭包。,一、简单优先文法分析法,(2)构造文法关系L，L+，L*

16、 1) L由文法关系直接求得，由L可求布尔矩阵BL (US.) 2) L+由关系矩阵LL1L2L3Ln求得 3) L*由关系矩阵L*BL0+L1L2L3Ln求得， 其中， BL0是单位矩阵。,一、简单优先文法分析法,(3)构造文法关系R，R+，R* 1) R由文法关系直接求得，由R可求布尔矩阵BR (U.S) 2) R+由关系矩阵RRRRRn求得 3) R*由关系矩阵R*BR0+RRRRn求得， 其中， BR0是单位矩阵。,一、简单优先文法分析法,例 求下面文法L，L+，L* f DdCDe ef 由文法规则求 L=(，)，(，)，(，)，(C，e)，(，) 由L求BL,A B C D e d

17、 f A 1 1 0 0 0 0 0 B 0 0 0 1 0 0 0 C 0 0 0 0 1 0 0 D 0 1 0 0 0 0 0 e 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 f 0 0 0 0 0 0 0,BL =,一、简单优先文法分析法,由BL求BL2BL BL,而BL2BL4BL6,BL2BL4BL6 ,A B C D e d f A 1 1 0 1 0 0 0 B 0 1 0 0 0 0 0 C 0 0 0 0 0 0 0 D 0 0 0 1 0 0 0 e 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 f 0 0 0 0 0 0 0,一、简单优先文

18、法分析法,由BL和BL2求BL3 BL BL2，而BL3BL5BL7,A B C D e d f A 1 1 0 1 0 0 0 B 0 0 0 1 0 0 0 C 0 0 0 0 0 0 0 D 0 1 0 0 0 0 0 e 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 f 0 0 0 0 0 0 0,BL3BL5BL7,一、简单优先文法分析法,BL+,A B C D e d f A 1 1 0 1 0 0 0 B 0 1 0 1 0 0 0 C 0 0 0 0 1 0 0 D 0 1 0 1 0 0 0 e 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 f 0

19、 0 0 0 0 0 0,所以 L+ (，),(，)，(，)，(，)， (，)，(，)，(，)，(，e),求BL+，BL+BL1BL2BL3BL4BL5BL6BL7,一、简单优先文法分析法,求 BL*= BL0+ BL+,BL*=,A B C D e d f A 1 1 0 1 0 0 0 B 0 1 0 1 0 0 0 C 0 0 0 0 1 0 0 D 0 1 0 1 0 0 0 e 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 f 0 0 0 0 0 0 0,A B C D e d f A 1 0 0 0 0 0 0 B 0 1 0 0 0 0 0 C 0 0 1 0 0

20、0 0 D 0 0 0 1 0 0 0 e 0 0 0 0 1 0 0 d 0 0 0 0 0 1 0 f 0 0 0 0 0 0 1,一、简单优先文法分析法,=,A B C D e d f A 1 1 0 1 0 0 0 B 0 1 0 1 0 0 0 C 0 0 1 0 1 0 0 D 0 1 0 1 0 0 0 e 0 0 0 0 1 0 0 d 0 0 0 0 0 1 0 f 0 0 0 0 0 0 1,所以L*= (A,A), (B,B), (C,C), (D,D), (e,e), (f,f), (d,d), (A,B), (A,D), (B,D), (D,B), (C,e) ,一、

21、简单优先文法分析法,(3) Warshall算法 为了有效地由布尔矩阵来计算，1962年Warshall提出了一种算法(简称Warshall算法)，该算法如下： )置矩阵; )置i=1; )对jn，若j, i，对所有k=1,2,n置 Aj, k=j, k+Ai, k (为布尔和) )置ii; )如果in,则转步骤()，否则停止。这样得到矩阵 nn,即nn。,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4

22、. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法,3. 文法优先关系概念,(1) 优先关系 在简单优先分析法中，为了找到可规约的句柄，需要在文法中确立任意符号对之

23、间的优先关系。 对文法的字母表中任一对符号S1和S2，假定有一句型S1S2，在规范分析中某一步，S1或S2或两者必须在句柄中，可发生以下三种情况： 1) S1是句柄一部分(恰好是尾)，但S2不是，用S1S2表示。 其意义就是S1优先于S2，因为S1必须在S2之前被归约。,AS2,S1,句柄,一、简单优先文法分析法,2) S1和S2两者都在句柄之中，这一情况可用S1 S2表示。 其意义就是这两个符号具有相同的优先级而同时被归约。,S,A,S1S2,句柄,一、简单优先文法分析法,3) S2在句柄中(恰好是头)，而S1不在句柄中， 我们用S1S2表示其意义就是S2优于S1归约。,S,S1 A,S2,

24、句柄,一、简单优先文法分析法,(2)几点说明 1) 句型中 S1S2 优先关系的确定是根据规范句型 2) 如果S1S2不同在规范句型中，则S1和S2不存在优先关系 3) 引入的三种优先关系都不具有对称性，即若S1S2，并不一定有 S2 S1必然存在。 (S1，S2)是有序偶。 例如下面例子中有 T，T + 我们可以根据下面文法的不同句型，枚举出各符号对之间的优先关系 U UU+T * i(),一、简单优先文法分析法, 句型U+i*i 我们可根据句型U+i*i的语法树找出该文法部分的优先关系,U,U,+,T,V,F,E,*,V,i,F,i,一、简单优先文法分析法,句型U+i*i中，第一个i是句柄

25、， 由此可得+ * 将i归约到F,句型U+F*i中， F是句柄 由此可得+ * 将F归约到V,句型 U+V*i ,i是句柄， 由此可得* i 将i归约到F,句型 U+V*F, V*F是句柄， 由此可得 + V, V *，* F 将V*F归约到V,句型 U+V, V是句柄， 由此可得 + V 将V归约到T,句型 U+T, U+T是句柄, 由此可得 U +，+ T 还有其它的符号对间的关系，必须借助于其它更多的句型来寻找。,U,U,+,T,V,F,E,*,V,i,F,i,由此看来，要找出文法符号对间全部关系是比较困难的。 下面将用其它方法比较容易地获得全部优先关系,一、简单优先文法分析法,(3)优

26、先矩阵 定义： 根据文法G上多种符号间优先关系列成一张二维表，称为优先矩阵。,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. L

27、ALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法,4. 文法优先关系的构造 (1)优先关系形式定义 为了较容易地构造文法优先关系，可以通过文法G的产生规则来重新定义文法的优先关系。 1) S1 S2当且仅当中有规则 US1S2； 2) S1 S2当且仅当中有规则 U并使得 与* S成立，而且是终结符。,一、简单优先文法分析法,(2) 优先关系构造 根据上面优先关系形式定义的构造文法G字汇表上符号之间优先关系就比 较容易做到。,1) 构造 关

28、系 关系的构造比较简单，对文法中所有形如U S1S2的产生式 右部S1S2 ，就可得 S1 S2 ( S1,S2 )| U S1S2 所以求 关系，只要察看文法中所有规则，就可以求出文法中全部 关系 2) 构造关系 ( )() 证明： 由关系的定义，我们知道一定存在规则 U 且 因此有 ， 由关系的乘积得 ( )() 所以 ( )(),一、简单优先文法分析法,所以求关系，即( )()，只要按下面步骤进行： 察看文法以求全部 关系；( U S1S2) 察看文法以求全部 L关系；( U S1) 由L关系求 先由L求BL，然后再求BL+(BL+BL1BL2BL3BLn ) 由BL+可求得 由 关系和

29、+关系，由公式( )() 可求得关系，同样，也是通过关系矩阵计算,一、简单优先文法分析法,3)构造关系 ()( )(*)其中()是的转置。 证明： 由关系S1 S2的定义，我们知道一定存在规则， U 且，*S2 并且S2是终结符 根据关系的转置 () 因此有 ()， ，*S2 由关系的乘积得 ()( )(* )S2 所以 ()( )(*),一、简单优先文法分析法,所以求关系，即 ()( )(*) ，按下面步骤进行： 察看文法以求全部 R关系； ( U S1) 由R关系求R 先由R求BR，然后再求BR+(BR+BR1BR2BR3BRn ) 由BR+可求得R 由R关系求()， ()是的转置) 察看

30、文法以求全部 关系；( U S1S2) 察看文法以求全部 L关系； ( U S1) 由L关系求* 先由L求BL，然后再求BL+(BL+BL1BL2BL3BLn ) 然后再由求BL+求BL+(BL*BL0BL+)，最后由BL*可求得* 由(+)关系、 关系和*关系求关系， 由公式 ()( )(*) 可求得关系，同样，也是通过关系矩阵计算,一、简单优先文法分析法,例如：文法GE:Z bMb M (L|a LMa) 下面我们根据上面形式定义求出符号间所有优先关系 (1)构造 关系:查看文法 US1S2，易得 =(b,M),(M,b),(,L),(M,a),(a,) (2) 构造关系 ( )() 1)

31、 关系已构造出，据此作出B, =,一、简单优先文法分析法,2)求L关系 Z bMb M (L|a LMa) 由L=(U，S)|U S，得 L=(Z，b), (M，()，(M，a), (L,M) 3) 根据L，作出BL,L =,一、简单优先文法分析法,4) 根据前面讲述由BL求BL+ BL+BL1BL2BL3 BL4 BL5 BL6 BL7,L+ =,一、简单优先文法分析法,5)由布尔矩阵B 和BL+求B B = (B )( BL+),=,6)根据B可求出关系 （b, (）,（b, a）,（(, M),（(, ( ）,（(, a）,一、简单优先文法分析法,(3)构造关系 ()( )(*) Z b

32、Mb M (L|a LMa) 1)由R=(U，S)|U S，得 R=(Z，b), (M，L)，(M，a), (L,) 2)根据R作出BR,R=,一、简单优先文法分析法,3)根据前面讲述由BR求BR+ BR+BR1BR2BR3 BR4 BR5 BR6 BR7,R+=,一、简单优先文法分析法,4)根据由BR+ 求(BR+ )T,(R+ )T =,一、简单优先文法分析法,5) 关系前面已构造出，据此作出B, =,一、简单优先文法分析法,6)求*关系，*I L+ *由L*求得，L*由I和BL+求得 求I，I是使主对角线都置1,I =,一、简单优先文法分析法, BL+前面已构造出,L+ =,一、简单优先

33、文法分析法,求L* ，L* I BL+,L* =,一、简单优先文法分析法,7)由 ()( )(*)，作布尔矩阵B B( B()( B ) B* 根据的形式定义，S1 S2，要求S2是终结符，所以将上步B中非终结符号的列置零，得B, =,一、简单优先文法分析法,(4)根据求得布尔矩阵B ，B，便得GE的优先关系矩阵。(p102表4.6),一、简单优先文法分析法,为进一步熟悉优先关系的构造方法和步骤请同学们课后将书本上98页的例4.8仔细看一遍！,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自

34、反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法,5.简单优先文法 (1)

35、简单优先文法定义 根据文法符号之间的优先关系可以确定归约先后，但要使上下文 无关文法满足符号间唯一优先关系，使得归约是唯一的，必须对文法 作必要的限制。也就是说只有简单优先文法才能满足上述条件。 定义：若文法G满足如下两个条件： 1) 在字汇表中，任意两个符号之间至多只有一种优先关系成立； 2) 任意两条规则都没有相同的右部，则称文法是简单优先文法， 或称(，)优先文法。 这类文法之所以称为简单优先文法或(，)优先文法，是因为在可能成为句柄的那些符号串两边各取一个符号就能判断它是否是句柄。,要证明一个文法是否是简单优先文法，就是要判断它是否满足上述两个 条件。另外，优先关系的确定除了构造优先关

36、系矩阵之外，还可以根据 语法树直观判断。,一、简单优先文法分析法,例如： 文法： bMb (a a) 是简单优先文法，因为其优先关系矩阵中任意两个符号间的优先关系 是唯一的，同时任意两条规则没有相同的右部。 但是，对于文法EE+E|E*E|(E)|i却不是简单优先文法，因为 从句型E+E和句型E+E+E对应的语法树能得出+ E，+ E两种 优先关系。,E,E,+,E,E,+,E,E,E,+,E,+ E,+ E,一、简单优先文法分析法,(2) 简单优先文法的性质 1)它的每个句型S1S2Sn具有一个唯一句柄，该句柄是满足下列条件 i-1Sj+1 的最左子串ii+1j 为了保证即便句柄是从第一个符

37、号开始或到最后一个符号结束时，上述 结论也正确，约定每个句型被括在两个符号之间，并且对文法的任意 符号均有 ,由该性质可知：若从左向右看Sj Sj+1,说明Sj是句柄尾 若从右向左看Si-1 Si ,说明Si是句柄头,一、简单优先文法分析法,2)简单优先文法是无二义性的，因为它的任一句型的句柄都是唯一的。 二义性就是指一个句型有不同的句柄 ，如文法EE+E|E*E|(E)|i 该文法的一个句型E+E*E，就存在E+E和E*E两个不同的句柄，所以该文法是二义的。它也不是简单优先文法。(我们在前面讲过),E,E,+,E,E,*,E,E,E,+,E,E,*,E,一、简单优先文法分析法 三、优先函数及

38、其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优

39、先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法,6.简单优先文法分析算法(即找句柄方法),对于简单优先文法，根据它满足的两个条件及优先关系的定义，不难找到其句型的句柄，即通过自左至右地扫描句型，逐个比较相邻符号直至遇到第一对关系j j+1为止，这时符号j为句柄尾；然后，由j开始自右向左逐个比较相邻符号直到遇到第一对符号i-1i为止，这时i为句柄头。这样很容易找到了句型的句柄。又由于简单优先文法没有相同的右部规则，于是能唯一地确定进行归约句柄的规则。,一、简单优先文法分析法,(1)分析基本思想 根据上述找句型的句柄的基本方法，可设计出如下简单优先分析算法

40、。在运行此算法之前，需要根据已知优先文法，构造其相应优先关系矩阵，此外还要将文法的规则以适当方式存贮，以供分析时查阅。 在算法分析中，为分析栈，用于存放文法符号，其指示器为i，并用S(1)，S(2)表示栈中各项，它随分析进展不断变化。和是以文法符或为值的变量。a1a2an为所要分析的输入符号串。,一、简单优先文法分析法,(2)分析算法 1)首先将符号“”送入栈的栈底。 2)将输入符号串a1a2an依次逐个存入符号栈中，直至符号栈顶的 符号(j)与下一个待输入的符号，有关系(j)为止。 3)句柄尾符号(j)已在符号栈的栈顶，然后再回头找句柄的首符号 (i)，即第一个遇到的关系(i-1)(i)为止

41、，这时符 号 (i)是句柄的头。 4)根据句柄(i)(j)查文法，即在文法中找和句柄(i)S(j)相同的右部规则。如找到，将句柄归约为相应的左部 即在符号栈顶用规则左部符号取代句柄(i)S(j)；如果找不到，则 输入串a1a2an不是该文法的句子。 5)重复上述过程，直到栈中只剩下文法开始符号而下一输入符号是为止。,一、简单优先文法分析法,算法流程图,开始,S(1):=; j:=1; K:=1,R:=ak; K:=K+1,S(j) R?,i:=j,S(i-1) S(i)?,检查文法中有无以S(i)S(j) 为右部的产生式,设U是该产生式的左部 Q:=U; j:=1; S(j):=Q,i:=i-

42、1,N,无,停止，当且仅当j=2, R= 且S(j)为开始符号时，分析成功,j:=j+1; S(j):=R,N,Y,Y,有,一、简单优先文法分析法,(3)分析过程 我们仍然以前面的例子文法来说明分析过程 文法：bMb (a a) 试用上述算法分析符号串b(aa)b是否为此文法的句子。 依据前面构造的该文法的优先关系矩阵,一、简单优先文法分析法,我们结合这两个表来说明简单优先文法分析分析符号串b(aa)b过程。,步骤 符号栈 关系 输入串 规则 1 # b(aa)b# 2 #b (aa)b# 3 #b( aa)b# 4 #b(a a)b# 5 #b(M a)b# M:=a 6 #b(Ma )b#

43、 7 #b(Ma) b# 8 #b(L b# L:=Ma) 9 #bM b# M:=(L 10 #bMb # 11 #Z # Z:=bMb,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系

44、概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分

45、析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,二、算符优先分析法,算符优先关系概念 简单优先文法分析技术是对字汇表中一切符号引进优先关系，这种优先关系是建 立在任意两个符号之间的，实际上，对于一些语法成分，特别是对于如 这样的分析，不需要任意两个符号之间的优先关系。 (1)算符优先关系 只需要对文

46、法的终结符号集中任意两个符号之间的优先关系比较，这种优先关 系称算符优先关系 。 (2)算符优先关系形式定义 已知文法，对于终结符号集中任意两个符号a和b，其算符优先关系 定义如下： 1) ab 当且仅当有规则Uab 或 UaAb 2) ab 当且仅当有规则U=Ab 而 a或 aB 其中和。此处算符优先关系 、与前面简单优先关系 含义是不一样的。它只限于两个终结符之间的优先关系。,二、算符优先分析法,例4.10 已知文法： =E+T =T*F =(E)i 该文法是一个算符文法。根据算符优先关系的定义，文法中： 由形式定义1)对() 得 ( ) 由形式定义2) 对+， 由于+i 得 + 由于+

47、得 + +,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应

48、用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,二、算符优先分析法,2. 算符优先文法 (1) 算符文法 若存在一个文法，如果中不含有形如 U=AB 的规则，其中A，B，则称文法为算符文法( OG：Operator-Grammar)。 如：文法 E=EAE|(E)|-E|i A=+|*|/| 就不是算符文法，因为它含有连续两个非终结符在一起的产生 式右部EAE 若改成下面的等价文法，就是算符文法。 E=E+E|E-E|E*E|E/E|EE|(E)|-E|i,二、算符优先分析法,(2) 算符优先文法 如果一个算符文法()的任意两

49、个终结符号对(a，b)之间至多只 满足下述三个关系之一： ab ,ab 则称是一个算符优先文法(OPG：Operator Precedence Grammar)。 例如： 文法： bMb (a a) 是简单优先文法，却不是算符优先文法。因为(和a之间有两 种优先关系。 由形式定义2) 对( ，由于 La) 得 ( a,一、简单优先文法分析法 三、优先函数及其构造 1. 与文法有关的一些关系定义 1.优先函数定义 2. 构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3. 文法优先关系概念 四、LR分析法 4. 文法优先关系的构造 1. LR分析法

50、一般概述 5. 简单优先文法 2. LR分析器工作原理 6. 简单优先文法分析算法 3. LR(0)分析表构造 二、算符优先分析法 4. SLR(1)分析表构造 1. 算符优先关系概念 5. LR(1)分析表构造 2. 算符优先文法 6. LALR分析表构造 3. 算符优先关系的构造方法 五、二义性文法的应用 4. 最左素短语 1.问题的提出 5. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,二、算符优先分析法,3. 算符优先关系的构造方法 按照定义，通过相当数量的推导来构造算符优先关系的办法是不可取的，我们可按和简单优先文法相仿的步骤来构造算符优先矩阵。 为了给出

51、构造算符优先关系，对于算符文法，先定义两个新关系： ()关系L1 设是一算符优先文法，是文法上的字汇表，上关系L1定义为 U L1b 当且仅当 U=b 或U=Vb 其中U、VVN，bVT。或 L1 (U, b)U=b或U=Vb ()关系R1 U R1b 当且仅当 U=b或U=bV 或 R1 (U, b)U=b或 U=bV,二、算符优先分析法,(3) 算符优先关系的构造 1) 对于关系 ，可以逐个查看文法中各规则右部，对形如ab 或aAb，a,b，令ab 2) 对于关系，有 ( )(*)() 证明： 由关系ab的定义，文法中有规则形如 U=aA 而 A +b 或 +b 由 UaA 规则，得a A

52、 由b或 Bb,得 *，=b，=Bb 因此有 *及 b 于是有 a A，*， b 由关系乘积得 a( )(*)()b 所以 ( )(*)(),二、算符优先分析法,求 关系，即 ( )(*)(1)，只要按下面步骤进行： 察看文法以求全部 关系； ( U S1S2 ) 察看文法以求全部 L关系； ( U S) 由L关系求* 先由L求BL，然后再求BL+(BL+BL1BL2BL3BLn ) 然后再由BL+求BL*(BL*BL0BL+)，最后由BL*可求得* 察看文法以求全部 L1关系( U=b或U=Vb ) 由 、* 和关系可求得关系， 即 ( )(*)() 可求得关系，同样，也可以通过关系矩阵计算

53、,二、算符优先分析法,)对于关系 ，有 (*)(1)( ) 证明： 由关系ab的定义，文法中有规则形如 U=Ab 而 +a或 aB 由U=Ab 规则 得A b 由+a或 aB 得*，=a， =aB 因此有 * 及 1a 由关系乘积得 *1a 由关系的转置得 *1a a(*)(1)T 于是有 a(*)(1)T ， b 由关系乘积得 a (*)(1)T ( )b 所以 (*)(1)T ( ),二、算符优先分析法,求 关系，即 (*)(1)T ( )，只要按下面步骤进行： 察看文法以求全部 R关系； ( U S) 由R关系求R，先由R求BR，然后再求BR+(BR+BR1BR2BR3BRn ) 然后再由BR+求BR*(BR*BR0BR+)，最后由BR*可求得* 察看文法以求全部R1关系；( U=b或 U=bV) 由R*关系和R1关系求(*)(1)关系 求(*)(1)关系的转置(*)(1)T 察看