TINYC编译器的设计与实现语法分析器的设计与实现.docx

《TINYC编译器的设计与实现语法分析器的设计与实现.docx》由会员分享，可在线阅读，更多相关《TINYC编译器的设计与实现语法分析器的设计与实现.docx（43页珍藏版）》请在三一办公上搜索。

1、TINYC编译器的设计与实现语法分析器的设计与实现目 录 摘 要 . 3 1. 前 言 . 4 2. 语法分析器的设计原理 . 6 2.1 语法分析器的功能 . 6 2.2 语法分析的目标和作用 . 6 2.3 构造语法分析器的步骤 . 6 2.4 上下文无关文法及分析 . 7 2.5 常用的语法分析方法和几种算法的比较 . 9 2.5.1自上而下分析法 . 9 2.5.2自下而上分析法 . 11 3. 语法分析器的设计和实现 . 14 3.1 TINY语言的介绍 . 14 3.2 TINY的文法生成 . 14 3.3 TINY语法分析器算法的选择 . 17 3.4 TINY语言的递归下降分析

2、程序 . 20 3.5 TINY语法分析的输出 . 22 3.5.1 语法分析的输出结果 . 22 3.5.2 抽象语法树的节点声明 . 23 3.5.3 语法树结构 . 24 3.6 语法分析的主要函数与核心代码 . 28 3.6.1 语法分析器的主要文件和函数 . 28 3.6.2 语法分析模块 . 29 4. 测试分析 . 39 4.1 测试方法 . 39 4.2 测试计划 . 39 4.3 测试项目说明 . 39 4.4 测试结论 . 43 5. 结论与心得 . 44 参 考 文 献 . 45 致 谢 . 错误！未定义书签。 附 录 . 错误！未定义书签。 Contents Abstr

3、act . 4 1. Preface . 6 2. Syntax analyzer principle of design . 7 2.1 Function of parsing . 7 2.2 Purpose and function of parsing . 7 2.3 The of parsing analyzer structure . 7 2.4 Context-free grammar and analysis . 8 2.5Commonly syntax analysis method and several algorithms comparison . 10 2.5.1 Fr

4、om top to bottom analytic method . 10 2.5.2 From bottom to top analytic method . 12 3. Syntax analyzer design and realization . 15 3.1 Introduce of TINY language . 15 3.2 Production of TINY grammar . 15 3.3 Choice of TINY syntax analyzer algorithm . 18 3.4 Recursion decline analysis programe of TINY

5、 . 21 3.5 Output of TINY grammar analysis . 23 3.5.1 Result of parsing . 23 3.5.2 Statement of abstract syntax tree node . 24 3.5.3 The syntax tree struction . 25 3.6 Main function and core code of syntax analyzer . 29 3.6.1Master document and function of syntax analyze 29 3.6.2Parsing module . 30 4

6、. Testing parse . 40 4.1 Testing method . 40 4.2 Testing Propose . 40 4.3 Explanation of test item . 40 4.4 Conclusion of testing . 44 5. Conclusion and what one has learned . 45 Bibliography . 46 Thanks . 47 Appendix . 47 2 TINY-C编译器的设计与实现 -语法分析器的设计与实现 摘 要 编译器是将一种源语言翻译为目标语言的计算机程序。 本项目采用一种类C 的小型语言：T

7、INY 语言作为源语言，构造TINY语言的编译器。项目由三人共同完成，其中本人主要是完成了语法分析器的构造，主要工作如下： 研究语法分析器的设计原理，并对几种典型的语法分析算法进行分析。生成TINY文法，并证明该文法为LL文法，在此基础上，选择递归下降算法实现TINY语法分析。最终实现了一个TINY语法分析器，它以词法分析器所产生的记号为输入，采用递归下降分析程序进行语法分析，并输出语法树作为下阶段编译的输入。我们最后构造了一个Dephi接口程序，显式输出抽象语法树。 关键词 : 编译器 TINY 记号 语法分析 语法树 Tiny-C Complier design and realizati

8、on -Syntax analyzer design and realization Ren Jun 3 Abstract The 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 whol

9、e 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 gramma

10、r, 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 dro

11、p 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 tree 1. 前 言 系统概述 在计算机上执行一个高级语言程序

