. . . LALR(1) 表达式计算器 源代码
程序代码：/* 产生式
lines : lines expr '\n'
| lines '\n'
| error '\n'
;
expr : expr '+' term
| expr '-' term
| term
;
term : term '*' factor
| term '/' factor
| factor
;
factor : '(' expr ')'
| '(' expr error
| '-' factor
| NUMBER
;
*/
// 110211 Flying Blue 整理
// 像天书一样.. 不过速度确实很快!
// 编译器的词法, 语法分析, 就是采用这种方式实现的
#include <ctype.h>
#include <stdio.h>
#define STYPE double
#define NUMBER 257
#define ERRCODE 256
short lhs_tbl[] =
{
-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3,
};
short len_tbl[] =
{
2, 3, 2, 0, 2, 3, 3, 1, 3, 3, 1, 3, 3, 2, 1,
};
short defred_tbl[] =
{
0, 0, 0, 4, 14, 2, 0, 0, 0, 0, 10, 13, 0, 1, 0, 0, 0, 0, 12, 11, 0, 0, 8, 9,
};
short dgoto_tbl[] =
{
2, 8, 9, 10,
};
short sindex_tbl[] =
{
- 251, 5, -10, 0, 0, 0, - 38, - 38, - 6, - 29, 0, 0, - 35, 0, - 38, - 38, - 38, - 38,
0, 0, - 29, - 29, 0, 0,
};
short rindex_tbl[] =
{
1, 0, 0, 0, 0, 0, 0, 0, 0, - 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 4, 0, 0,
};
short gindex_tbl[] =
{
0, 12, 2, 6,
};
#define TABLESIZE 260
short main_tbl[] =
{
5,
3, 7, 7, 13, 1, 19, 6, 14, 5, 15,
3, 11, 16, 6, 3, 20, 21, 17, 12, 0,
0, 22, 23, 0, 0, 0, 0, 0, 0, 7,
0, 0, 0, 7, 6, 7, 14, 7, 15, 5,
3, 5, 0, 5, 6, 3, 6, 0, 6, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 4, 0,
18, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 4, 0, 7, 0,
0, 0, 0, 0, 5, 0, 0, 3, 0, 6,
};
short check_tbl[] =
{
10,
0, 40, 10, 10, 256, 41, 45, 43, 10, 45,
10, 6, 42, 10, 10, 14, 15, 47, 7, -1,
-1, 16, 17, -1, -1, -1, -1, -1, -1, 40,
-1, -1, -1, 41, 45, 43, 43, 45, 45, 41,
40, 43, -1, 45, 41, 45, 43, -1, 45, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 257, -1,
256, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 257, -1, 256, -1,
-1, -1, -1, -1, 256, -1, -1, 257, -1, 256,
};
#define FINAL 2
#define STACKSIZE 500
#define MAXDEPTH 500
#define errok (errflag=0)
int nerrs;
int errflag;
int mychar;
short *state_stack_ptr;
STYPE *vsp;
STYPE val;
STYPE lex_val;
short state_stack[STACKSIZE];
STYPE val_stack[STACKSIZE];
//-------------------------------------------------------------------------
char formula[256] = "111 + 222 - 333 + 4.5\n";
int formula_ptr = 0;
int lex(void)
{
int c;
while((c = formula[formula_ptr]) == ' ')
formula_ptr++;
if(c == '.' || isdigit(c))
{
int tmp;
sscanf(formula + formula_ptr, "%lf%n", &lex_val, &tmp);
formula_ptr += tmp;
return NUMBER;
}
else formula_ptr++;
return c;
}
//-------------------------------------------------------------------------
int parse()
{
int m, n, state;
formula_ptr = 0;
nerrs = 0;
errflag = 0;
mychar = ( -1);
state_stack_ptr = state_stack;
vsp = val_stack;
*state_stack_ptr = state = 0;
loop:
if(n = defred_tbl[state])
{
goto reduce;
}
if(mychar < 0)
{
if((mychar = lex()) < 0)
{
mychar = 0;
}
}
if((n = sindex_tbl[state]) && (n += mychar) >= 0 && n <= TABLESIZE && check_tbl[n] == mychar)
{
if(state_stack_ptr >= state_stack + STACKSIZE - 1)
{
goto overflow;
}
*++state_stack_ptr = state = main_tbl[n];
*++vsp = lex_val;
mychar = ( -1);
if(errflag > 0)
{
--errflag;
}
goto loop;
}
if((n = rindex_tbl[state]) && (n += mychar) >= 0 && n <= TABLESIZE && check_tbl[n] == mychar)
{
n = main_tbl[n];
goto reduce;
}
if(errflag)
{
goto inrecovery;
}
printf("error: 语法错误!\n");
++nerrs;
inrecovery:
if(errflag < 3)
{
errflag = 3;
for(;;)
{
if((n = sindex_tbl[ *state_stack_ptr]) && (n += ERRCODE) >= 0 && n <= TABLESIZE && check_tbl[n] == ERRCODE)
{
if(state_stack_ptr >= state_stack + STACKSIZE - 1)
{
goto overflow;
}
*++state_stack_ptr = state = main_tbl[n];
*++vsp = lex_val;
goto loop;
}
else
{
if(state_stack_ptr <= state_stack)
{
goto abort;
}
--state_stack_ptr;
--vsp;
}
}
}
else
{
if(mychar == 0)
{
goto abort;
}
mychar = ( -1);
goto loop;
}
reduce:
m = len_tbl[n];
val = vsp[1-m];
switch(n)
{
case 1:
{
printf("* 运算结果: %g\n", vsp[-1]);
}
break;
case 4:
{
printf("error: 请重新输入: ");
errok;
}
break;
case 5:
{
val = vsp[-2] + vsp[0];
}
break;
case 6:
{
val = vsp[-2] - vsp[0];
}
break;
case 8:
{
val = vsp[-2] *vsp[0];
}
break;
case 9:
{
val = vsp[-2] / vsp[0];
}
break;
case 11:
{
val = vsp[-1];
}
break;
case 12:
{
val = vsp[-1];
printf("error: 缺少')'\n");
errok;
}
break;
case 13:
{
val = - vsp[0];
}
break;
}
state_stack_ptr -= m;
state = *state_stack_ptr;
vsp -= m;
m = lhs_tbl[n];
if(state == 0 && m == 0)
{
state = FINAL;
*++state_stack_ptr = FINAL;
*++vsp = val;
if(mychar < 0)
{
if((mychar = lex()) < 0)
{
mychar = 0;
}
}
if(mychar == 0)
{
goto accept;
}
goto loop;
}
if((n = gindex_tbl[m]) && (n += state) >= 0 && n <= TABLESIZE && check_tbl[n] == state)
{
state = main_tbl[n];
}
else
{
state = dgoto_tbl[m];
}
if(state_stack_ptr >= state_stack + STACKSIZE -1)
{
goto overflow;
}
*++state_stack_ptr = state;
*++vsp = val;
goto loop;
overflow:
printf("error: 堆栈溢出!\n");
abort:
return (1);
accept:
return (0);
}
int main(void)
{
char currch;
int cptr;
printf("======== LALR(1) 表达式计算器========\n\n");
while(1)
{
printf("* 请输入表达式: ");
cptr = 0;
do
{
currch = getchar();
if(currch == '#') return 0;
formula[cptr] = currch;
cptr++;
} while(currch != '\n');
formula[cptr] = 0;
parse();
}
return 0;
}
[ 本帖最后由 flyue 于 2011-2-12 20:18 编辑 ]
