计算器：递归下降法构造,支持标识符.docx

文法，用BNF表示 - (+|-) - (*|/) - ()| num| indent| indent = num表示十进制实数indent表示标识符。标识符是由字母和数字构成的序列，第一个字符必须是字母另外要求，Expr以;结尾。根据语法分析树的特点，位于低层的先被求值，也就是说优先级高。由文法可以看出: *、/ 优先级最高； +、-次之；赋值操作符=最低，另外赋值操作符具有右结合性，例如a=b=c;等价于a=(b=c);。(这些都是包含在文法中的，不是约定)1. 词法分析Token种类：实数、标识符、运算符、分隔符。enum token_type NUMBER, IDENT, OPERATOR, SEPARATOR, UNKOWN; Token结构struct Token int type; union double val; / 数值 char *name; / 标识符名字 int op; / 运算符、分隔符，以及其他单个字符 u;使用hash存储标识符HashNode结构/ hash, 标识符名字，和其对应的数值struct HashNode char *name; double value; struct HashNode *next;typedef struct HashNode HashNode;字符串hash 函数int hash(char *s) int hashval; for (hashval = 0; *s != 0; +s) hashval = *s + 31 * hashval; if(hashval next) if (strcmp(ptr-name, name) = 0) return ptr; / 没有找到 ptr = (HashNode *)malloc(sizeof(HashNode); ptr-name = (char *)malloc(strlen(name) * sizeof(char) + 1); strcpy(ptr-name, name); ptr-value = 0; ptr-next = hash_tablehash_value; hash_tablehash_value = ptr; return ptr;词法分析程序：struct Token next_token;/ 词法分析程序void lex() int c; while(c = getchar() != EOF & isspace(c) ; if(isdigit(c) / 识别实数 next_token.type = NUMBER; next_token.u.val = get_num(c); return; else if(isalpha(c) / 识别标识符 char *name = get_ident(c); name = lookup(name)-name; next_token.type = IDENT; next_ = name; return; / 其他 next_token.u.op = c; switch(c) case +: case -: case *: case /: case =: next_token.type = OPERATOR; break; case (: case ): case ;: next_token.type = SEPARATOR; break; default: next_token.type = UNKOWN; double get_num(char c) int val; val = c - 0; while (isdigit(c = getchar() val = val * 10 + c - 0; int n = 0; if(c = .) while (isdigit(c = getchar() n+; val = val * 10 + c - 0; ungetc(c, stdin); return (val / pow(10, n);#define BUFSIZE 100char *get_ident(char c) static char bufBUFSIZE; int bufp = 0; bufbufp+ = c; while (isalnum(c = getchar() bufbufp+ = c; ungetc(c, stdin); bufbufp = 0; return buf;2. 语法分析编写递归下降子程序有一个协定:每一个子程序都在全局量nextToken中放入下一个输入的token。因而，当开始一个语法分析函数时，假定nextToken具有还没有被语法分析过程使用的输入标记中最左面的那个标记。还有另一种解决方案，每个递归子程序开始都自己取下一个标记，若不能处理则放回。我们采用前一种solution。三个非终结符对应三个递归子程序：表达式：/ - (+ | -) double expr() double val; / 分析第一个term val = term(); / 只要下一个token是 + 或 - , / 调用lex() 取得下一个token， / 然后分析下一个term while(next_token.type = OPERATOR & (next_token.u.op = + | next_token.u.op = -) int op = next_token.u.op; lex(); if(op = +) val += term(); else if(op = -) val -= term(); return val;项：/ - (* | /) double term() double val; / 分析第一个factor val = factor(); / 只要下一个token是 * 或 / , / 调用lex() 取得下一个token， / 然后分析下一个factor while(next_token.type = OPERATOR & (next_token.u.op = * | next_token.u.op = /) int op = next_token.u.op; lex(); if(op = *) val *= factor(); else if(op = /) int tmp; tmp = factor(); if(fabs(tmp) 1e-6) fprintf(stderr, 除0); exit(1); else val /= tmp; return val;因子：/ - () | num | ident | ident = double factor() double val; if(next_token.type = SEPARATOR & next_token.u.op = () lex(); val = expr(); if(next_token.type = SEPARATOR & next_token.u.op = ) lex(); / 读取下一个token else fprintf(stderr, 括号不匹配n); exit(1); else if(next_token.type = NUMBER) val = next_token.u.val; lex(); else if(next_token.type = IDENT) HashNode *ptr; ptr = lookup(next_); lex(); if(next_token.type = OPERATOR & next_token.u.op = =) / 赋值操作 lex(); val = expr(); ptr-value = val; else val = ptr-value; else / 既不是数字也不是(, 也不是标识符 fprintf(stderr, unkown charactor: %cn, next_token.u.op); exit(1); return val;3、在语法分析的同时进行求值递归下降法的优点之一，就语义加工来说，这种方法十分灵活，可以在子程序的任何地方插入语义处理程序。4、错误处理括号是否匹配，除0。目录树./|- hash.h|- hash.c|- main.c|- makefile|- front.h 词法分析程序和语法分析程序的头文件|- scanner.c 词法分析|- parser.c 语法分析|- specification.txt 说明- test.in 测试数据最后给出完整的程序包和运行演示：/files/calculator.zip?lymlocalhost calculator$ makegcc -g -Wall -c hash.cgcc -g -Wall -c parser.cgcc -g -Wall -c scanner.cgcc -g -Wall -c main.cgcc -g -Wall hash.o pars