基于文法分析的表达式计算器的实现.doc

基于分析的表达式计算器的实现 2008-11-21 11:11:02 阅读(38) 发表评论 　　这个基于LL分析器的计算器是大三时上编译原理的一个作业。感觉是自己做过相对比较有深度的一个程序。第一次放出来跟大家分享。希望多多指教。 　　这个计算器支持带括号的四则运算和乘方运算。具体实现过程如下： 　　词法分析器: 　　相关正则定义: 　　　　　　DIGIT　　 [0-9] 　　　　　　NUMBER　{DIGIT}((.{DIGIT}+)|{DIGIT}*) 　　　　　　DELIM　　[ t\n]//字符类，空格、制表（\t）、换行（\n） 　　　　　　OPERATOR [+|-|*|/|^|(|)|=] 　　识别数值的DFA的状态转换图: 　　　　 　　词法分析器的构造： 　　因为要识别表达式中的负数（形如1+ -1），这个工作有两个做法，一个是在词法分析的过程中使得词法分析器可以识别负数。一个是词法分析器只识别正数，让语法分析器去识别负数还是减法运算符。前一种方法不是一个标准的词法分析程序可以完成的，因为它要引用上下文。至少向前看一个字符。这就是LL文法或LR（1）文法的范围了。所以使用第二种方案。这也是大多数情况下所采用的方案。 　　文法分析器： 　　计算器的功能：计划包括含括号的实数四则运算和乘方运算。同时还可以识别出负号。 　　初期文法： 　　　　 　　将上述文法消除左递归可得出下面的文法：注意乘方运算是具有右结合性的。而四则运算是左结合的。由于LL分析法本身的限制，要将一个非二义也非左递归的一个产生式：进行转化（因为它有公共的左因子），使其可以用LL分析法进行分析。 　　　　 　　计算出上述文法的FIRST集和FOLLOW集，如下： 　　　　 　 　　分析表的建立：因为空间原因，表项中只给出产生式的右部 id + - * / ^ ( ) $ E TE’ TE’ TE’ E’ +TE’ -TE’ T FT’ FT’ FT’ T’ *FT’ /FT’ F N -N N N MN’ MN’ N’ ^N M Id (E) 　　文法的分析表 　　文法分析表建立完成之后，就可以开始写程序了。代码如下： #includeiostream #includestring #includecmath using namespace std; #define NUMBER 1000 #define MYERROR 1001 #define END 1002 //词法分析器的当前状态 int state; //读取的内容 string input; //字符串的长度 int inputlength; //字符串读取的位置. int i=0; //词法分析器的返回值 int returnvalue; //读取到数字时的值 string strval; double yylval = 0; /**/////////////////////////////////////////////////////////////////////////// //词法分析器 /**/////////////////////////////////////////////////////////////////////////// bool isdigit(char c){ return (c = 0 c = 9)?true:false; } bool isoperator(char c){ return (c == +||c == -||c == *||c == /||c == ^||c == (||c == )||c == =)?true:false; } //识别数字的DFA的状态转移函数　 int move(int state,char c){ if (isdigit(c)){ return (state==0)?1:state; } else if (state == 1 c == .){ return 2; } else if (( state == 2 || state == 1) (c == || c == n || c == 0 || isoperator(c))){ i--;//操作符 return 3;//接受 } else return 0; } int lexer(){ if (i == inputlength) return END; if