12、一般要分为两步:第一步,用一个编译程4 序把高级语言翻译成机器语言程序;第二步:运行所得的机器语言程序求得计算结果。通常所说的翻译程序是指这样的一个程序,它能够把某一种语言程序转换成另一种语言程序,而后者与前者在逻辑上是等价的。语法分析器,简称分析器,对单词符号串进行语法分析(根据语法规则进行推导或规约),识别除各类语法单位,最终判断输入串是否构成语法上的正确的”程序”。 源程序 表格管理 词法分析器 单词符号 语法分析器 语法单位 词义分析和中间代码产生器 中间代码 优化器 中间代码 目标代码生成器 目标代码 图1-1编译程序框 错误处理 TINY语言的概述 TINY的程序结构很简单，它在语

13、法上和Pascal的语法相似：仅是一个由分号分隔开的语句序列。另外，它既无过程也无声明。所有的变量都是整型变量，通过对其赋值可较轻易地声明变量。它只有两个控制语句： if语句和repeat语句，这两个控制语句本身也可包含语句序列。If语句有一个可选的else部分且必须由关键字end结束。除此之外，read语句和write语句完成输入/输出。在花括号中可以有注释，但注释不能嵌套。 5 2. 语法分析器的设计原理 2.1 语法分析器的功能 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1.1所示

14、。 取下一个单词符号 单词符号 语法分析树 词法分析 语法分析器 编译后续部分 图2.1 语法分析器在编译程序中的地位 2.2 语法分析的目标和作用 1）语法分析的目标是确定程序的语法，或称作结构，也正是这个原因，它又被称作语法分析。 2）分析过程 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树。因此，可将分析程序看作一个函数，该函数把由扫描程序生成的记号序列作为输入，并生成语法树作为它的输出：记号序列语法树。 2.3 构造语法分析器的步骤 a写出文法 b根据文法选择合适的分析算法。 C实现算法 6 2.4 上下文无关文法及分析

15、实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。 1）上下文无关文法定义 在计算机科学中，一个形式文法G = (N P S)称之为上下文无关的，如果它的产生式规则都取如下的形式：V - w ，这里 VN ， w (N)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的条目上下文无关语言。上下文无关文法重要的原因在于它们拥有足够强的表达力

16、来表示大多数程序设计语言的语法； BNF 巴克斯-诺尔范式经常用来表达上下文无关文法。 2）上下文无关文法规则 上下文无关文法规则确定了为由规则定义的结构的记号符号符合语法的串集。文法规则通过推导确定记号符号的正规串。推导是在文法规则的右边进行选择的一个结构名字替换序列。推导以一个结构名字开始并以记号符号串结束。在推导的每一个步骤中，使用来自文法规则的选择每一次生成一个替换。 3）上下文无关文法的形式定义 定义上下文无关文法由以下各项组成： 集合T。 集合N。 或文法规则Aa的集合P，其中A是N的一个元素，a是*中的一个元素。 。 令G是一个如上所定义的文法，则G = (T, N, P, S)

17、。G上的推导步骤格式a Ag abg，其中a和g是(T N) *中的元素，且有Ab在P中，且(T N) *中的串a被称作句型）。将关系a *b定义为推导步骤关系 的传递闭包；也就是：假若有零个或更多个推导步骤，就有a *ba1 a2 an- 1 an其中a=a1，b=an 。在文法G上的推导形如S *w，且w T *），S是G的开始符号。 由G生成的语言写作L (G)，它被定义为集合L (G) = w T * |存在G的一个推导S *w，也就是：L (G)是由S推导出的句子的集合。 最左推导S *w 是一个推导，在其中的每一个推导步骤aAg abg都有almT*，换言之，a 仅由终结符组成。类

18、似地，最右推导就是每一个推导步骤aAg abg 都有属性g T*。 文法G上的分析树是一个带有以下属性的作了标记的树： ，就有AX1 , X2 , . . . Xn P。每一个推导都引出一个分析树，这个分析树中的每一个步骤aAg abg 都在推导中，且b= X1 , X2 , . . . Xn 与带有标记X1 , X2 , . . . Xn 的n 个孩子的结构相对应，其中X1 , X2 , . . . Xn 带有标记A。许多推导可引出相同的分析树。但每个分析树只有唯一的一个最左推导和一个最右推导。 最左推导与分析树的前序编号相对应，而与之相反，最右推导与分析树的后序编号相对应。若上下文无关文法

19、G有L=L(G)，就将串L的集合称作上下文无关语言。一般地，许多不同的文法可以生成相同的上下文无关语言，但是根据所使用的文法的不同，语言中的串也会有不同的分析树。若存在串w L (G)，其中w 有两个不同的分析树，那么文法G就有二义性。 8 2.5 常用的语法分析方法和几种算法的比较 语言的语法结构是用上下文无关文法描叙的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给出一串符号时，怎么知道它是不是该文法的一个句子？就要从文法的开始符号出发推导出这个输入串，也就是要建立一个与输入串相匹配的语法分析树。 按照语法分析树的建立方法，可以将语法分析办

