1 什么时候需要优先级和结合性？
代码语言：javascript复制expr:
expr '-' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
…
;1.1 场景一：不同token如何决定计算的先后顺序？（需要优先级）
当输入1 - 2 * 3时，上面语法无法决定(1 - 2) * 3 or 1 - ( 2 * 3)？
这时需要定义不同token的优先级，来决定先reduce 1-2还是reduce 2*3。
情况一：
代码语言：javascript复制| |
| 3 | --- shift
| |
| 2 | ---
| | reduce: expr '-' expr
| 1 | ---/
|---|情况二：
代码语言：javascript复制| |
| 3 | ---
| | reduce: expr '*' expr
| 2 | ---/
| |
| 1 | --- shift
|---|1.2 场景二：当token优先级相同时，如何决定运算顺序？（需要结合性）
当输入1 - 2 - 5时，上面语法无法决定：(1 - 2) - 5 or 1 - (2 - 5)？
这时优先级相同，需要定义结合性的方向，来决定是先reduce 1-2还是先reduce 2-5。
2 如何声明优先级与结合性？
结合性声明方式：
- 左结合：%left
- 右结合：%right
- 不能结合：%nonassoc
- 连续发现两次运算符会会报语法错误。
优先级的声明方式：
- 不同运算符的相对优先级由声明它们的顺序控制。文件中的第一个优先级/关联性声明声明优先级最低的运算符，下一个此类声明声明优先级稍高的运算符，依此类推。
3 局部提升优先级
有些符号的优先级与上下文强绑定，例如负号
- 作为一元运算符时有很高的优先级：
-4 * 5 - 作为二元运算符时只有中等优先级：
3 - 4 * 5
yacc or bison允许临时修改优先级，使用prec语法修饰运算符：
代码语言：javascript复制…
%left ' ' '-'
%left '*'
%left UMINUS
%%
exp:
…
| exp '-' exp
…
| '-' exp %prec UMINUS // 临时提升优先级为UMINUS，UMINUS具有比*更高的优先级。4 一个计算器实例
效果：
代码语言：javascript复制[mingjie@x ~/proj/lex1]$ make
bison -t -v -d calc.y
flex calc.l
gcc -o calc calc.tab.c lex.yy.c
[mingjie@x ~/proj/lex1]$ ./calc
3-5*6
Result: -27calc.l
代码语言：javascript复制%option noyywrap
%{
#include <stdio.h>
#define YY_DECL int yylex()
#include "calc.tab.h"
%}
whitespace [ t]
newline [n]
digit [0-9]
integer {digit}
decimal (({digit}*.{digit} )|({digit} .{digit}*))
%%
{whitespace} {
/* ignore */
}
{newline} {
return T_NEWLINE;
}
{integer} {
yylval.ival = atoi(yytext);
return T_INT;
}
{decimal} {
yylval.fval = atof(yytext);
return T_FLOAT;
}
" " {return T_PLUS;}
"-" {return T_MINUS;}
"*" {return T_MULTIPLY;}
"/" {return T_DIVIDE;}
"(" {return T_LEFT;}
")" {return T_RIGHT;}
"exit" {return T_QUIT;}
"quit" {return T_QUIT;}
%%calc.y
代码语言：javascript复制%{
#include <stdio.h>
#include <stdlib.h>
extern int yylex();
extern int yyparse();
extern FILE* yyin;
void yyerror(const char* s);
%}
%union
{
int ival;
float fval;
}
%token<ival> T_INT
%token<fval> T_FLOAT
%token T_PLUS T_MINUS T_MULTIPLY T_DIVIDE T_LEFT T_RIGHT
%token T_NEWLINE T_QUIT
%left T_PLUS T_MINUS
%left T_MULTIPLY T_DIVIDE
%nonassoc UMINUS
%type<ival> expr
%type<fval> fexpr
%start calculation
%%
calculation:
| calculation line
;
line: T_NEWLINE
| fexpr T_NEWLINE
{
printf("tResult: %fn", $1);
}
| expr T_NEWLINE
{
printf("tResult: %in", $1);
}
| T_QUIT T_NEWLINE
{
printf("bye!n"); exit(0);
}
;
fexpr: T_FLOAT { $$ = $1; }
| fexpr T_PLUS fexpr { $$ = $1 $3; }
| fexpr T_MINUS fexpr { $$ = $1 - $3; }
| fexpr T_MULTIPLY fexpr { $$ = $1 * $3; }
| fexpr T_DIVIDE fexpr { $$ = $1 / $3; }
| T_LEFT fexpr T_RIGHT { $$ = $2; }
| expr T_PLUS fexpr { $$ = $1 $3; }
| expr T_MINUS fexpr { $$ = $1 - $3; }
| expr T_MULTIPLY fexpr { $$ = $1 * $3; }
| expr T_DIVIDE fexpr { $$ = $1 / $3; }
| fexpr T_PLUS expr { $$ = $1 $3; }
| fexpr T_MINUS expr { $$ = $1 - $3; }
| fexpr T_MULTIPLY expr { $$ = $1 * $3; }
| fexpr T_DIVIDE expr { $$ = $1 / $3; }
| expr T_DIVIDE expr { $$ = $1 / (float)$3; }
;
expr: T_INT { $$ = $1; }
| expr T_PLUS expr { $$ = $1 $3; }
| expr T_MINUS expr { $$ = $1 - $3; }
| expr T_MULTIPLY expr { $$ = $1 * $3; }
| T_LEFT expr T_RIGHT { $$ = $2; }
| T_PLUS expr %prec UMINUS { $$ = $2; }
| T_MINUS expr %prec UMINUS { $$ = -$2; }
;
%%
int main()
{
yyin = stdin;
do
{
yyparse();
} while(!feof(yyin));
return 0;
}
void yyerror(const char* s)
{
fprintf(stderr, "Parse error: %sn", s);
exit(1);
}makefile
代码语言：javascript复制all: calc
calc.tab.c calc.tab.h: calc.y
bison -t -v -d calc.y
lex.yy.c: calc.l calc.tab.h
flex calc.l
calc: lex.yy.c calc.tab.c calc.tab.h
gcc -o calc calc.tab.c lex.yy.c
clean:
rm calc calc.tab.c lex.yy.c calc.tab.h calc.output
