条件语句语法分析及语义分析程序设计

1、课程设计任务书学生姓名：姚春萌专业班级：计算机0502指导教师：杨铭熙工作单位：计算机学院题目：条件语句的语法分析及语义分析程序设计初始条件：词法分析的结果，即已经分析得到的TOKENS。要求完成的主要任务：1. 系统功能：能读取词法分析结果进行语法分析，在语法分析的同时进行语义分析，生成中 间代码；2. 数据结构：设计存储中间结果及中间代码（逆波兰式）的数据结构；3. 算法：LR分析法的实现；4. 编程及上机实现；5. 撰写设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包 括引言、需求分析、数据结构设计、算法设计、运行结果及有关技术的讨论、设计体会等;（4 ）

2、结束语；（5）参考文献。时间安排:周一：给出语法分析方法及中间代码形式的描述、文法和属性文法的设计; 周二到周四：简要的分析与概要设计、算法设计与程序设计； 周五：撰写课程设计报告书。指导教师签名:系主任（或责任教师）签名:条件语句语法分析及语义分析程序设计LR法输出逆波兰表达式摘要我的设计任务是条件语句的翻译，采用的语法分析方法是LR(0)法.具体地说其形式如下：if 表达式then 赋值表达式 else 赋值表达式 的形式.if语句是一种条件语 句，它用来控制程序流程中的跳转，使之可以改变死板的顺序执行方式.任务中包括的必备环节是：词法分析器、语法分析器、语义的分析产生中间代码即操作流程如

3、下：首先将输入的源程序交给词法分析器处理，产生单词序列；其次，将单词序列送给语法分析器分析；最后按语法树中各结点的属性值进行语义分析，得出中间代码 关键字：条件语句 词法分析LR语法分析语句分析逆波兰式AbstractMy design mission is the condition lexical translation, the phrasing of the adoption's analysis' method is a LR(0) method.Say its form concretely as follows: Ifthen elseof form.If Ian

4、guage sentenceis a kind of condition Ianguage sentence,it uses to control procedure process in of jump to turn, make it be able to cha nge in flexible in proper order performa nee way.The esse ntial link which includes in the mission BE: The phrase method analysis machine, phrasing analyzes a machi

5、ne, la nguage righteous ness of an alytical creati on middle code. Operate process n amely as follows:The source procedure that will in put first hands over to a phrase method an an alysis mach ine a process ing, produci ng a sin gle phrase seque nce;Se nd the sin gle phrase seque nee to the phras i

6、ng to an alyze mach ine an alysis sec on dly;The attribute value which presses each crunode in the phras ing trees fin ally carries on Ian guage righteous nessa nalysis, get middle code.keywords: condition Ianguage sentence the phrase method analyze the LR phrasing analysis Ianguage negative Poland

7、type0.引言编译器是现代计算机技术的基本组成部分，它们担任翻译器的角色，将面向人的程序 设计语言转换成面向计算机的机器语言。整个编译程序的过程分为词法分析、语法分析、 语义分析、中间代码生成、优化及目标代码生成。1. 文法及其属性文法1.1文法的直观概念和语言概述文法（Grammer）是描述语言的语法结构的形式规则（即语法规则）.这些规则必须是准确 的，易于理解的.而且，应当具备相当强的描述能力，足以描述各种不同的结构由这种规则所形成的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语 法分析程序。文法按其产产生式的不同，可以分为四种：0型文法、1型文法、2型文法、3

