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

TINY-C编译器的与实现-语法分析器的设计与实现 目 录 摘 ‎‎要 ................................................ 3 1. 前 ‎‎ 言 ............................................. 5 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‎‎的文法生成‎‎ ................................................................. 15 3.3 TINY语法分析器算法的选择 ............................................... 18 3.4 TINY语言的递归下降分析程序 ............................................ 21 3.5 TINY语法分析的输出 .......................................................... 23 3.5.1 语法分析的输出结果.................................................. 23 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 测试项目说明 ...................................................................... 40 4.4 测试结论.............................................................................. 44 5. 结论与心得 ........................................ 44 参 考 文 献 .......................................... 45 致 谢 ................................ 错误～未定义签。 附 录‎‎ ................................ 错误～未定义书签。 Contents ‎‎ Abstract .............................................. 4 ‎‎ 1. Preface ............................................ 6 2. Syntax analyzer principle of design .................. 7 2.1 Function of parsing ............................. 7 2.2 Purpose‎‎ and func‎‎tion of parsing .................. 7 2.3 The of parsing analyzer structure ................ 7 2.4 Context-f‎‎ree grammar and anal‎‎ysis ................ 8 ‎‎ 2.5Commonly s‎‎yntax analysis method and several algorithms comparison ...................................... 10 2.5.1 From top to bot‎‎tom analy‎‎tic method.......... 10 2.5.2 From bottom to top analytic method.......... 12 3. Syntax analyzer design and rea‎‎lization .............. ‎‎15 3.1 Introduce of TINY language ...................... 15 3.2 Production of TINY grammar ...................... 15 3.3 Choice of TINY s‎‎yntax ana‎‎lyzer algorithm ......... 18 3.4 Recursion decline analysis programe of TINY ...... 21 3.5 Output of TINY gr‎‎ammar ana‎‎lysis ................. 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 docume‎‎nt and fu‎‎nction of‎‎ syntax analyze 29 3.6.2Parsing module ............................. 30 4. Testing parse ...................................... 40 4.1 Testing method ................................. 4‎‎0 ‎‎ 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编译器的设计与实现 ---‎‎语法分析器的设计与实‎‎现 摘 要 编译器是将一种源语言翻译为目标语言的计算机程序。 本项目采用一种类(ANSI)C 的小型语言:TINY 语言作为源语言，构造‎‎TINY语言的编译器。项目由三人共同‎‎完成，其中本人主要‎‎是完成了语法分析器的构造，主要工作如下: 研究语法分析器的设计原理，并对几种典型的语法分析算法进行分析。生成TINY文法，并证‎‎明该文法为LL(1)文法，在此基础上，‎‎选择递归下降算法实‎‎现TINY语法分析。最终实现了一个TINY语法分析器，它以词法分析器所产生的记号为输入，采用递归下降分析程序进行语法分析，并输出语法树作为下阶段编译的输入。我们最后构造了一个‎‎Deph‎‎i接口程序，显式输出抽象语法树。 关键词 : 编译器 TINY 记号 语法分析 语法树 3 Tiny-C Complier design and realizati‎‎on ‎‎ ---Syntax analyzer design and realization ‎‎ Ren J‎‎un‎‎ Abstract The compiler is a computer program which translates the source language into t‎‎he target ‎‎language. This project uses a language similar to (ANSI) C: Using the TINY language as th‎‎e source l‎‎anguage 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. T‎‎he major w‎‎ork 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 ndation, choosing recursion drop algorithm to realize LL (1) gram‎‎mar, and i‎‎n this fou the TINY grammar analysis.‎‎ A TINY gr‎‎ammar analyzer has thus been accomplished. It applies the symbols which are produced by th‎‎e morpholo‎‎gy analyzer as the input, and uses the recursion drop analysis program to carry on the gra‎‎mmar analy‎‎sis, then output the syntax tree as the input for next compiling phase’s input. We to display the abstract syntax tree. structu‎‎red a Deph‎‎i interface routine at last Keyword :Compiler ， TINY ‎‎，Token ，Syntax an‎‎alysis，Syntax tree 4 1. 前 言 系统概述 在计算机上执行一个高级语言程序一般要分为两步:第一步,用一个‎‎编译程序把高级语言翻‎‎译成机器语言程序;第二步:运行所得的机器语言程序求得计算结果。通常所说的翻译程序是指这样的一个程序,它能够把某一种语言程序转换成另一种语言程序,而后者与前者在逻辑上是等价的。语法分‎‎析器,简称分析器,对‎‎单词符号串进行语法分析(根据语法规则进行推导或规约),识别除各类语法单位,最终判断输入串是否构成语法上的正确的”程序”。 源程序 词法分析器 单词符号 错 语法分析器 误 格处语法单位 理 管 理 词义分析和中间代码产生器 中间代码 优化器 中间代码 目标代码生成器 目标代码 图1-1编译程序框 TINY语言的概述 TINY的程序结构很简单，它在语法上和‎‎Pascal‎‎的语法相似‎‎:仅是一个由分号分隔开的语句序列。另外，它既无过程也无声明。所有的变量都是整型变量，通过对其赋值可较轻易地声明变量(类似FORTRAN或BASIC)。它只有两个控制语‎‎句: if语句和‎‎repeat语句，这两个控制语句本身也可包含语句序列‎‎。If语句有一个可选的else部分且必须由关键字end结束。除此之外，read语句和write语句完成输入/输出。在花括号中可以有注释，但注释不能‎‎嵌套。‎‎ 5 2. 语法分析器的设计原理 2.1 语法分析器的功能 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则‎‎。语法分析器在编译程‎‎序中的地位如图1.1所示。 语法分析树 单词符号 词法分析 语法分析器 编译后续部分 取下一个单词符号 图2.1 语法分析器在编译程序中的地位 2.2 语法分析的目标和作用 1)语法分析的目标是确定程序的‎‎语法，或称作结构，也‎‎正是这个原因，它又被称作语法分析(syntax analysis)。 2)分析过程 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地‎‎构造出表示该结构的分‎‎析树或语法树。因此，可将分析程序看作一个函数，该函数把由扫描程序生成的记号序列作为输入，并生成语法树作为它的输出:记号序列语法树。 2.3 构造语法分析器的步骤 a写出文法 b根据‎‎文法选择合适的分析算‎‎法。 C实现算法 6 2.4 上下文无关文法及分析 实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检‎‎验一个给定字串是否是‎‎由某个上下文无关文法产生的。 1)上下文无关文法定义 在计算机科学中，一个形式文法G = (N Σ P S)称之为上下文无关的，如果它的产生式规则都取如下的形式-> :w ，这V ‎‎里 V?N ， w ‎‎?(N?Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V出现的上下文。一个形式语言是上下文无关的，如果它是由上下文‎‎无关文法生成的,条目‎‎上下文无关语言,。上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法; BNF ,巴克斯-诺尔范式,经常用来表达上下文无关文法。 2)上下文无关文法规‎‎ 则 上下文无关文法规‎‎则确定了为由规则定义的结构的记号符号符合语法的串集。文法规则通过推导确定记号符号的正规串。推导(derivation)是在文法规则的右边进行选择的一个结构名字替换序列。推导以一个结‎‎构名字开始并以记号符‎‎号串结束。在推导的每一个步骤中，使用来自文法规则的选择每一次生成一个替换。 3)上下文无关文法的形式 定义 定义上下文无关文法由以下各项组成: (1) 终结符(terminal)集合‎‎T。 (2) 非终结‎‎符(nonterminal)集合N(与T不相交)。 (3) 产生式(production)(或文法规则grammar r‎‎ule)A?a的集合P，其中A是N的一个元素，a是(T È ,,N)*中的一个元素(‎‎是终结符和非终结符的一个可为空的序列)。 (4) 来自集合N的开始符号(start symbol)。 令G是一个如上所定义的文法，则G = (T, N, P, S)。G上的推导步骤‎‎(derivatio‎‎n 7 step)格式a, Ag Þ ab,g，其中a和g是(T È, N) *中的元素，且有A?b在P中(终结符和非终结符的并集，有时被称作G的符号集，set of symbol)，且(‎‎T È N) *中的‎‎串a被称作句型(sentential form))。将关系a, Þ *b定义为推导步骤关系Þ, 的传递闭包;也就是:假若有零个或更多个推导步骤，就有a Þ *b(n?0)a1 Þ a,,2 Þ ? Þ an‎‎- 1 Þ an其中a=a1，b=a,n (如果n= 0，则a,=b)。在文法G上的推导(derivation)形如S Þ ,*w，且wÎ T *(即:w 是终结符的一个串，称作句子(s‎‎entence))，‎‎S是G的开始符号。 由G生成的语言(language generated by G)写作L (G)，它被定义为集合L (G) = { w Î, T * |存在G的一个推导S Þ *w‎‎}，也就是:L (G‎‎)是由S推导出的句子的集合。 最左推导(leftmost derivation)S Þ *w 是一个推导，在其中的每一个推导步骤aAg Þ ,ab,g都有aÎlmT*，换言之，a 仅‎‎由终结符组成。类似地‎‎，最右推导( rightmost derivation)就是每一个推导步骤aAg, Þ ab,g 都有属性g Î, T*。 文法G上的分析树(parse tree)是一个带有以下属性的作‎‎了标记的树: (1)‎‎ 每个节点都用终结符、非终结符或标出。 (2) 根节点用开始S标出。符号 (3) 每个叶节点都用终结符或标出。 (4) 每个非叶节点都用非终结符标出。 (5) 如带有标记A Î N‎‎的节点有n 个带有标‎‎X1 , 记X2 , . . . Xn ‎‎的孩子(可以是终结符也可以是非终结符)，A?X就有1 , X2 , . . . Xn ‎‎PÎ (文法的一个产生式)。每一个推导都引出一个分析树‎‎，这个分析树中的每一Ag Þ ‎‎,a个步骤,bg a都在推导中，且b= X1 X, 2 , . Xn . . 与带‎‎有标记X1 , X2 , . Xn . .的n 个孩子的结构相对应，X其1 , 中X2 ‎‎, . . . Xn ‎‎带有标记A。许多推导可引出相同的分析树。但每个分析树只有唯一的一个最左推导和一个最右推导。 最左推导与分析树的前序编号相对应，而与之相反，最右推导与分析树的后序编号相对应。若上下‎‎文无关文法G有L=L‎‎G)，就将串(L的集合称作上下文无关( c 语言ontext-freel anguage)。一般地，许多不同的文法可以生成相同的上下文无关语言，但是根据所使用的文法的不同，语言中的‎‎串也会有不同的分析树‎‎。若存在串w Î ,L (G)，其中w 有两个不同的分析树(或最左推导或最右推导)，那么文法G就有二义性(ambiguou s)。 8 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)文法不含左递归 ‎‎ 9 2)对于文法的每一个非‎‎终结符A的各个产生式的候选首符集两两不相交。即:FIRST(α)?FIRST(β),Φ;它们不应该都能推出空字ε; 3)对于文法中的每个非终结‎‎符A，若它存在某个候选首符集包含‎‎ε。即:‎‎假若β包含ε,那么,FIRST(α)? FOLLOW(A),Φ. 4)主要算法 A(递归下降分析程序 定义:若一个文法G不含有左递归，而且每个非终结符的所有候选式的‎‎首符集都是两两不相交的，那么就能‎‎为G中每个非终结符编写一个相应的递归过程。把该文法中所有这样的递归过程组合起来就可能构成一个不带回溯的自上而‎‎下分析程序——递归下降分析程序。 实现思想:为文法中每个非终结符编写一个递‎‎归过程，每个过程的‎‎功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，按LL(1)形式唯一确定选择哪个候选式进行推导，若遇到某候选式为e，认为其自动匹配。把这些递归过程组合起来就构成了‎‎文法的递归下降分析‎‎程序。 实现方法: a)使用LL(1)文法 先将文法消除左递归、提取公共左因子，使之成为LL(1)文法，后将每个非终结符对应一个递归过程，过程体是按照相应产生式的‎‎右部符号串顺序编‎‎写。每匹配一个终结符，则再读入下一个符号，对产生式右部的每个非终‎‎结符，则调用相应的过程。 b)使用BNF范式 先将文法改写为BNF形式，后再书写递归子程序。‎‎ 10 优点:容易理解。‎‎ 缺点 a)对文法的要求高，必须满足LL(1)文法。 b)高深度的递归调用会影响语法分析的效率，速度慢，占空间多。 B(预测分析程序 定义:使用高级语言的递归过程描述递归下降分析器，‎‎只有当具有实现这种‎‎‎过程的编译系统时才有实际意义。实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。 实现思想: 预测分析程序就是属于这种类型的LL(1)分析器。‎‎ 实现方法: 构造分析表和栈，‎‎设栈顶符号为X，读入符号为a，则 a)若X=a=‘#’，则表示识别成功，退出分析程序; b)若X=a?’#’，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个‎‎符号，以读入下一个符‎‎号;若X是终结符，但X?a，则调用error处理; c)若X，则查ÎV预测分析表M。若M[X,a]中存放着关于X的产生式，则弹出N X，且将相应产生式右部以自右向左的顺序压入栈，在输‎‎出带上记下产生式编号‎‎;若M[X,a]中存放着出错标记，则调用相应Error处理。 优点:过程比递归分析的效率高，速度快，占空间少，仅用表结构。 缺点: 对文法的要求高，必须满足LL(1)文法。 2.5.2‎‎自下而上分析法 ‎‎1)定义:所谓自下而上分析法就是从输入串开始，逐步进行“规约”， 直至规约到文法的开始符号;或者说从语‎‎法树的末端开始，步步向上“规约”，直到根结。 11 2)优点:从输入符号串开始‎‎分析开始分析，因此进‎‎行语法分析和进行语义分 析可以在一遍内进行，而自上而下的分析法是从根节点开始进行语法分析， 因此必须先经过一遍扫描建立语法树，让后再经过一遍扫描进行语法分析。 因此自下而上的分析法效率更‎‎高。 3)缺点:和人的思想相反，不容易‎‎理解，算法更复杂。‎‎ 4) 主要算法 A( 算符优先分析法 定义:定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这 种优先关系寻找“可归约串”和进行归约。 实‎‎现思想:优先表构造优‎‎先函数，寻找最作素短语。(设算符G是一个文 法，β是句型 baδ关于A的短语(即有S->αAδ且A->β )且β至少含有一个 终结符号，并且除自身之外不再含有任何更小的 带有终结符号的短语，则‎‎ 称β是句型αβδ‎‎关于A的素短语。所谓最左素短语是指处于句型最左边的‎‎ 那个素短语。) 实现方法: 算符优先分析法自底向上地分析句子，解决了前面提到的两个问题，即: 1)可以只根据相邻运算符的优‎‎先关系，就能方便地并‎‎且唯一地确定归约的“句柄”; 2)可以用来分析二义性文法所产生的语言。 是仿照算术表达式的四则运算过程而设计的一种语法分析方法。 终结符号 运算符 非终结符号 运算对象 算符优先分‎‎析法的关键在于用合适‎‎的方法去定义任何两个可能相继出现的结符号a和b(它们之间可能插有一个非终结符号)之间的优先级。然后利用这种关系比较相邻运算符之间的优先级来确定可归约串并进行归约. 终结符号a与b‎‎之间的优先关系有三种‎‎: 12 a,?b 表示a的优先级低于b a?b 表示a的优先级等于b a?,b 表示a的优先级大于b 优点: a)有利于表达式分析，宜于手工实现。 b)使用优先表，只对算符优先比较，占用的存储量比‎‎‎‎较小，速度快。 缺点: a) 可能错误接受非法句子，能力有限 b) 要求文法必须是算符优先文法，这个条件比较苛刻。 B( LR算法 定义:从左到右扫描输入串。并且构造一个最右推导的逆‎‎过程。 实现思想与方‎‎法:LR分析的核心部分是一张分析表。这张分析表包括两部分，一是“动作”(ACTIOB)表，另一是“状态转换”(C0m)表。它们都是二维数组。 优点:对文法要求较低，适合大部分文法。 ‎‎ 缺点:算法比算符优先法复杂，占用资源‎‎较多，速度较慢。 13 3. 语法分析器的设计和实现 3.1 TINY语言的介绍 1) TINY的程序结构是一个由分‎‎号分隔开的语句序列。‎‎ 2) 既无过程也无声明。 3) 所有的变量都是整型变量，通过对其赋值可较轻易地声明变量。 4) 只有两个控制语句: if语句和repeat语句，这两个控制语句本身也可包含语‎‎句序列。If语句有一‎‎个可选的else部分且必须由关键字end结束。 5) read语句和write语句完成输入/输出。 6) TINY的表达式只有布尔表达式和整型算术表达式。布尔表达式由对两个算术表达‎‎式的比较组成，该比较‎‎使用<与=比较算符。算术表达式可以包括整型常数、变量、参数以及4个整型算符+、,、*、/，此外还有一般的数学 属性。例子:一个输出其输入阶乘的TINY语言程序 read x;{i‎‎nput an in‎‎teger} if 0 stmt-sequence stmt-sequence -> stmt-sequence;statement|st‎‎atement pr‎‎ogram表示程序, stmt-sequence表示语句序列，statement表示语句 语言介绍中的第2，3，4，5条可知语句分为赋值语句、if语句、repeat由TINY 语句‎‎、read语句和wr‎‎ite，其文法表示如下: statement -> if-stmt;repeat-stmt;assign-stmt;read-stmt;write-stmt (语句) ‎‎ (if语句)(循环‎‎语句)(赋值语句)(读语句) (写语句) A) if语句(if-stmt) 而if语句有两种形式: a)if 表达式 then 语句序列 end x<0 then ‎‎y:=1 end 例如:if b‎‎)if 表达式 then 语句序列 else 语句序列 end 例如:if x<0 then y:=1 else y:=0 end 由此可得if语句的文法为:(e‎‎xp表示参考量) ( ‎‎if-stmt ->‎‎ if exp then stmt- sequence end | if exp then stmt- sequence else stmt-sequence e‎‎nd 15 B) 循环语‎‎句(repeat-stmt) 循环语句语句的形式为:repeat 语句序列 until 表达式 例如:repeat fact:=fact*x; ‎‎ x:=x-1 u‎‎ntil x=0; 由此可得循环语句语句的文法为: repeat-stmt -> repeat stmt-sequence until exp C)赋值语句(assign-stm‎‎) 由3可知赋值语句‎‎的左边为变量(标识符)，右部为表达式。 形式为:变量:= 表达式|值 例如:x:=x-1 由此可得赋值语句的文法为: assign-stmt -> identifier := ex‎‎p D)读写语句(‎‎read-stmt和write-stmt) 读写语句形式为:读出 变量 | 写入 变量 例如:read x;{input an integer} w‎‎rite fact ‎‎{output factorial of x} 由此可得读写语句的文法为: read-stmt -> read identifier write-stmt -> write exp‎‎ E)布尔表达式和‎‎整型算术表达式 表达式的要求: 表达式满足优先顺序，优先顺序从低到高为: 比较运算符<和, ? 加和减 ? 乘和除 ? 括号 算术运算是左结合，布尔表达式由对两‎‎个算术表达式的比较组‎‎成，无结合关系。 为‎‎了满足以上优先关系，我们可以认为表达式为布尔表达式和算术表达式 16 两种，而布尔表达式由对两个算术表达式的比较组成，这样，比较运算将最后进行，因此比较运算的优先级最低。 exp -‎‎> simple-e‎‎xp comparison-op simple-exp | simple-exp comparison-op -> <| = 类似的，算术表达式由加法项(term表示)构成。这时，‎‎加减法在算术运算中最‎‎后进行，因此在算术运算中加减法的优先级最低。另外加减法必须满足左结合原则，因此递归项simple-exp置于产生式右部的最左边 。 simple-exp -> simple-exp ‎‎addop term‎‎ |term addop -> +|- 依此类推，我们可以得到表达式的文法如下所示: exp -> simple-exp comparison-op simple-exp | si‎‎mple-exp c‎‎omparison-op -> <| = simple-exp -> simple-exp addop term |term addop -> +|- term -> term m‎‎ulop facto‎‎r |factor mulop -> *|/ factor -> (exp)|number | identifier 其中，exp表示表达式，simple-exp表示算术表达式 t‎‎erm表示加法项，m‎‎ulop表示乘除项，factor表示其他因子(数字或标示符) 综上所述，可以得到下图TINY的文法如图2,1所示: program -> stmt-sequence stmt-‎‎sequence -‎‎> stmt-sequence;statement|statement statement -> if-stmt;repeat-stmt;assign-stmt;read-stm‎‎t;write-st‎‎mt if-stmt -> if exp then stmt- sequence end | if exp then stmt- sequence else st‎‎mt-sequenc‎‎e end repeat-stmt -> repeat stmt-sequence until exp assign-stmt -> identifier := exp read-‎‎stmt -> re‎‎ad identifier 17 write-stmt -> write exp exp -> simple-exp comparison-op simple-exp | simple-‎‎exp compar‎‎ison-op -> <| = simple-exp -> simple-exp addop term |term addop -> +|- term -> term mulop ‎‎factor |fa‎‎ctor mulop -> *|/ factor -> (exp)|number | identifier 粗体表示终结符，如if then +等等。 图2-1 TINY的BNF的‎‎文法 3.3 TINY‎‎语法分析器算法的选择 选择: 自上而下文法的递归下降分析程序 分析: 根据2.2节中TINY的文法生成，可以计算TINY文法的FIRST集合和Follow集合。 A(F‎‎IRST集合的定义 ‎‎FIRST(X)表示X所有可能推出的开始终结符,包括ε. 1,显然，若X为终结符，则FIRST(X) = {X}。 2,如果X为非终结符两种情况:，有 „ (1)若有产生式 X?,则把‎‎aa加入FI‎‎RST(X)中; 若有产生式 X?ε,则把ε加入FIRST(X)中. „ (2)若有产生式 X, Y?Y 是非终结符, ?如果Y不能推出ε,也就是说,ε不属于FIRS‎‎T(Y),那么X所能‎‎推出的开头 终结符也就是Y所能推出的开头终结符.我们把FIRST(Y)加入FIRST(X)中. ?如果Y能推出ε,即FIRST(Y)中包含ε,假设跟在Y后的,那么当符‎‎‎号为 Y2我们用ε匹配Y时,X‎‎所能推出的开头终结符所能推出就为Y的开头终结符(不2 包括ε).也就是说在这种情况下, X所能推出的开头终结符不但包括Y所能推出 的除ε之外的开头终结符也应包括所Y能推出的除ε之外的‎‎开头终结符.应把2 FI‎‎RST(Y)和FIR)中所ST(Y有非ε-元素加入FIRST(X)中. 2 FIRST集合计算结果: PROGRAM 的 FIRST集:{ IF REPEAT A‎‎SSIGN READ WRITE } ‎‎ STMT_SEQUE‎‎NCE 的 FIRST集:{ IF REP‎‎EAT ASSIGN READ WRITE } STATEMENT 的 FIRST集:{ IF REPEAT ASSI‎‎‎GN READ WRITE } ‎‎ IF_STMT 的 FIRST集:{ IF PROGRAM } REPEAT_STMT 的 FIRST集: { REPEAT PROGRAM } 18 ASSIGN_STMT ‎‎的 FIRST‎‎集: { IDENTIFIER PROGRAM } READ_STMT 的 FIRST集: { READ PROGRAM } WRITE_STMT 的 FIRST集: { WRITE PROG‎‎RAM } ‎‎ EXP 的 FIRST集: { LPAR NUMBER IDENT‎‎IFIER PROGRAM } SIMPLE_EXP 的 FIRST集: { LPAR NUMBER IDENTIFI‎‎ER PROGRA‎‎M } 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集:{ IDENTIFIE‎‎R } IF 的 FIRST集: { IF } THEN 的 FIRST集: {‎‎ THEN } ELSE 的 FIRST‎‎集: { ELSE } ‎‎ END 的 FIRST集: { END }‎‎ REPEAT 的 FIRST集: { REPEAT } UNTIL 的 FIRST集:{ UNTIL } READ 的 FIRST‎‎集: { READ } ‎‎ WRITE 的 FIRST集: { WRITE } ST集: { ADD } ADD 的 FIR 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) 若存在产生式B?αAβ,α,β为符号串,那么紧跟A之后的终结 符应为β的第一个终结符(不包括ε),因此将First(β)-{ε}加入Follow(A)中。 (3) 若存‎‎在产生式B?αA, ‎‎那么紧跟B的终结符也可能是紧跟A的终结符,因此要将Follow(B)加入Follow(A)中. (4) 若存在产生式B?αAβ，而β=>ε,即ε?FIRST(β).那么如果用ε匹配‎‎β,就有以下推导: ‎‎B=>αA,在这种情况下, 紧跟B的终结符也可能是紧跟A的终结符,因此要将Follow(B)加入Follow(A)中. 注意:根据规则3和4,如果存在B?αA 或 B?αAβ，而β‎‎=>ε.那么当Fol‎‎low(B)改变时, Follow(A)也会改变.因此计算文法G中所有非终结符的Follow集合时,一趟计算是不够的.只有当文法中所有非终结符的Follow集合 19 都不再发生变化时,我‎‎们才能结束对文法中非‎‎终结符的Follow集合的计算. FOLLOW集合的结果: PROGRAM 的 FOLLOW集: { DOUBLE_CROSS } STMT_SEQUENCE 的 FOLLOW集‎‎: { DOUBLE_CROSS EN‎‎D ELSE UNTIL } STATEMENT 的 FOLLOW集: { SEMICOLON DOUBLE_CROSS PROGRAM EN‎‎D ELSE UNTIL } ‎‎IF_STMT ‎‎的 FOLLOW集: { SEMICOLON DOUBLE_CROSS PROGRAM END ELSE UNTIL } REPEA‎‎T_STMT 的 FOLLOW集: { SEMICOLO‎‎N 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_C‎‎ROSS RPAR‎‎ PROGRAM END ELSE UNTIL } SIMPLE_EXP 的 FOLLOW集: { LESS EQUAL THEN SEMICOLON DOUBLE_CROSS ‎‎ PROGRAM RP‎‎AR END ELSE UNTIL } COMPARISON‎‎_OP 的 FOLLOW集: { LPAR NUMBER IDENTIFIER PROGRAM } ‎‎ADDOP 的 FOLLOW‎‎集: { LPAR NUM‎‎BER IDENTIFIER PROGRAM } ULOP 的 FOLLOW集: { LPAR NUMBER IDENTIFIER PROGRAM } ‎‎M 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 PROG‎‎‎RAM RPAR END ELSE ‎‎ UNTIL } 首先判断出文法的每一个非终结符A的各个产生式的候选首符集两两不相交。即:FIRST(α)?FIRST(β),Φ;它们不能推出空字ε; 其次是对于文法中的每个非终‎‎结符‎‎A，它存在的某个候选首符集包含ε。即:假若β包含ε,那么,FIRST(α)? FOLLOW(A),Φ. 结论: 由此可以确‎‎定是满足LL(1)条件，我们就可以为它构造一个不带回溯的自上‎‎而下分析程序，而且‎‎TINY语句简单‎‎只有5类，并且语句分析程序是由一组递归过程组成，所以选择递归下降分析。 20 3.4 TINY语言的递归下降分析程序 编译说穿了是对一个数据流进行逐字的分析， 把分析‎‎过程看做是不断的读取‎‎数据，是实现程序的一个基本思想。现在让我们自顶而下地对表达式进行分析，自顶向下(top - down)的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为‎‎自顶向下是由于分析树‎‎隐含的编号是一个前序编号，而且其顺序是由根到叶递归下降分析的概念极为简单:将一个A‎‎的非终结符文法规则看作将识A的一个过别程的定A义。的文法规则的右边指出这个过程的代码结构:一个选择‎‎中的终结符与非终结符‎‎序列与相匹配的输入以及对其他过程的调用相对应，而选择与在代码中的替代情况(case语句和if语句)相对应。 TINY递归下降程序中使用的是比BNF更加完善的EBNF-TINY语言的‎‎文法，如下: pro‎‎gram -> stmt-sequence stmt-sequence -> stmt-sequence {;statement} statement -> if-stmt|re‎‎peat-stmt|‎‎assign-stmt|read-stmt|write-stmt if-stmt -> if exp then stmt- sequence [else stmt-sequence‎‎] end repe‎‎at-stmt -> repeat stmt-sequence until exp assign-stmt -> identifier := exp read-stmt -> re‎‎ad identif‎‎ier write-stmt -> write exp exp -> simple-exp [ comparison-op simple-exp ] comparison-op -‎‎> <| = sim‎‎ple-exp -> term { addop term } addop -> +|- term -> factor{ mulop factor } mulop -> *|/ ‎‎factor -> ‎‎(exp)|number | identifier 分析程序构造了语法树，除此之外，它还将语法树的表示打印到列表文件中。 TINY分析程序完全按照递归下降程序的要点，‎‎这个分析程序包括两个‎‎代码文件:parse.h和parse.c。parse . h文件。另外:它由一个声明 21 TreeNode * parse (void); 组成，它定义了主分析例程parse，pars‎‎e又返回一个指向由分‎‎析程序构造的语法树的指针。parse.c文件，它由11个相互递归的过程组成，这些过程与BNF文法直接对应:一个对应于stmt - sequence，一个对应于statement，5‎‎个分别对应于5种不同‎‎的语句，另有4个对应于表达式的不同优先层次。操作符非终结符并未包括到过程之中，但却作为与它们相关的表达式被识别。这里也没progra有过程m‎‎与相对应，这是因为一个程序就是一个语句序‎‎列，所以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) ne‎‎wStmtNode，‎‎它取用一个指示语句种类的参数，它还在分配该类的新语句节点的同时返回一个指向新分配的节点的指针。 2) newExpNode，它取用一个指示表达式种类的参数，它还在分配该类新表达式节‎‎点的同时返回一个指向‎‎新分配的节点的指针。 3) copyString，它取用一个串参数，为拷贝分配足够的空间，并拷贝串，同时返回一个指向新分配的拷贝的指针。 由于C语言不为串自动分配空间，且扫描程序会‎‎为它所识别的记号的串‎‎值(或词法)重复使用相同的空间，所以copyString过程是必要的。 util.c中也包括了过程printTree，util.c将语法树的线性版本写在了列表中，这样就能看到分析的‎‎结果了。这个过程在全‎‎程变量trace Parse控制之下从主程序中调用。通过打印节点信息以及在此之后缩排到孩子信息中来操作printTree 22 过程;从这个缩排中可构造真正的树。 3.5 TINY语法分析的输出‎‎ 3.5.1 语法分析的输出结果‎‎ 输出:抽象语法树 抽象语法树是表述记号串结构的一种十分有用的表示法。在分析树中，记号表现为分析树的树叶(自左至右)，而分析树的内部节点则表示推导的各个‎‎步骤(按某种顺序)。‎‎但是，分析树却包括了比纯粹为编译生成可执行代码所需更多的信息。 这种树是真正的源代码记号序列的抽象表示。虽然不能从其中重新得到记号序列(不同于分析树)，但是它们却包含了转换所需的所‎‎有信息，而且比分析树‎‎效率更高。这样的树称作抽象语法树(abstract syntax tree)或简称为语法树(syntax tree)。分析程序可通过一个分析树表示所有步骤，但却通常只能构造出一个抽‎‎象的语法树(或与它等‎‎同的)。 3.5.2 抽象语法树的节点声明 TINY有两种基本的结构类型:语句和表达式。语(句共有if语5类句、repea t语句、assign语句、read语句和write语句)‎‎，表达式共有3类(算‎‎符表达式、常量表达式和标识符表达式)。因此，语法树节点首先按照它是语句还是表达式来分类，接着根据语句或表达式的种类进行再次分类。树节点最大可有3个孩子的结构(仅在带有else部分的‎‎if语句中才需要它们‎‎)。 它们还可帮助提醒每个节点类型的属性。现在谈谈说明中两个未曾提到过的属性。第1个是簿记属性lineno;它允许在转换的以后步骤中出现错误时能够打印源代码行数。第2个是type域‎‎，在后面的表达式(且‎‎仅是表达式)类型检查中会用到它。它被说明为枚举类型ExpType。 TINY语法树节点的C声明: typedef enum {StmtK,ExpK} NodeKind;//定义语句‎‎和表达式节点 typ‎‎edef enum {IfK,RepeatK,AssignK,ReadK,WriteK} StmtKind;//定义5类语句 23 typedef enum {OpK,ConstK,Id‎‎K} ExpKind‎‎;//定义操作符，值，标示 typedef enum {Void,Integer,Boolean} ExpType;//表达式类型检测 #define MAXCHILDREN ‎‎3 typedef‎‎ struct treeNode//语法树结构 { struct treeNode * child[MAXCHILDREN]; struct treeNode * ‎‎sibling; ‎‎ int lineno; NodeKind nodekind; union { StmtKind stmt; ExpKind exp;} kind; ‎‎ union {‎‎ TokenType op; int val; char * name; } attr; ExpType type; ‎‎ } Tree‎‎Node; 3.5.3 语法树结构 抽象语法树的表示和在运行界面中的显示: 现在将语法树结构的描述用图形表示出来，并且画出示例程序的语法树。为了做到这一点，我们使用矩形框表‎‎示语句节点，用圆形框‎‎或椭圆形框表示表达式节点。语句或表达式的类型用框中的标记表示，额外的属性在括号中也列出来了。属性指针画在节点框的右边，而子指针则画在框的下面。我们还在图中用三角形表示额外的非指定的‎‎树结构，其中用点线表‎‎示可能出现也可能不出现的结构。语句序列由同属域连接(潜在的子树由点线和三角形表示)。则该图如下: 24 图3-2 1) if 语句‎‎(带有3个可能的孩子‎‎)如下所示: 图3-3 IF语句 例如:在界面中的显示if语句(IF) 输‎‎入: if 0 < ‎‎x then x=y+1 end 输出: If // 根节点为IF，表示这是个IF语句 Op: < //IF语句的第一个孩子为表达式，‎‎用表达式的操作符 表‎‎示该表达式节点 Const: 0 Id: x Assign to: x Op: + Id: x Co‎‎nst: 1 2)‎‎ repeat 语句有两个孩子。第1个是表示循环体的语句序列，第2个是一个测试 表达式: 25 图3-4 repeat 语句 例如:在界面中的显示循环语句(repeat 语句) 输‎‎入: ‎‎ repeat fact := fact * x; x := x - 1 until x = 0; en‎‎d 输出: ‎‎ Repeat // 根节点为Repeat，表示这是个循环语句 Assign to: fact // Repeat语句的第一个孩子为赋值 ‎‎ Op: * ‎‎ Id: fact Id: x Assign to: x // Repeat语句的第二个孩子为赋值 O‎‎p: - ‎‎ Id: x Const: 1 Op: = Id: x Cons‎‎t: 0 3) as‎‎sign 语句有一个表示其值是被赋予的表达式的孩子(被赋予的变量名保存在语句节点中): 26 图3-5 assign 语句 例如:在界面中的显示赋值语句(assi‎‎gn 语句) 输入:‎‎fact := 1; 输出:Assign to: fact // 根节点为Assign，表示这是个赋值语句 Const: 1 4) write 语句也有‎‎一个孩子，它表示要写‎‎出值的表达式: ‎‎ 图3-6 write 语句 例如:在界面中的显示读写语句(read-stmt和write-stmt) 输入:read x; fact:=1; write‎‎ fact 输出: ‎‎ Read: x // 根节点为READ，表示这是个读语句 Assign to: fact Const: 1 ‎‎ W‎‎rite // 同层次的根节点为Write，表示这是个写语句 Id: fact 5) 算符表达式有两个孩子，它们表示左操作数表达式和右操作数表达式:‎‎ 27 ‎‎ 图3-7 算符表达式 例如:在界面中的显示布尔表达式和整型算术表达式 输入:fact := 1; fact := fact * 10; 输出: Assign ‎‎to: fact ‎‎// 根节点为Assign，表示这是个赋值语句 Const: 1 Assign to: fact // 同层次根节点Assign，表示这是个赋‎‎值语句 Op: ‎‎* //第一个孩子为表达式，用表达式的操作符 表示该表达式节点 Id: fact Const: 10 其他所有的节点(read语句、标识符表达式‎‎和常量表达式)都是叶‎‎子节点。 3.6 语法分析的主要函数与核心代码 3.6.1 语法分析器的主要文件和函数 globals.h mai‎‎n.c util.h util.c ‎‎(工具集) scan.h ‎‎ scan.c (扫描程序，即词法分析) parse.h parse.c (分析程序，即语法分析) 28 语法分析程序主要的‎‎函数(11个递归调用‎‎函数): static TreeNode * stmt_sequence(void); /* 语句序列 */ static TreeNode * statement(vo‎‎id); ‎‎ /* 语句 */ static TreeNode * if_stmt(void); /* if语句 */ static TreeNode * repe‎‎at_stmt(vo‎‎id); /* 循环语句 */ static TreeNode * assign_stmt(void); /* 赋值语句 */ static TreeN‎‎ode * read‎‎_stmt(void); /* 输入语句 */ static TreeNode * write_stmt(void); /* 输出语句 */ st‎‎atic TreeN‎‎ode * exp(void); /* 表达式 */ static TreeNode * simple_exp(void); /* 简‎‎单表达式 */ st‎‎atic TreeNode * term(void); /* 乘法项 */ static TreeNode * factor(void); ‎‎ /* 因‎‎子 */ 另外还有6个重要函数: 1)-打印语法树 void printTree( TreeNode * tree ) 2)-分配该类的新语句节点 TreeNode * newSt‎‎mtNode(Stm‎‎tKind kind) 3)-分配该类新表达式节点 TreeNode * newExpNode(ExpKind kind) 4)-为拷贝分配足够的空间，并拷贝串 char * co‎‎pyString(c‎‎har * s) 5)-保存向前看记号的静态变量token和检测输入的记号是否和预期相同 static void match(TokenType expected) 6)-‎‎ 显示出错信息 st‎‎atic void syntaxError(char * message) 3.6.2 语法分析模块 功能:确定程序的语法，从由扫描程序产生的记号中确定程序的语法结构， 以及或隐式‎‎或显式地构造出表示该‎‎结构的语法树 29 输入项目:扫描程序产生的记号。 输出项目:表示该程序结构的语法树。 界面: 图3-8语法分析结果-语法树 原代码主要‎‎包括parse.h ‎‎ 和parse.c: /****************************************************/ /* 文件:parse.h ‎‎ ‎‎ */ /* TINY编译器的语法分析接口 */ /********************************************‎‎********/ ‎‎#include "globals.h" #ifndef _PARSE_H_ #define _PARSE_H_ /* * 函数parse返回最近被构建的语法树 */ 30 Tr‎‎eeNode * p‎‎arse(void); #endif /****************************************************/ /* 文件: parse.c ‎‎ ‎‎ */ /* TINY编译器的语法分析执行程序 */ /*************************‎‎**********‎‎*****************/ #include "globals.h" #include "util.h" #include "scan.h" #include "par‎‎se.h" sta‎‎tic TokenType token; /* 保留当前的记号 */ */ /* 递归调用时候的函数原型 static TreeNode * stmt_sequence(void‎‎); /*‎‎ 语句序列 */ static TreeNode * statement(void); /* 语句 */ static TreeNode * if_stmt(vo‎‎id); ‎‎ /* if语句 */ static TreeNode * repeat_stmt(void); /* 循环语句 */ static TreeNode * ‎‎assign_stm‎‎t(void); /* 赋值语句 */ static TreeNode * read_stmt(void); /* 输入语句 */ static T‎‎reeNode * ‎‎write_stmt(void); /* 输出语句 */ static TreeNode * exp(void); /* 表达式 */‎‎ static Tr‎‎eeNode * simple_exp(void); /* 简单表达式 */ static TreeNode * term(void); ‎‎ /* 乘法项 */‎‎ static TreeNode * factor(void); /* 因子 */ /* 显示出错信息*/ 31 static void syntaxError‎‎(char * me‎‎ssage) { /*fprintf(errorout,"\n>>> ");*/ fprintf(errorout,"Syntax error at line %d:‎‎ %s\n",lin‎‎eno,message); Error = TRUE; } /* 保存向前看记号的静态变量token和检测输入的记号是否和预期相同 */ static void match(‎‎TokenType ‎‎expected) { char msgerror[100]; /*它找到匹配时就调用getToken，否则就声明出错*/ if (token == expected‎‎) token = ‎‎getToken(); else { strcpy(msgerror,"unexpected token -> "); strcat(msgerror,toke‎‎nString); ‎‎ syntaxError(msgerror); /*syntaxError("unexpected token -> "); printToken(token‎‎,tokenStri‎‎ng); fprintf(listing," ");*/ } } /* 用来匹配非终结符stmt_sequence */ TreeNode * stmt_se‎‎quence(voi‎‎d) { TreeNode * t = statement(); TreeNode * p = t; /* 当输入的记号不标识语句序列结束的记号 */ while ((‎‎token!=END‎‎FILE) && (token!=END) && (token!=ELSE) && (token!=UNTIL)) 32 { TreeNode * q; /* ‎‎跳过分号 */ ‎‎ match(SEMI); q = statement(); if (q!=NULL) { if (t==NULL) t = p = q; ‎‎ else /* 如‎‎果t不是NULL，那么p也一定不是NULL */ { /* 把state链接起来 */ p->sibling = q; ‎‎ p = q; ‎‎ } } } return t; } /* 用来匹配statement非终结符 */ TreeNode * statement(void) { c‎‎har msgerr‎‎or[100]; TreeNode * t = NULL; /* 检测当前的token，根据输入决定如何识别 */ switch (token) { case ‎‎IF : t = i‎‎f_stmt(); break; case REPEAT : t = repeat_stmt(); break; case ID : t = assign_stmt‎‎(); break;‎‎ case READ : t = read_stmt(); break; case WRITE : t = write_stmt(); break; /* 出错，没‎‎有预料到的输入 */‎‎ 33 default : strcpy(msgerror,"unexpected token -> "); strca‎‎t(msgerror‎‎,tokenString); syntaxError(msgerror); /*syntaxError("unexpecte‎‎d token ->‎‎ "); printToken(token,tokenString);*/ token = getToken(); ‎‎ ‎‎break; } return t; } /* 用来匹配if_stmt非终结符 */ TreeNode * if_stmt(void) { TreeNode * t = ‎‎newStmtNod‎‎e(IfK); match(IF); if (t!=NULL) t->child[0] = exp(); match(THEN); if (t!=NULL) t->‎‎child[1] =‎‎ stmt_sequence(); if (token==ELSE) { match(ELSE); if (t!=NULL) t->child[2] = stm‎‎t_sequence‎‎(); } match(END); return t; } /* 用来匹配repeat_stmt非终结符 */ TreeNode * repeat_stmt(void)‎‎ { TreeNod‎‎e * t = newStmtNode(RepeatK); match(REPEAT); 34 if (t!=NULL) t->child[0] = stmt_sequence(‎‎); match‎‎(UNTIL); if (t!=NULL) t->child[1] = exp(); return t; } /* 用来匹配assign_stmt非终结符 */ TreeN‎‎ode * assi‎‎gn_stmt(void) { TreeNode * t = newStmtNode(AssignK); if ((t!=NULL) && (token==ID)) t‎‎->attr.nam‎‎e = copyString(tokenString); match(ID); match(ASSIGN); if (t!=NULL) t->child[0] = ex‎‎p(); ret‎‎urn t; } /* 用来匹配read_stmt非终结符 */ TreeNode * read_stmt(void) { TreeNode * t = newStmtNode(R‎‎eadK); m‎‎atch(READ); if ((t!=NULL) && (token==ID)) t->attr.name = copyString(tokenString); ‎‎match(ID);‎‎ return t; } /* 用来匹配write_stmt非终结符 */ TreeNode * write_stmt(void) { TreeNode * t = newSt‎‎mtNode(Wri‎‎teK); match(WRITE); if (t!=NULL) t->child[0] = exp(); 35 return t; } /* 用来匹配exp非终结符 */ ‎‎TreeNode *‎‎ exp(void) { TreeNode * t = simple_exp(); if ((token==LT)||(token==EQ)) { TreeNode *‎‎ p = newEx‎‎pNode(OpK); if (p!=NULL) { p->child[0] = t; p->attr.op = token; t = ‎‎p; } ‎‎ match(token); if (t!=NULL) t->child[1] = simple_exp(); } return t; } /* 用‎‎来匹配simple_‎‎stmt非终结符 */ TreeNode * simple_exp(void) { TreeNode * t = term(); while ((token==PLUS)||(‎‎token==MIN‎‎US)) { TreeNode * p = newExpNode(OpK); if (p!=NULL) { p->child[0] = t; p‎‎->attr.op ‎‎= token; t = p; match(token); t->child[1] = term(); 36 } } return t‎‎; } /* 用来匹‎‎配term非终结符 */ TreeNode * term(void) { TreeNode * t = factor(); while ((token==TIMES)||(to‎‎ken==OVER)‎‎) { TreeNode * p = newExpNode(OpK); if (p!=NULL) { p->child[0] = t; p->a‎‎ttr.op = t‎‎oken; t = p; match(token); p->child[1] = factor(); } } return t;‎‎ } /* 用来匹配‎‎factor非终结符 */ TreeNode * factor(void) { char msgerror[100]; TreeNode * t = NULL; ‎‎ switch (‎‎token) { case NUM : t = newExpNode(ConstK); if ((t!=NULL) && (token==NUM))‎‎ t‎‎->attr.val = atoi(tokenString); 37 match(NUM); break; case ID : t = new‎‎ExpNode(Id‎‎K); if ((t!=NULL) && (token==ID)) t->attr.name = copyString(tokenString); ‎‎ match(‎‎ID); break; case LPAREN : match(LPAREN); t = exp(); match(RPAR‎‎EN); ‎‎ break; default: strcpy(msgerror,"unexpected token -> "); strcat(msgerro‎‎r,tokenStr‎‎ing); syntaxError(msgerror); /*syntaxError("unexpected token -> "); pr‎‎intToken(t‎‎oken,tokenString);*/ token = getToken(); break; } return t; } /********‎‎**********‎‎**********************/ /* 语法分析程序的主函数 */ /**************************************‎‎**/ /* 38 * ‎‎函数parse返回最近被构建的语法树 */ TreeNode * parse(void) { TreeNode * t; token = getToken(); t = ‎‎stmt_seque‎‎nce(); if (token!=ENDFILE) syntaxError("Code ends before file\n"); return t;} ‎‎ 4. 测试分析‎‎ 4.1 测试方法 a)编写目的: 通过测试暴露软件中隐藏的错误和缺陷，以考虑是否可以接受该产品。 b)项目背景: TINY编译器语法分析阶段。 4.2 测试计划 a‎‎)测试方案: 1)对预先‎‎定义的TINY文法进行测试。 39 2)随机编写任意语法结构进行测试。 b)测试项目 语法错误 4.3 测试项目说明 4.3.1 测试项目名称及测试内容 语法分析模块 测试‎‎对象:完整并且正确的‎‎TINY程序。 {Sample program in TINY language-computes factorial} read x;{input an integer} i‎‎f 0x then {>是没有语法单位} fact=1 {赋值语句缺少 := } ‎‎ rep‎‎eat fact:=fact*x {去掉了分号} x:=x-1 {去掉了分号} until x=0 {去‎‎掉了分号} ‎‎ write fact {output factorial of x} end 预期结果:语法分析必须不仅

