编译原理课程的设计

C语言编译器摘要编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析，并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。而在整个归约过程中，起决定作用的是相继连个终结符之间的优先关系。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。关键词程序设计；数据库；SQL；C++；1任务申请1.1、 引言编译器的设计涉及到编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。尽管“编译程序”是特指将高级程序设计语言翻译成低级语言的软件，但编译程序构造的基本原理和技术也广泛应用于一般的设计和实现，因此，是一门对实践性要求较高的课程。目前，世界上存在着数千种源语言，既有Fortran和Pascal这样的传统程序设计语言，也有各计算机应用领域中出现的专用语言。目标语言也同样广泛，目标语言可以是另一种程序设计语言或者是从微处理机到计算机的任何计算机的机器语言。不同语言需要不同的编译器。根据编译器的构造方法或者它们要实现的功能，编译器被分为一遍编译器、多遍编译器、装入并执行编译器、调试编译器、优化编译器等多种类别。从表面上看，编译器的种类似乎千变万化，多种多样，实质上任何编译器所要完成的基本任务都是相同的。通过理解这些任务，我们可以利用同样的基本技术为各种各样的源语言和目标机器构建编译器。1.2、 背景编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。1.3、目标（1） 设计符号表确定符号表的组织方式，一般应包括名字栏和信息栏，其中名字栏作为关键字。要考虑能够存储有关名字的信息，并可以高效地完成如下操作：查找：根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针；删除：从符号表中删除给定名字的表项。（2） 设计词法分析器设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；能够拼出语言中的各个单词；将拼出的标识符填入符号表；返回（种别码，属性值）。（3） 语法分析器要求用预测分析法、递归下降分析法、算符优先分析法、SLR分析法（几种方法任选），实现对表达式、各种说明语句、控制语句进行语法分析。（4） 目标代码生成器能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码（汇编指令应包括加、减、乘、除），要求指令条数最少的情况下，尽量使用寄存器，尽量少访问内存，这样才能做到运行效率高2可行性研究报告2.1、引言编写编译器的原理和技术具有十分普遍的意义，以致于在每一个计算机科学家的研究生涯中，许多原理和技术都会反复用到。编译器的编写涉及到程序设计语言、计算机体系结构、语言理论、算法和软件工程等学科。简单的说，编译器是一个程序，它读入用某种语言（源语言）编写的程序并将其翻译成一个与之等价的以另一种语言（目标语言）编写的程序。作为这个翻译过程匠一个重要组成部分，编译器能够向用户报告被编译的源程序中3功能需求分析3.1、引言3.1.1词法语法分析简介词法分析的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个的单词（也称单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等，即判断单词序列是否符合组成各类语法短语的组成规则，一般这种语法短语，也称为语法单位，可表示成语法树。3.1.2词法需求分析简介词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。3・2、任务概述3.2.1目标1、 了解编译器的基本结构，分析编译器的设计原理。2、 加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。3、 加深对语法分析器工作过程的理解；加强对递归下降法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。4、 加深对中间代码生成的工作过程的理解。5、 加深对代码优化的工作过程的理解。6、 加深对目标代码生成的工作过程的理解3.3、语法需求分析简介语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词

