+语法分析(一)PPT演示课件

.西北工业大学软件与微电子学院 machunyan,1,2018/6/12,西北工业大学软件与微电子学院 machunyan,1,课程内容第1章 概论第2章 词法分析第3章上下文无关文法第4章语法分析第5章语义分析第6章运行时环境第7章代码生成,.西北工业大学软件与微电子学院 machunyan,2,machunyan,西北工业大学软件与微电子学院,2,语法分析程序的任务：语法分析以词法分析程序输出的单词序列为输入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序。语法分析阶段可以确定单词流中违反源语言语法结构规则的错误。通常语法分析的结果是构造出表示该语法结构的分析树（parse tree）或语法树(syntax tree)。,第四章 自上而下的语法分析,.西北工业大学软件与微电子学院 machunyan,3,machunyan,西北工业大学软件与微电子学院,3,4.1 自上而下的语法分析算法概述4.2 递归下降分析（Recursive-Descent Top-Down Parsing）4.3 LL(1)分析4.4 自上而下的语法分析器自动生成工具JavaCC4.5 项目：编译器实现（语法分析模块）,第四章 自上而下的语法分析,.西北工业大学软件与微电子学院 machunyan,4,machunyan,西北工业大学软件与微电子学院,4,自上而下的语法分析算法：已知文法GS，对任意输入串w，若从文法的开始符号S出发, 能为w构造一个最左推导，则w是一个合法的句子，即w L(G)，否则w有语法错误。该算法自上而下为w的分析结果建立一棵语法树。,4.1自上而下的语法分析算法概述,.西北工业大学软件与微电子学院 machunyan,5,machunyan,西北工业大学软件与微电子学院,5,例4.1：文法G：S aAS cAdA aA ab识别输入串w=cabd是否为该文法所定义的句子？,运用自上而下的语法分析方法：,4.1自上而下的语法分析算法概述(续),.西北工业大学软件与微电子学院 machunyan,6,machunyan,西北工业大学软件与微电子学院,6,cAd cabd,cAd cad,从文法开始符号S出发试图为w=cabd构造一个最左推导:,S cAd cabd,成功,.西北工业大学软件与微电子学院 machunyan,7,machunyan,西北工业大学软件与微电子学院,7,4.1自上而下的语法分析算法概述(续),自上而下的语法分析方法：从文法开始符号S出发试图为输入符号串构造一个最左推导；构造最左推导的过程就是选择产生式和匹配符号串的过程；有时需要重复扫描词法分析输出的单词序列。,.西北工业大学软件与微电子学院 machunyan,8,machunyan,西北工业大学软件与微电子学院,8,4.1 自上而下的语法分析算法概述4.2 递归下降分析（Recursive-Descent Top-Down Parsing）4.3 LL(1)分析4.4 自上而下的语法分析器自动生成工具JavaCC4.5 项目：编译器实现（语法分析模块）,第四章 自上而下的语法分析,.西北工业大学软件与微电子学院 machunyan,9,machunyan,西北工业大学软件与微电子学院,9,4.2 递归下降语法分析,4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析,.西北工业大学软件与微电子学院 machunyan,10,machunyan,西北工业大学软件与微电子学院,10,例4.2：文法G：S cAd A ab,识别输入串w=cabd是否为该文法定义的句子？,4.2.1 递归下降分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,11,machunyan,西北工业大学软件与微电子学院,11,void match(TokenType tokenExpected) if (currentToken.tokentype = tokenExpected) currentToken = scanner.getToken(); else error: tokenExpected expectedbut currentToken found,4.2.1 递归下降分析的基本方法(续),match函数：全局变量currentToken存储即将扫描的下一个单词,.西北工业大学软件与微电子学院 machunyan,12,machunyan,西北工业大学软件与微电子学院,12,void S(void) match(c); A(); match(d);,void A(void) match(a); match(b); ,4.2.1 递归下降分析的基本方法(续),识别S的递归下降函数的伪代码：,.西北工业大学软件与微电子学院 machunyan,13,machunyan,西北工业大学软件与微电子学院,13,递归下降分析方法是一种自上而下的语法分析方法，该方法执行一组递归函数判断输入的单词序列是否符合语法规则。递归函数如何写？为每个产生式规则撰写一个函数，以产生式左部的非终结符作为函数的名子，根据产生式规则的右部撰写函数体。遇到终结符，匹配并读取下一个单词；遇到非终结符，调用该非终结符所在产生式对应的函数；,4.2.1 递归下降分析的基本方法,.西北工业大学软件与微电子学院 machunyan,14,machunyan,西北工业大学软件与微电子学院,14,例4.3：文法G：S cAd A a A ab,识别输入串w=cabd是否为该文法定义的句子？,4.2.1 递归下降分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,15,machunyan,西北工业大学软件与微电子学院,15,识别S的递归下降函数的伪代码：,void S(void) match(c); A1(); match(d); if(调用A1()失败) A2(); match(d); ,void A1(void) match(a); void A2(void) match(a); match(b); ,/记住当前的token位置,.西北工业大学软件与微电子学院 machunyan,16,machunyan,西北工业大学软件与微电子学院,16,如果语法分析方法使用递归下降分析程序,为了避免重复扫描词法分析输出的单词序列(提高效率)，需要先将文法G采用EBNF表示法，然后写出递归下降分析程序。,4.2.1 递归下降分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,17,machunyan,西北工业大学软件与微电子学院,17,4.2 递归下降语法分析,4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法 4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析,.西北工业大学软件与微电子学院 machunyan,18,machunyan,西北工业大学软件与微电子学院,18,1.选择的情况EBNF使用 表示选择： 文法G： S cAd A a A ab,文法G的EBNF表示法如下：,S cAdA ab,4.2.2 文法规则使用EBNF表示法,.西北工业大学软件与微电子学院 machunyan,19,machunyan,西北工业大学软件与微电子学院,19,识别S的递归下降函数的伪代码： ScAd A ab,void S(void) match(c); A(); match(d);,void A(void) match(a); if token=b then match(b);,避免了重复扫描词法分析输出的单词序列,1.选择的情况(续),.西北工业大学软件与微电子学院 machunyan,20,machunyan,西北工业大学软件与微电子学院,20,例4.4：一个简化了的if语句的文法规则：if-stmtif (exp) statement |if (exp) statement else statement,写出识别if-stmt的递归下降函数的伪代码,1.选择的情况(续),首先给出if文法规则的EBNF表示法：if-stmtif(exp)statementelse statement,.西北工业大学软件与微电子学院 machunyan,21,machunyan,西北工业大学软件与微电子学院,21,viod ifStmt(void) match(if); match(); exp(); match(); statement(); if token = else then match(else); statement(); ,1.选择的情况(续),if-stmt if(exp)statementelse statement,.西北工业大学软件与微电子学院 machunyan,22,machunyan,西北工业大学软件与微电子学院,22,简单整型算术表达式文法：expexp addop term|termaddop+|-termterm mulop factor|factormulop*factor(exp)|number,写出识别表达式exp的递归下降函数的伪代码,4.2.2 文法规则使用EBNF表示法,.西北工业大学软件与微电子学院 machunyan,23,machunyan,西北工业大学软件与微电子学院,23,现在考虑简单算术表达式文法中exp对应的递归下降函数： expexp addop term|term,存在无限递归循环的问题；由于从exp和term出发都可以首先推导出终结符number或（，所以存在选用 产生式expexp addop term还是产生式expterm进行推导的问题；,重复情况,.西北工业大学软件与微电子学院 machunyan,24,machunyan,西北工业大学软件与微电子学院,24,解决问题的办法是使用EBNF规则：,EBNF使用 表示重复： A,重复的一般规则：AA|(左递归), 表示其中的内容重复n次(n=0)写递归下降语法分析程序时可将花括号表示的重复部分翻译成循环代码；,重复情况（续）：,AA|(右递归),A,.西北工业大学软件与微电子学院 machunyan,25,machunyan,西北工业大学软件与微电子学院,25,将花括号表示的重复部分addop term翻译成循环代码， 语法结构exp对应的函数定义如下：,上述产生式规则expexp addop term|term用EBNF表示成,重复情况（续）：,exp termaddop term,.西北工业大学软件与微电子学院 machunyan,26,machunyan,西北工业大学软件与微电子学院,26,viod exp(void) term( ); while token=+ or token=- match(token); term( ); ,重复情况（续）：,exp termaddop term,.西北工业大学软件与微电子学院 machunyan,27,machunyan,西北工业大学软件与微电子学院,27,简单整型算术表达式文法：expexp addop term|termaddop+|-termterm mulop factor|factormulop*factor(exp)|number,写出识别表达式exp的完整的递归下降函数的伪代码？,重复情况（续）：,.西北工业大学软件与微电子学院 machunyan,28,machunyan,西北工业大学软件与微电子学院,28,4.2递归下降语法分析,4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法 4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析,.西北工业大学软件与微电子学院 machunyan,29,machunyan,西北工业大学软件与微电子学院,29,4.2.3 其它应注意的问题,递归下降分析方法简单、功能强大，但它仍有特殊性。若使用的是一个设计精巧的小型语言（例如TINY），那么对于构造一个完整的语法分析程序，递归下降分析是适合的，但可能会出现一些问题（例如，下页的1），2）两点）。,.西北工业大学软件与微电子学院 machunyan,30,machunyan,西北工业大学软件与微电子学院,30,间接递归的文法(会导致死循环，要将文法进行相应处理): 例如：文法GS:SAb|c ASa，试写出它的递归下降分析程序。避免分析程序死循环的解决办法：可将间接递归的文法进行等价改造为SSab|c，进而改造为：S cab,4.2.3 其它应注意的问题(续),.西北工业大学软件与微电子学院 machunyan,31,machunyan,西北工业大学软件与微电子学院,31,4.2.3 其它应注意的问题(续),对于两个或多个文法规则的选项A| ， 如果和均以非终结符开始，那么就很难决定何时使用A选项，何时又使用A选项，这样撰写的递归下降分析程序就存在回溯。解决办法：计算和的First集合（LL(1)分析方法给出定义和求解方法）。,.西北工业大学软件与微电子学院 machunyan,32,2018/6/12,西北工业大学软件与微电子学院 machunyan,32,4.2.3 其它应注意的问题(续),.西北工业大学软件与微电子学院 machunyan,33,GS写出上述文法的递归下降语法分析程序,2018/6/12,西北工业大学软件与微电子学院 machunyan,33,4.2.3 其它应注意的问题(续),.西北工业大学软件与微电子学院 machunyan,34,machunyan,西北工业大学软件与微电子学院,34,在递归下降分析程序中，应该增加代码以实现保存语法分析结果的功能：（1）构造相应的语法树节点（2）保持运算的结合性（3）计算表达式值（4）,4.2.3 其它应注意的问题(续),.西北工业大学软件与微电子学院 machunyan,35,machunyan,西北工业大学软件与微电子学院,35,4.2递归下降语法分析,4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法 4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析,.西北工业大学软件与微电子学院 machunyan,36,2018/6/12,西北工业大学软件与微电子学院 machunyan,36,简单整型算术表达式文法：exp exp op exp|(exp)|numberop +|-|*,简单算术表达式对应的抽象语法树结构,4.2.4 分析树 与抽象语法树,.西北工业大学软件与微电子学院 machunyan,37,2018/6/12,西北工业大学软件与微电子学院 machunyan,37,分析树对于显示程序的各语法单位或程序的单词序列很有帮助，但是相比纯粹为编译生成可执行代码所需的信息而言，分析树却包括了冗余的信息。所以语法分析程序更趋向于生成抽象语法树，抽象语法树是分析树中所含信息的浓缩，包含了进一步分析所需的所有信息，比分析树效率高。例如：见下页,4.2.4 分析树 与抽象语法树(续),.西北工业大学软件与微电子学院 machunyan,38,2018/6/12,西北工业大学软件与微电子学院 machunyan,38,exp exp op expexp (exp)| Numberop +|-|*,抽象语法树结构,分析树结构,4.2.4 分析树 与抽象语法树(续),.西北工业大学软件与微电子学院 machunyan,39,2018/6/12,西北工业大学软件与微电子学院 machunyan,39,3+4的抽象语法树,（34-3）+42 的抽象语法树,4.2.4 分析树 与抽象语法树(续),.西北工业大学软件与微电子学院 machunyan,40,抽象语法树设计各语法单位对应的抽象语法树的结构可以规定，没有标准，但可以参考现有编译器的做法。例如：工具：Pyc parser，可以打印C语言程序的抽象语法树,2018/6/12,西北工业大学软件与微电子学院 machunyan,40,4.2.4 分析树 与抽象语法树(续),.西北工业大学软件与微电子学院 machunyan,41,设计抽象语法树（续）画出产生式规则的语法分析树在保证语义信息不丢失的情况下，除掉语法分析树的冗余节点形成抽象语法树；,2018/6/12,西北工业大学软件与微电子学院 machunyan,41,4.2.4 分析树 与抽象语法树(续),.西北工业大学软件与微电子学院 machunyan,42,machunyan,西北工业大学软件与微电子学院,42,EBNF文法表示的tiny语言的语法.doc,用递归下降分析算法写出TINY语言的语法分析程序？,4.2.5 案例：Tiny语法分析,.西北工业大学软件与微电子学院 machunyan,43,machunyan,西北工业大学软件与微电子学院,43,语法分析的基本步骤,对程序设计语言的语法规则进行形式化描述（用2型文法）；根据语言的语法描述形式，定义各种基本语法结构的抽象语法树；选择一种合适的语法分析算法，并在分析程序中插入动作() -语法分析程序。,.西北工业大学软件与微电子学院 machunyan,44,machunyan,西北工业大学软件与微电子学院,44,语句序列stmt-sequence statement;statement,TINY语言的各基本语法范畴的抽象语法树结构形式如下：,每个语句对应子树的右兄弟指向下一个语句对应的子树,.西北工业大学软件与微电子学院 machunyan,45,machunyan,西北工业大学软件与微电子学院,45,if-stmt if exp then stmt-sequenceelse stmt-sequenceend,if语句的抽象语法树结构：,.西北工业大学软件与微电子学院 machunyan,46,machunyan,西北工业大学软件与微电子学院,46,repeat 语句repeat-stmtrepeat stmt-sequence until exp,.西北工业大学软件与微电子学院 machunyan,47,machunyan,西北工业大学软件与微电子学院,47,assign 语句assign_stmtidentifier := exp,.西北工业大学软件与微电子学院 machunyan,48,machunyan,西北工业大学软件与微电子学院,48,write语句 write_stmt write exp,read语句 read_stmtread identifier,.西北工业大学软件与微电子学院 machunyan,49,machunyan,西北工业大学软件与微电子学院,49,算符表达式,.西北工业大学软件与微电子学院 machunyan,50,machunyan,西北工业大学软件与微电子学院,50,typedef enumStmtK, ExpKNodeKind;,typedef enumIfK, RepeatK, AssignK, ReadK, WriteKStmtKind;,typedef enumOpK, ConstK, IdKExpKind;,typedef enumVoid, Integer, BooleanExpType;,#define MAXCHILDREN 3,抽象语法树的定义,.西北工业大学软件与微电子学院 machunyan,51,machunyan,西北工业大学软件与微电子学院,51,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;,抽象语法树的定义(续),.西北工业大学软件与微电子学院 machunyan,52,machunyan,西北工业大学软件与微电子学院,52,statementif-stmt|repeat-stmt|assign-stmt| read-stmt|write-stmt,Tiny语法分析程序：PARSE.C,.西北工业大学软件与微电子学院 machunyan,53,machunyan,西北工业大学软件与微电子学院,53,Tiny语法分析程序：PARSE.C,if-stmtif exp then stmt-sequence else stmt-squence end,.西北工业大学软件与微电子学院 machunyan,54,machunyan,西北工业大学软件与微电子学院,54,Tiny语法分析程序：PARSE.C,产生式：repeat-stmt-repeat stmt-sequence until exp,.西北工业大学软件与微电子学院 machunyan,55,machunyan,西北工业大学软件与微电子学院,55,一个输出其输入阶乘的TINY语言程序read x;if x0 then fact:=1; repeat fact:=fact* x; x:=x-1 until x=0; write fact end,4.2.4 案例：Tiny语法分析(续),.西北工业大学软件与微电子学院 machunyan,56,machunyan,西北工业大学软件与微电子学院,56,Read(x),IF,op(),id(x),Assign(fact),const(0),const(1),repeat,write,4.2.4 案例：Tiny语法分析(续),PARSE.C,.西北工业大学软件与微电子学院 machunyan,57,machunyan,西北工业大学软件与微电子学院,57,4.1 自上而下的语法分析算法概述4.2 递归下降分析4.3 LL(1)分析4.4 自上而下的语法分析器自动生成工具JavaCC4.5 项目：编译器实现（语法分析模块）,第四章 自上而下的语法分析,.西北工业大学软件与微电子学院 machunyan,58,machunyan,西北工业大学软件与微电子学院,58,4.3 LL( 1 )分析,4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析与算法 4.3.3 消除左递归和提取左因子,.西北工业大学软件与微电子学院 machunyan,59,machunyan,西北工业大学软件与微电子学院,59,4.3.1 LL(1)分析的基本方法,LL (1)分析方法是一种自上而下的语法分析方法：第1个“L”指的是由左向右地处理输入；第2个“L”指的是它为输入串找出一个最左推导；括号中的数字1意味着它使用输入单词序列中的一个单词预测分析的动作。,.西北工业大学软件与微电子学院 machunyan,60,machunyan,西北工业大学软件与微电子学院,60,例如：假设有简单文法：S(S)S|a 判断输入串(a)a是否是符合该文法规则的句子？,4.3.1 LL(1)分析的基本方法(续),S(S)S (a)S (a)a,(a)a的最左推导,.西北工业大学软件与微电子学院 machunyan,61,machunyan,西北工业大学软件与微电子学院,61,4.3.1 LL(1)分析的基本方法(续),针对每一步推导，构造最左推导的语法分析程序要解决的问题：定位当前句型进行下一步推导的非终结符：每一步推导是针对当前句型中最左一个非终结符进行推导；选择产生式：用该非终结符对应的哪一个产生式进行推导最有可能成功？符号串的替换：用选择产生式的左部替换右部。,.西北工业大学软件与微电子学院 machunyan,62,machunyan,西北工业大学软件与微电子学院,62,LL (1)分析方法如下：通过栈来“记忆”针对当前句型中的哪一个非终结符进行推导，首先将文法的开始符号S入栈；如果栈的顶部是非终结符A,则利用A对应的某个文法规则A将栈顶部的非终结符A(出栈)替换成串(将串自左至右还是自右至左入栈？)。如果栈的顶部是终结符a,则将其与当前输入单词匹配(出栈)。,4.3.1 LL(1)分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,63,machunyan,西北工业大学软件与微电子学院,63,构造一个非终结符和终结符索引的二维表格MN，T，通过表格指出用哪一个产生式进行进行下一步推导，其中N是非终结符的集合，T是终结符的集合。即构造一个LL(1)分析表，通过该表格引导用哪一个产生式进行推导。 例如：,4.3.1 LL(1)分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,64,machunyan,西北工业大学软件与微电子学院,64,MN,T,S,(,),$,S (S)S,S a,文法S(S)S|a的LL(1)分析表,4.3.1 LL(1)分析的基本方法(续),MS,(表示当前分析栈的栈顶符号为S，而当前词法分析的输入单词为(时，按产生式S(S)S进行推导；MS,a表示当前分析栈的栈顶符号为S，而当前词法分析的输入单词为a时，按产生式Sa进行推导。,a,.西北工业大学软件与微电子学院 machunyan,65,machunyan,西北工业大学软件与微电子学院,65,步骤,分析栈,输入,动作,S （S）S,匹配,S a,匹配,S a,匹配,引入$作为输入符号串的限界符；句型自右至左入栈,LL (1)分析方法示例,匹配,接受,.西北工业大学软件与微电子学院 machunyan,66,machunyan,西北工业大学软件与微电子学院,66,LL(1)分析程序通过将分析栈顶部的非终结符替换成文法规则中该非终结符的一个选择来做出分析。在分析过程中有两个基本动作：,如果栈的顶部是终结符a,则将其与当前输入单词匹配。如果不能匹配，出现什么情况？如果栈的顶部是非终结符A,则利用文法规则A将栈顶部的非终结符A替换成串(保证自右至左入栈)。,4.3.1 LL(1)分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,67,machunyan,西北工业大学软件与微电子学院,67,问题：如何构造LL(1)分析表？,构造分析表的步骤：求First集合求Follow集合构造LL(1)分析表,4.3.1 LL(1)分析的基本方法(续),.西北工业大学软件与微电子学院 machunyan,68,2018/6/12,西北工业大学软件与微电子学院 machunyan,68,1)求First集合,.西北工业大学软件与微电子学院 machunyan,69,machunyan,西北工业大学软件与微电子学院,69,若X是终结符或，则First(X) =,X,1)求First集合（续）,文法符号X的First(X)集合：若X可推导出以终结符a为首的字符串，则a在First(X)中； 令X为一个文法符号（一个终结符或非终结符）或，则First(X)是终结符的集合，此外可能还有，它的定义如下：,.西北工业大学软件与微电子学院 machunyan,70,machunyan,西北工业大学软件与微电子学院,70,若X是非终结符，则对于X对应的每个产生式XX1X2.Xn ，First(X)包括 First(X1)-。若对于某个i TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,先求其First( )集包含的非终结符：,例：考虑下述文法，求各非终结符的First()集合；,文法G E:,E,T,.西北工业大学软件与微电子学院 machunyan,74,machunyan,西北工业大学软件与微电子学院,74,First(E),First(E),First(T),从文法的开始符号E,将求First()集的算法过程表示成下列图示；,.西北工业大学软件与微电子学院 machunyan,75,machunyan,西北工业大学软件与微电子学院,75,求得上述文法各非终结符的First集合如下：First(E)=(,aFirst(E)=+,First(T)=(,aFirst(T)=*,First(F)=(,a,.西北工业大学软件与微电子学院 machunyan,76,machunyan,西北工业大学软件与微电子学院,76,文法符号串的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)也包括。,1)求First集合(续),.西北工业大学软件与微电子学院 machunyan,77,machunyan,西北工业大学软件与微电子学院,77,Follow集合的定义：给出一个非终结符A，集合Follow(A)是由终结符组成，此外可能还有$。集合Follow(A)的定义如下：,2)求Follow集合,1. 若A是开始符号,则Follow(A)包含$2. 若存在产生式BA,则Follow(A)包含 First()-3. 若存在产生式BA，且在First()中，则 Follow(A)包含Follow(B)注：求解Follow(A) ，考虑A出现在哪些产生式右部。Follow 集仅针对非终结符，并且不包含,.西北工业大学软件与微电子学院 machunyan,78,machunyan,西北工业大学软件与微电子学院,78,例如：aFollow(B)若有句型Ba出现，由于BA，且在First()中，所以有：Ba Aa * A a = AaaFollow(A),2)求Follow集合（续）,.西北工业大学软件与微电子学院 machunyan,79,machunyan,西北工业大学软件与微电子学院,79,例：考虑下述简单整型表达式文法，求各非终结符的Follow()集合；,expexp addop term (2) expterm(3) addop+ (4) addop-(5) termterm mulop factor(6) term factor(7) mulop* (8) factor(exp)(9) factornumber,.西北工业大学软件与微电子学院 machunyan,80,machunyan,西北工业大学软件与微电子学院,80,Follow(exp)=,Follow(addop)=,Follow(term)=,Follow(mulop)=,Follow(factor)=,$,+,-,),(,number,$,+,-,*,),(,number,$,+,-,*,),2)求Follow集合(续),.西北工业大学软件与微电子学院 machunyan,81,machunyan,西北工业大学软件与微电子学院,81,例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:,.西北工业大学软件与微电子学院 machunyan,82,machunyan,西北工业大学软件与微电子学院,82,从文法的开始符号E,将求Follow()集的算法过程表示成下列图示；,.西北工业大学软件与微电子学院 machunyan,83,machunyan,西北工业大学软件与微电子学院,83,.西北工业大学软件与微电子学院 machunyan,84,machunyan,西北工业大学软件与微电子学院,84,各非终结符的Follow集合如下：,Follow(E)=) , $,Follow(E)=), $,Follow(T)=+, ), $,Follow(T)=+, ), $ ,Follow(F)=*, +, ), $,.西北工业大学软件与微电子学院 machunyan,85,machunyan,西北工业大学软件与微电子学院,85,构造LL(1)分析表,对于First()中的每个终结符a，都将A添加到MA,a元素位置，置MA,a =“A”。即当当前分析栈的栈顶符号为A时，而当前词法分析的输入单词为a时，按产生式A进行推导；,LL(1)分析表的构造方法：,分析表以非终结符作为行索引，以终结符作为列索引，分析表的元素位置存储产生式，为每个非终结符A和它对应的产生式A重复以下两步骤：,.西北工业大学软件与微电子学院 machunyan,86,machunyan,西北工业大学软件与微电子学院,86,定义：如果文法G相关的LL(1)分析表的每个项目中至多只有一个产生式，则该文法就是LL(1)文法。,3)所有没有定义的元素位置A,a标上“出错”标志。,若在First()中，则对于Follow(A)的每个元素a(或是$)，都将A添加到 MA,a中。即在此情况下按产生式A进行推导。,LL(1)分析表的构造方法(续)：,例如：bAa. b a * b a ba,.西北工业大学软件与微电子学院 machunyan,87,machunyan,西北工业大学软件与微电子学院,87,例：考虑简化了的C变量声明的文法：declarationtype var-listtypeint|floatvar-listidentifier listlist ,var-list| 求该文法各非终结符的First()集合和Follow()集合。构造该文法的LL(1)分析表。说明该文法是LL(1)文法。假设有输入串 int x,y,z 写出相对应的LL(1)分析程序的动作。,.西北工业大学软件与微电子学院 machunyan,88,machunyan,西北工业大学软件与微电子学院,88,First(declaration)=int,float,First(type) =int,float,First(var-list) =identifier,First(list) =, ,所求得的各非终结符的First集合和Follow集合如下：,.西北工业大学软件与微电子学院 machunyan,89,machunyan,西北工业大学软件与微电子学院,89,Follow(declaration)=$,Follow(type)=identifier,Follow(var-list)=$,Follow(list) =$,.西北工业大学软件与微电子学院 machunyan,90,machunyan,西北工业大学软件与微电子学院,90,r1: declarationtype var-listr2: typeintr3: type floatr4: var-listidentifier listr5: list ,var-listr6: list ,对各产生式进行编号：,构造该文法的LL(1)分析表。,.西北工业大学软件与微电子学院 machunyan,91,machunyan,西北工业大学软件与微电子学院,91,MN,T,declaration,int,identifier,$,type,var-list,list,float,r1,r1,r2,r3,r4,r5,由于文法G相关的LL(1)分析表的每个项目中至多只有一个产生式，故该文法是LL(1)文法。,.西北工业大学软件与微电子学院 machunyan,92,machunyan,西北工业大学软件与微电子学院,92,输入串 int x 相对应的LL(1)分析程序的分析过程如下表所示：,.西北工业大学软件与微电子学院 machunyan,93,machunyan,西北工业大学软件与微电子学院,93,补充产生式案例分析,.西北工业大学软件与微电子学院 machunyan,94,machunyan,西北工业大学软件与微电子学院,94,MN,T,declaration,int,identifier,$,type,var-list,list,float,r1,r1,r2,r3,r4,r5,r6,由于文法G相关的LL(1)分析表的每个项目中至多只有一个产生式，故该文法是LL(1)文法。,.西北工业大学软件与微电子学院 machunyan,95,machunyan,西北工业大学软件与微电子学院,95,输入串 int x,y,z 相对应的LL(1)分析程序的分析过程如下表所示：,.西北工业大学软件与微电子学院 machunyan,96,machunyan,西北工业大学软件与微电子学院,96,.西北工业大学软件与微电子学院 machunyan,97,machunyan,西北工业大学软件与微电子学院,97,4.3 LL( 1 )分析,4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析与算法 4.3.3 消除左递归和提取左因子,.西北工业大学软件与微电子学院 machunyan,98,machunyan,西北工业大学软件与微电子学院,98,.西北工业大学软件与微电子学院 machunyan,99,machunyan,西北工业大学软件与微电子学院,99,4.3.2 LL(1)分析与算法,基于表的LL(1)分析算法流程：LL(1)分析表的构造是LL(1)分析算法的关键技术。,.西北工业大学软件与微电子学院 machunyan,100,machunyan,西北工业大学软件与微电子学院,100,4.3 LL( 1 )分析,4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析与算法 4.3.3 消除左递归和提取左因子,.西北工业大学软件与微电子学院 machunyan,101,machunyan,西北工业大学软件与微电子学院,101,简单直接左递归文法是否是LL(1)文法？例如：AAaAb若文法G有产生式Uxy |xw | xz则该文法是否是LL(1)文法？,4.3.3 消除左递归和提取左因子,.西北工业大学软件与微电子学院 machunyan,102,machunyan,西北工业大学软件与微电子学院,102,4.3.3 消除左递归和提取左因子(续),由于含有左递归和左公共因子的文法不是LL(1)文法，如果要使用LL(1)语法分析算法对该文法定义的语言进行语法分析，那么必须通过消除左递归和提取左公共因子，将文法进行等价改造。,.西北工业大学软件与微电子学院 machunyan,103,machunyan,西北工业大学软件与微电子学院,10