报告

软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载

错误信息，而且还必须从错误状态恢复并且继 续进行分析(找出尽可能的错误‎‎)， Read: x‎‎ If Const: 0 Assign to: x Assign to: fact Repeat Assign to: fact ‎‎ Op:‎‎ * Id: fact Id: x Assign to: x 42 Op: - Id: x ‎‎ Con‎‎st: 1 Op: = Id: x Const: 0 Write Id: fact 测试结果:如图4-2测试结果2 ‎‎ ‎‎ 图4-2测试结果2 测试结论:和预期的结果相同，并且提示出错类型和位置。 43 4.4 测试结论 该TINY编译器系统具备必须的编译器系‎‎统的功能，在语法分析‎‎方面基本符合了一个编译器语法分析的要求，输出结果符合2.3.3节语法树输出的要求。但是该系统也存在不少的局限性，界面中友好程度不够，过于简单。 5. 结论与心得 ‎‎在这次毕业设计中，前‎‎后3个月的时间，我学会了很多东西，也发现很多不足的地方。 1)通过编写毕业设计感觉TINY语言虽小，但是很实用。 2)以前用多了面向对象的语言，现在来写TINY-C编译器才发现自己‎‎对面向过程的语言没学‎‎好，以前的C语言的学习没下工夫，现在用来特别吃力。特别是对C语言的文件和指针的学习不够。 3)另外感觉数据结构特别重要，在毕业设计中，语法树的产生就是一个数据结构的使用，数据结构真‎‎的很难全部懂，但是不‎‎懂就不可以使程序高效运行。学习数据结构就是要多实践但不是拿到就马上动手编码，而是要学会如合作项目，比如比如需求分析，详细设计，构思算法等等，其实数据结构我觉得就是培养一种逻 辑思维，同时也能培养动手能力‎‎，要是每个程序都按‎‎软件工程的设计顺序来做。还要从根本上就要认识到数据结构的本质，数据结构和算法之间的密切关系，以 及数据结构的应用方法。树是好‎‎的数据结构——它有非常简单而高效的线性化规‎‎ 44 则，因此可以利用树设计出许多非常高效‎‎的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，‎‎反之亦然。实际上，每一种递‎‎归的结构都可以被转化为(或等价于)树形结构。 在毕业后的工作中，我还是会继续从事计算机编程工作，我更加要学习基础语言和数据结构，真的很高兴这次编写TINY-编‎‎译器，认识到了自己的‎‎不足之处。以后会多多学习，多编写程序 。 参 考 文 献 [1]Kenneth C.Louden . Compiler Construction Principles and Practice‎‎(‎‎编译原理 及实践) [M] . 机械工业出版社 . 2000‎‎-01-11 [2] 陈火旺，刘春林 .程序设计语言-编译原理(第3版)[M] . 国防工业出版‎‎ 社 .2000-01-12 ‎‎ [3]严蔚敏，吴伟民 .数据结构C语言版[M] . 清华大学出版社 .1997-10-25 [4] H.M.Deitel,P.J.Deitel . C ho‎‎‎w to program(Second‎‎ Edition) C语言程序设计教程 [M] . 机械工业出版‎‎社 . 2000-07-11 [5]刘炜玮，汪晓平 .C语言高‎‎级实例解析[M] . 清华大学出版社 .2003-09-‎‎25 ‎‎ [6]伍俊良.Delphi 6控件应用实例教程[M]. 北京希望电子出版社.2003-1-12 45 [7]潘锦平,施小姚,姚天昉 . 软件系统开发技术[M] .西安电子科技大学出版社‎‎.2004-1 ‎‎ [8]李芷,窦万峰,任满杰.软件工程方法与实践[M] .高等教育出版社.2003-5-12 [9]Ivar Jacobson,Grady Booch,James Rumbaugh‎‎.‎‎统一软件开发过程(英文影印版)[M].‎‎ 机械工业出版社.2003-08-12 [10]杨宗志 .Delphi资料库程式设计[M].清华大学出版社 .2003-10-25 ‎‎ ‎‎ 46