基于表达式计算器的编译原理课程设计

1、*工程学院编译原理课程设计i果程i殳计题目表达式计算器姓 名：*院（系）:计算机科学与工程学院专业班级：计算机科学与技术084班学 号：200810214415 指导教师:*役计日期:2010年12月26日目录表达式计算器11. 需求分析11.1. 总述12. 概要设计12.1. 开发环境122总体设计22.2.1. 模块结构图22.2.2. 模块说明22.2.3. 界面设计33. 详细设计43.1. 词法分析模块: 43.1.1. 词法分析简介： 43.1.2. 词法分析模块的设计及实现432语法分析模块11321.语法分析简介113.22语法分析器的实现113.3 文法分析19.1 文法分

2、析器生成工具yacc194 测试分析215课程总结246 .参考文献25农达式计算器1. 需求分析1.1 总述计算器是我们经常使用的小工具，它能帮我们对数据进行冇效的 运算，如通过四则运算能实现对输入数据的加减乘除。本课程设计结 合了编译原理屮的词法分析、语法分析及语义分析方法，给出了表达 式计算器的系统设计过程，并在VC+6.0中使用面向对象的技术实 现了计算器。1.2 功能要求计算器的功能要求如下：可以支持加（ +）、减（）、乘（*）、除 （/）运算,如3+45*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）语法分析模块：将单词分解为各类语法短语，若存在不符 合规则的语法短语，则报错并停止计算。(3) 计算模块：对符合语法规则的语法

4、短语进行计算，若计算 不能进行，则报错并停止计算。计算器的三个功能模块中语法分析模块起到了核心作用，如图1 所示。223.界面设计图2表达式计算器3 详细设计3.1. 词法分析模块：其词法分析器调用接口为lex()3.1.1 词法分析简介：词法分析是编译原理程序的第一阶段，其任务是：从左至右逐个 字符地对源程序扫描和分解，识别出一个个的单词(如标志符、常量、 运算符、界符等)，并判断单词的构成是否符合词法规则。可以使用 上下文无关文法来描述词法规则，使用有限口动机来识别单词。3.1.2. 词法分析模块的设计及实现lex工具的基本使用方法和工作原理：Lex工具是一种词法分析程序生成器，它可以根拥

5、词法规则说明书的 要求来生成单词识别程序，由该程序识别出输入文本中的各个单词。一般可以分为 定义部分X规则部分X用户子程序部分。其屮规则部分是必须的，定义和用户子程序 部分是任选的。(1) 定义部分定义部分起始于%符号,终止于%符号，其间可以是包括include语句、声明语句在内的C语句。这部分跟普通C程序开头没什么区别。%#include "stdio.h"int linenum;%(2) 规则部分规则部分起始丁%符号，终止于%符号，其间则是词法规则。词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分 是由C语言语句组成，这些语句用来对所匹配的模

