《编译原理课程设计基于表达式计算器.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计基于表达式计算器.doc（28页珍藏版）》请在三一文库上搜索。
1、*工程学院编译原理课程设计课程设计题目 ：表达式计算器姓 名 ：*院（系） ：计算机科学与工程学院 专业班级 ：计算机科学与技术084班学 号 ：200810214415指导教师 ：*设计日期 ：2010 年 12 月26日目录表达式计算器11. 需求分析11.1.总述12. 概要设计12.1.开发环境12.2.总体设计22.2.1.模块结构图22.2.2.模块说明22.2.3.界面设计33. 详细设计43.1.词法分析模块：43.1.1.词法分析简介：43.1.2.词法分析模块的设计及实现43.2.语法分析模块113.2.1.语法分析简介113.2.2.语法分析器的实现113.3文法分析19
2、.1文法分析器生成工具yacc194.测试分析215课程总结246.参考文献25表达式计算器1. 需求分析1.1. 总述计算器是我们经常使用的小工具，它能帮我们对数据进行有效的运算，如通过四则运算能实现对输入数据的加减乘除。本课程设计结合了编译原理中的词法分析、语法分析及语义分析方法，给出了表达式计算器的系统设计过程，并在VC+6.0中使用面向对象的技术实现了计算器。1.2. 功能要求计算器的功能要求如下：可以支持加（+）、减（-）、乘（*）、除（/）运算，如3+4-5*2/2;支持括号运算，如（4+5）*5/8；判断用户输入的表达式是否正确，如3+-*3是一个错误的表达式，在计算时将提示错误
3、；用户输入表达式后，按下等号按钮执行计算。2. 概要设计2.1. 开发环境开发平台：Windows XP + VC+6.0开发语言：C+2.2. 总体设计程序在VC+6.0中使用面向对象的技术实现了计算器。模块设计2.2.1. 模块结构图词法分析模块语法分析模块计算模块需要一个单词识别一个单词得到一个语法短语计算结果图1. 程序模块图2.2.2. 模块说明计算器分为三个功能模块：（1）词法分析模块：对输入的表达式从左到右扫描，识别出表达式中的单词（包括运算符和运算数），若单词的构成不符合词法规则（运算符和运算数的构成规则），则报错并停止计算。（2）语法分析模块：将单词分解为各类语法短语，若存在
4、不符合规则的语法短语，则报错并停止计算。（3）计算模块：对符合语法规则的语法短语进行计算，若计算不能进行，则报错并停止计算。计算器的三个功能模块中语法分析模块起到了核心作用，如图1所示。2.2.3. 界面设计图2表达式计算器3. 详细设计3.1. 词法分析模块：其词法分析器调用接口为lex()3.1.1. 词法分析简介：词法分析是编译原理程序的第一阶段，其任务是：从左至右逐个字符地对源程序扫描和分解，识别出一个个的单词（如标志符、常量、运算符、界符等），并判断单词的构成是否符合词法规则。可以使用上下文无关文法来描述词法规则，使用有限自动机来识别单词。3.1.2. 词法分析模块的设计及实现lex
5、工具的基本使用方法和工作原理：Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识别程序，由该程序识别出输入文本中的各个单词。 一般可以分为。其中规则部分是必须的，定义和用户子程序部分是任选的。(1)定义部分 定义部分起始于 % 符号，终止于 % 符号，其间可以是包括include语句、声明语句在内的C语句。这部分跟普通C程序开头没什么区别。% #include stdio.hint linenum;%(2) 规则部分 规则部分起始于%符号，终止于%符号，其间则是词法规则。词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组成，
6、这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单词存放在yytext字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多行执行语句，也可以用括起来。%title showtitle();n linenum+;0-9+ printf(Int : %sn,yytext);0-9*.0-9+ printf(Float : %sn,yytext);a-zA-Za-zA-Z0-9* printf(Var : %sn,yytext);+-*/% printf(Op : %sn,yytext);
7、. printf(Unknown : %cn,yytext0);%A.规则部分的正则表达式规则部分是Lex描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字符含义：A-Z, 0-9, a-z 构成模式部分的字符和数字。- 指定范围。例如：a-z 指从 a 到 z 之间的所有字符。 转义元字符。用来覆盖字符在此表达式中定义的特殊意义， 只取字符的本身。 表示一个字符集合。匹配括号内的任意字符。如果第一个字 符是那么它表示否定模式。例如: abC 匹配 a, b, 和C 的任何一个。 表示否定。* 匹配0个或者多个上述模式。+ 匹配1个或者多个上述模式。? 匹配0个或1个上述模式。$
8、作为模式的最后一个字符时匹配一行的结尾。 表示一个模式可能出现的次数。 例如: A1,3 表示 A 可 能出现1次或3次。a-z5 表示长度为5的，由a-z组成的 字符。此外，还可以表示预定义的变量。 . 匹配任意字符，除了 n。( ) 将一系列常规表达式分组。如：Letter(Letter|Digit)* | 表达式间的逻辑或。一些符号 字符的字面含义。元字符具有。如：* 相当于 *。/ 向前匹配。如果在匹配的模式中的/后跟有后续表达式， 只匹配模版中/前面的部分。如：模式为 ABC/D 输入 ABCD， 时ABC会匹配ABC/D，而D会匹配相应的模式。输入ABCE的话， ABCE就不会去匹
9、配ABC/D。B.规则部分的优先级规则部分具有优先级的概念，先举个简单的例子：%#include stdio.h%n ;A printf(ONEn);AA printf(TWOn);AAAA printf(THREEn);%此时，如果输入内容：rootlocalhost liweitest# cat file1.txtAAAAAAArootlocalhost liweitest# ./parser file1.txtTHREETWOONELex分析词法时，是逐个字符进行读取，自上而下进行规则匹配的，读取到第一个A字符时，遍历后发现三个规则皆匹配成功，Lex会继续分析下去，读至第五个字符时，发现
10、AAAA只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符匹配规则。如果将规则AAAA printf(THREEn);改为AAAAA printf(THREEn);./parser E+T2,$E,$E,$MINUS,$T,0,3,$E,$T,0,0,0,4,$T,$T,$MUL,$F,0,5,$T,$T,$DIV,$F,0,6,$T,$F,0,0,0,7,$F,$LPAR,$E,$RPAR,0,8,$F,$INT,0,0,0,0,0,0;/action表int action168 = / i,+,-,*,/,(,),# S+5,BLANK,BLANK,BLANK,BLA
11、NK,S+4,BLANK,BLANK,BLANK,S+6,S+7,BLANK,BLANK,BLANK,BLANK,ACC,BLANK,R+3,R+3,S+8,S+9,BLANK,R+3,R+3,BLANK,R+6,R+6,R+6,R+6,BLANK,R+6,R+6,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,BLANK,R+8,R+8,R+8,R+8,BLANK,R+8,R+8,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK
12、,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,BLANK,S+6,S+7,BLANK,BLANK,BLANK,S+15,BLANK,BLANK,R+1,R+1,S+8,S+9,BLANK,R+1,R+1,BLANK,R+2,R+2,S+8,S+9,BLANK,R+2,R+2,BLANK,R+4,R+4,R+4,R+4,BLANK,R+4,R+4,BLANK,R+5,R+5,R+5,R+5,BLANK,R+5,R+5,BLANK,R+7,R+7,R+7,R+7,BL
13、ANK,R+7,R+7;/Goto表int go163 = /E,T,F1,2,3,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,10,2,3,BLANK,BLANK,BLANK,BLANK,11,3,BLANK,12,3,BLANK,BLANK,13,BLANK,BLANK,14,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK;int SLR1()/SLR1分析表入
14、口int token;/输入符号int s,e;/状态栈顶、符号栈顶元素int *pr,pl;/产生式右部、左部int act;/动作/分析栈rstack slrstack(256);slrstack.push(0, $END);token = Lex();while(true)if (token = $UNKNOWN)ProcError();return FAIL;elseact = actionslrstack.top(s,e)token-1;if (act = BLANK)ProcError();return FAIL;else if (act = ACC)printf(接受！);ret
15、urn SUCCESS;else if (act , vnpl-100.name);while(*pr != 0)if (*pr = 100)printf(%s , vn*pr-100.name);elseprintf(%s , vt*pr-1.name);slrstack.pop(s, e);pr+;printf(n);s = goslrstack.top(s,e)pl-100;slrstack.push(s, pl);/if (act = BLANK)/if (token = $UNKNOWN)/while3.3 文法分析.1 文法分析器生成工具yacc简单来说，yacc(Yet Anot
16、her Compiler-Compiler)就是编译器的编译器。Yacc是一个通用的工具，能够根据用户指定的规则，生成一个词法分析程序。yacc能识别LALR(1)且无歧义的文法，它的输入是词法分析器的输出。我们知道，生成词法分析器是lex分内的事，因此lex和yacc常常珠联璧合。先让我们看一下yacc文件的格式。和前面介绍的lex的格式类似：declarations%rules%programs声明%规则%其它程序其中声明段声明一些符号常量，可以为空。同lex一样，声明段中可以有出现在目标C程序中的代码，放在%中；还有一些yacc关键词可以指示出token的结合顺序：left左结合%rig
17、ht右结合%nonassoc不结合%token声明token俗话说“没有规矩，不成方圆”。 规则段描述规则，自然是重中之重了。规则段的结构是如下，A : BODY ;A表示非终结符名，BODY表示产生式和动作。产生式包括非终结符和终结符，终结符用引用。一些转义字符，比如r,n等，和C里面的表示是一样的。动作(action)则是在输入被当前规则识别出来时而执行的。动作实际上就是C的代码，写在 中。为了沟通词法分析器和动作，yacc引入了形式变量，以$开头。如果希望获得词法分析器和前面的动作返回的值，我们可以使用$1,$2,。$i表示一条规则右侧第i个单元的值。比如有这样的一条规则，A : B C
18、 D ;C的返回值为$2，D为$3。依此类推。程序段放一些其它的程序，也可以省略，连%都可以不要。连接时需要指定连接库，gcc的参数为-ly。4. .测试分析功能测试：图2进行加法运算图3表达式进行减法运算图4表达式进行乘法运算图5表达式进行除法运算图6表达式进行四则运算图7表达式进行括号优先运算5 课程总结本课程设计基于程序设计语言的编译原理，给出了表达式计算器的设计过程，并在VC+6.0下将其进行了实现。其中由于时间问题，在词法分析与语义分析中分别运用了LEX和YACC工具。所以本课程设计的核心内容在于语法分析阶段，语法分析采用自上而下分析法，确定相关的文法产生式，确定FIRST和FOLL
19、OW集合，对产生式进行移近和规约，构造ACTION和GOTO表，最后进行代码的编写。通过本课程设计让我深刻掌握了词法分析、语法分析和语义分析等相关内容。特别是能灵活的运用LEX和YACC工具进行词法和语义分析。6 .参考文献1 Alfred V.Aho, Ravi Sethi, Jeffrey D,Ullman著，李建中, 姜守旭等译. 编译原理M. 北京：机械工业出版社出版2 陈火旺,刘春林, 谭庆平, 赵克佳, 刘越著. 程序设计语言编译原理（第三版）M. 长沙：国防工业出版社出版3 Ken Arnold，James Gosling，David Holmes著，陈昊鹏，章程，张思博，李楠译. Java程序设计语言（第版）M. 北京：人民邮电出版社出版