第四章 语法分析(一)

1、2022-5-7西北工业大学软件与微电子学院 machunyan1o 课程内容课程内容 第第1 1章章 概论概论 第第2 2章章 词法分析词法分析 第第3 3章上下文无关文法章上下文无关文法 第第4 4章语法分析章语法分析n 第第5 5章语义分析章语义分析n 第第6 6章运行时环境章运行时环境n 第第7 7章代码生成章代码生成machunyan西北工业大学软件与微电子学院2o 语法分析程序的任务语法分析程序的任务：n 语法分析以词法分析程序输出的单词序列为输入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序。o语法分析阶段可以确定单词流中违反源语言语法结构规则的错误。n 通常语法

2、分析的结果是构造出表示该语法结构的分析树（parse tree）或语法树(syntax tree)。第四章第四章 自上而下的语法分析自上而下的语法分析machunyan西北工业大学软件与微电子学院3 4.1 4.1 自上而下的语法分析算法概述自上而下的语法分析算法概述 4.2 4.2 递归下降分析（递归下降分析（Recursive-Descent Recursive-Descent Top-Down ParsingTop-Down Parsing） 4.3 4.3 LL(1)LL(1)分析分析 4.4 4.4 自上而下的语法分析器自动生成工具自上而下的语法分析器自动生成工具JavaCCJava

3、CC 4.5 4.5 项目：编译器实现（语法分析模块）项目：编译器实现（语法分析模块）第四章第四章 自上而下的语法分析自上而下的语法分析machunyan西北工业大学软件与微电子学院4o 自上而下的语法分析算法自上而下的语法分析算法：n 已知文法GS，对任意输入串w，若从文法的开始符号S出发, 能为w构造一个最左推导，则w是一个合法的句子，即w L(G)，否则w有语法错误。n 该算法自上而下为w的分析结果建立一棵语法树。4.1自上而下的语法分析算法概述自上而下的语法分析算法概述machunyan西北工业大学软件与微电子学院5例4.1：文法G：S aAS cAdA aA ab识别输入串w=cab

4、d是否为该文法所定义的句子？运用自上而下的语法分析方法：4.1自上而下的语法分析算法概述自上而下的语法分析算法概述(续续)machunyan西北工业大学软件与微电子学院6cAd cabdcAd cadS cAd从文法开始符号S出发试图为w=cabd构造一个最左推导:S cAd cabdcSdAba成功machunyan西北工业大学软件与微电子学院74.1自上而下的语法分析算法概述自上而下的语法分析算法概述(续续)o 自上而下的语法分析方法：自上而下的语法分析方法：n 从文法开始符号S出发试图为输入符号串构造一个最左推导；n 构造最左推导的过程就是选择产生式和匹配符号串的过程；n 有时需要重复扫

5、描词法分析输出的单词序列。machunyan西北工业大学软件与微电子学院8 4.1 4.1 自上而下的语法分析算法概述自上而下的语法分析算法概述 4.2 4.2 递归下降分析（递归下降分析（Recursive-Recursive-Descent Top-Down ParsingDescent Top-Down Parsing） 4.3 4.3 LL(1)LL(1)分析分析 4.4 4.4 自上而下的语法分析器自动生成自上而下的语法分析器自动生成工具工具JavaCCJavaCC 4.5 4.5 项目：编译器实现（语法分析模项目：编译器实现（语法分析模块）块）第四章第四章 自上而下的语法分析自上而

6、下的语法分析machunyan西北工业大学软件与微电子学院94.2 递归下降语法分析 4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析machunyan西北工业大学软件与微电子学院10例4.2：文法G：S cAd A ab识别输入串w=cabd是否为该文法定义的句子？4.2.1 递归下降分析的基本方法(续)machunyan西北工业大学软件与微电子学院11void match(TokenType tokenExpected) if (currentToken.tokenty

7、pe = tokenExpected) currentToken = scanner.getToken(); else error: tokenExpected expectedbut currentToken found4.2.1 递归下降分析的基本方法(续)match函数：全局变量currentToken存储即将扫描的下一个单词machunyan西北工业大学软件与微电子学院12void S(void) match(c); A(); match(d);void A(void) match(a); match(b); 4.2.1 递归下降分析的基本方法(续)识别S的递归下降函数的伪代码：mac