6、式进fj湘应处理。需要注意的是，lex将识别出來的单词存放在yytextf字符数据小，因此该数组的内容就代表了所识别出來的单词的内容。类似yytext这些预定义的变量函数会随着后而内容展开一一介绍。动作部分如果冇多行执行语句，也可以用括起来。%titleshowtitle();n0-9 +:%sn，z, yytext);1i nenum+;printf (z，Tnt0-9*0-9 +printf("Float : %srT,yytext);a-zA-Z a-zA-ZO-9* printf (/zVar : %snz，, yytext);+-*/%printf (/z0p: %snz，

7、, yytext);printf ('"Unknown : %cn", yytext0);%A.规则部分的正则表达式规则部分是Lex描述文件中最为复杂的一部分，下面列出些模式部分的正则表达式字符含义：A-Z, 0-9, a-z构成模式部分的字符和数字。指定范围。例如：a-z指从a到z之间的所冇字符。转义元字符。用來覆盖字符在此表达式中定义的特殊意义，只取字符的本身。表示一个字符集合。匹配括号内的任意字符。如果第i个字符是那么它表示否定模式。例如：abC匹配a, b,和C的任何一个。表刀I否立。*匹配0个或者多个上述模式。+匹配1个或者多个上述模式。9匹配0个或1个上

8、述模式。$作为模式的最后一个字符时匹配一行的结尾。表示一个模式可能出现的次数。例如：A1,3表示A可能出现1次或3次。a-z 5表示长度为5的，由a-z组成的字符。此外，还可以表示预定义的变量。匹配任意字符，除了 no()将一係列常规表达式分组。如：Letter(Letter|Digit)1表达式间的逻辑或。"一些符号字符的字面含义。元字符具有。如：相当于*。/向前匹配。如果在匹配的模式中的厂后跟有后续表达武,只匹配模版中7前面的部分。如：模式为ABC/D 输入 ABCD,吋ABC会匹配ABC/D,而D会匹配相应的模式。输入ABCE的话，ABCE就不会去匹配ABC/D0B.规则部分的

9、优先级规则部分貝有优先级的概念，先举个简单的例子:%#include "stdio.h"%n*Aprintf (/z0NEnz/);AAprintf (z，TW0n，z);AAAAprintf("THREEn)；;%此时，如果输入内容：root local host liweitest# cat filel.txtAAAAAAArootlocalhost liweitest# . /parser < filel. txtTHREETWOONELex分析词法时，是逐个字符进行读取，口上而下进行规则匹配的，读取到第一个A字符时，遍历后发现三个规则皆匹配成功，Le

10、x会继续分析下去，读至第五个字符时，发现AAAA只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符匹配规则。如果将规则AAAAprintfCTHREEnz/)；改为AAAAAprintfCTIIREEn，z);./parser < filel. txt 输出结果为:THREETWO(3) 用户子程序部分最后一个%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子程序可以用在前面的动作中，这样就可以达到简化编程的II的。这里9需要注意的是，当编译时不带T1选项时，是必须加入main函数和yywrap（yywrap将下后面说明）。如:%showt it

11、le()printf (z，Lex Examplenz，);int main()1inenumO;yylexO ; /* 进行 Lex 分析 */printf CAnLine Count: %dn，z, linenum);return 0;int yywrap ()return 1;io3.2. 语法分析模块3.2.1. 语法分析简介语法分析的任务是：在词法分析的基础上，根据语言的语法规则, 把单词串分解成各类语法短语(如句子、程序、表达式等)，从而确 定整个输入串的结构是否正确。可使用上下文无法文法描述语法规 则，算符优先分析法是一种语法分析方法，它特别适合分析各类表达 式。3.2.2. 语

12、法分析器的实现(1) 产生式：(0)S, -E E-E+TET T-T*FT-F(5) F- (E)(6) F-*i E-E-T T-T/Fii（2）得出LR分析表:状态ACTIONGOTO1+*/()#ETF0S5S41231S6S7ACC2r2r2S8S9r2r23r4r4r4r4r4r44S5S410235r6r6r6r6r6r66S5S41137S5S41238S5S4139S5S41410S6S7S1511rlrlS8S9rlrl12r7r7S8S9r7r713r3r3r3r3r3r314r8r8r8r8r8r815r5r5r5r5r5r5（3）代码实现：严以下变量用于语法分析*/终

13、结符符号表Vvt=” i”,$INT,”+”,$PLUS,”“,$MINUS,”*“,$MUL,”厂,$DIV,” (”,$LPAR.”)”,$RPAR,”#”,$END非终结符符号表V vn=” E”,$E,” F”,$F；文法的产生式集合P pset=1 ,$E, $E,$PLUS,$T,() ,/E>E+T2, $E,$E,$MINUS,$T,0,3, $E,$T,0,0.0,4, $T,$T,$MUL,$F,(),5, $T,$T,$DIV,$F,0,6, $T,$F,0,0,0,7, $F, $LPAR,$E,$RPAR,0,& $F,$INT.0,0,0,0,0,()