序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。语法分析的任务是语法分析器接收词法分析研究器提供的记号串，检查它们是否能由源程序的文法产生，语法分析器在编译器中的位置如图所示：典型的文法的语法分析器有三类：一类是通用的语法分析方法，如Cocke-Younger-Kasami算法和Early算法，这些方法在生成编译器时效率太低。编译器常用的是自顶向下和自底向上的方法。采用自顶向下的递归子程序法，就是对应每个非终结符语法单元，编一个独立的处理子程序。语法分析从读入第一个单词开始，由非终结符即开始符出发，沿语法描述图箭头指出的方向进行分析。当遇到非终结符时，则调用相应的处理子程序，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若都不匹配时可能是进入下一非终结符语法单位或是出错。4关键技术实现介绍4.1、引言本次课程设计中的关键是：扫描和语法分析函数，它使用一个用于存放文法符号的先进后出栈，并利用有限关系可以确定最左素短语是否已形成来决定分析器的动作。如果当前栈顶的终结符号和带输入符号之间优先关系是＜或二则表示栈顶符号串未形成最左素短语，此时分析器将移进输入符号。如果当前栈顶的终结符号和待输入符号之间的优先关系是〉，则表示已找到最左素短语的尾，在从栈顶开始，按优先关系在栈内向左寻找最左素短语的头，然后分析器将归约最左素短语。如果出现两个终结符号之间不存在优先关系，则表示存在语法错误。以及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们的思维能力。4・2、用途4.2.1功能员工培训管理信息系统以计算机为工具，通过对培训部门所需的信息管理，把管理人员从繁琐的数据计算处理中解脱出来，使其有更多的精力从事公司的其他业务需求。4.2.2性能1数据精确度由于采用数据库技术并且用户的应用领域对数据精确度的要求不是太高，所以这点在系统中表现得比较少，但是用户数据的安全性与正确性是完全保证的，所以对用户的使用没有多大的障碍。2时间特性本系统的数据库较小，所以程序在响应时间，数据更新处理时间上性能是比较突出的。而且也正由于数据量相对较少，故在数据传输时间和系统运行时间上表现的较让人俩息、。3适应性该系统软件是使用VisualC++6.0在windowsxp系统下完成的所以只要是兼容windows的软件或是操作系统，该软件都可以正确地运行，有较好的适应能力与兼容性。而且应用户的特殊需求软件在完成后的维护阶段可以保持一个与其他类软件接口，随时满足用户的使用要求。4.3、运行环境4.3.1硬设备选用PC级服务器。具体配置如下：Intel486CPU或以上256M内存1个4.3G硬盘，1个激光打印机4.3.2支持软件Microsoftaccess4.3.3数据结构