8、hunyan西北工业大学软件与微电子学院13 递归下降分析方法是一种自上而下的语法分析方法，该方法执行一组递归函数判断输入的单词序列是否符合语法规则。 递归函数如何写？ 为每个产生式规则撰写一个函数，以产生式左部的非终结符作为函数的名子，根据产生式规则的右部撰写函数体。 遇到终结符，匹配并读取下一个单词； 遇到非终结符，调用该非终结符所在产生式对应的函数；4. 4.2.1 2.1 递归下降分析的基本方法递归下降分析的基本方法machunyan西北工业大学软件与微电子学院14例4.3：文法G：S cAd A a A ab识别输入串w=cabd是否为该文法定义的句子？4.2.1 递归下降分析的基本

9、方法(续)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西北工业大学软件与微电子学院16o 如果语法分析方法使用递归下降分析程序,为了避免重复扫描词法分析输出的单词序列(提高效率)，需要先将文法G采用EBNF表示法，然后写出递归下降分析程序。4.2.1 递归下降分析的基

10、本方法(续)machunyan西北工业大学软件与微电子学院174.2 递归下降语法分析 4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法 4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析machunyan西北工业大学软件与微电子学院181.选择的情况选择的情况EBNF使用使用 表示选择表示选择： 文法文法G： S cAd A a A ab文法G的EBNF表示法如下：S cAdA ab4.2.2 文法规则使用文法规则使用EBNF表示法表示法machunyan西北工业大学软件与微电子学院19 识别S的递归下降函数的伪代码：

11、ScAd A abvoid S(void) match(c); A(); match(d);void A(void) match(a); if token=b then match(b);避免了重复扫描词法分析输出的单词序列1.选择的情况(续)machunyan西北工业大学软件与微电子学院20例4.4：一个简化了的if语句的文法规则：if-stmtif (exp) statement |if (exp) statement else statement写出识别if-stmt的递归下降函数的伪代码1.选择的情况(续)p首先给出if文法规则的EBNF表示法：pif-stmtif(exp)state

12、mentelse statementmachunyan西北工业大学软件与微电子学院21viod ifStmt(void) match(if); match(); exp(); match(); statement(); if token = else then match(else); statement(); 1.选择的情况(续)nif-stmt if(exp)statementelse statementmachunyan西北工业大学软件与微电子学院22简单整型算术表达式文法：expexp addop term|termaddop+|-termterm mulop factor|facto

13、rmulop*factor(exp)|number写出识别表达式exp的递归下降函数的伪代码4.2.2 文法规则使用文法规则使用EBNF表示法表示法machunyan西北工业大学软件与微电子学院23现在考虑简单算术表达式文法中exp对应的递归下降函数： expexp addop term|termo 存在无限递归循环的问题；存在无限递归循环的问题；o 由于从由于从exp和和term出发都可以首先推导出终出发都可以首先推导出终结符结符number或或（，所以存在选用，所以存在选用 产生式产生式expexp addop term还是还是产生式产生式expterm进进行推导的问题；行推导的问题； 重

14、复情况machunyan西北工业大学软件与微电子学院24解决问题的办法是使用EBNF规则：EBNF使用 表示重复： A 重复的一般规则：AA|(左递归) 表示其中的内容重复n次(n=0)写递归下降语法分析程序时可将花括号表示的重复部分翻译成循环代码；重复情况（续）：AA|(右递归)Amachunyan西北工业大学软件与微电子学院25将花括号表示的重复部分addop term翻译成循环代码， 语法结构exp对应的函数定义如下：上述产生式规则expexp addop term|term用EBNF表示成重复情况（续）：exp termaddop termmachunyan西北工业大学软件与微电子学院

15、26viod exp(void) term( ); while token=+ or token=- match(token); term( ); 重复情况（续）：exp termaddop termmachunyan西北工业大学软件与微电子学院27简单整型算术表达式文法：expexp addop term|termaddop+|-termterm mulop factor|factormulop*factor(exp)|number写出识别表达式exp的完整的递归下降函数的伪代码？重复情况（续）：machunyan西北工业大学软件与微电子学院284.2递归下降语法分析 4.2.1 递归下降分

