布尔表达式的LR翻译器--中间代码为四元式.docx

《布尔表达式的LR翻译器--中间代码为四元式.docx》由会员分享，可在线阅读，更多相关《布尔表达式的LR翻译器--中间代码为四元式.docx（23页珍藏版）》请在优知文库上搜索。

1、学号：课程设计题目布尔表达式的LR翻译器学院计算机科学与技术学院专业软件工程班级软件1102姓名李帅奇指导教师何九周2023年1月2日课程设计任务书学生姓名：李帅奇专业班级:软件1102指导教师：何九周工作单位:计算机科学与技术学院题目：布尔表达式的LR翻译器初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务：（包括课程设计工作量及其技术要求，说明书撰写等具体要求）1 .明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的根本方法与步

2、骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2 .主要功能包括：利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后计假设干用例，上机测试并通过所设计的分析程序。（参考教材P181182）进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。3 .设计报告：要求层次清楚、整洁标准、不得相互抄袭。正文字数不少于0.3万字。包含内容：课程设计的题目。目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原那么1给出语法分析方法及中间代码形式的描述

3、、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。参考文献。附录：软件清单（或者附盘）。时间安排:消化资料、系统调查、形式描述系统分析、总体设计、实施方案撰写课程设计报告书指导教师签名：2023年1月2日系主任（或责任教师）签名:2023年1月2日目录2需求分析33总体设计及开发工具的选择43设计分析43.2 设计原理5词法分析5语法分析5中间代码生成53.3 开发工具64设计原那么65数据结构与模块说明75.1 ACTION表和GOTO表75.2 存储符号和产生式的数组85.3 状态栈和符号栈8

4、6算法设计136.1 词法分析算法描述13词法分析流程图13词法分析算法136.2 语法分析算法代码描述14语法分析算法流程图14语法分析算法146.3 中间代码的生成177软件调试198软件的测试方法和结果209有关技术的讨论20IO收获与体会2011参考文献21本科生课程设计成绩评定表21布尔表达式的LR翻译器1引言编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和根本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程这门课在理论、技术、方法上都对学生提供了系统而有效的

5、训练，有利于提高软件人员的素质和能力。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。2需求分析有如下的布尔表达式文法：BBandTITTTorFFFnotFtrueIfalse(B)iropi利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后计假设干用例，上机测试并通过所设计的分析程序。布尔表达式的LR分析分为扩

6、展文法，构造识别活动前缀的DFA图，判断有误冲突,假设有冲突，那么消除冲突和构造LR分析表等步骤。首先要拓广文法：非二义性文法如下：(0)BB(1) BBandT(2) BT(3) TTorF(4) TF(5) FnotF(6) F(B)(7) Ftrue(8) Ffalse(9) Firopi 构造识别活动前缀的DFA图 判断有无冲突LR(O)分析时有移进一规约冲突，但冲突可以由SLR(1)分析解决。 构造LR分析表状态SiACIONGOTOandornottruefalse()irop#BTFOS4S5S6S7S81231S9R2ACC2R2SlOR2R23R4R4R4R44S4S5S6S

7、7S8115R7R7R7R76R8R8R8R87S4S5S6S7S812238S139S4S5S6S7S814310S4S5S6S7S81511R5R5R5R512S9S1613R3S1714RlSlORlRl15R3R3R3R316R6R6R6R617R9R9R9R93总体设计及开发工具的选择3.1设计分析编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果为中间代码即逆波兰式。整个编译程序分为三局部：词法分析局部、语法分析处理及逆波兰式生成局部、输出显示局部。编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词，而词法分析

8、局部的任务是：从左至右扫描源程序的字符串，按照词法规那么（正那么文法规那么）识别出一个个正确的单词，并转换成该单词相应的二元式种别码、属性值）交给语法分析使用。因此，词法分析是编译的根底。执行词法分析的程序称为词法分析器。语法分析是编译程序的核心局部,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析中主要以二元式作为输入局部,所以输出显示局部的任务是将二元式通过LR分析表对语法分析处理过程进行控制，使逆波兰式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。3.2设计原理词法分析词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独

9、立意义的单词，即根本保存字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字(保存字/根本字)、标识符、常数、运算符、界限符。词法分析的功能是输入源程序，输出单词符号。词法分析的单词符号常常表示成二元式(单词种别码，单词符号的属性值)。词法分析器的设计方法有如下四个步骤：1、写出该语言的词法规那么。2、把词法规那么转换为相应的状态转换图。3、把各转换图的初态连在一起，构成识别该语言的自动机。4、设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终态，

10、送出二元式语法分析语法分析是编译程序的核心局部,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作.法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL(K)方法和LR(K)方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法.Syntax进行语法分析。对于语法分析，这里采用LR(I)分析法，判断程序是否满足规定的结构.构造LR(I)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR(K)分析方法是严格的从左向右扫描，和自底向上的语法分析方法。中间代码生成进入编译程序的第三阶段：中间

11、代码产生阶段。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有：逆波兰式、四元式、三元式、树表示。本课程设计主要实现逆波兰式的生成。逆波兰式定义：将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。3.3开发工具Windows环境下使用VisualC+6.04设计原那么算法是对问题求解

12、过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性： 有穷性：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。 可行性：算法中的所有操作都必须足够根本，都可以通过己经实现的根本操作运算有限次实现之。 有输入：作为算法加工对象的量值，通常表达为算法中的一组变量。但有些算法的字面上可以没有输入，实际上己被嵌入算法之中。 有输出：它是一组与“输入有确定关系的量值，是算法进行信

13、息加工后得到的结果,这种确定关系即为算法的功能。在设计算法时，通常应考虑以下原那么：首先说设计的算法必须是“正确的，其次应有很好的“可读性，还必须具有“健壮性，最后应考虑所设计的算法具有“高效率与低存储量。所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要讨论相应的算法。这里有两重意思，即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，那么无论执行多少遍，所得结果都应该相同。5数据结构与模块说明5.1 ACTION表和GOTO表在程序中，我们使用两个二维数组存储SLR分析表，并初始化，初始化SLR表，其中action表中：100表示acc,除了100以外整数表示移进状态；负数表示用对应产生式进行规约。intaction1810=0,0,4