我按照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都试过了，结果都是一样。
不知如何才能使结果是预想的这样？
25 个解决方案
#1
那是什么东东？
#2
你试试看 1^2^3 在想想是咋回事 ....
#3
1^2^3
debug 1
debug 1
debug 1
debug 7
debug 7
1
还不是很明白，难道只有都是right的操作才会先执行右面的？
但是c++的编译器执行p()=p1()+p2();（函数p返回一个引用，这样就可以赋值了）的时候，会先打印出p1和p2的执行结果，然后再执行函数p打印p中的printf然后返回引用的
debug 1
debug 1
debug 1
debug 7
debug 7
1
还不是很明白，难道只有都是right的操作才会先执行右面的？
但是c++的编译器执行p()=p1()+p2();（函数p返回一个引用，这样就可以赋值了）的时候，会先打印出p1和p2的执行结果，然后再执行函数p打印p中的printf然后返回引用的
#4
你再在有疑问的几个地方下个断点看看 yyvs 里的内容吧 ...
#5
稍微有点明白了，我再看看……
#6
yyvs保存的是语意值，每次把规则执行结果放到里面，1^2^3的时候yyvs显示是先执行2^3然后执行1^8的，不过还是不清楚如何修改程序才能达到执行(1+2)^(4-3)的时候先执行4-3然后执行1+2最后执行3^1？
#7
这个顺序有关系么 ...
如果你的程序有代码生成的过程, 可以在这个时候做这件事情 ...
如果你的程序有代码生成的过程, 可以在这个时候做这件事情 ...
#8
确实有代码生成的过程，需要先执行后面的生成先决条件，然后执行前面的。
不过c++在执行p1()+p2()=p3()-p4();的时候执行的顺序是p3()、p4()、'-'、p1()、p2()、'+'、'='，是重载了+-=操作符在里面打印出执行顺序之后得出的结论。
我认为操作符结合性不仅表现为结合性的计算顺序，还要表现为结合性的左右子表达式的执行顺序，bison只实现了部分操作符结合性的特性，如果能和c++编译器那样执行就好了。
现在碰到这种情况，唯一的办法就是先对语句进行预分析，生成先决条件，然后对语句再进行分析了，其中设个标志位就可以。
不过c++在执行p1()+p2()=p3()-p4();的时候执行的顺序是p3()、p4()、'-'、p1()、p2()、'+'、'='，是重载了+-=操作符在里面打印出执行顺序之后得出的结论。
我认为操作符结合性不仅表现为结合性的计算顺序，还要表现为结合性的左右子表达式的执行顺序，bison只实现了部分操作符结合性的特性，如果能和c++编译器那样执行就好了。
现在碰到这种情况，唯一的办法就是先对语句进行预分析，生成先决条件，然后对语句再进行分析了，其中设个标志位就可以。
#9
c/cpp 里表达式求值本来就大部分是从右到左, 偶觉得这暴不自然, 竟然有人会稀饭这种顺序, 狂晕 ...
不需要对语句进行预分析, yacc 直接可以生成你需要的东东.. 一会有空的时候写个 ..
不需要对语句进行预分析, yacc 直接可以生成你需要的东东.. 一会有空的时候写个 ..
#10
但是执行p1()+p2()和p3()+p4()的时候却是从左到右的，这应该是按照结合性执行的，只有right结合的话才会先执行右面的，并不是大部分是从右到左的。
yacc不是和bison一样的吗？bison是yacc的GNU版？
yacc不是和bison一样的吗？bison是yacc的GNU版？
#11
yacc..
不太明白..
不太明白..
#12
什么跟什么哦, 左结合只是表示 a+b+c+d == ((a+b)+c)+d ,右结合只是表示 a^b^c^d == a^(b^(c^d))), abcd 的计算顺序本来就没有保证, 你想怎么算就怎么算 ...
#13
这是知道的，不过好像c++编译器的结合性的执行顺序也有区别的。
#14
c++有右结合的东东么, 赋值不算 ..
#15
除了赋值，其它好像都是左结合的了。
不过赋值操作可以说明问题吧
不过赋值操作可以说明问题吧
#16
对了，好像三元“?:”和逗号“,”有一个也是右结合，忘记是哪个了
#17
C++操作符的优先级&结合性: http://hi.baidu.com/xyh2007/blog/item/b2cd4b60c5dfa145eaf8f8b3.html
#18
bison中的left和right只是用来解决生成语法树的二义性，而左右部分哪个先运算出来是由语法树的遍历方式决定的吧。
#19
从上面和mLee79的讨论来看也的确是这个样子了，所以如果需要后面的子表达式来初始化一些信息的话，只能先对语句进行预分析，生成先决条件，然后对语句再进行分析了，其中设个标志位就可以。
不知道还有没有更好的办法？
不知道还有没有更好的办法？
#20
偶可木有说过要预处理才能生成结果, 代码生成的时候你想先给右边的表达式求值就先求右边, 想先求左边就先左边, 跟其他东东有啥关系 ...
#21
怎么做到？按照一开始的程序，输入(1+2)^(4-3)的时候如何才能先计算4-3然后计算1+2？从而debug信息中的printf先输出"debug 3"然后是"debug 2"？
#22
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;...
}
...
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;...
}
...
#23
多谢WizardLucien了，不过现在是解释执行的程序，就如上面的算术表达式运算这样，看来改起来比较麻烦，还要想其他的办法，当然也可以改成编译执行的方式，只是改动比较大了。
再次感谢大家的帮助，基本都明白了，受益非浅，准备结贴了……
再次感谢大家的帮助，基本都明白了，受益非浅，准备结贴了……
#24
解释执行的话，可以利用延迟计算来完成，例如可以这样：
%{
...
typedef struct node{
char op;//存放运算符
struct node *left; //左子树
struct node *right; //右子树
double value; //叶子节点
}node_t;
double calculate( node_t *node );//实际运算的函数
...
%}
%union{
node_t *pnode;
double value;
};
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的产生式好像加减法和乘除法优先级相同。
%{
...
typedef struct node{
char op;//存放运算符
struct node *left; //左子树
struct node *right; //右子树
double value; //叶子节点
}node_t;
double calculate( node_t *node );//实际运算的函数
...
%}
%union{
node_t *pnode;
double value;
};
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的产生式好像加减法和乘除法优先级相同。
#25
好，我再研究一下
#1
那是什么东东？
#2
你试试看 1^2^3 在想想是咋回事 ....
#3
1^2^3
debug 1
debug 1
debug 1
debug 7
debug 7
1
还不是很明白，难道只有都是right的操作才会先执行右面的？
但是c++的编译器执行p()=p1()+p2();（函数p返回一个引用，这样就可以赋值了）的时候，会先打印出p1和p2的执行结果，然后再执行函数p打印p中的printf然后返回引用的
debug 1
debug 1
debug 1
debug 7
debug 7
1
还不是很明白，难道只有都是right的操作才会先执行右面的？
但是c++的编译器执行p()=p1()+p2();（函数p返回一个引用，这样就可以赋值了）的时候，会先打印出p1和p2的执行结果，然后再执行函数p打印p中的printf然后返回引用的
#4
你再在有疑问的几个地方下个断点看看 yyvs 里的内容吧 ...
#5
稍微有点明白了，我再看看……
#6
yyvs保存的是语意值，每次把规则执行结果放到里面，1^2^3的时候yyvs显示是先执行2^3然后执行1^8的，不过还是不清楚如何修改程序才能达到执行(1+2)^(4-3)的时候先执行4-3然后执行1+2最后执行3^1？
#7
这个顺序有关系么 ...
如果你的程序有代码生成的过程, 可以在这个时候做这件事情 ...
如果你的程序有代码生成的过程, 可以在这个时候做这件事情 ...
#8
确实有代码生成的过程，需要先执行后面的生成先决条件，然后执行前面的。
不过c++在执行p1()+p2()=p3()-p4();的时候执行的顺序是p3()、p4()、'-'、p1()、p2()、'+'、'='，是重载了+-=操作符在里面打印出执行顺序之后得出的结论。
我认为操作符结合性不仅表现为结合性的计算顺序，还要表现为结合性的左右子表达式的执行顺序，bison只实现了部分操作符结合性的特性，如果能和c++编译器那样执行就好了。
现在碰到这种情况，唯一的办法就是先对语句进行预分析，生成先决条件，然后对语句再进行分析了，其中设个标志位就可以。
不过c++在执行p1()+p2()=p3()-p4();的时候执行的顺序是p3()、p4()、'-'、p1()、p2()、'+'、'='，是重载了+-=操作符在里面打印出执行顺序之后得出的结论。
我认为操作符结合性不仅表现为结合性的计算顺序，还要表现为结合性的左右子表达式的执行顺序，bison只实现了部分操作符结合性的特性，如果能和c++编译器那样执行就好了。
现在碰到这种情况，唯一的办法就是先对语句进行预分析，生成先决条件，然后对语句再进行分析了，其中设个标志位就可以。
#9
c/cpp 里表达式求值本来就大部分是从右到左, 偶觉得这暴不自然, 竟然有人会稀饭这种顺序, 狂晕 ...
不需要对语句进行预分析, yacc 直接可以生成你需要的东东.. 一会有空的时候写个 ..
不需要对语句进行预分析, yacc 直接可以生成你需要的东东.. 一会有空的时候写个 ..
#10
但是执行p1()+p2()和p3()+p4()的时候却是从左到右的，这应该是按照结合性执行的，只有right结合的话才会先执行右面的，并不是大部分是从右到左的。
yacc不是和bison一样的吗？bison是yacc的GNU版？
yacc不是和bison一样的吗？bison是yacc的GNU版？
#11
yacc..
不太明白..
不太明白..
#12
什么跟什么哦, 左结合只是表示 a+b+c+d == ((a+b)+c)+d ,右结合只是表示 a^b^c^d == a^(b^(c^d))), abcd 的计算顺序本来就没有保证, 你想怎么算就怎么算 ...
#13
这是知道的，不过好像c++编译器的结合性的执行顺序也有区别的。
#14
c++有右结合的东东么, 赋值不算 ..
#15
除了赋值，其它好像都是左结合的了。
不过赋值操作可以说明问题吧
不过赋值操作可以说明问题吧
#16
对了，好像三元“?:”和逗号“,”有一个也是右结合，忘记是哪个了
#17
C++操作符的优先级&结合性: http://hi.baidu.com/xyh2007/blog/item/b2cd4b60c5dfa145eaf8f8b3.html
#18
bison中的left和right只是用来解决生成语法树的二义性，而左右部分哪个先运算出来是由语法树的遍历方式决定的吧。
#19
从上面和mLee79的讨论来看也的确是这个样子了，所以如果需要后面的子表达式来初始化一些信息的话，只能先对语句进行预分析，生成先决条件，然后对语句再进行分析了，其中设个标志位就可以。
不知道还有没有更好的办法？
不知道还有没有更好的办法？
#20
偶可木有说过要预处理才能生成结果, 代码生成的时候你想先给右边的表达式求值就先求右边, 想先求左边就先左边, 跟其他东东有啥关系 ...
#21
怎么做到？按照一开始的程序，输入(1+2)^(4-3)的时候如何才能先计算4-3然后计算1+2？从而debug信息中的printf先输出"debug 3"然后是"debug 2"？
#22
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;...
}
...
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;...
}
...
#23
多谢WizardLucien了，不过现在是解释执行的程序，就如上面的算术表达式运算这样，看来改起来比较麻烦，还要想其他的办法，当然也可以改成编译执行的方式，只是改动比较大了。
再次感谢大家的帮助，基本都明白了，受益非浅，准备结贴了……
再次感谢大家的帮助，基本都明白了，受益非浅，准备结贴了……
#24
解释执行的话，可以利用延迟计算来完成，例如可以这样：
%{
...
typedef struct node{
char op;//存放运算符
struct node *left; //左子树
struct node *right; //右子树
double value; //叶子节点
}node_t;
double calculate( node_t *node );//实际运算的函数
...
%}
%union{
node_t *pnode;
double value;
};
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的产生式好像加减法和乘除法优先级相同。
%{
...
typedef struct node{
char op;//存放运算符
struct node *left; //左子树
struct node *right; //右子树
double value; //叶子节点
}node_t;
double calculate( node_t *node );//实际运算的函数
...
%}
%union{
node_t *pnode;
double value;
};
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的产生式好像加减法和乘除法优先级相同。
#25
好，我再研究一下