CH04--语法分析.ppt

第4章 语法分析,知识点：预测分析方法、LL(1)分析程序 移进-归约分析方法、LR分析程序 SLR(1)、LR(1)、LALR(1)分析表,2/152,4 语法分析,简介4.1 语法分析程序4.2 自顶向下分析方法4.3 自底向上分析方法4.4 LR分析方法4.5 软件工具YACC 小结,3/152,语法分析简介,语法分析是编译过程的核心部分语法分析任务由语法分析程序完成语法分析的工作依据是：语言的语法规则本章内容安排：首先讨论常用的语法分析方法和技术自顶向下的方法自底向上的方法,4/152,4.1 语法分析程序,语法分析程序的任务从源程序记号序列中识别出各类语法成分进行语法检查语法分析程序的地位：,5/152,常用的分析方法自顶向下的方法：从树根到叶子来建立分析树自底向上的方法：从树叶到树根来建立分析树对输入符号串的扫描顺序：自左向右,语法分析程序的作用输入：记号流/记号序列工作依据：语法规则功能：将记号组合成语法成分、语法检查输出：分析树错误处理,6/152,4.2 自顶向下分析方法,一、递归下降分析二、递归调用预测分析三、非递归预测分析,7/152,一、递归下降分析,从文法的开始符号出发，进行推导，试图推出要分析的输入串的过程。对给定的输入串，从对应于文法开始符号的根结点出发，自顶向下地为输入串建立一棵分析树。试探过程，是反复使用不同产生式谋求匹配输入串的过程。,8/152,例:试分析输入串=cad是否为如下文法的一个句子。ScAd Aab|a(文法4.1),ScAd cad试图为输入符号串建立一个最左推导序列的过程。,c a d,S,c,A,d,a,b,c a d,S,c,A,d,a,推导？,9/152,因为对输入串的扫描是自左至右进行的，只有使用最左推导，才能保证按扫描的顺序匹配输入串。递归下降分析方法的实现文法的每一个非终结符号对应一个递归过程，即可实现这种带回溯的递归下降分析方法。每个过程作为一个布尔过程，一旦发现它的某个产生式与输入串匹配，则用该产生式展开分析树，并返回true，否则分析树不变，返回false。实践中存在的困难和缺点左递归的文法，可能导致分析过程陷入死循环。回溯工作的重复效率低、代价高：穷尽一切可能的试探法。,为什么采用最左推导？,10/152,二、递归调用预测分析,一种确定的、不带回溯的递归下降分析方法如何克服回溯？对文法的要求预测分析程序的构造,11/152,如何克服回溯？,能够根据所面临的输入符号准确地指派一个候选式去执行任务。该选择的工作结果是确信无疑的。例：A1|2|i|n当前输入符号：a指派i去匹配输入符号串,12/152,对文法的要求,1.不含左递归,2.FIRST(i)FIRST(j)=（ij）A1|2|n 非终结符号A的所有候选式的开头终结符号集两两互不相交,左递归？,AA,13/152,例:有如下产生PASCAL类型子集的文法：typesimple|id|arraysimple of typesimpleinteger|char|num dotdot num（文法4.2）分析输入串：array num dotdot num of char,type的三个候选式，有：FIRST(simple)=integer,char,num FIRST(id)=FIRST(arraysimple of type)=array simple的三个候选式，有：FIRST（integer）=integer FIRST(char)=char FIRST(num dotdot num)=num,14/152,输入：array num dotdot num of char,树：type,array simple of type,num dotdot num,simple,char,产生式：A缺席匹配当递归下降分析程序没有适当候选式时，可以用一个-候选式，表示其它候选式可以缺席。,15/152,预测分析程序的构造,预测分析程序的转换图转换图的工作过程转换图的化简预测分析程序的实现,16/152,预测分析程序的转换图,为预测分析程序建立转换图作为其实现蓝图每一个非终结符号有一张图有向边的标记可以是终结符号，也可以是非终结符号。在一个非终结符号A上的转移意味着对相应A的过程的调用。在一个终结符号a上的转移，意味着下一个输入符号若为a，则应做此转移。,17/152,改写文法重写文法消除左递归提取左公因子对每一个非终结符号A，做如下工作：创建一个初始状态和一个终结状态。对每一个产生式AX1X2Xn创建一条从初态到终态的路径，有向边的标记依次为X1,X2,Xn。,从文法构造转换图,改写文法？,18/152,例：为如下文法构造预测分析程序转换图 EE+T|T TT*F|F F(E)|id(文法4.3),消除文法中存在的左递归，得到 ETE E+TE|TFT T*FT|F(E)|id(文法4.4),19/152,为每个非终结符号构造转换图：,ETEE+TE|TFTT*FT|F(E)|id,20/152,转换图的工作过程,从文法开始符号所对应的转换图的开始状态开始分析经过若干动作之后，处于状态S,21/152,转换图的化简,用代入的方法进行化简,22/152,把E的转换图代入E的转换图：,利用状态转换图识别符号串 id+id*id,23/152,预测分析程序的实现,要求用来描述预测分析程序的语言允许递归调用E的过程：void procE(void)procT;if(char=+)forward pointer;procE();,24/152,T的过程：void procT(void)procF();if(char=*)forward pointer;procT();,25/152,F的过程：void procF(void)if(char=()forward pointer;procE();if(char=)forward pointer;else error();else if(char=id)forward pointer;else error();,26/152,三、非递归预测分析,使用一张分析表和一个栈联合控制，实现对输入符号串的自顶向下分析。预测分析程序的模型及工作过程预测分析表的构造LL(1)文法预测分析方法中的错误处理示例,27/152,预测分析程序的模型及工作过程,预测分析控制程序,分析表M,输入缓冲区,输出,核心,关键,28/152,每部分的作用,输入缓冲区：存放被分析的输入符号串，串后随右尾标志符$。符号栈：存放一系列文法符号，$存于栈底。分析开始时，先将$入栈，以标识栈底，然后再将文法的开始符号入栈。分析表：二维数组MA,a，AVN，aVT$。根据给定的A和a，在分析表M中找到将被调用的产生式。输出流：分析过程中不断产生的产生式序列。,$,29/152,X=a=$，宣告分析成功，停止分析X=a$，从栈顶弹出X，输入指针前移一个位置XVT，但Xa，报告发现错误，调用错误处理程序，以报告错误及进行错误恢复。若XVN，访问分析表MX,a,预测分析控制程序：根据栈顶符号X和当前输入符号a，决定分析动作有4种可能：,30/152,MX,a=X从栈顶弹出X；MX,a=error调用出错处理程序。,MX,a=XY1Y2Yn先将X从栈顶弹出，然后把产生式的右部符号串按反序（即按Yn、Yn-1、Y2、Y1的顺序）一一推入栈中；,