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

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

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

3、：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。参考文献。附录：软件清单（或者附盘）。时间安排：消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名： 2014年 1月 2日系主任（或责任教师）签名： 2014年 1月 2日 目录1引言32需求分析33总体设计及开发工具的选择53.1设计分析53.2设计原理63.2.1词法分析63.2.2语法分析63.2.3

4、中间代码生成73.3开发工具74设计原则75数据结构与模块说明85.1 ACTION表和GOTO表85.2 存储符号和产生式的数组95.2 状态栈和符号栈96算法设计146.1词法分析算法描述146.1.1词法分析流程图146.1.2词法分析算法146.2语法分析算法代码描述156.2.1语法分析算法流程图156.2.2语法分析算法156.3中间代码的生成197软件调试218软件的测试方法和结果219有关技术的讨论2310收获与体会2411参考文献24本科生课程设计成绩评定表25布尔表达式的LR翻译器1引言编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括

5、语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作（是移进还是按某一产生式进行归约等）。2需求分析已知有如下的布尔表达式文法：B ®B and T |

6、T T®T or F | F F®not F|truefalse |（B）| i rop i利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后计若干用例，上机测试并通过所设计的分析程序。布尔表达式的LR分析分为扩展文法，构造识别活动前缀的图，判断有误冲突，若有冲突，则消除冲突和构造LR分析表等步骤。l 首先要拓广文法：非二义性文法如下： (0) B ® B (1) B ® B and T (2) B ® T (3) T ® T or F (4) T ® F (5) F ® not

7、 F(6) F ® ( B ) (7) F ® true(8) F ® false (9) F ® i rop il 构造识别活动前缀的DFA图l 判断有无冲突LR(0)分析时有移进规约冲突，但冲突可以由SLR（1）分析解决。l 构造LR分析表状态SiACTIONGOTOandornottruefalse()irop#BTF0S4S5S6S7S81231S9R2ACC2R2S10R2R23R4R4R4R44S4S5S6S7S8115R7R7R7R76R8R8R8R87S4S5S6S7S812238S139S4S5S6S7S814310S4S5S6S7S8

8、1511R5R5R5R512S9S1613R3S1714R1S10R1R115R3R3R3R316R6R6R6R617R9R9R9R93总体设计及开发工具的选择3.1设计分析编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果为中间代码即逆波兰式。整个编译程序分为三部分：词法分析部分、语法分析处理及逆波兰式生成部分、输出显示部分。编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词，而词法分析部分的任务是：从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值

9、）交给语法分析使用。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析中主要以二元式作为输入部分，所以输出显示部分的任务是将二元式通过LR分析表对语法分析处理过程进行控制，使逆波兰式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。3.2设计原理3.2.1词法分析词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一

10、般分为五种：关键字（保留字/基本字）、标识符、常数、运算符、界限符。词法分析的功能是输入源程序，输出单词符号。词法分析的单词符号常常表示成二元式（单词种别码，单词符号的属性值）。词法分析器的设计方法有如下四个步骤：1、写出该语言的词法规则。2、把词法规则转换为相应的状态转换图。3、把各转换图的初态连在一起，构成识别该语言的自动机。4、设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终态，送出二元式3.2.2语法分析语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠

11、错工作.法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL(K)方法和LR(K)方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法. Syntax进行语法分析。对于语法分析，这里采用LR(1)分析法，判断程序是否满足规定的结构.构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR(K)分析方法是严格的从左向右扫描，和自底向上的语法分析方法。3.2.3中间代码生成进入编译程序的第三阶段：中间代码产生阶段。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的

12、分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有: 逆波兰式、四元式、三元式、树表示。本课程设计主要实现逆波兰式的生成。逆波兰式定义: 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。3.3开发工具Windows环境下使用Visual C+6.04设计原则算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个

13、重要特性：l 有穷性：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。l 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。l 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 l 有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可以没有输入，实际上已被嵌入算法之中。l 有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。在设计算法时，通常应考虑以下原则：首先说设计的

14、算法必须是“正确的”，其次应有很好的“可读性”，还必须具有“健壮性”，最后应考虑所设计的算法具有“高效率与低存储量”。所谓算法是正确的，除了应该满足算法说明中写明的"功能"之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。 算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要讨论相应的算法。这里有两重意思，即算法中的操作步