16、析的基本方法 4.2.2 文法规则使用EBNF表示法 4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析machunyan西北工业大学软件与微电子学院294.2.3 其它应注意的问题o 递归下降分析方法简单、功能强大，但它仍递归下降分析方法简单、功能强大，但它仍有特殊性。若使用的是一个设计精巧的小型有特殊性。若使用的是一个设计精巧的小型语言（例如语言（例如TINY），），那么对于构造一个完那么对于构造一个完整的语法分析程序，递归下降分析是适合的，整的语法分析程序，递归下降分析是适合的，但可能会出现一些问题（例如，下页的但可能会出现一些问题（例如，下

17、页的1），），2）两点）。）两点）。machunyan西北工业大学软件与微电子学院30间接递归的文法(会导致死循环，要将文法进行相应处理): n例如：文法GS:SAb|c ASa，试写出它的递归下降分析程序。n避免分析程序死循环的解决办法：n可将间接递归的文法进行等价改造为SSab|c，进而改造为：S cab4.2.3 其它应注意的问题(续)machunyan西北工业大学软件与微电子学院314.2.3 其它应注意的问题其它应注意的问题(续续)o对于两个或多个文法规则的选项对于两个或多个文法规则的选项A| ， 如果如果和和均以非终结符开始，那么就很难决均以非终结符开始，那么就很难决定何时使用定何

18、时使用A选项，何时又使用选项，何时又使用A选选项，这样撰写的递归下降分析程序就存在回项，这样撰写的递归下降分析程序就存在回溯。溯。p解决办法：计算和的First集合（LL(1)分析方法给出定义和求解方法）。2022-5-7西北工业大学软件与微电子学院 machunyan324.2.3 其它应注意的问题其它应注意的问题(续续)o GSo 写出上述文法的递归下降语法分析程序写出上述文法的递归下降语法分析程序2022-5-7西北工业大学软件与微电子学院 machunyan334.2.3 其它应注意的问题其它应注意的问题(续续)machunyan西北工业大学软件与微电子学院34在递归下降分析程序中，应

19、该增加代码以实现保存语法分析结果的功能：p（1）构造相应的语法树节点p（2）保持运算的结合性p（3）计算表达式值p（4）4.2.3 其它应注意的问题(续)machunyan西北工业大学软件与微电子学院354.2递归下降语法分析 4.2.1 递归下降分析的基本方法 4.2.2 文法规则使用EBNF表示法 4.2.3 其它应注意的问题 4.2.4 分析树与抽象语法树 4.2.5 案例：Tiny语法分析2022-5-7西北工业大学软件与微电子学院 machunyan36简单整型算术表达式文法：exp exp op exp|(exp)|numberop +|-|*简单算术表达式对应的抽象语法树结构4.

20、2.4 分析树 与抽象语法树2022-5-7西北工业大学软件与微电子学院 machunyan37o 分析树对于显示程序的各语法单位或程序的单词序列分析树对于显示程序的各语法单位或程序的单词序列很有帮助，但是相比纯粹为编译生成可执行代码所需很有帮助，但是相比纯粹为编译生成可执行代码所需的信息而言，分析树却包括了冗余的信息。的信息而言，分析树却包括了冗余的信息。o 所以语法分析程序更趋向于生成抽象语法树，抽象语所以语法分析程序更趋向于生成抽象语法树，抽象语法树是分析树中所含信息的浓缩，包含了进一步分析法树是分析树中所含信息的浓缩，包含了进一步分析所需的所有信息，比分析树效率高。所需的所有信息，比分

21、析树效率高。o 例如：见下页例如：见下页4.2.4 分析树 与抽象语法树(续)2022-5-7西北工业大学软件与微电子学院 machunyan38o exp exp op expo exp (exp)| Numbero op +|-|*opl_expr_expExpl_expr_expop抽象语法树结构分析树结构4.2.4 分析树 与抽象语法树(续)2022-5-7西北工业大学软件与微电子学院 machunyan39+343+4的抽象语法树（34-3）+42 的抽象语法树+-423434.2.4 分析树 与抽象语法树(续)o 抽象语法树设计抽象语法树设计n 各语法单位对应的抽象语法树的结构可以

