编 译 原 理 Compiler Principles,蒋凌云 jianglingyunnjupt.edu.cn 南京邮电大学.计算机学院,第四章 语法分析,教材：编译技术原理及其实现方法王汝传 编著,第四章 语法分析,本章内容,4.1 引言一、语法分析任务二、语法分析方法 4.2 自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法 4.3 自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用 4.4 语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,第四章 语法分析,本章内容,4.1 引言一、语法分析任务二、语法分析方法 4.2 自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法 4.3 自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用 4.4 语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,一、简单优先文法分析法 三、优先函数及其构造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. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,自底向上语法分析,自底向上语法分析，是从输入符号串出发，试图把它归约成识别符号。从图形上看，自底向上分析过程是以输入符号串作为末端结点符号串，向着根结点方向往上构造语法树，使识别符号正是该语法树的根结点。自底向上分析是一个不断进行直接归约的过程。任何自底向上分析方法的关键是要找出这种句柄。目前已有多种自底向上分析技术的实现方法。如简单优先分析法、算符优先分析法以及LR(K)分析法等。,一、简单优先文法分析法 三、优先函数及其构造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. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法 三、优先函数及其构造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. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,一、简单优先文法分析法 三、优先函数及其构造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. 算符优先分析算法 2.二义性文法分析表的构造,4.3 自底向上语法分析,1.与文法有关的一些关系定义一般说来，一集合上的（二目）关系就是指某一性质，此性质对集合中任意两个符号来说，或者满足或者不满足。如果在集合中两个元素c和d之间满足某一关系，就表示成cRd，如：33。所以可以把关系看成是有序偶的集合：即（c, d) R，当且仅当cRd。,一、简单优先文法分析法,一、简单优先文法分析法,关系R可以具有自反、非自反、对称、非对称 、传递性质外，还具有转置性质，即若cRd，则d(R)c称关系(R)是关系的转置 。如是） ,一、简单优先文法分析法,关系的同等关系记为，cd当且仅当c=d关系的传递闭包定义为：aRb当且仅当对某个n0，aRnb，显然，如果aRb，则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 + 当且仅当存在一条规则序列（至少有一条规则），使得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 为恒等关系即* （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) ,