20、法分成两类，一类是自上而下分析法，另一类是自下而上分析法。 2.5.1自上而下分析法 1）定义： 从文法的开始符号出发，向下推导，推出句子。 2）优点：符合人的思想，比较容易理解 3）缺点： a) 文法的左递归性问题，因此使用自上而下分析发必须消除文法的左递归性。 b) 回溯问题 c) 虚假匹配 d) 效率低，代价高 e) 难于确定出错位置 f) 只适合LL文法 *注释：LL文法：一个文法G, 若它的分析表M不含多重定义入口,则被称为LL为(1)文法。LL(1)中的第一 个“L”意味着自左而右地扫描输入,第二个“L”意味着生成一个最左推导,并且“1”意味着为做 出分析动作的决定，在每一步利用一

21、个向前看符号,一个文法G是LL的，那么必须满足： 1）文法不含左递归 2）对于文法的每一个非终结符A的各个产生式的候选首符集两两不相交。即：FIRSTFIRST；它们不应该都能推出空字; 9 3）对于文法中的每个非终结符A，若它存在某个候选首符集包含。即：假若包含,那么,FIRST FOLLOW. 4）主要算法 A递归下降分析程序 定义：若一个文法G不含有左递归，而且每个非终结符的所有候选式的首符集都是两两不相交的，那么就能为G中每个非终结符编写一个相应的递归过程。把该文法中所有这样的递归过程组合起来就可能构成一个不带回溯的自上而下分析程序递归下降分析程序。 实现思想：为文法中每个非终结符编写

22、一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，按LL(1)形式唯一确定选择哪个候选式进行推导，若遇到某候选式为e，认为其自动匹配。把这些递归过程组合起来就构成了文法的递归下降分析程序。 实现方法： a)使用LL(1)文法 先将文法消除左递归、提取公共左因子，使之成为LL(1)文法，后将每个非终结符对应一个递归过程，过程体是按照相应产生式的右部符号串顺序编写。每匹配一个终结符，则再读入下一个符号，对产生式右部的每个非终结符，则调用相应的过程。 b)使用BNF范式 先将文法改写为BNF形式，后再书写递归子程序。 优点：容易理解。 缺点 a）对文法的要求

23、高，必须满足LL(1)文法。 B预测分析程序 b）高深度的递归调用会影响语法分析的效率，速度慢，占空间多。 10 定义：使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。 实现思想： 预测分析程序就是属于这种类型的LL(1)分析器。 实现方法： 构造分析表和栈，设栈顶符号为X，读入符号为a，则 a)若X=a=#，则表示识别成功，退出分析程序； b)若X=a#，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但Xa，则调用error处理；

24、 c)若XVN，则查预测分析表M。若MX,a中存放着关于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若MX,a中存放着出错标记，则调用相应Error处理。 优点：过程比递归分析的效率高，速度快，占空间少，仅用表结构。 缺点: 对文法的要求高，必须满足LL(1)文法。 2.5.2自下而上分析法 1）定义：所谓自下而上分析法就是从输入串开始，逐步进行“规约”， 直至规约到文法的开始符号；或者说从语法树的末端开始，步步向上“规约”，直到根结。 2）优点：从输入符号串开始分析开始分析，因此进行语法分析和进行语义分析可以在一遍内进行，而自上而下的分析法是从根

25、节点开始进行语法分析，因此必须先经过一遍扫描建立语法树，让后再经过一遍扫描进行语法分析。因此自下而上的分析法效率更高。 3）缺点：和人的思想相反，不容易理解，算法更复杂。 4) 主要算法 A 算符优先分析法 11 定义：定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。 实现思想：优先表构造优先函数，寻找最作素短语。 实现方法： 算符优先分析法自底向上地分析句子，解决了前面提到的两个问题，即： 1)可以只根据相邻运算符的优先关系，就能方便地并且唯一地确定归约的“句柄”； 2)可以用来分析二义性文法所产生的语言。 是仿照算术表达式的四则运算过程而设