charch='\0';/*从字符缓冲区中读取当前字符*/intcount=0;/*词法分析结果缓冲区计数器*/staticcharspelling[10]={""};/*存放识别的字*/staticcharline[81]={""};/*一行字符缓冲区(最多80个字符)*/char*pline;/*字符缓冲区指针*/staticcharntab1[100][10];/*变量名表：共100项，每项长度为10*/5系统分析5.1、基础知识5.1.1算符优先分析法的基本思想仿照算术表达式的四则运算过程算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。5.1.2算符优先关系的定义设G是一个不含£产生式的算符文法，算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。5.1.2算符优先关系的定义设G是一个不含£产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系工、心"定义如下：a三b当且仅当G中含有形如A一...ab...或A一...aBb...的产生式^-;b当且仅当G中含有形如A—...aB…的产生式，且B与b...或B与Cb...a)b当且仅当 — ..以上三种关系也可由下列语法树来说明葺b..\ …\o"CurrentDocument"aMb则存在语法子树如图2.1(a) /其中8为£或为B，这样a,b在同一句柄中同时归约所以优a三b则存在语法子树如图2.1(,其中8为£或为C。a,b不在同一句柄中，b先归约，所以,a的优先级低于b。a子b则存在语法子树如图2.1(c)。(a)a.Mb (b)a<-b形如A—..…的产生式，级相同。图2.1由语法树结构决定优先性5.1.3算符优先文法的定义设有一文法G，如果G中没有形如A—...BC...的产生式，其中B和C为非终结符，则称G为算符文法(OperaterGrammar)也称OG文法。例如：表达式文法E—E+E|E*E|(E)|i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。设有一不含£产生式的算符文法G,如果对任意两个终结符对a,b之间至多只有心、源和三三种关系中的一种成立，则称G是一个算符优先文法。(OperatorPrecedenceGrammar)即OPG文法。由以上内容我们可计算出给定的算符文法中任何两个终结符对(a,b)之间的优先关系，其算法如下：首先定义如下两个集合：FIRSTVT(B)={blB与b...或B冬Cb...}LASTVT(B)={alB与...a或B与...aC}三种优先关系的计算为工关系：可直接查看产生式的右部，对如下形式的产生式A-・・・ab・・・,A-・・.aBb・・・有a三b成立。，：三关系：求出每个非终结符B的FIRSTVT(B)，在如下形式的产生式Af.aB...中，对每一b^FIRSTVT(B),有a必b成立。关系：计算每个非终结符B的LASTVT(B),在如下形式的产生式A—...Bb...中，对每一a^LASTVT(B),有a・*b成立。5.1.4最左素短语的定义设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。例如,若表达式文法G[E]为：E—E+T|TT—T*F|FF—PfF|PP一(E)|i若有句型#T+T*F+i#，其短语有：T+T*F+i相对于非终结符E的短语T+T*F相对于非终结符E的短语T相对于非终结符E的短语T*F相对于非终结符T的短语i相对于非终结符P,F,T的短语由以上内容知i和T*F为素短语，T*F为最左素短语。也为算符优先分析的可归约串。由算符优先分析算法可知一个算符优先文法的最左素短语满足如下条件：ai-1■:三aiMai+1三...三可：；，aj+1上述句型#T+T*F+i#写成算符分析过程的形式为：#N1a1N2a2N3a3a4#其中al=+,a2=*,a3=+,a4=ial*：a2（因+,:三*）a2'；"a3（因*子+）由此N2a2N3即T*F为可归约串，也就是前面分析的最左素短语。5・2、解决问题的基本思路根据课程设计的要求，程序应具有如下功能：对输入的文法进行分析并判断是否为算符优先文法。如果是算符优先分析文法则再进一步输入符合该算符优先文法的字符串，并对该字符串进行算符优先分析，同时输出算符优先分析的过程。5.3、总体方案5.3.1设计词法分析器设计思想：要求：1.对单词的构词规则有明确的定义；编写的分析程序能够正确识别源程序中的单词符号；识别出的单词以〈种别码，值〉的形式保存在符号表中；词法分析中源程序的输入以/格式，分析后的符号表保存在.txt文件中。对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析；输入：由符合规定单词类别结构的各类单词组成的源程序。实现方法：根据加入语义过程的状态转换图直接编写词法分析程序。根据每一组状态转换关系（标识符）组织程序结构，并将所有公共处理过程分别实现即可。在扫描源程序字符串时，一旦识别出关键字、运算符、标识符、无符号常数中之一，即以二元式形式（类别编码，值）输出单词。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词。5.3.2设计语法、语义分析器设计思想：要求：1.对语法规则有明确的定义；编写的分析程序能够对实验一的结果进行正确的语法分析；编写的分析程序能够对实验二的结果进行正确的语义分析；对于遇到的语法、语义错误，能够做出简单的错误处理，给出简单的错误提示，保证语义分析过程；实现方法：在词法分析识别出单词符号的基础上分析并规定程序的语法结构是否符合语法规则。其工作本质就是按文法的产生式，识别输入符号串是否为一个句子。首先定义语法规则，然后按照规则实现语法分析。5.3.3单词符号及种别表单词符号种别编码单词值