8、型文法. 其中2型文法即上下文无关文法，它是这样一中文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的例如，在程序语言中，当碰到一个算术表达式时， 我们完全可以对它“就事论事”进行处理，而不管它所处的上下文1.2、属性文法的描述条件语句的属性文法产生式语义规则S->if E then S1 else S2E.true:=newlabel;E.false:=n ewlabel;S1 .n ext:=S .n ext;9.n ext:=S .n ext;S.code:=E.cod |gen(E.true: ' ) | S1.code |gen( 'go

9、to' S.next) |gen(E.false': ' ) | S.code1.2.2 条件语句的翻译在翻译if-then-else语句S->if E then S 1 else S 2时，布尔表达式E的代码 中有这样的转移指令：若 E为真则转移到Si的第一条指令，若E为假则转移到S2 的第一条指令。继承属性S.next给出了紧接着S的代码之后将被执行的三地址指 令的标号。在Si的代码之后有一条明显的转移指令 goto S.next,但S2之后没有。1.3本任务文法在本任务中，我的文法属于上下问无关文法，而且经验证是符合规则的LR文法.具体形式如下：S'

10、 S（S '是文法的开始符号，自下而上分析法中就是向上归约，最终得S'）S 2E3B4 （2代表:if ; E代表关系判断语句（本次实验中只对” >”（大于），” < （小 于），”=”（等于）作了设计；3:代表else ; B代表赋值语句。E 1A1（ 1:代表标志符;A代表上面所室的三种关系运算符.）A >|<|= = （t代表终结符，表示由数字和标志符一起构成的集合）2. 语法分析方法及中间代码的描述2.1语法分析方法LR有两种通用的语法分析方法：自上而下（top-down）和自下而上（buttom-up）.很多的语法 分析技术采用了后一种方法.该

11、分析器从分析树的底部（树的根结点，它们都是终结符号）开 始发现其结构，并确定用来生成叶结点的产生式.随后发现用来生成叶结点的直接父结点的产 生式.这种发现将持续到语法分析器到达用于扩展开始符号的产生式为止.又称为“移进-归约”法.LR分析法又分为四种：LR（0）、简单LR（SLR）、规范LR、向前LR（LALR）.下面来说说明 LR分析器的角色.规范归约也称最左归约，关键问题是寻找句柄 （即最左简单短语）。LR方法的基本思想是：在规范归约的过程中，一方面记住已移进和归约出的整个符号串， 另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行展望.一个LR分析器实质上是一个带先进后出存

12、储器（栈）的确定有限自动机。任何时候，栈顶的状态都代表了 整个历史和已推测出的展望。即LR分析器每一步的工作都是由栈顶状态和现行输入符号所唯 一确定的.它包括两个存储器和一个输入流外加一个总控程序 丄R分析器核心部分是一张分析表.这张 分析表包括两部分：一是动作（ACTION）表，另一个是状态转换（GOTO）表.他们都是二维数组. 每一项ACTIONs,a所规定的动作不外是下述四种可能之一：移进、归约、接受和报错.一个LR分析器的工作过程可看成是栈里的状态序列、已归约串和输入串构成的三元式的变 化过程.对于一个文法，如果能够构成一张分析表，使得它的每个入口均是唯一确定的，称为 LR文法.对于L

13、R文法，当分析器对输入串进行自左至右扫描时，一旦发现句柄，就能及时的 进行归约在本任务中，我用的LR（O）法，它只概括历史而不包含推测性展望材料的状态 .我们希望仅 由这种简单状态就能识别出呈现在栈顶的某些句柄基本实现步骤如下 ：首先写出一个本题目要求的能够实现目标的 LR文法.其次，根据此 文法构造它的项目集族，从而构建 DFA根据DFA创建LR分析器的核心：ACTION和GOTO 表.从而明确何时移进，何时归约.2.2中间代码的形式描述（逆波兰式）逆波兰式，该表示法是把运算量（操作数）写在前面，把算符写在后面（后缀）。例如：把a+b写成ab+，把a*b写成ab*。一个表达式E的后缀式可以如

14、下定义：（1）如果E是一个变量或常量，则E的后缀式是E自身。（2） 如果E是E1opE2形式的表达式，这里op是任何二元操作符，则 E的后缀式为E1'E2'op，这里E1'和E2'分别是E1 和 E2的后缀式。（3）如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。3. 简要的分析与概要设计我的题目是IF语句的翻译,采用的方法是LR（0）法.整个问题的大致技术问题前面基本都 已介绍。以下是重要的步骤：（1）写出符合待解决问题的文法使它能够推导出符合规则的句型（2）设计好词法分析器，使它能够正确识别输入的源程序串，分辨出哪些是关键字，哪 些是标志符，经过

15、这一步，输出为一个个的单词。（3）设计好语法分析器，对一个个的单词进行处理，查看是否符合语法上的要求（4）对语法分析的结果应用其属性文法，进行语义分析，最后得中间代码三地址码表示其主流程图为:NY打卽生成中网代鸥dnr打即岀辂佔4. 详细的算法描述4.1文法部分具体形式如下：S' S （S '是文法的开始符号，自下而上分析法中就是向上归约，最终得S'）S 2E3B4 （2代表：if ;E代表关系判断语句（本次实验中只对” > （大于），” <”（小于），”=”（等于）作了设计；3:代表else ; B代表赋值语句。E 1A1（ 1:代表标志符；A代表上面所室

16、的二种关系运算符.）A >|<|= = （t代表终结符，表示由数字和标志符一起构成的集合）4.2词法分析器在本次实验中，对输入符进行了如下的编码:标志符1not7!=13if2digital8=14the n3<9=15else4<=10space16and5>11(17or6>=12)18但是在我这个程序中，我只用到了起中一部分：（1； 2； 3； 4； 8； 9； 11； 14； 15）经过编码后，将识别的输入程序交给语法分析器做语法分析。4.3实现语法分析器，接受上步的输出将上步的结果交给语法分析器处理void lr_analysis（）实现语法分析处

17、理，首先构造符合该文法的ACTION和GOT0表#123489111415SABE0S211acc2S433S54S6S7S895S11106R4R4R4R4R4R4R4R4R4R47R5R5R5R5R5R5R5R5R5R58R6R6R6R6R6R6R6R6R6R69S1610S1211S1412S111313R2R2R2R2R2R2R2R2R2R214S1515R7R7R7R7R7R7R7R7R7R7（表中未填值的得当作出错处理。）int gototable1710;用for语句双层循环将goto表全部置0；然后在对个别非0的元素赋值。5. 软件的测试方法和测试结果5.1软件的测试方法运行程

18、序之后，输入符合要求的源程序串，即：if 表达式 then赋值表达式else赋值表达式例如输入为：if ab then c=3 else d=4 #,输出分析结果：分析结果正确!6.心得体会通过本次课程设计，我了解了 LR分析法的运用，熟悉了编译程序从词法分析到语法分析,再到语义分析及生成中间代码生成，这系列的动作的意义。将上课的理论知识与这次的实践 经验结合使我对编译的整个过程有了更为清晰的认识。同时，在7.2节中所述的翻译程序的不足和欠缺，说明我对于这门课程的掌握和理解程 度并没有达到理想的目标，我还需要进一步努力地学习它。现的错误，另外，由于编程水平 低下，在程序的编制过程中出现了许多的不应该出先的错误，其实是可以通过多加练习来克 服的，因此要加强基础编