22、规定，没有标准，但可以参考现有编译器的做法。例如：o工具：Pyc parser，可以打印C语言程序的抽象语法树2022-5-7西北工业大学软件与微电子学院 machunyan404.2.4 分析树 与抽象语法树(续)o 设计抽象语法树（续）设计抽象语法树（续）n 画出产生式规则的语法分析树n 在保证语义信息不丢失保证语义信息不丢失的情况下，除掉语法分析树的冗余节点形成抽象语法树；2022-5-7西北工业大学软件与微电子学院 machunyan414.2.4 分析树 与抽象语法树(续)machunyan西北工业大学软件与微电子学院42EBNF文法表示的tiny语言的语法.doc用递归下降分析算法

23、写出TINY语言的语法分析程序？4.2.5 案例：Tiny语法分析machunyan西北工业大学软件与微电子学院43语法分析的基本步骤语法分析的基本步骤o 对程序设计语言的语法规则进行形式化描述对程序设计语言的语法规则进行形式化描述（用（用2型文法）；型文法）；o 根据语言的语法描述形式，定义各种基本语根据语言的语法描述形式，定义各种基本语法结构的法结构的抽象语法树抽象语法树；o 选择一种合适的选择一种合适的语法分析算法语法分析算法，并在分析程，并在分析程序中插入动作序中插入动作() -语法分析程序。语法分析程序。machunyan西北工业大学软件与微电子学院44语句序列stmt-sequen

24、ce statement;statementTINY语言的各基本语法范畴的抽象语法树结构形式如下：每个语句对应子树的右兄弟指向下一个语句对应的子树machunyan西北工业大学软件与微电子学院45if-stmt if exp then stmt-sequenceelse stmt-sequenceendif语句的抽象语法树结构：machunyan西北工业大学软件与微电子学院46repeat 语句repeat-stmtrepeat stmt-sequence until expmachunyan西北工业大学软件与微电子学院47assign 语句assign_stmtidentifier := e

25、xpmachunyan西北工业大学软件与微电子学院48write语句 write_stmt write expread语句 read_stmtread identifiermachunyan西北工业大学软件与微电子学院49算符表达式machunyan西北工业大学软件与微电子学院50typedef enumStmtK, ExpKNodeKind;typedef enumIfK, RepeatK, AssignK, ReadK, WriteKStmtKind;typedef enumOpK, ConstK, IdKExpKind;typedef enumVoid, Integer, Boolean

26、ExpType;#define MAXCHILDREN 3抽象语法树的定义抽象语法树的定义machunyan西北工业大学软件与微电子学院51typedef 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;抽象语法树的定

27、义(续)machunyan西北工业大学软件与微电子学院52o statementif-stmt|repeat-stmt|assign-stmt| read-stmt|write-stmtTiny语法分析程序：语法分析程序：PARSE.Cmachunyan西北工业大学软件与微电子学院53Tiny语法分析程序：语法分析程序：PARSE.Co if-stmtif exp then stmt-sequence else stmt-squence end machunyan西北工业大学软件与微电子学院54Tiny语法分析程序：语法分析程序：PARSE.Co产生式：产生式：repeat-stmt-repe

28、at stmt-sequence until expmachunyan西北工业大学软件与微电子学院55一个输出其输入阶乘的TINY语言程序read x;if x0 then fact:=1; repeat fact:=fact* x; x:=x-1 until x=0; write fact end4.2.4 案例：Tiny语法分析(续)machunyan西北工业大学软件与微电子学院56Read(x)IFop()id(x)Assign(fact)const(0)const(1)repeatwrite4.2.4 案例：Tiny语法分析(续)PARSE.Cmachunyan西北工业大学软件与微电子

29、学院57 4.1 自上而下的语法分析算法概述 4.2 递归下降分析 4.3 LL(1)分析 4.4 4.4 自上而下的语法分析器自动生成工自上而下的语法分析器自动生成工具具JavaCCJavaCC 4.5 4.5 项目：编译器实现（语法分析模块）项目：编译器实现（语法分析模块）第四章第四章 自上而下的语法分析自上而下的语法分析machunyan西北工业大学软件与微电子学院584.3 LL( 1 )分析4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析与算法 4.3.3 消除左递归和提取左因子machunyan西北工业大学软件与微电子学院594.3.1 LL(1)分析的基本方法o

