编译原理课程设计之第四章 自上而下的语法分析

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,课程内容,第一章,概论,第二章,词法分析,第三章,上下文无关文法及分析,第四章,自上而下的语法分析,第五章,自下而上的语法分析,第六章,语义分析,第七章,运行时环境,第八章,代码生成,1,2,语法分析以词法分析程序输出的单词序列为输入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序。,通常我们将,语法分析的结果表示为分析树（,parse tree）,或语法树(,syntax tree)。,3,4.1,分析树与抽象语法树,4.2,自上而下的语法分析算法概述,4.3,递归下降分析,4.3,LL(1),分析,第四章 自上而下的语法分析,4,4.1,分析树与抽象语法树,句子的每一个推导过程都对应一个分析树，分析树的定义：,文法,G=(,V,T,V,N,P,S),对应的,分析树,是一个作了标记的树：,(1)每个节点都用终结符、非终结符或,标出；,(2)根结点用开始符号,S,标出；,(3)每个叶结点都用终结符或,标出；,5,(4)每个非叶结点都用非终结点标出；,(5),每一步直接推导对应一个子树,：如果分析树中标记为,AV,N,的节点有,n,个标记为,X,1,，X,2,X,n,的孩子(,可以是终结符也可以是非终结符,),则文法,G,中有对应的产生式,A,X,1,X,2,X,n,P,；,6,exp,exp op exp,number,op exp,number,+ exp,number,+,number,简单整型算术表达式文法：,exp,exp op exp,|(,exp,)|,number,op,+,|,-,|,*,符号串3+4的最左推导:,7,exp,exp,op,exp,number,+,number,1,2,3,4,3+4的分析树,8,exp,exp op exp,exp op,number,exp +,number,number,+,number,简单整型算术表达式文法：,exp,exp op exp,|(,exp,)|,number,op,+,|,-,|,*,3+4的最右推导,9,exp,exp,op,exp,number,+,number,1,2,3,4,3+4的分析树,10,分析树对于显示程序的各语法单位或程序的单词序列很有帮助，,但是相比纯粹为编译生成可执行代码所需的信息而言，分析树却包括了更多的信息。,所以语法分析程序更趋向于生成抽象语法树，抽象语法树是分析树中所含信息的浓缩，这种树是源代码单词序列的抽象表示。它却包含了进一步分析所需的所有信息。而且比分析树效率更高。,注：各语法单位对应的抽象语法树的结构可以规定，没有标准，但可以参考现有编译器的做法。,11,简单整型算术表达式文法：,exp,exp op exp,|(,exp,)|,number,op,+,|,-,|,*,简单算术表达式,的对应的,抽象语法树结构,op,l_operand,r_operand,12,+,3,4,3+4的抽象语法树,+,-,42,（34-3）+42 的抽象语法树,34,3,13,Typedef,enum,Plus,Minus,Times,OpKind,;,Typedef,enum,OpKind,ConstKind,ExpKind,;,Typedef,struct,streenode,ExpKind,kind;,OpKind,op;,struct,streenode,*,lchild,*,rchild,;,int,val,;,StreeNode,Typedef,StreeNode,*,SyntaxTree,;,14,4.1,分析树与抽象语法树,4.2,自上而下的语法分析算法概述,4.3,递归下降分析,4.3,LL(1),分析,第四章 自上而下的语法分析,15,自上而下的语法分析算法：,从文法的开始符号出发，反复使用文法的产生式规则，试图寻找与输入符号串匹配的推导。,从语法树的构造过程来看，是从文法的开始符号出发，将它做为语法树的根，试图向下逐步建立语法树，语法树的叶子节点是输入符号串；,4.2,自上而下的语法分析算法概述,16,自上而下的语法分析算法,：,已知文法,GS,对任意输入串,w,若从文法的开始符号,S,出发, 能为,w,构造一个,最左推导,，则,w,是一个合法的句子，即,w,L(G),否则,w,有语法错误。,从,S,出发，尝试了所有可能的最左推导序列都不能推出,w，,则说明,w,有语法错误；,该算法试图自上而下为,w,的分析结果建立一棵语法树。,17,例4-1：文法,G：,S ,aA,S ,cAd,A a,A ,ab,识别输入串,w=,cabd,是否为该文法所定义的句子？,运用自上而下的语法分析方法：,18,c,A,d,cabd,c,A,d,cad,S,c,A,d,从文法开始符号,S,出发试图为,w=,cabd,构造一个最左推导:,S,c,A,d,cabd,c,S,d,A,b,a,成功,19,自上而下的语法分析方法：,从文法开始符号,S,出发试图为输入符号串构造一个最左推导；,构造最左推导的过程就是选择产生式和匹配符号串的过程；,有时需要重复扫描词法分析输出的单词序列。,20,4.1 递归下降语法分析,4.1.1 递归下降分析的基本方法,4.1.2 文法规则使用,EBNF,表示法,4.1.3 其它应注意的问题,21,递归下降分析法,是一种自上而下的语法分析方法，在这种方法中，执行一组,递归,函数,来处理输入串。,对文法的每一个,非终结符,A,，,都根据其相应的产生式(即文法规则)为其编写,一个函数,(子程序)，用来,识别,该非终结符所表示的,语法范畴,。,4.1.1 递归下降分析的基本方法,22,例4-2：文法,G：S ,c,A,d,A ,ab,识别输入串,w=,cabd,是否为该文法定义的句子？,识别,S,的递归下降函数的伪代码,：,23,void,match,(expectedToken,);, if token=,expectedToken,token =,getToken,();,else,error;,cabd,变量,token,存储当前扫描的下一个单词,24,void,S,(void), match(,c,);,A();,match(,d,);,void,A,(void), match(,a,);,match(,b,);,25,例4-3：文法,G：S ,c,A,d,A ,a,A ,ab,识别输入串,w=,cabd,是否为该文法定义的句子？,写出识别,S,的递归下降函数的伪代码,：,26,识别,S,的递归下降函数的伪代码,：,void,S,(void), match(,c,);,A1();,/,记住当前的,token,位置,match(,d,);,if,(,error) then, A2();,match(,d,);,void,A1,(void), match(,a,);,void,A2,(void), match(,a,);,match(,b,);,27,如果语法分析使用递归下降分析程序,为了避免重复扫描词法分析输出的单词序列(提高效率,)，,需要先将文法,G,采用,EBNF,表示法，然后写出,递归下降分析程序。,28,4.1 递归下降语法分析,4.1.1 递归下降分析的基本方法,4.1.2 文法规则使用,EBNF,表示法,4.1.3 其它应注意的问题,29,选择的情况,重复的情况,4.1.2 文法规则使用,EBNF,表示法,30,选择的情况,EBNF,使用 表示选择,：,文法,G： S ,c,A,d,A ,a,A ,ab,的,EBNF,表示法如下：,S ,c,A,d,A ,a,b,31,识别,S,的递归下降函数的伪代码,：,S,c,A,d,A ,a,b,void,S,(void), match(,c,);,A();,match(,d,);,void,A,(void), match(,a,);,if token=,b,then,match(,b,);,避免了重复扫描词法分析输出的单词序列,32,例4-4：,一个简化了的,if,文法规则：,if-stmt,if (,exp,),statement,|if (,exp,),statement,else,statement,写出识别,if-stmt,的递归下降函数的伪代码,33,首先给出,if,文法规则的,EBNF,表示法,：,if-stmt,if,(,exp,),statement,else,statement,识别,if-stmt,的递归下降函数的伪代码如下：,34,viod,ifStmt,(void,), match(,if,);,match(,(,);,exp,();,match(,),);,statement,();,if token =,else,then, match(,else,);,statement,();,35,重复情况：,简单整型算术表达式文法：,exp,exp,addop,term|term,addop,+,|,-,term,term,mulop,factor|factor,mulop,*,factor,(,exp)|,number,写出识别表达式,exp,的递归下降函数的伪代码,36,现在考虑,BNF,中简单算术表达式文法中的,exp,情况：,exp,exp,addop,term|term,如要我们试着将写一个,exp,函数，则首先应做的是调用,exp,本身，而这将导致一个无限递归循环。,由于,exp,和,term,可以以相同的单词开头（一个数或左括号），所以要想测试使用哪个选择（,exp,exp,addop,term,或,exp,term,）,就会出现问题了。,37,解决问题的办法是使用,EBNF,规则：,EBNF,使用 表示重复：,A,和,A,重复的一般规则,：,A,A,|,(,左递归),和,A,A,|,(,右递归), 表示其中的内容重复,n,次(,n=1),写,递归下降程序时,可将花括号,表示的,重复部分翻译成循环代码,38,将花括号,表示的,重复部分,addop,term,翻译成循环代码， 语法范畴,exp,对应的函数的定义如下：,上述产生式规则,exp,exp,addop,term|term,用,EBNF,表示成,exp,term,addop,term,39,viod,exp,(,void),term( ),;,while,token=+ or token=-,match(token);,term( ),;,40,简单整型算术表达式文法：,exp,exp,addop,term|term,addop,+,|,-,term,term,mulop,factor|factor,mulop,*,factor,(,exp)|,number,写出识别表达式,exp,的完整的递归下降函数的伪代码？,41,4.1 递归下降语法分析,4.1.1 递归下降分析的基本方法,4.1.2 文法规则应使用,EBNF,表示法,4.1.3 其它应注意的问题,42,4.1.3 其它应注意的问题,前面描述的递归下降分析虽然非常强大，但它仍有特殊性。若使用的是一个设计精巧的小型语言（例如,TINY，,甚至是,C），,那么对于构造一个完整的分析程序，这些办法是适合的；但还会出现一些问题。,43,两个或多个文法规则的选项,： 例如：,A|,如果,和,均以非终结符开始，那么就很难决定何时使用,A,选项，何时又使用,A,选项。这个问题就要求计算,和,的,First,集合。,间接递归的文法:,例如：,SAb|c,ASa,可将其变换为,SSab|c,，,进而变换为：,S ,cab,44,在分析程序中安排动作,：,例如,（1）,保持运算的结合性,（,2）构造相应的语法树节点,45,EBNF,文法表示的,tiny,语言的语法.,doc,用递归下降分析算法写出,TINY,语言的语法分析程序？,46,语法分析的基本步骤,根据语言的语法描述形式，定义各种基本语法结构的,抽象语法树形式,；,选择一种合适的,语法分析算法,；,生成句子,语法分析的结果,(,抽象语法树或错误报告,),。,47,语句序列,stmt-sequence,statement,;,statement,TINY,语言的各基本语法范畴的抽象语法树结构形式如下：,48,if-stmt,if,exp,then,stmt-sequence,else,stmt-sequence,end,if,语句的抽象语法树结构：,49,repeat,语句,repeat-stmt,repeat,stmt-sequence,until,exp,50,assign,语句,assign_stmt,identifier :=,exp,51,write,语句,write_stmt,write,exp,read,语句,read_stmt,read,identifier,52,算符表达式,53,typedef,enumStmtK,ExpKNodeKind,;,typedef,enumIfK,RepeatK,AssignK,ReadK,WriteKStmtKind,;,typedef,enumOpK,ConstK,IdKExpKind,;,typedef,enumVoid, Integer,BooleanExpType,;,#,define MAXCHILDREN 3,54,typedef,struct,treeNode,struct,treeNode,* childMAXCHILDREN;,struct,treeNode,* sibling;,int,lineno,;,NodeKind,nodekind,;,union,StmtKind,stmt;ExpKind,exp; kind;,union,TokenType,op;,int,val,;,char * name;,attr,;,ExpType,type;,TreeNode,;,55,Tiny,语言的递归下降分析函数如下：,PARSE.C,一个输出其输入阶乘的,TINY,语言程序,read x;,if x0 then,fact:=1;,repeat,fact:=fact* x;,x:=x-1,until x=0;,write fact,end,56,57,一个输出其输入阶乘的,TINY,语言程序,read x;,if x0 then,fact:=1;,repeat,fact:=fact* x;,x:=x-1,until x=0;,write fact,end,58,59,递归下降语法分析课程设计（共,20,分）：,详细信息：,语法分析课程设计.,doc,60,第四章 自上而下的语法分析,4.1 递归下降分析,4.2 LL(1),分析,作业,61,4.2,LL( 1 ),分析,4.2.1,LL(1),分析的基本方法,4.2.2,LL(1),分析与算法,4.2.3 消除左递归和提取,62,4.2.1,LL(1),分析的基本方法,LL (1),分析方法是一种自上而下的语法分析方法：第,1,个“,L,”,指的是由左向右地处理输入。第,2,个“,L,”,指的是它为输入串找出一个最左推导。括号中的数字,1,意味着它仅使用输入串中的一个符号来预测分析的方向。,63,例如：假设有生成成对括号的串的简单文法,：,S,(S)S|,判断,输入串,( )是否是符合该文法规则的句子？,LL (1),分析方法如下：,输入串( ),的自上而下分析程序的分析动作：,64,S,(S)S,(,)S,(,),( ),的最左推导,S,（,）,S,S,构造最左推导要解决的问题：,每一步推导是针对当前句型中的哪一个非终结符进行推导,？,用该非终结符的哪一个产生式进行推导(,选择产生式,)？,65,LL (1),分析方法如下：,通过栈来记忆针对当前句型中的哪一个非终结符进行推导,首先将文法的开始符号,S,入栈；,如果栈的顶部是终结符,a,则将其与当前输入记号,匹配(出栈,),。,如果栈的顶部是非终结符,A,则,利用,A,对应的某个,文法规则,A,将栈顶部的非终结符,A,(,出栈,),替换,成串,(,将串,自右至左入栈)。,66,构造一个,终结符,和,非终结符索引,的二维表格,MN,T,可以表达出用哪一个产生式进行进行下一步推导,其中,N,是非终结符的集合，,T,是终结符的集合，即构造一个,LL(1),分析表，通过该表格引导用哪一个产生式进行推导。,67,MN,T,S,(,),$,S,(S)S,S,S, ,文法,S,(S)S|,的,LL(1),分析表,M,S,(,表示,当前分析栈的栈顶符号为,S,，而当前词法分析的输入记号为(时，按产生式,S,(S)S,进行推导；,M,S,),表示,当前分析栈的栈顶符号为,S,，而当前词法分析的输入记号为)时，按产生式,S,进行推导；,68,分析栈,输入,动作,步骤,$,S,1,( ),$,S,（S）S,$,S)S(,2,( ),$,匹配,$,S)S,3,),$,S, ,$,S),4,),$,匹配,$,S,5,$,S, ,$,6,$,接受,注：将句型自右至左入栈,LL (1),分析方法,69,LL(1),分析程序通过将分析栈顶部的,非终结符,替换,成文法规则中该非终结符的一个选择,来做出分析。在分析过程中有两个基本动作：,如果栈的顶部是终结符,a,则将其与当前输入记号,匹配,。,如果栈的顶部是非终结符,A,则利用文法规则,A,将栈顶部的非终结符,A,替换,成串,(,保证,自右至左入栈)。,70,问题：,如何构造,LL(1),分析表？,构造分析表的步骤：,求,First,集合,求,Follow,集合,构造,LL(1),分析表,71,文法符号,X,的,First(),集合,：,令,X,为一个,文法符号,（一个终结符或非终结符）或,，则,First(X),是,终结符的集合,，此外可能还有,，它的定义如下：,若,X,是终结符或,，则,First(X) =X,。,72,若,X,是非终结符，则对于,X,对应的,每个产生式,XX,1,X,2,.,X,n,，,First(X),包括,First(X,1,)-,。,若对于某个,i TE (2) E +TE (3) E ,(4) T FT (5) T *FT (6) T ,(7) F (E) (8) F a,先求其,First( ),集包含,的非终结符：,例4-4：考虑下述文法，求各非终结符的,First(),集合；,文法,G E:,E,T,77,First(E),First(E),First(T),First(T),First(F),(,a,+,*,从文法的开始符号,E,将求,First(),集的算法过程表示成下列图示；,78,求得各非终结符的,First,集合如下：,First(E)=(,a,First(E)=+,First(T)=(,a,First(T)=*,First(F)=(,a,79,定义,：给出一个非终结符,A,，,那么集合,Follow(A),则是由终结符组成，此外可能还有$。集合,Follow(A),的定义如下：,Follow,集合,1. 若,A,是开始符号,则,Follow(A),包含$,2. 若存在产生式,B,A,则,Follow(A),包含,First(,)-,3. 若存在产生式,B,A,，,且,在,First(,),中，则,Follow(A),包含,Follow(B),80,例4-5：考虑下述简单整型表达式文法，求各非终结符的,Follow(),集合；,exp,exp,addop,term,(2),exp,term,(3),addop,+,(4),addop,-,(5),term,term,mulop,factor,(6),term,factor,(7),mulop,*,(8),factor,(,exp,),(9),factor,number,81,Follow(exp)=,Follow(addop,)=,Follow(term)=,Follow(mulop,)=,Follow(factor)=,$,+,-,),(,number,$,+,-,*,),(,number,$,+,-,*,),82,例2：考虑下述文法，求各非终结符的,Follow(),集合；,先求其,First,集包含,的非终结符为：,E， T,(1) E TE (2) E +TE (3) E ,(4) T FT (5) T *FT (6) T ,(7) F (E) (8) F a,文法,G E:,83,Follow(E),),$,Follow(E),Follow(E),Follow(T),First(E),Follow(E),从文法的开始符号,E,将求,Follow(),集的算法过程表示成下列图示；,84,Follow(T),Follow(T),Follow(F),First(T),Follow(T),85,各非终结符的,Follow,集合如下：,Follow(E)=) , $,Follow(E)=), $,Follow(T)=+, ), $,Follow(T)=+, ), $,Follow(F)=*, +, ), $,86,构造,LL(1),分析表,对于,First(,),中的每个终结符,a，,都将,A,添加到项目,MA,a,中，置,MA,a,=“,A,”。,即当当前分析栈的栈顶符号为,A,时，而当前词法分析的输入记号为,a,时，按产生式,A,进行推导；,LL(1),分析表的构造方法：,为每个非终结符,A,和它对应的产生式,A,重复以下两步骤：,87,定义：如果文法,G,相关的,LL(1),分析表的每个项目中至多只有一个产生式，则该文法就是,LL(1),文法,。,3),所有没有定义的元素位置,A,a,标上“出错”标志。,若,在,First(,),中，则对于,Follow(A),的每个元素,a,(,或是,$,)，都将,A,添加到,MA,a,中。,即在此情况下按产生式,A,进行推导。,88,例4-6：考虑简化了的,C,声明的文法,：,declaration,type,var,-list,type,int,|,float,var-list,identifier,list,list,var,-list,|,求该文法各非终结符的,First(),集合和,Follow(),集合。,构造该文法的,LL(1),分析表。,说明该文法是,LL(1),文法。,假设有输入串,int,x,y,z,写出相对应的,LL(1),分析程序的动作。,89,First(,declaration,)=,int,float,First(,type,) =,int,float,First(,var,-list,) =identifier,First(,list,) =,所求得的各非终结符的,First,集合和,Follow,集合如下：,90,Follow(,declaration,)=$,Follow(,type,)=identifier,Follow(,var,-list,)=$,Follow(,list,) =$,91,r1: declarationtype,var,-list,r2:,type,int,r3: type,float,r4:,var-list,identifier,list,r5: list ,var,-list,r6: list ,对各产生式进行编号：,构造该文法的,LL(1),分析表。,92,MN,T,declaration,int,identifier,$,type,var,-list,list,float,r1,r1,r2,r3,r4,r5,r6,由于文法,G,相关的,LL(1),分析表的每个项目中至多只有一个产生式，故该文法是,LL(1),文法,。,93,输入串,int,x,y,z,相对应的,LL(1),分析程序的分析过程如下表所示：,步骤,分析栈,输入,动作,1,$,declaration,int,x,y,z,$,r1,4,$,var,-list,x,y,z,$,r4,2,$,var,-list,type,r2,int,x,y,z,$,3,int,x,y,z,$,匹配,$,var,-list,int,94,5,$,list,identifier,x,y,z,$,匹配,6,$,list,y,z,$,r5,$,var,-list,y,z,$,7,匹配,$,var,-list,8,r4,y,z,$,步骤,分析栈,输入,动作,$,成功,$,95,4.2,LL( 1 ),分析,4.2.1,LL(1),分析的基本方法,4.2.2,LL(1),分析与算法,4.2.3 消除左递归和提取,96,Input,$,总控程序,LL(1),预测分析表,stack,$,97,4.2.2,LL(1),分析与算法,基于表的,LL(1),分析算法流程,：,98,4.2,LL( 1 ),分析,4.2.1,LL(1),分析的基本方法,4.2.2,LL(1),分析与算法,4.2.3 消除左递归和提取,99,由于含有左递归和左公共因子的文法,不是,LL(1),文法，如果要使用,LL(1),语法分析算法对该文法定义的语言进行语法分析，那么必须通过,消除左递归和提取左公共因子，将文法进行等价改造,100,4.2.3 消除左递归和提取左因子,简单直接左递归的消除,A,A,A,简单直接左递归的文法是否是,LL(1),文法？,如果文法,G,相关的,LL(1),分析表的每个项目中至多只有一个产生式，则该文法就是,LL(1),文法,。,101,消除直接左递归后将上述文法重写为：,A,A,A,A,|,A,A,|,102,例：消除下面文法的左递归规则：,exp exp,addop,term|term,exp term exp,消除左递归后将上述文法重写为：,exp ,addop,term exp|,103,多项直接左递归的消除,A,A,1,|,A,2,|,A,n,|,1,|,2,|,|,m,消除左递归后将上述文法重写为：,A, ,1,A,|,2,A,|,m,A,A,1,A,|,2,A,|,n,A|,104,例：消除下面文法的左递归规则：,exp exp+term| exp-term| term,exp term exp,消除左递归后将上述文法重写为：,exp +term exp| -term exp| ,105,提取左因子,：,若文法,G,有产生式,U,xy,|,xw,|,xz,则该文法是否是,LL(1),文法？,106,若在,y,w,z,中仍然有左公共因子，可以再次提取。注意，若有：,U,xy|x,则提取后：,Ux(y|),若有产生式,U,xy|xw,|,xz,，,则提取左公共因子并用,EBNF,表示为：,U,x(y|w|z),再引入另一个非终结符号,V，,将产生式变为：,U,xV,V y|w|z,107,设有产生式：,Sif B then S,1,else S,2,|if B then S,1,其中，,S,表示两种类型的条件语句。,引入非终结符号,R：,Sif B then S,1,R Relse S,2,|,提取公因子，改成：,Sif B then S,1,(else S,2,|,),108,本章小结,本章学习了两类自上而下的语法分析算法：,递归下降分析方法,手写语法分析程序比较适合,LL(1),分析方法,实际中不常用到,算法思想,109,考虑文法,GS:,S- A,B A-b|c B-(C) C-CS|S,消除上述文法的左递归，重写该文法。,求消除左递归后的文法的非终结符构造,First,集合和,Follow,集合。,为消除左递归后的文法构造,LL(1),分析表。,并写出对句子 (,bc,),的,LL(1),分析过程。,作业,110,