bison操作符结合性有bug
好像bison的操作符结合性不起作用啊，
我按照bison的手册上抄过来的，程序如下（在exp规则中加了一些printf的debug信息）：
/* Reverse polish notation calculator. */
%{
#define YYSTYPE double
#include <math.h>
#include <ctype.h>
#include <stdio.h>
int yylex (void);
void yyerror (char const *);
%}
%token NUM
/* Bison declarations. */
%token NUM
%left '- ' '+ '
%left '* ' '/ '
%left NEG /* negation--unary minus */
%right '^ ' /* exponentiation */
%% /* The grammar follows. */
input: /* empty */
| input line
;
line: '\n '
| exp '\n ' { printf ( "\t%.10g\n ", $1); }
;
exp: NUM { $$ = $1;printf( "debug 1\n "); }
| exp '+ ' exp { $$ = $1 + $3;printf( "debug 2\n "); }
| exp '- ' exp { $$ = $1 - $3;printf( "debug 3\n "); }
| exp '* ' exp { $$ = $1 * $3;printf( "debug 4\n "); }
| exp '/ ' exp { $$ = $1 / $3;printf( "debug 5\n "); }
| '- ' exp %prec NEG { $$ = -$2;printf( "debug 6\n "); }
| exp '^ ' exp { $$ = pow ($1, $3);printf( "debug 7\n "); }
| '( ' exp ') ' { $$ = $2;printf( "debug 8\n "); }
;
%%
/* The lexical analyzer returns a double floating point
number on the stack and the token NUM, or the numeric code
of the character read if not a number. It skips all blanks
and tabs, and returns 0 for end-of-input. */
int
yylex (void)
{
int c;
/* Skip white space. */
while ((c = getchar ()) == ' ' || c == '\t ')
;
/* Process numbers. */
if (c == '. ' || isdigit (c))
{
ungetc (c, stdin);
scanf ( "%lf ", &yylval);
return NUM;
}
/* Return end-of-input. */
if (c == EOF)
return 0;
/* Return a single char. */
return c;
}
int
main (void)
{
return yyparse ();
}
/* Called by yyparse on error. */
void
yyerror (char const *s)
{
fprintf (stderr, "%s\n ", s);
}
运行之后输入(1+2)^(4-3)
然后这是结果：
(1+2)^(4-3)
debug 1
debug 1
debug 2
debug 8
debug 1
debug 1
debug 3
debug 8
debug 7
3
为什么不是预想的：
(1+2)^(4-3)
debug 1
debug 1
debug 3
debug 8
debug 1
debug 1
debug 2
debug 8
debug 7
3
或
(1+2)^(4-3)
debug 1
debug 1
debug 1
debug 1
debug 3
debug 8
debug 2
debug 8
debug 7
3
？把right改成left之后执行结果也是一样，那么操作符结合性还有什么意义？
Solaris和Windows下的bison都试过了，结果都是一样。
不知如何才能使结果是预想的这样？
[解决办法]
那是什么东东？
[解决办法]
你试试看 1^2^3 在想想是咋回事 ....
[解决办法]
你再在有疑问的几个地方下个断点看看 yyvs 里的内容吧 ...
[解决办法]
这个顺序有关系么 ...
如果你的程序有代码生成的过程, 可以在这个时候做这件事情 ...
[解决办法]
c/cpp 里表达式求值本来就大部分是从右到左, 偶觉得这暴不自然, 竟然有人会稀饭这种顺序, 狂晕 ...
不需要对语句进行预分析, yacc 直接可以生成你需要的东东.. 一会有空的时候写个 ..
[解决办法]
yacc..
不太明白..
[解决办法]
什么跟什么哦, 左结合只是表示 a+b+c+d == ((a+b)+c)+d ,右结合只是表示 a^b^c^d == a^(b^(c^d))), abcd 的计算顺序本来就没有保证, 你想怎么算就怎么算 ...
[解决办法]
bison中的left和right只是用来解决生成语法树的二义性，而左右部分哪个先运算出来是由语法树的遍历方式决定的吧。
[解决办法]
偶可木有说过要预处理才能生成结果, 代码生成的时候你想先给右边的表达式求值就先求右边, 想先求左边就先左边, 跟其他东东有啥关系 ...
[解决办法]
bison生成语法树的顺序是没法改变的。bison用的是LALR分析法。(1+2)^(4-3)中1+2会被先规约,也就是：(1+2)^(4-3)中
1.规约exp -> exp + exp 即 (exp)^(4-3)
2.规约exp -> ( exp ) 即 exp ^ ( 4-3 )，这时^是右结合的，所以会先规约右侧
3.规约exp -> exp - exp 即 exp ^ ( exp )， 现作这个规约是因为在遇到 ') '前，遇到了 '+ '。
4.规约exp -> ( exp )即 exp ^ exp
5.规约exp -> exp ^ exp 即 exp, 规约完成。
所以执行顺序是无法改变的。但是，如果不是解释执行，而是编译执行，就像C++这样的。bison是可以自定义语意记录的。所以实现起来还是比较简单的。
例如，基本块使用链表保存的。
...
%{
typedef struct block{
struct block *next;
...//存放生成代码的中间结果。
}block_t;
%}
%union{
block_t *pblock;/*语意记录*/
};
...
type <pblock> exp
%%
...
exp:
...
| exp '+ ' exp {//左结合
$$ = $1；$1-> next=$3;...
}
| exp '^ ' exp{//右结合
$$ = $3;$3-> next=$1;...
}
...
[解决办法]
解释执行的话，可以利用延迟计算来完成，例如可以这样：
%{
...
typedef struct node{
charop;//存放运算符
struct node *left; //左子树
struct node *right; //右子树
double value; //叶子节点
}node_t;
double calculate( node_t *node );//实际运算的函数
...
%}
%union{
node_t *pnode;
doublevalue;
};
type <pnode> exp
type <value> NUM
...
%%
input:| input line;
line: '\n '
| exp '\n ' { printf( "\t%.10g\n ", calculate($1)); };
exp: NUM {
$$ = (node_t*)malloc(node_t);$$-> op= '\0 ';$$-> value = $1;
}
| exp '+ ' exp { $$ = (node_t*)malloc(node_t);$$-> op = '+ ';$$-> left=$1;$$-> right=$3; }
| exp '^ ' exp { $$ = (node_t*)malloc(node_t);$$-> op = '^ ';$$-> left=$1;$$-> right=$3; }
...
%%
double calculate( node_t *node )
{
double ret= 0.0;
if(node == NULL)return ret;
switch( node-> op )
{
case '\0 ':ret=node-> value;break;
case '+ ':ret=calculate(node-> left)+calculate(node-> right);break;
case '^ ':{
double tmpr = calculate(node-> right);//这里实现了先算右侧。
double tmpl = calculate(node-> left);
ret= pow(tmpl,tmpr);
}break;
...
}
free( node );
return ret;
}
...
还有，lz的产生式好像加减法和乘除法优先级相同。