26、计的一种语法分析方法。 终结符号 运算符 非终结符号 运算对象 算符优先分析法的关键在于用合适的方法去定义任何两个可能相继出现的结符号a和b(它们之间可能插有一个非终结符号)之间的优先级。然后利用这种关系比较相邻运算符之间的优先级来确定可归约串并进行归约. 终结符号a与b之间的优先关系有三种： ab 表示a的优先级低于b ab 表示a的优先级等于b ab 表示a的优先级大于b 优点： a）有利于表达式分析，宜于手工实现。 b）使用优先表，只对算符优先比较，占用的存储量比较小，速度快。 缺点： a) 可能错误接受非法句子，能力有限 b) 要求文法必须是算符优先文法，这个条件比较苛刻。 B LR算

27、法 12 定义：从左到右扫描输入串。并且构造一个最右推导的逆过程。 实现思想与方法：LR分析的核心部分是一张分析表。这张分析表包括两部分，一是“动作”(ACTIOB)表，另一是“状态转换”(C0m)表。它们都是二维数组。 优点：对文法要求较低，适合大部分文法。 缺点：算法比算符优先法复杂，占用资源较多，速度较慢。 13 3. 语法分析器的设计和实现 3.1 TINY语言的介绍 1) TINY的程序结构是一个由分号分隔开的语句序列。 2) 既无过程也无声明。 3) 所有的变量都是整型变量，通过对其赋值可较轻易地声明变量。 4) 只有两个控制语句： if语句和repeat语句，这两个控制语句本身也

28、可包含语句序列。If语句有一个可选的else部分且必须由关键字end结束。 5) read语句和write语句完成输入/输出。 6) TINY的表达式只有布尔表达式和整型算术表达式。布尔表达式由对两个算术表达式的比较组成，该比较使用与=比较算符。算术表达式可以包括整型常数、变量、参数以及4个整型算符+、*、/，此外还有一般的数学属性。 例子：一个输出其输入阶乘的TINY语言程序 read x;input an integer if 0x then dont compute if x stmt-sequence stmt-sequence - stmt-sequence;statement|st

29、atement program表示程序, stmt-sequence表示语句序列，statement表示语句 14 由TINY语言介绍中的第2，3，4，5条可知语句分为赋值语句、if语句、repeat语句、read语句和write，其文法表示如下： statement - if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmt (语句) (if语句) A) if语句 而if语句有两种形式： a)if 表达式 then 语句序列 end 例如：if x0 then y:=1 end b)if 表达式 then 语句序列 else 语句序列 end

30、 例如：if x if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence end B) 循环语句 循环语句语句的形式为：repeat 语句序列 until 表达式 例如：repeat fact:=fact*x; x:=x-1 until x=0; 由此可得循环语句语句的文法为： repeat-stmt - repeat stmt-sequence until exp C）赋值语句 由3可知赋值语句的左边为变量，右部为表达式。 形式为：变量：= 表达式|值 例如：x:=x-1 由此可得赋值语句的

31、文法为： 15 assign-stmt - identifier := exp D）读写语句 读写语句形式为：读出 变量 | 写入 变量 例如：read x;input an integer write fact output factorial of x 由此可得读写语句的文法为： read-stmt - read identifier write-stmt - write exp E）布尔表达式和整型算术表达式 表达式的要求： 表达式满足优先顺序，优先顺序从低到高为： 比较运算符 simple-exp comparison-op simple-exp | simple-exp compar

32、ison-op - simple-exp addop term |term addop - +|- 依此类推，我们可以得到表达式的文法如下所示： exp - simple-exp comparison-op simple-exp | simple-exp comparison-op - simple-exp addop term |term addop - +|- 16 term - term mulop factor |factor mulop - *|/ factor - (exp)|number | identifier 其中，exp表示表达式，simple-exp表示算术表达式 ter

33、m表示加法项，mulop表示乘除项，factor表示其他因子 综上所述，可以得到下图TINY的文法如图21所示： program - stmt-sequence stmt-sequence - stmt-sequence;statement|statement statement - if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmt if-stmt - if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence end repeat-stmt

34、 - repeat stmt-sequence until exp assign-stmt - identifier := exp read-stmt - read identifier write-stmt - write exp exp - simple-exp comparison-op simple-exp | simple-exp comparison-op - simple-exp addop term |term addop - +|- term - term mulop factor |factor mulop - *|/ factor - (exp)|number | ide

35、ntifier 粗体表示终结符，如if then +等等。 图2-1 TINY的BNF的文法 3.3 TINY语法分析器算法的选择 选择： 自上而下文法的递归下降分析程序 分析： 17 根据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

36、不能推出,也就是说,不属于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

37、 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 PROGRA