15、骤为有限个，且每个步骤都能在有限时间内完成。确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。5数据结构与模块说明5.1 ACTION表和GOTO表在程序中，我们使用两个二维数组存储SLR分析表，并初始化，初始化SLR表，其中action表中：100表示acc，除了100以外整数表示移进状态；负数表示用对应产生式进行规约。int action1810= 0, 0 ,4,5, 6 ,7, 0, 8, 0, 0,/0 9, 0 ,0,0, 0 ,0,-2, 0, 0,100,/1 -2,10 ,0,0, 0 ,0,-2, 0, 0, -

16、2,/2-4,-4 ,0,0, 0 ,0,-4, 0, 0, -4,/3 0, 0 ,4,5, 6 ,7, 0, 8, 0, 0,/4-7,-7 ,0,0, 0 ,0,-7, 0, 0, -7,/5-8,-8 ,0,0, 0 ,0,-8, 0, 0, -8,/6 0, 0 ,4,5, 6 ,7, 0, 8, 0, 0,/7 0, 0 ,0,0, 0 ,0, 0, 0,13, 0,/8 0, 0 ,4,5, 6 ,7, 0, 8, 0, 0,/9 0, 0 ,4,5, 6 ,7, 0, 8, 0, 0,/10 -5,-5 ,0,0, 0 ,0,-5, 0, 0, -5,/11 9, 0 ,0,0

17、, 0 ,0,16, 0, 0, 0,/12 0, 0 ,0,0, 0 ,0, 0,17, 0, 0,/13-1,10 ,0,0, 0 ,0,-1, 0, 0, -1,/14-3,-3 ,0,0, 0 ,0,-3, 0, 0, -3,/15-6,-6 ,0,0, 0 ,0,-6, 0, 0, -6,/16-9,-9 ,0,0, 0 ,0,-9, 0, 0, -9;/17int gotol183= 1,2, 3,0,0, 0,0,0, 0,0,0, 0,0,0,11,0,0, 0,0,0, 0,12,2, 3,0,0, 0,0,14, 3, 0,0,15,0,0, 0,0,0, 0,0,0, 0

18、,0,0, 0,0,0, 0,0,0, 0,0,0, 0;5.2 存储符号和产生式的数组用三个数组来存储和符号以及产生式相关的信息：endls数组存储终结符、noends数组存储非终结符、products数组存储产生式信息。/终结符集合string endls10="and","or","not","true","false", "(",")", "i","rop","#" ;/非终结符集合str

19、ing noends3="B","T","F"/产生式集合string products10="B","B and T", "T","T or F","F","not F","( B )","true", "false","i rop i"5.2 状态栈和符号栈我们用类来模拟状态栈和符号栈。这是状态栈： class statestackp

20、rivate:int *base;/栈底指针int *top;/栈顶指针int size;/栈内元素个数int stacksize;/栈的大小public:statestack()size=0;stacksize=20;base=new intstacksize;top=base;int getTop()/获取栈顶的元素。if(base=top)return -1; elsereturn *(top-1); bool statePush(int elem)/元素入栈+size;(*top)=elem;+top;return true;void statePop(int time)/元素出栈fo

21、r(int i=0;i<time;i+)-top;-size;void printState()/输出栈内的所有元素string str=" "int *pre;for(pre=base;pre<top;pre+)if(*pre>9)char ch1=(*pre/10)+48;char ch2=(*pre%10)+48; str+=ch1;str+=ch2;else char ch=*pre+48; str+=ch;cout<<setw(15)<<setiosflags(ios_base:left)<<str;这是符号栈

22、： class symbolstackprivate:string *base;string *top;int size;int stacksize;public:symbolstack()size=0;stacksize=20;base=new stringstacksize;top=base;string getTop()/获取栈顶的元素。if(base=top)return " " elsereturn *(top-1); /元素入栈bool symbolPush(string elem)+size;*top=elem;+top;return true;/元素出栈vo

23、id symbolPop(int time)for(int i=0;i<time;i+)-top;-size;/输出栈内的所有元素void printSymbol()string str=" "string *pre;for(pre=base;pre<top;pre+) str+=*pre;cout<<setw(15)<<setiosflags(ios_base:left)<<str;6算法设计6.1词法分析算法描述6.1.1词法分析流程图6.1.2词法分析算法 用该函数将布尔表达式分开，并存储在vector中。/将字符串按空