main1int2float3double4char5if6else7do8while9l(l|d)*10内部字符串(+|-|£ )d*(.dd*|£)(e(+|-|£)dd*|£)20二进制数值表示21+22-23*24/25(26)27{28}29,30:31>32>=33<34<=3536!=375.3.4系统功能结构启动VC++,新建源程序并进行编程，程序的功能模块图如图2-1所示主函数main1r r 1P aFirStVt函数 LastVt函数OpPrioTable函数InputAnalyse函数 图2-1系统功能结构图 函数功能：Main()函数：调用主函数，运行程序;FIRSTVT()函数：构造FIRSTVT表；LASTVT（）函数：构造LASTVT表；OpPrioTable（）函数：构造算符优先关系表；InputAnalyse（）函数：分析输入串是否为文法中的句子，并给出规约过程。6系统设计6.1、算法实现算符优先分析法的具体过程如下：1、 首先先输入文件的路径，在readfile（charsen[][col]）函数中，将需要分析的文法通过输入流文件打开函数open（）复制到sen[row][col]中。2、 然后利用FIRSTVT（）构造产生式sen[row][col]的FIRSTVT表。先找出形如A->…a„（a为第一个终结符）的产生式，把（A,a）压入Operator栈中。从Operator栈顶抛出项（A，a），填入first表相应位置。在找出形如B->A…的产生式，把（B,a）压入Operator栈中。循环直到Operator栈为空，此时FIRSTVT表构造完毕。3、 然后把产生式右部翻转，调用FIRSTVT函数求出LASTVT表。4、 接着调用OpPriotable（）构造算符优先关系表opTable。先把产生式中所有终结符填入opTable表第一行和第一列，然后利用产生式和FIRSTVT表LASTVT表分别找出满足=关系、<关系、>关系的算符填表。若相应位已有关系，说明两个终结符之间至少有两种优先关系，该文法不是算符优先文法。5、 最后调用InputAnalyse（）对输入串进行分析。初始化分析栈S，依次判断当前输入符a和分析栈中离栈顶最近的终结符S[j]的关系，若S[j]<a，则a移近，若S[j]<a，则往前找到第一个S[j]>a，将S[j-1]到栈顶S[k]规约，若S[j]=a，如果S[j]=#，则接受，如果S[j]！=#，则移进。直到接受或者出错，算符优先分析结束。6.2编译过程概述编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级玉器言，则这种翻译程序称作编译程序。高级语言程序的处理过程如图：需处理的源程序预处理程序

源程序编译程序目标汇编程序汇编程序可再装配的机器代码装配/装配/连接一编辑程序可在装配的目标文件绝对机器代码一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫做预处理程序的程序完成，有些预处理程序也负责宏展开，像C语言和预处理程序要完成文件合并、宏展开等任务。也就是说，一个编译程序的输入可能要一个或多个预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。图1将编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、六个阶级。另外两个重要的工作：表格处理和出错处理与上述六个阶级都有联系。编译过程是源程序和各种信息被子保留在种种不同的表格里，编译各阶级的工作都涉及到构造、查找或更新有关的表格，因此需要有表格处理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。语义分析阶级是审查源程序有无语义错误，为代码生成阶级收集类型信息。比如语分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用个数组下标的情况报告错误。又如某些语言规定运算对象可被强制，那么当二目运算一整数和一实型时，编译程序应将整型转换成实型而不能认为是源程序的错误。代码优化在此阶级的任务是对前阶级产生的是间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。6.3、流程图读入.txt文件厂"••产生式全扫描完？>YN图3-1程序流程图7代码编写#include<iostream.h>#include<fstream.h>#include<string.h>#include<iomanip.h>#include<malloc.h>enumkeyword($right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao,$equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end};/关键字的枚举typedefstructToken{keywordtype;charch;}Token;//定义的token结构typedefenum{JUMP,JGJL,equal,END,add,mul,sub,div}OpKind;/臊作符定义为opkindtypedefstruct{intlabel;//标号OpKindop;//操作符charpar1,par2;//操作数union{charresult;//结果intaddress;//地址};}Quad;〃四元式入口#defineMAX_TOKEN256//Token表大小#defineMAX_QUAD256//四元式数组大小Tokentokentable[MAX_TOKEN];Quadquad[MAX_QUAD];inttoken_index;//token表索弓Iinttotal_len;//token表有效长度intquad_len;//四元式表有效长度intquad_index;//四元式索引Tokencur;Tokenqueue[10];intlabel,k,one;〃标记接口charcurchar;//存储当前待比较字符charcurtocmp;//存储当前栈顶字符ifstreamins;inttrueadd,falseadd,end;inttable[5][8]={{1,0,0,0,0,1,0,0},{0,1,1,0,0,0,1,1},{1,0,0,0,0,1,0,0},{0,1,1,1,1,0,1,1},{1,0,0,0,0,1,0,0}};//存储预测分析表，1为有产生式，0为没有inti,j;intflag;structLchar{charchar_ch;structLchar*next;}Lchar,*temp,*top,*base;intright;//定义开关项boolinitialize(charfilename[255]);//文件打开初始化boolaccidence。;//词法分析voidprint();//输出单词表voidbackpath(int,int);//回填出口