30、LL (1)分析方法是一种自上而下的语法分析分析方法是一种自上而下的语法分析方法：方法：n 第1个“L”指的是由左向右地处理输入；n 第2个“L”指的是它为输入串找出一个最左推导；n 括号中的数字1意味着它使用输入单词序列中的一个单词预测分析的动作。machunyan西北工业大学软件与微电子学院60例如：假设有简单文法：S(S)S|a 判断输入串(a)a是否是符合该文法规则的句子？4.3.1 LL(1)分析的基本方法(续)S(S)S (a)S (a)a(a)a的最左推导S（）SS a amachunyan西北工业大学软件与微电子学院614.3.1 LL(1)分析的基本方法分析的基本方法(续续)

31、o 针对每一步推导，构造最左推导的语法分析针对每一步推导，构造最左推导的语法分析程序要解决的问题：程序要解决的问题：n 定位当前句型进行下一步推导的非终结符：每一步推导是针对当前句型中最左一个非终结符进行推导；n 选择产生式：用该非终结符对应的哪一个产生式进行推导最有可能成功？1. 符号串的替换：用选择产生式的左部替换右部。machunyan西北工业大学软件与微电子学院62LL (1)分析方法如下：o通过栈来通过栈来“记忆记忆”针对当前句型中的哪一个非针对当前句型中的哪一个非终结符进行推导，首先将文法的开始符号终结符进行推导，首先将文法的开始符号S入栈；入栈；n如果栈的顶部是非终结符A,则利用

32、A对应的某个文法规则A将栈顶部的非终结符A(出栈)替换成串(将串自左至右还是自右至左入栈？)。1. 如果栈的顶部是终结符a,则将其与当前输入单词匹配(出栈)。4.3.1 LL(1)分析的基本方法(续)machunyan西北工业大学软件与微电子学院63o构造一个构造一个非终结符非终结符和和终结符索引终结符索引的二维表格的二维表格MN，T，通过表格指出用哪一个产生式进，通过表格指出用哪一个产生式进行进行下一步推导，其中行进行下一步推导，其中N是非终结符的集是非终结符的集合，合，T是终结符的集合。是终结符的集合。p即构造一个LL(1)分析表，通过该表格引导用哪一个产生式进行推导。 例如：例如：4.3

33、.1 LL(1)分析的基本方法(续)machunyan西北工业大学软件与微电子学院64MN,TS()$S (S)SS a文法S(S)S|a的LL(1)分析表4.3.1 LL(1)分析的基本方法(续)o MS,(表示表示当前分析栈的栈顶符号为当前分析栈的栈顶符号为S，而当前，而当前词法分析的输入单词为词法分析的输入单词为(时，按产生式时，按产生式S(S)S进行推导；进行推导；o MS,a表示表示当前分析栈的栈顶符号为当前分析栈的栈顶符号为S，而当前，而当前词法分析的输入单词为词法分析的输入单词为a时，按产生式时，按产生式Sa进行推导。进行推导。amachunyan西北工业大学软件与微电子学院65

34、步骤分析栈输入动作$S1(a)a$S （S）S$S)S(2(a)a$匹配$S)S3a)a$S a$S)a4a)a$匹配$S6a$S a$a7a$匹配引入$作为输入符号串的限界符；句型自右至左入栈LL (1)分析方法示例$S)5)a$匹配$8$接受machunyan西北工业大学软件与微电子学院66LL(1)分析程序通过将分析栈顶部的非终结符替换成文法规则中该非终结符的一个选择来做出分析。在分析过程中有两个基本动作： 如果栈的顶部是终结符a,则将其与当前输入单词匹配。p 如果不能匹配，出现什么情况？ 如果栈的顶部是非终结符A,则利用文法规则A将栈顶部的非终结符A替换成串(保证自右至左入栈)。4.3

35、.1 LL(1)分析的基本方法(续)machunyan西北工业大学软件与微电子学院67问题：如何构造LL(1)分析表？构造分析表的步骤：求First集合求Follow集合1) 构造LL(1)分析表4.3.1 LL(1)分析的基本方法(续)2022-5-7西北工业大学软件与微电子学院 machunyan681)求求First集合集合machunyan西北工业大学软件与微电子学院69 若X是终结符或，则First(X) =X1)求求First集合（续）集合（续）o 文法符号文法符号X的的First(X)集合集合：o 若X可推导出以终结符a为首的字符串，则a在First(X)中； o 令令X为一个为

