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

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