voidERROR();voidsentence();//分析语句voidboolean();//分析E->id<idIid>id语句boolnexttoken();//读下一单词charnewchar();voidpush();//进队列chardosome(void);//算法函数voidpushs(charpchar);//A栈函数voidpop(void);//出栈函数voiddoforpush(intt);//根据数组下标计算的值产生式入栈voidchangchartoint();//^根据curchar,curtocmp转为数字以判断是否有产生式voidsemantic。;//语法语义分析charLL1();//LL(1)文法分析voidprintQuad();//输出四元式voidERROR(charstr[20]);voidAD_ADDRESS(intnlabel,OpKindnop,charnpar1,charnpar2,intnaddress);voidmain(){voidmain(){cout<<"<<"<<endl<<endl"<<endl<<endl"<<endl;@基于LL(1)法的条件语句语法语义分析程序@—cout<<"输入您要编译编译文件的文件名(文件名.txt):";charfname[100];cin>>fname;if(!initialize(fname))//初始化文件return;if(!accidence())〃词法分析return;charch;while(1){if(ins.eof())//ifstreamins;文件输入串，若文件已完。则breakbreak;ins>>ch;//继续读入文件内容}cout<<endl<<"词法分析结果如下:”；print();//打印词法分析的结果cout<<endl;cout<<"词法分析结束。"<<endl<<endl;semantic(); //语法语义分析cout<<endl<<”输出四元式:"<<endl;printQuadOy/输出四元式if(right==1)cout<<"分析成功"<<endl;elsecout<<"分析失败"<<endl;cout<<"语法语义分析结束"<<endl;}charnewchar(){charp;p=char(k);//intlabel,k,one;//标记接口k++;returnp;}//文件打开初始化boolinitialize(charfilename[100]){one=0;token_index=0;//token表索弓Itotal_len=0;//token表有效长度quad_len=0;//四元表有效长度quad_index=0;//四元表索引label=0;//intlabel,k,one;〃标记接口end=0;//前面定义的全局变量inttrueadd,falseadd,end;k=48;ins.open(filename,ios::nocreate|ios::in);if(ins.fail()){cout<<"文件打开出错!”<<endl;returnfalse;}returntrue;}〃词法分析boolaccidence(){intk=0;charbuf[16];//暂存数组单元charch;while(1){ins>>ch;if(ins.fail())break;while(ch==''){ins>>ch;}if(ch==T){ins>>buf;〃对关键字分析if(strcmp(buf,"F")==0)tokentable[total_len++].type=$IF;}elseif(ch=='T'){ins>>buf;if(strcmp(buf,"HEN")==0)tokentable[total_len++].type=$THEN;}elseif(ch=='E'){ins>>buf;if(strcmp(buf,"LSE")==0)tokentable[total_len++].type=$ELSE;}〃对关系运算符分析elseif(ch=='>'){tokentable[total_len++].type=$greater;}elseif(ch=='<'){tokentable[total_len++].type=$less;}elseif(ch=='=='){tokentable[total_len++].type=$equal;}〃对字母的分析elseif((ch>='A'&&ch<='Z')11(ch>='a'&&ch<='z')){tokentable[total_len].type=$id;tokentable[total_len++].ch=ch;}//对数字的分析elseif(ch>='0'&&ch<='9'){tokentable[total_len].type=$num;tokentable[total_len++].ch=ch;}Else//采用switch语句对运算符，括号分析switch(ch){case'+':tokentable[total_len].type=$add;tokentable[total_len++].ch=ch;break;case'-':tokentable[total_len].type=$sub;tokentable[total_len++].ch=ch;break;case'/':tokentable[total_len].type=$div;tokentable[total_len++].ch=ch;break;case'*':tokentable[total_len].type=$mul;tokentable[total_len++].ch=ch;break;case';':tokentable[total_len].type=$fenhao;tokentable[total_len++].ch=ch;break;case'(':tokentable[total_len].type=$left_paren;tokentable[total_len++].ch=ch;break;case')':tokentable[total_len].type=$right_paren;tokentable[total_len++].ch=ch;break;default:cout<<"!"<<endl;}}returntrue;}〃词法分析结束〃语法语义分析voidsemantic(){if(!nexttoken())ERROR("s(0)");cout<<"开始进行语法语义分析:"<<endl<<"所使用的产生式:"<<endl<<"<if语句〉->ifEthenSelseS"<<endl<<"S->ifEthenp1elseP2"<<endl<<"E->a>b"<<endl<<"P1->x:=a*c"<<endl<<”P2->x:=b*c”<<endl<<"语法语义分析过程如下:"<<endl;if(cur.type==$IF){boolean();//分析布尔语句if(!nexttoken())ERROR("S(0)");if(cur.type==$THEN){backpath(trueadd,quad_len);//回填出口sentence();//分析语句end=quad_len;AD_ADDRESS(quad_len,JUMP,'-','-',end);俨生跳转地址的四元式if(cur.type==$ELSE){backpath(falseadd,quad_len);sentence();backpath(end,quad_len);}elseERROR("S(else)”);}else{ERROR("S(then)”);}}elseERROR("S(if)");AD_RESULT(quad_len,END,0,0,'-');俨生数值语句的四元式}〃读下一箪词boolnexttoken(){if(token_index>=total_len)returnfalse;if(tokentable[token_index].type==$fenhao)token_index++;cur.type=tokentable[token_index].type;cur.ch=tokentable[token_index].ch;token_index++;returntrue;}〃进队列voidpush(){one=0;while(tokentable[token_index].type!=$fenhao){queue[one].type=tokentable[token_index].type;queue[one].ch=tokentable[token_index].ch;cout<<queue[one].ch;token_index++;one++;}queue[one].type=$end;queue[one].ch='#';cout<<queue[one].ch;}〃队列下一个字符voidnext(){cur.type=queue[one].type;cur.ch=queue[one].ch;one++;}//分析E->id<id|id>id语句voidboolean(){chara,b;intc;if(!nexttoken())ERROR("E(0)");if(cur.type==$idllcur.type==$num){a=cur.ch;if(!nexttoken())ERROR("E(0)");if(cur.type==$greater||cur.type==$less){c=cur.type;if(!nexttoken())ERROR("E(0)");if(cur.type==$id||cur.type==$num)b=cur.ch;elseERROR("E(id/num)");if(c==$greater){trueadd=quad_len-1;falseadd=quad_len;AD_ADDRESS(quad_len,JGa,b,trueadd);AD_ADDRESS(quad_len,JUMP,0,0,falseadd);}else{trueadd=quad_len;falseadd=quad_len+1;AD_ADDRESS(quad_len,JL,a,b,trueadd);AD_ADDRESS(quad_len,JUMP,0,0,falseadd);}}elseERROR("E(id/num)");}elseERROR("E(greater/less)");}//分析语句voidsentence(){charrtn;charc;if(!nexttoken())ERROR("S(0)");if(cur.type==$id){c=cur.ch;if(!nexttoken())ERROR("S(0)");if(cur.type!=$equal)ERROR("S(equal)");push();one=0;rtn=LL1();AD_RESULT(quad_len,equal,rtn,'-',c);nexttoken();while(cur.type==$id){c=cur.ch;if(!nexttoken())ERROR("S(0)");if(cur.type!=$equal)ERROR("S(equal)");push();one=0;rtn=LL1();AD_RESULT(quad_len,equal,rtn,'-',c);nexttoken();}}}//LL(1)文法分析charLL1(){right=1;//开关项为1flag=0;chart;base=(structLchar*)malloc(sizeof(Lchar));//初始化堆栈base->next=NULL;base->char_ch='#';temp=(structLchar*)malloc(sizeof(Lchar));temp->next=base;temp->char_ch='E';top=temp;//初始化堆栈t=dosome();//开始识别if(right)//如果开关项为1cout<<"OK!"<<endl<<endl;elsecout<<"Error!"<<endl;returnt;}//入栈函数voidpushs(charpchar){temp=(structLchar*)malloc(sizeof(Lchar));temp->char_ch=pchar;temp->next=top;top=temp;}〃出栈函数voidpop(void){curtocmp=top->char_ch;if(top->char_ch!='#')top=top->next;}//根据数组下标计算的值产生式入栈voiddoforpush(intt){switch(t){case0:pushs('A');pushs('T');break;case5:pushs('A');pushs('T');break;case11:pushs('A');pushs('T');pushs('+');break;case12:pushs('A');pushs('T');pushs('-');break;case20:pushs('B');pushs('F');break;case25:pushs('B');pushs('F');break;case33:pushs('B');pushs('F');pushs('*');break;case34:pushs('B');pushs('F');pushs('/');break;case40:pushs('i');break;case45:pushs(')');pushs('E');pushs('(');}}//根据curchar,curtocmp转为数字以判断是否有产生式voidchangchartoint(){switch(curtocmp){case'A':i=1;break;case'B':i=3;break;case'E':i=0;break;case'T':i=2;break;case'F':i=4;}switch(curchar){case'i':j=0;break;case'+':j=1;break;case'-':j=2;break;case'*':j=3;break;case'/':j=4;break;case'(':j=5;break;case')':j=6;break;case'#':j=7;}}//算法函数chardosome(void){intt,a=0;charbian1,bian2;OpKindopa;charc='$';next();for(;;){pop();if(cur.type!=$id&&cur.type!=$num)curchar=cur.ch;elsecurchar='i';cout<<endl;cout<<curchar<<""<<curtocmp<<endl;if(curtocmp=='#'&&curchar=='#')break;if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F')//当前字符为非终结符{if(curtocmp!='#')//当前比较字符不为'#'{changchartoint();if(j=0){ a++;flag++;if(flag==1){ if(c=='$')bian1=cur.ch;elsebian1=c;}elseif(flag==3){bian2=cur.ch;flag=1;c=newchar();AD_RESULT(quad_len,opa,bian1,bian2,c);/产生四元式}}else{switch(j){case1:opa=add;flag++;break;case2:opa=sub;flag++;break;case3:opa=mul;flag++;break;case4:opa=div;flag++;}}if(table[i][j])//有产生式{t=10*i+j;//计算产生式在数组中的位置doforpush(t);continue;}else〃没有产生式{right=0;//出错break;}}else〃当前比较字符为'#'if(curtocmp!=curchar){right=0;//出错break;}elsebreak;〃正确}else〃当前字符为终结符if(curtocmp!=curchar){right=0;//出错break;}else{next();//读取下一个字符continue;}}if(a>1)returnc;elsereturnbian1;}〃产生数值语句的四元式voidAD_RESULT(intnlabel,OpKindnop,charnpar1,charnpar2,charnresult){quad[quad_len].label=nlabel;quad[quad_len].op=nop;quad[quad_len].par1=npar1;quad[quad_len].par2=npar2;quad[quad_len].result=nresult;quad_len++;}〃产生跳转地址的四元式voidAD_ADDRESS(intnlabel,OpKindnop,charnpar1,charnpar2,intnaddress){quad[quad_len].label=nlabel;quad[quad_len].op=nop;quad[quad_len].par1=npar1;quad[quad_len].par2=npar2;quad[quad_len].address=naddress;quad_len++;}〃回填出口voidbackpath(intnlabel,intaddr){quad[nlabel].address=addr;}〃错误处理voidERROR(charstr[20]){label++;cout<<endl;cout<<"error!"<<str<<endl;}〃词法分析。输出单词表tokenvoidprint(){for(token_index=0;token_index<total_len;token_index++){if(token_index%100==0)cout<<endl;if(tokentable[token_index].type==$IF)cout<<setw(2)<<"[IF(0)],";if(tokentable[token_index].type==$ELSE)cout<<setw(2)<<"[ELSE(1)],";if(tokentable[token_index].type==$THEN)cout<<setw(2)<<"[THEN(-)],";if(tokentable[token_index].type==$id) 〃字母cout<<setw(2)<<"["<<tokentable[token_index].ch<<"(25)"<<"],";if(tokentable[token_index].type==$num) //数字cout<<setw(2)<<"["<<tokentable[token_index].ch<<"(26)"<<"],";if(tokentable[token_index].type==$equal)cout<<setw(2)<<"["<<'='<<”(18)"<<"],";if(tokentable[token_index].type==$greater)cout<<setw(1)<<"["<<'>'<<"(22)"<<"],";if(tokentable[token_index].type==$less)cout<<setw(2)<<"["<<'<'<<"(22)"<<"],";if(tokentable[token_index].type==$add)cout<<setw(2)<<"["<<'+'<<"(14)"<<"],";if(tokentable[token_index].type==$sub)cout<<setw(2)<<"["<<'-'<<"(15)”<<"],”;if(tokentable[token_index].type==$mul)cout<<setw(2)<<"["<<'*'<<”(16)"<<"],";if(tokentable[token_index].type==$div)cout<<setw(2)<<"["<<'/'<<"(17)"<<"],";if(tokentable[token_index].type==$fenhao)cout<<setw(2)<<"["<<';'<<"(6)"<<"],";if(tokentable[token_index].type==$left_paren)cout<<setw(2)<<"["<<'('<<"(23)”<<"],”;if(tokentable[token_index].type==$right_paren)cout<<setw(2)<<"["<<')'<<"(24)"<<"],"; }token_index=0;}〃输出四元式voidprintQuad(){for(inti=0;i<quad_len;i++){if(quad[i].label>-1)cout<<”("<<quad[i].label<<")"<<”:";elsecout<<endl;if(quad[i].op==JG){cout<<"("<<"j>,"<<quad[i].par1<<","<<quad[i].par2<<","<<quad[i].address<<")"<<endl;}elseif(quad[i].op==JL){cout<<"("<<”j<,"<<quad[i].par1<<”,"<<quad[i].par2<<”,"<<quad[i].address<<”)”<<endl;}elseif(quad[i].op==JUMP){cout<<"("<<"j,”<<”-,-,”<<quad[i].address<<”)”<<endl;}elseif(quad[i].op==equal){if(quad[i-1].result==quad[i].par1)cout<<"("<<":=,”<<”T”<<quad[i].par1<<”,-,”<<quad[i].result<<”)”<<endl;elsecout<<"("<<”:=,"<<quad[i].par1<<”,-,"<<quad[i].result<<”)”<<endl;}elseif(quad[i].op==END){cout<<”(”<<”-,-,-,-”<<”)”<<endl;}elseif(quad[i].op==add){if(quad[i].result>='0'&&quad[i].result<='9')c