36、一个文法符号文法符号（一个终结符或非终结符）（一个终结符或非终结符）或或，则，则First(X)是是终结符的集合终结符的集合，此外可能还，此外可能还有有，它的定义如下：，它的定义如下：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,Tmachuny

37、an西北工业大学软件与微电子学院74First(E)First(E)First(T)First(T)First(F)(a+* 从文法的开始符号E,将求First()集的算法过程表示成下列图示；machunyan西北工业大学软件与微电子学院75求得上述文法各非终结符的First集合如下：First(E)=(,aFirst(E)=+,First(T)=(,aFirst(T)=*,First(F)=(,amachunyan西北工业大学软件与微电子学院76文法符号串的First()集合：设任意串a=X1X2.Xn（终结符和非终结符组成的符号串），则First(a)的定义如下： First(a)包括Fi

38、rst(X1)- 。 对于每个i = 2,.,n，如果对于所有的k=1,.,i-1，First(Xk)包括了，则First(a)也包括First(Xi)-。 如果对于所有的i =1,.,n，First(Xi)包括了，则First(a)也包括。1)求First集合(续)machunyan西北工业大学软件与微电子学院77Follow集合的定义：给出一个非终结符A，集合Follow(A)是由终结符组成，此外可能还有$。集合Follow(A)的定义如下：2)求Follow集合1. 若A是开始符号,则Follow(A)包含$2. 若存在产生式BA,则Follow(A)包含 First()-3. 若存在产

39、生式BA，且在First()中，则 Follow(A)包含Follow(B)注：求解Follow(A) ，考虑A出现在哪些产生式右部。Follow 集仅针对非终结符，并且不包含machunyan西北工业大学软件与微电子学院78o 例如：例如：a Follow(B)n 若有句型Ba出现，由于BA，且在First()中，所以有：o Ba Aa * A a = Aao aFollow(A)2)求Follow集合（续）machunyan西北工业大学软件与微电子学院79例：考虑下述简单整型表达式文法，求各非终结符的Follow()集合； expexp addop term (2) expterm(3)

40、addop+ (4) addop-(5) termterm mulop factor(6) term factor(7) mulop* (8) factor(exp)(9) factornumbermachunyan西北工业大学软件与微电子学院80Follow(exp)=Follow(addop)=Follow(term)=Follow(mulop)=Follow(factor)=$,+,-,)(,number$,+,-,*,)(,number$,+,-,*,)2)求Follow集合(续)machunyan西北工业大学软件与微电子学院81例2：考虑下述文法，求各非终结符的Follow()集合；

41、 先求其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西北工业大学软件与微电子学院82Follow(E)$Follow(E)Follow(E)Follow(T)First(E)Follow(E) 从文法的开始符号E,将求Follow()集的算法过程表示成下列图示；machunyan西北工业大学软件与微电子学院83Follow(T)Follow(T)Follow(F)First(T)Follow(T)machunyan西北工业大学软件与微电子

42、学院84各非终结符的Follow集合如下：Follow(E)=) , $Follow(E)=), $Follow(T)=+, ), $Follow(T)=+, ), $ Follow(F)=*, +, ), $machunyan西北工业大学软件与微电子学院85 构造LL(1)分析表对于First()中的每个终结符a，都将A添加到MA,a元素位置，置MA,a =“A”。 即当当前分析栈的栈顶符号为A时，而当前词法分析的输入单词为a时，按产生式A进行推导；LL(1)分析表的构造方法：分析表以非终结符作为行索引，以终结符作为列索引，分析表的元素位置存储产生式，为每个非终结符A和它对应的产生式A重复以

43、下两步骤：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 bamachunyan西北工业大学软件与微电子学院87例：考虑简化了的C变量声明的文法：declarationtype var-listtypeint|floatvar-listidentif

