TINY-C编译器的设计与实现-语法分析器的设计与实现

目 录摘 要41. 前 言62. 语法分析器的设计原理72.1 语法分析器的功能72.2 语法分析的目标和作用72.3 构造语法分析器的步骤72.4 上下文无关文法及分析82.5 常用的语法分析方法和几种算法的比较102.5.1自上而下分析法102.5.2自下而上分析法123. 语法分析器的设计和实现153.1 TINY语言的介绍153.2 TINY的文法生成153.3 TINY语法分析器算法的选择183.4 TINY语言的递归下降分析程序213.5 TINY语法分析的输出233.5.1 语法分析的输出结果233.5.2 抽象语法树的节点声明243.5.3 语法树结构253.6 语法分析的主要函数与核心代码293.6.1 语法分析器的主要文件和函数293.6.2 语法分析模块304. 测试分析404.1 测试方法404.2 测试计划404.3 测试项目说明404.4 测试结论445. 结论与心得45参 考 文 献46致 谢47附 录47ContentsAbstract41. Preface62. Syntax analyzer principle of design72.1 Function of parsing72.2 Purpose and function of parsing72.3 The of parsing analyzer structure72.4 Context-free grammar and analysis82.5Commonly syntax analysis method and several algorithms comparison102.5.1 From top to bottom analytic method102.5.2 From bottom to top analytic method123. Syntax analyzer design and realization153.1 Introduce of TINY language153.2 Production of TINY grammar153.3 Choice of TINY syntax analyzer algorithm183.4 Recursion decline analysis programe of TINY213.5 Output of TINY grammar analysis233.5.1 Result of parsing233.5.2 Statement of abstract syntax tree node243.5.3 The syntax tree struction253.6 Main function and core code of syntax analyzer293.6.1Master document and function of syntax analyze293.6.2Parsing module304. Testing parse404.1 Testing method404.2 Testing Propose404.3 Explanation of test item404.4 Conclusion of testing445. Conclusion and what one has learned45Bibliography46Thanks47Appendix47TINY-C编译器的设计与实现 -语法分析器的设计与实现摘 要 编译器是将一种源语言翻译为目标语言的计算机程序。 本项目采用一种类（ANSI）C 的小型语言：TINY 语言作为源语言，构造TINY语言的编译器。项目由三人共同完成，其中本人主要是完成了语法分析器的构造，主要工作如下：研究语法分析器的设计原理，并对几种典型的语法分析算法进行分析。生成TINY文法，并证明该文法为LL（1）文法，在此基础上，选择递归下降算法实现TINY语法分析。最终实现了一个TINY语法分析器，它以词法分析器所产生的记号为输入，采用递归下降分析程序进行语法分析，并输出语法树作为下阶段编译的输入。我们最后构造了一个Dephi接口程序，显式输出抽象语法树。关键词 : 编译器 TINY 记号 语法分析 语法树Tiny-C Complier design and realization -Syntax analyzer design and realization Ren JunAbstractThe compiler is a computer program which translates the source language into the target language. This project uses a language similar to (ANSI) C: Using the TINY language as the source language to construct the compiler of TINY. The whole process of the project is finished by the joint effort of three people, and I myself mainly completed the structure of syntax analyzer. The major work is as follows: Analyzing the designing principles of the syntax analyzer, and several kinds of typical parsing algorithm. Producing the TINY grammar, proving this grammar is LL (1) grammar, and in this foundation, choosing recursion drop algorithm to realize the TINY grammar analysis. A TINY grammar analyzer has thus been accomplished. It applies the symbols which are produced by the morphology analyzer as the input, and uses the recursion drop analysis program to carry on the grammar analysis, then output the syntax tree as the input for next compiling phases input. We structured a Dephi interface routine at last to display the abstract syntax tree.Keyword ：Compiler ， TINY ，Token ，Syntax analysis，Syntax tree1. 前 言系统概述在计算机上执行一个高级语言程序一般要分为两步:第一步,用一个编译程序把高级语言翻译成机器语言程序;第二步:运行所得的机器语言程序求得计算结果。通常所说的翻译程序是指这样的一个程序,它能够把某一种语言程序转换成另一种语言程序,而后者与前者在逻辑上是等价的。语法分析器,简称分析器,对单词符号串进行语法分析(根据语法规则进行推导或规约),识别除各类语法单位,最终判断输入串是否构成语法上的正确的”程序”。词法分析器目标代码生成器语法分析器词义分析和中间代码产生器优化器表格管理错误处理目标代码中间代码中间代码语法单位单词符号源程序图1-1编译程序框TINY语言的概述 TINY的程序结构很简单，它在语法上和Pascal的语法相似：仅是一个由分号分隔开的语句序列。另外，它既无过程也无声明。所有的变量都是整型变量，通过对其赋值可较轻易地声明变量（类似FORTRAN或BASIC）。它只有两个控制语句： if语句和repeat语句，这两个控制语句本身也可包含语句序列。If语句有一个可选的else部分且必须由关键字end结束。除此之外，read语句和write语句完成输入/输出。在花括号中可以有注释，但注释不能嵌套。2. 语法分析器的设计原理2.1 语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1.1所示。词法分析语法分析器编译后续部分单词符号取下一个单词符号语法分析树 图2.1 语法分析器在编译程序中的地位2.2 语法分析的目标和作用1）语法分析的目标是确定程序的语法，或称作结构，也正是这个原因，它又被称作语法分析（syntax analysis）。 2）分析过程 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树。因此，可将分析程序看作一个函数，该函数把由扫描程序生成的记号序列作为输入，并生成语法树作为它的输出：记号序列语法树。2.3 构造语法分析器的步骤a写出文法b根据文法选择合适的分析算法。C实现算法 2.4 上下文无关文法及分析实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。1）上下文无关文法定义在计算机科学中，一个形式文法G = (N P S)称之为上下文无关的，如果它的产生式规则都取如下的形式：V - w ，这里 VN ， w (N)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的条目上下文无关语言。上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法； BNF 巴克斯-诺尔范式经常用来表达上下文无关文法。2）上下文无关文法规则上下文无关文法规则确定了为由规则定义的结构的记号符号符合语法的串集。文法规则通过推导确定记号符号的正规串。推导（derivation）是在文法规则的右边进行选择的一个结构名字替换序列。推导以一个结构名字开始并以记号符号串结束。在推导的每一个步骤中，使用来自文法规则的选择每一次生成一个替换。3）上下文无关文法的形式定义定义上下文无关文法由以下各项组成：（1) 终结符（terminal）集合T。（2) 非终结符（nonterminal）集合N（与T不相交）。（3) 产生式（production）或文法规则（grammar rule）Aa的集合P，其中A是N的一个元素，a是（T N）*中的一个元素（是终结符和非终结符的一个可为空的序列）。（4) 来自集合N的开始符号（start symbol）。令G是一个如上所定义的文法，则G = (T, N, P, S)。G上的推导步骤（derivation step）格式a Ag abg，其中a和g是(T N) *中的元素，且有Ab在P中（终结符和非终结符的并集，有时被称作G的符号集，set of symbol），且(T N) *中的串a被称作句型（sentential form）。将关系a *b定义为推导步骤关系 的传递闭包；也就是：假若有零个或更多个推导步骤，就有a *b（n0）a1 a2 an- 1 an其中a=a1，b=an （如果n= 0，则a=b）。在文法G上的推导（derivation）形如S *w，且w T *（即：w 是终结符的一个串，称作句子（sentence），S是G的开始符号。由G生成的语言（language generated by G）写作L (G)，它被定义为集合L (G) = w T * |存在G的一个推导S *w，也就是：L (G)是由S推导出的句子的集合。最左推导（leftmost derivation）S *w 是一个推导，在其中的每一个推导步骤aAg abg都有almT*，换言之，a 仅由终结符组成。类似地，最右推导（ rightmost derivation）就是每一个推导步骤aAg abg 都有属性g T*。文法G上的分析树（parse tree）是一个带有以下属性的作了标记的树：（1) 每个节点都用终结符、非终结符或标出。（2) 根节点用开始符号S标出。（3) 每个叶节点都用终结符或标出。（4) 每个非叶节点都用非终结符标出。（5) 如带有标记A N的节点有n 个带有标记X1 , X2 , . . . Xn 的孩子（可以是终结符也可以是非终结符），就有AX1 , X2 , . . . Xn P（文法的一个产生式）。每一个推导都引出一个分析树，这个分析树中的每一个步骤aAg abg 都在推导中，且b= X1 , X2 , . . . Xn 与带有标记X1 , X2 , . . . Xn 的n 个孩子的结构相对应，其中X1 , X2 , . . . Xn 带有标记A。许多推导可引出相同的分析树。但每个分析树只有唯一的一个最左推导和一个最右推导。最左推导与分析树的前序编号相对应，而与之相反，最右推导与分析树的后序编号相对应。若上下文无关文法G有L=L(G)，就将串L的集合称作上下文无关语言（ c ontext-freel anguage）。一般地，许多不同的文法可以生成相同的上下文无关语言，但是根据所使用的文法的不同，语言中的串也会有不同的分析树。若存在串w L (G)，其中w 有两个不同的分析树（或最左推导或最右推导），那么文法G就有二义性（ambiguous）。2.5 常用的语法分析方法和几种算法的比较语言的语法结构是用上下文无关文法描叙的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串（指由单词符号组成的有限序列）是否为一个句子。对于一个文法，当给出一串符号时，怎么知道它是不是该文法的一个句子（“程序”）？就要从文法的开始符号出发推导出这个输入串，也就是要建立一个与输入串相匹配的语法分析树。按照语法分析树的建立方法，可以将语法分析办法分成两类，一类是自上而下分析法，另一类是自下而上分析法。2.5.1自上而下分析法1）定义： 从文法的开始符号出发，向下推导，推出句子。2）优点：符合人的思想，比较容易理解3）缺点：a) 文法的左递归性问题，因此使用自上而下分析发必须消除文法的左递归性。b) 回溯问题c) 虚假匹配d) 效率低，代价高e) 难于确定出错位置f) 只适合LL（1）文法*注释：LL（1）文法：一个文法G, 若它的分析表M不含多重定义入口,则被称为LL为(1)文法。LL(1)中的第一 个“L”意味着自左而右地扫描输入,第二个“L”意味着生成一个最左推导,并且“1”意味着为做 出分析动作的决定，在每一步利用一个向前看符号,一个文法G是LL（1）的，那么必须满足：1）文法不含左递归 2）对于文法的每一个非终结符A的各个产生式的候选首符集两两不相交。即：FIRST（）FIRST（）；它们不应该都能推出空字; 3）对于文法中的每个非终结符A，若它存在某个候选首符集包含。即：假若包含,那么,FIRST（） FOLLOW（A）. 4）主要算法A递归下降分析程序 定义：若一个文法G不含有左递归，而且每个非终结符的所有候选式的首符集都是两两不相交的，那么就能为G中每个非终结符编写一个相应的递归过程。把该文法中所有这样的递归过程组合起来就可能构成一个不带回溯的自上而下分析程序递归下降分析程序。实现思想：为文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，按LL(1)形式唯一确定选择哪个候选式进行推导，若遇到某候选式为e，认为其自动匹配。把这些递归过程组合起来就构成了文法的递归下降分析程序。实现方法： a)使用LL(1)文法 先将文法消除左递归、提取公共左因子，使之成为LL(1)文法，后将每个非终结符对应一个递归过程，过程体是按照相应产生式的右部符号串顺序编写。每匹配一个终结符，则再读入下一个符号，对产生式右部的每个非终结符，则调用相应的过程。 b)使用BNF范式先将文法改写为BNF形式，后再书写递归子程序。优点：容易理解。缺点a）对文法的要求高，必须满足LL(1)文法。 b）高深度的递归调用会影响语法分析的效率，速度慢，占空间多。B预测分析程序定义：使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。实现思想：预测分析程序就是属于这种类型的LL(1)分析器。实现方法：构造分析表和栈，设栈顶符号为X，读入符号为a，则a)若X=a=#，则表示识别成功，退出分析程序；b)若X=a#，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但Xa，则调用error处理；c)若XVN，则查预测分析表M。若MX,a中存放着关于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若MX,a中存放着出错标记，则调用相应Error处理。优点：过程比递归分析的效率高，速度快，占空间少，仅用表结构。缺点: 对文法的要求高，必须满足LL(1)文法。2.5.2自下而上分析法1）定义：所谓自下而上分析法就是从输入串开始，逐步进行“规约”， 直至规约到文法的开始符号；或者说从语法树的末端开始，步步向上“规约”，直到根结。2）优点：从输入符号串开始分析开始分析，因此进行语法分析和进行语义分析可以在一遍内进行，而自上而下的分析法是从根节点开始进行语法分析，因此必须先经过一遍扫描建立语法树，让后再经过一遍扫描进行语法分析。因此自下而上的分析法效率更高。3）缺点：和人的思想相反，不容易理解，算法更复杂。4) 主要算法A 算符优先分析法定义：定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。实现思想：优先表构造优先函数，寻找最作素短语。（设G是一个算符文法，是句型 ba关于A的短语(即有S-A且A- )且至少含有一个终结符号，并且除自身之外不再含有任何更小的 带有终结符号的短语，则称是句型关于A的素短语。所谓最左素短语是指处于句型最左边的那个素短语。）实现方法： 算符优先分析法自底向上地分析句子，解决了前面提到的两个问题，即：1)可以只根据相邻运算符的优先关系，就能方便地并且唯一地确定归约的“句柄”；2)可以用来分析二义性文法所产生的语言。是仿照算术表达式的四则运算过程而设计的一种语法分析方法。终结符号 运算符非终结符号 运算对象算符优先分析法的关键在于用合适的方法去定义任何两个可能相继出现的结符号a和b(它们之间可能插有一个非终结符号)之间的优先级。然后利用这种关系比较相邻运算符之间的优先级来确定可归约串并进行归约. 终结符号a与b之间的优先关系有三种：ab 表示a的优先级低于b ab 表示a的优先级等于b ab 表示a的优先级大于b 优点：a）有利于表达式分析，宜于手工实现。b）使用优先表，只对算符优先比较，占用的存储量比较小，速度快。缺点：a) 可能错误接受非法句子，能力有限b) 要求文法必须是算符优先文法，这个条件比较苛刻。 B LR算法定义：从左到右扫描输入串。并且构造一个最右推导的逆过程。实现思想与方法：LR分析的核心部分是一张分析表。这张分析表包括两部分，一是“动作”(ACTIOB)表，另一是“状态转换”(C0m)表。它们都是二维数组。优点：对文法要求较低，适合大部分文法。缺点：算法比算符优先法复杂，占用资源较多，速度较慢。3. 语法分析器的设计和实现3.1 TINY语言的介绍 1) TINY的程序结构是一个由分号分隔开的语句序列。 2) 既无过程也无声明。3) 所有的变量都是整型变量，通过对其赋值可较轻易地声明变量。4) 只有两个控制语句： if语句和repeat语句，这两个控制语句本身也可包含语句序列。If语句有一个可选的else部分且必须由关键字end结束。5) read语句和write语句完成输入/输出。6) TINY的表达式只有布尔表达式和整型算术表达式。布尔表达式由对两个算术表达式的比较组成，该比较使用与=比较算符。算术表达式可以包括整型常数、变量、参数以及4个整型算符+、*、/，此外还有一般的数学属性。例子：一个输出其输入阶乘的TINY语言程序 read x;input an integer if 0x then dont compute if x stmt-sequencestmt-sequence- stmt-sequence;statement|statementprogram表示程序, stmt-sequence表示语句序列，statement表示语句由TINY语言介绍中的第2，3，4，5条可知语句分为赋值语句、if语句、repeat语句、read语句和write，其文法表示如下：statement - if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmt (语句) (if语句)（循环语句）（赋值语句）（读语句） （写语句）A) if语句（if-stmt）而if语句有两种形式：a)if 表达式 then 语句序列 end 例如：if x0 then y:=1 endb)if 表达式 then 语句序列 else 语句序列 end例如：if x if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence endB) 循环语句（repeat-stmt）循环语句语句的形式为：repeat 语句序列 until 表达式 例如：repeat fact:=fact*x; x:=x-1until x=0;由此可得循环语句语句的文法为：repeat-stmt - repeat stmt-sequence until expC）赋值语句（assign-stm）由3可知赋值语句的左边为变量（标识符），右部为表达式。形式为：变量：= 表达式|值例如：x:=x-1由此可得赋值语句的文法为：assign-stmt - identifier := expD）读写语句（read-stmt和write-stmt）读写语句形式为：读出 变量 | 写入 变量 例如：read x;input an integer write fact output factorial of x由此可得读写语句的文法为：read-stmt - read identifierwrite-stmt - write expE）布尔表达式和整型算术表达式表达式的要求：表达式满足优先顺序，优先顺序从低到高为：比较运算符 simple-exp comparison-op simple-exp | simple-expcomparison-op - simple-exp addop term |termaddop - +|-依此类推，我们可以得到表达式的文法如下所示：exp - simple-exp comparison-op simple-exp | simple-expcomparison-op - simple-exp addop term |termaddop - +|-term - term mulop factor |factormulop - *|/factor - (exp)|number | identifier其中，exp表示表达式，simple-exp表示算术表达式 term表示加法项，mulop表示乘除项，factor表示其他因子（数字或标示符）综上所述，可以得到下图TINY的文法如图21所示：program - stmt-sequencestmt-sequence- stmt-sequence;statement|statementstatement - if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmtif-stmt - if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence endrepeat-stmt - repeat stmt-sequence until expassign-stmt - identifier := expread-stmt - read identifierwrite-stmt - write expexp - simple-exp comparison-op simple-exp | simple-expcomparison-op - simple-exp addop term |termaddop - +|-term - term mulop factor |factormulop - *|/factor - (exp)|number | identifier粗体表示终结符，如if then +等等。图2-1 TINY的BNF的文法3.3 TINY语法分析器算法的选择 选择： 自上而下文法的递归下降分析程序分析： 根据2.2节中TINY的文法生成，可以计算TINY文法的FIRST集合和Follow集合。AFIRST集合的定义FIRST(X)表示X所有可能推出的开始终结符,包括. 1,显然，若X为终结符，则FIRST(X) = X。 2,如果X为非终结符，有两种情况： (1)若有产生式 Xa,则把a加入FIRST(X)中; 若有产生式 X,则把加入FIRST(X)中. (2)若有产生式 XY , Y是非终结符, 如果Y不能推出,也就是说,不属于FIRST(Y),那么X所能推出的开头终结符也就是Y所能推出的开头终结符.我们把FIRST(Y)加入FIRST(X)中. 如果Y能推出,即FIRST(Y)中包含,假设跟在Y后的符号为 Y2,那么当我们用匹配Y时,X所能推出的开头终结符就为Y2所能推出的开头终结符(不包括).也就是说在这种情况下, X所能推出的开头终结符不但包括Y所能推出的除之外的开头终结符也应包括Y2所能推出的除之外的开头终结符.应把FIRST(Y)和FIRST(Y2)中所有非-元素加入FIRST(X)中.FIRST集合计算结果：PROGRAM 的 FIRST集： IF REPEAT ASSIGN READ WRITE STMT_SEQUENCE 的 FIRST集： IF REPEAT ASSIGN READ WRITE STATEMENT 的 FIRST集： IF REPEAT ASSIGN READ WRITE IF_STMT 的 FIRST集： IF PROGRAM REPEAT_STMT 的 FIRST集： REPEAT PROGRAM ASSIGN_STMT 的 FIRST集： IDENTIFIER PROGRAM READ_STMT 的 FIRST集： READ PROGRAM WRITE_STMT 的 FIRST集： WRITE PROGRAM EXP 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM SIMPLE_EXP 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM COMPARISON_OP 的 FIRST集： LESS EQUAL PROGRAM ADDOP 的 FIRST集： ADD SUBTRACT PROGRAM MULOP 的 FIRST集： MULTIPLY DIVIDE PROGRAM TERM 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM FACTOR 的 FIRST集： LPAR NUMBER IDENTIFIER PROGRAM NUMBER 的 FIRST集： NUMBER PROGRAM PROGRAM IDENTIFIER 的 FIRST集： IDENTIFIER IF 的 FIRST集： IF THEN 的 FIRST集： THEN ELSE 的 FIRST集： ELSE END 的 FIRST集： END REPEAT 的 FIRST集： REPEAT UNTIL 的 FIRST集： UNTIL READ 的 FIRST集： READ WRITE 的 FIRST集： WRITE ADD 的 FIRST集： ADD SUBTRACT 的 FIRST集： SUBTRACT MULTIPLY 的 FIRST集： MULTIPLY DIVIDE 的 FIRST集： DIVIDE EQUAL 的 FIRST集： EQUAL LESS 的 FIRST集： LESS LPAR 的 FIRST集： LPAR RPAR 的 FIRST集： RPAR SEMICOLON 的 FIRST集： SEMICOLON ASSIGN 的 FIRST集： ASSIGN B Follow集合的定义A为非终结符,FOLLOW(A)表示紧跟A后的所有终结符,包括结束符#.(1) 若A为文法的开始符号S，置#于FOLLOW(A)中。(2) 若存在产生式BA,为符号串,那么紧跟A之后的终结 符应为的第一个终结符(不包括),因此将First()-加入Follow(A)中。(3) 若存在产生式BA, 那么紧跟B的终结符也可能是紧跟A的终结符,因此要将Follow(B)加入Follow(A)中.(4) 若存在产生式BA，而=,即FIRST().那么如果用匹配,就有以下推导: B=A,在这种情况下, 紧跟B的终结符也可能是紧跟A的终结符,因此要将Follow(B)加入Follow(A)中.注意:根据规则3和4,如果存在BA 或 BA，而=.那么当Follow(B)改变时, Follow(A)也会改变.因此计算文法G中所有非终结符的Follow集合时,一趟计算是不够的.只有当文法中所有非终结符的Follow集合都不再发生变化时,我们才能结束对文法中非终结符的Follow集合的计算.FOLLOW集合的结果：PROGRAM 的 FOLLOW集： DOUBLE_CROSS STMT_SEQUENCE 的 FOLLOW集： DOUBLE_CROSS END ELSE UNTIL STATEMENT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL IF_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL REPEAT_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL ASSIGN_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL READ_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL WRITE_STMT 的 FOLLOW集： SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL EXP 的 FOLLOW集： THEN SEMICOLON DOUBLE_CROSS RPAR PROGRAM END ELSE UNTIL SIMPLE_EXP 的 FOLLOW集： LESS EQUAL THEN SEMICOLON DOUBLE_CROSS PROGRAM RPAR END ELSE UNTIL COMPARISON_OP 的 FOLLOW集： LPAR NUMBER IDENTIFIER PROGRAM ADDOP 的 FOLLOW集： LPAR NUMBER IDENTIFIER PROGRAM MULOP 的 FOLLOW集： LPAR NUMBER IDENTIFIER PROGRAM TERM 的 FOLLOW集： ADD SUBTRACT LESS EQUAL THEN SEMICOLON DOUBLE_CROSS PROGRAM RPAR END ELSE UNTIL FACTOR 的 FOLLOW集： MULTIPLY DIVIDE ADD SUBTRACT LESS EQUAL THEN SEMICOLON DOUBLE_CROSS PROGRAM RPAR END ELSE UNTIL 首先判断出文法的每一个非终结符A的各个产生式的候选首符集两两不相交。即：FIRST（）FIRST（）；它们不能推出空字; 其次是对于文法中的每个非终结符A，它存在的某个候选首符集包含。即：假若包含,那么,FIRST（） FOLLOW（A）.结论：由此可以确定是满足LL(1)条件，我们就可以为它构造一个不带回溯的自上而下分析程序，而且TINY语句简单只有5类，并且语句分析程序是由一组递归过程组成，所以选择递归下降分析。3.4 TINY语言的递归下降分析程序编译说穿了是对一个数据流进行逐字的分析， 把分析过程看做是不断的读取数据，是实现程序的一个基本思想。现在让我们自顶而下地对表达式进行分析，自顶向下（top - down）的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶递归下降分析的概念极为简单：将一个非终结符A的文法规则看作将识别A的一个过程的定义。A的文法规则的右边指出这个过程的代码结构：一个选择中的终结符与非终结符序列与相匹配的输入以及对其他过程的调用相对应，而选择与在代码中的替代情况（case语句和if语句）相对应。TINY递归下降程序中使用的是比BNF更加完善的EBNF-TINY语言的文法，如下：program - stmt-sequencestmt-sequence- stmt-sequence ;statementstatement - if-stmt|repeat-stmt|assign-stmt|read-stmt|write-stmtif-stmt - if exp then stmt- sequence else stmt-sequence endrepeat-stmt - repeat stmt-sequence until expassign-stmt - identifier := expread-stmt - read identifierwrite-stmt - write expexp - simple-exp comparison-op simple-exp comparison-op - term addop term addop - +|-term - factor mulop factor mulop - *|/factor - (exp)|number | identifier 分析程序构造了语法树，除此之外，它还将语法树的表示打印到列表文件中。 TINY分析程序完全按照递归下降程序的要点，这个分析程序包括两个代码文件：parse.h和parse.c。parse . h文件。另外：它由一个声明TreeNode * parse (void);组成，它定义了主分析例程parse，parse又返回一个指向由分析程序构造的语法树的指针。parse.c文件，它由11个相互递归的过程组成，这些过程与BNF文法直接对应：一个对应于stmt - sequence，一个对应于statement，5个分别对应于5种不同的语句，另有4个对应于表达式的不同优先层次。操作符非终结符并未包括到过程之中，但却作为与它们相关的表达式被识别。这里也没有过程与program相对应，这是因为一个程序就是一个语句序列，所以parse例程仅调用stmt_sequ ence。分析程序代码还包括了一个保存向前看记号的静态变量token以及一个查找特殊记号的match过程，当它找到匹配时就调用getToken，否则就声明出错；此外代码还包括将出错信息打印到列表文件中的syntaxError过程。主要的parse程将token初始化到输入的第1个记号中，同时调用stmt_sequence，接着再在返回由stmt_ sequence构造的树之前检查源文件的末尾（如果在stmt_ sequence返回之后还有更多的记号，那么这就是一个错误）。每个递归过程的内容应有相对的自身解释性， stmt_sequence却有可能是一个例外，它可写在一个更为复杂的格式中以提高对出错的处理能力；递归分析过程使用3种实用程序过程，为了方便已将它们都放在了文件util.c中，此外它还带有接口util.h。这些过程是：1) newStmtNode，它取用一个指示语句种类的参数，它还在分配该类的新语句节点的同时返回一个指向新分配的节点的指针。2) newExpNode，它取用一个指示表达式种类的参数，它还在分配该类新表达式节点的同时返回一个指向新分配的节点的指针。3) copyString，它取用一个串参数，为拷贝分配足够的空间，并拷贝串，同时返回一个指向新分配的拷贝的指针。