14、；/action 表int action168 = iS+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK.BLANK,S+6,S+7,BLANK,BLANK.BLANK,BLANK,ACC,BLANK,R+3,R+3,S+&S+9,BLANK,R+3,R+3,BLANK.R+6.R+6.R+6.R+6,BLANK,R+6.R+6,14S+5,BLANK,BLANK,BLANK.BLANK,S+4.BLANK,BLANK,BLANK,R+&R+&R+&R+8,BLANK,R+&R+&S+5,BLANK,BLANK

15、,BLANK,BLANK,S+4,BLANK,BLANK,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,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,BLANKR+l ,R+1 ,S+8,S+9,BLANK,R+l ,R+1,BLANK,R+2,R+2,S+8,S+9,BLANK,R+2.R+2,BLANK,R+4,R+4.R+4R+4,B

16、LANK,R+4R+4,BLANK,R+5,R+5R+5.R+5,BLANK,R+5,R+5,BLANK,R+7,R+7.R+7,R+7,BLANK,R+7.R+7；/Goto 表int go163 = /E,T,F123,BLANK,BLANK.BLANK,BLANK,BLANK.BLANK,BLANK,BLANK,BLANK,10,2,3,BLANK,BLANK,BLANK,BLANK J 1,3,BLANK, 12,3,BLANK,BLANK,13,BLANK,BLANK,14,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK.BLANK,B

17、LANK,BLANK. BLANK,BLANK,BLANK.BLANK,BLANK,BLANK.BLANK；int SLR1()/SLR1 分析表入口int token;/输入符号int s,e; /U态栈顶、符号栈顶元素ini *pipl;产生式右部、左部int act;/动作分析栈rstack slrstack(256);slrstack.push(0, SEND);token = Lex();while(true)if (token = $UNKNOWN)ProcError();return FAIL;elseact = actionslrstack.top(s,e) token-1;i

18、f (act = BLANK)ProcError();return FAIL; else if (act = ACC)primf(”接受！ ”);return SUCCESS;else if (act < R)移入printf(n移入sn", vtftoken-1 .name);slrstack.push(act-S, token);token = Lex();else规约pr = psetact-R-l.right;pl = psetact-R-l.left;printfC'规约产生式:%s->", );while(*pr !

19、= 0)if (*pr >= 100)printf(H%s vn*pr-IOO.name);elseprintf("%s ", vt*);slrstack.pop(s, e);pr+;printf(nnM);s = goslrstack.top(s,e) pl -100;slrstack.push(s, pl);/if (act = BLANK)/if (token = $UNKN0WN)/while3.3文法分析.1文法分析器生成工具yacc简单来说,yacc(Yet Another Compiler-Compiler)就是编译器的编 译器。Yac

20、c是一-个通用的工具，能够根据用户指定的规则，生成一 个词法分析程序。yacc能识别LALR且无歧义的文法，它的输入是 词法分析器的输出。我们知道，生成词法分析器是lex分内的事，因 此lex和yacc常常珠联璧合。先让我们看一下yacc文件的格式。和前面介绍的lex的格式类 似：declarations声明%rules规则%programs其它程序其屮声明段声明一些符号常量，可以为空。同lex样，声明段中可 以有出现在目标C程序中的代码,放在%-%中；还有一些yacc关 键词可以指示出token的结介顺序：% left左结合%right右结合%nonassoc不结合%token声明token

21、俗话说“没有规矩，不成方圆”。规则段描述规则，自然是重中之重To规则段的结构是如下，A : BODY ;A表示非终结符名，BODY表示产生式和动作，产生式包括非终结符和 终结符，终结符用''引用。一些转义字符，比如'L等, 和C里而的表示是一样的。动作(action)则是在输入被当前规则识别 出來时而执行的。动作实际上就是C的代码，写在 屮。为了沟通 词法分析器和动作，yacc引入了形式变量，以$开头。如果希望获得 词法分析器和前面的动作返冋的值，我们可以使用$1,$2,。$丄表示一条规则右侧第7个单元的值。比如冇这样的一条规则,A : B C D ;C的返回值为$2, D为$3。依此类推。程序段放些其它的程序，也可以省略，连%都可以不要。连接时需要指定连接库，gcc的参数为Ty。4 测试分析功能测试:图2进行加法运算25盘表达式计算晋