44、ier listlist ,var-list| 求该文法各非终结符的First()集合和Follow()集合。构造该文法的LL(1)分析表。说明该文法是LL(1)文法。a.假设有输入串 int x,y,z 写出相对应的LL(1)分析程序的动作。machunyan西北工业大学软件与微电子学院88First(declaration)=int,floatFirst(type) =int,floatFirst(var-list) =identifierFirst(list) =, 所求得的各非终结符的First集合和Follow集合如下：machunyan西北工业大学软件与微电子学院89Follow(

45、declaration)=$Follow(type)=identifierFollow(var-list)=$Follow(list) =$machunyan西北工业大学软件与微电子学院90r1: declarationtype var-listr2: typeintr3: type floatr4: var-listidentifier listr5: list ,var-listr6: list 对各产生式进行编号： 构造该文法的LL(1)分析表。machunyan西北工业大学软件与微电子学院91MN,Tdeclarationintidentifier$ ,typevar-listlist

46、floatr1r1r2r3r4r5r6 由于文法G相关的LL(1)分析表的每个项目中至多只有一个产生式，故该文法是LL(1)文法。machunyan西北工业大学软件与微电子学院92 输入串 int x,y,z 相对应的LL(1)分析程序的分析过程如下表所示：步骤分析栈输入动作1$ declarationint x,y,z$r14 $ var-listx,y,z$r42$ var-list typer2int x,y,z$3int x,y,z$匹配$ var-list intmachunyan西北工业大学软件与微电子学院935$ list identifierx,y,z$匹配6$ list,y,

47、z$r5$var-list,y,z$7匹配$var-list8r4y,z$步骤分析栈输入动作$成功$machunyan西北工业大学软件与微电子学院944.3 LL( 1 )分析 4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析与算法 4.3.3 消除左递归和提取左因子machunyan西北工业大学软件与微电子学院95Input$总控程序LL(1)预测分析表stack$machunyan西北工业大学软件与微电子学院964.3.2 LL(1)分析与算法o 基于表的基于表的LL(1)分析算法流程分析算法流程：n LL(1)分析表的构造是LL(1)分析算法的关键技术。machunyan

48、西北工业大学软件与微电子学院974.3 LL( 1 )分析 4.3.1 LL(1)分析的基本方法 4.3.2 LL(1)分析与算法 4.3.3 消除左递归和提取左因子machunyan西北工业大学软件与微电子学院98o 简单直接左递归文法是否是简单直接左递归文法是否是LL(1)文法？例如：文法？例如：n AAan Abo 若文法若文法G有产生式有产生式Uxy |xw | xz则该文法是则该文法是否是否是LL(1)文法？文法？4.3.3 消除左递归和提取左因子machunyan西北工业大学软件与微电子学院994.3.3 消除左递归和提取左因子(续)o由于含有左递归和左公共因子的文法由于含有左递归

49、和左公共因子的文法不不是是LL(1)文法，如果要使用文法，如果要使用LL(1)语法分析算语法分析算法对该文法定义的语言进行语法分析，那么法对该文法定义的语言进行语法分析，那么必须通过必须通过消除左递归和提取左公共因子，消除左递归和提取左公共因子，将文法进行等价改造。将文法进行等价改造。machunyan西北工业大学软件与微电子学院100简单直接左递归的消除AAA4.3.3 消除左递归和提取左因子(续)消除直接左递归将文法重写为：AAAA|machunyan西北工业大学软件与微电子学院101例：消除下面文法的左递归规则：exp exp addop term|termexp term exp消除左

50、递归后将上述文法重写为：exp addop term exp|machunyan西北工业大学软件与微电子学院102多项直接左递归的消除AA1|A2| An|1|2 | |m消除左递归后将上述文法重写为：A 1A|2A|mAA1A|2A|nA|machunyan西北工业大学软件与微电子学院103例：消除下面文法的左递归规则：exp exp+term| exp-term| termexp term exp消除左递归后将上述文法重写为：exp +term exp| -term exp| machunyan西北工业大学软件与微电子学院104若在y,w,z中仍然有左公共因子，可以再次提取。注意，若有：Uxy|x 则提取后：Ux(y|)若有产生式Uxy|xw|xz ，则提取左公共因子并用EBNF表示为： Ux(y|w|z) 再引入另一个非终结符号V，将产生式变为：UxVV y|w|z提取左因子：machunyan西北工业大学软件与微电