24、格分开,并存入vector中。vector<string> separatestrEX(string str)vector<string> vec;int pos=0;for(int i=0;i<str.size();+i) if(isspace(stri)/如果当前字符是空格vec.push_back(str.substr(pos,i-pos);/复制起始位置为pos且长度为i-pos的字符串。pos=i+1;vec.push_back(str.substr(pos,str.size()-pos);return vec;6.2语法分析算法代码描述6.2.1语法分

25、析算法流程图6.2.2语法分析算法用actionGoto函数对每个符号进行分析：void actionGoto(string str,string str1) int x=state.getTop();/当前栈顶状态int y=strtoInt(str);/当前将要输入的字符if(actionxy>0&&judgeSymbol(str)&&(str!="#")/移进printfInfoEX(step,state,symbol,str1,"移入"+str);state.statePush(actionxy);symbo

26、l.symbolPush(str);+step;if(actionxy<0&&judgeSymbol(str)/规约int z=-actionxy;/用-actionxy对应的产生式规约string lenstr=productsz;/生成需要规约的产生式int n=calculatenum(lenstr);/计算产生式的长度，进行规约int c=chooseNoEnds(z);string ch=noendsc;/生成规约后的非终结符createforchief(n,lenstr,ch);/生成四元式printfInfoEX(step,state,symbol,str1

27、,"规约"+noendsc+"->"+productsz);state.statePop(n);symbol.symbolPop(n);int m=state.getTop();/获取规约后的栈顶状态if(gotolmc>0)int g=gotolmc;state.statePush(g);symbol.symbolPush(ch); +step; actionGoto(str,str1);if(actionxy=100)&&(str="#")printfInfoEX(step,state,symbol,s

28、tr1,"分析完成");如下是strtoInt函数的代码：/将终结符和非终结符转换为action和gotol表中对应的列号int strtoInt(string str)if(str="and")return 0;if(str="or")return 1;if(str="not")return 2;if(str="true")return 3;if(str="false")return 4;if(str="(")return 5;if(str="

29、)")return 6;if(str="i")return 7;if(str="rop")return 8;if(str="#")return 9;if(str="B")return 0;if(str="T")return 1;if(str="F")return 2;如下是judgeSymbol函数的代码：/判断字符是终结符还是非终结符bool judgeSymbol(string str)for (int i = 0;i<10; i+)if(endlsi=s

30、tr)return true;return false;如下是chooseNoEnds函数的代码：/根据产生式选择非终结符int chooseNoEnds(int num)if(num=1|num=2)return 0;/选择“B”if(num=3|num=4)return 1;/选择“T” return 2;/选择“F”如下是calculatenum函数的代码：/计算字符串中元素的个数int calculatenum(string str)int num=0;for(int i=0;i<str.size();+i)if(isgraph(stri)continue;else+num;+n

31、um; return num;6.3中间代码的生成该函数负责生成中间代码：/生成四元式void createforchief(int num,string lenstr,string ch)vector<string> strs=separatestrEX(lenstr);vector<string>:iterator iter=strs.begin();string str=" " string l1="("string l2=")"string l3=","if(num=1)string

32、 l0="="string arg1=*iter;str=l1+l0+l3+arg1+l3+"_"+l3+ch+l2;if(num=2)string op=*iter;string arg1=*(iter+1);str=l1+op+l3+arg1+l3+"_"+l3+ch+l2;if(num=3)string arg1=*iter;string op=*(iter+1);string arg2=*(iter+2);if(arg1="(") string l0="="str=l1+l0+l3+op

33、+l3+"_"+l3+ch+l2;elsestr=l1+op+l3+arg1+l3+arg2+l3+ch+l2;fors.push_back(str);/输出四元式void printForsInfo()printInfo("中间代码四元式为");vector<string>:iterator it=fors.begin();for(it;it<fors.end();it+)cout<<*it<<endl;7软件调试在整个编译器设计过程中，遇到了很多意想不到的困难，其主要原因是对各个部分要实现的功能考虑不够周全。

34、通过反复查找资料，以及向同学请教，才得以完成。在布尔表达式翻译器的设计过程中，在语法分析器设计过程中，程序相当复杂，需要利用到大量的编译原理，以及数据结构中的相关算法。其中在分析表的构造时遇到了非常大的困难，对输入字符串的移进和归约冲突得不到很好的处理，造成了调试的困难。经过我的努力，通过多次调试，最终构造出来分析表并调试成功。在调试的过程中，出现了如下的问题：l 因为函数较多，所以在编程的过程中，多次将函数名写错。l 因为在分析和翻译的过程中，关系较为复杂，所以多次搞混关系。l ACTION表计算错误。l 进栈和出栈的元素关系弄错了。 当然，错误不止这些，但从这次课设，我觉得自己在某些方面仍有所欠缺