yacc介绍
? ? ? ? 在mysql源码中，解析sql在sql_yacc.yy中实现，这个文件是一个硕大的文件，用bison来转换为c文件。
? ? ? ? 在《编译原理及实践》中有yacc介绍，编译原理是很深奥的科目，学好了对编程技术好很大的帮助，可惜当初没好好学，需要回炉一下。
? ? ? ? 这里是从《编译原理及实践》的摘录。
? ? ? ? 一个简单的算术表达式的计算器。calc.y，BNF文法如下：
?%{
#include <stdio.h>
#include <ctype.h>
%}
?
%token NUMBER
?
%%
?
command : exp { printf("%d\n", $1);}
? ? ? ? ? ? ? ? ;
exp : exp '+' term { $$ = $1 + $3 ;}
? ? ? | exp '-' term { $$ = $1 - $3 ;}
? ? ? | term { $$ = $1 ;}
? ? ? ;
term : term '*' factor { $$ = $1 * $3 ;}
? ? ? ? | factor { $$ = $1 ;}
? ? ? ? ;
factor : NUMBER { $$ = $1 ;}
? ? ? ? ? | '(' exp ')' { $$ = $2 ;}?
? ? ? ? ? ;
%%
?
main(){
? ? ? ? ?/*extern int yydebug ; ? ?------- 此处为debug显示yacc执行调用用
? ? ? ? ?yydebug = 1 ;*/
? ? ? ? return yyparse();
}
?
int yylex(void){ ? ? ? ? ? -------可以通过lex工具来进行词法分析，这里用手工实现
? ? ? ? int c ;
? ? ? ? while( (c = getchar()) == ' ');
? ? ? ? if( isdigit(c) ){
? ? ? ? ? ? ? ?ungetc(c, stdin);
? ? ? ? ? ? ? ?scanf("%d", &yylval);
? ? ? ? ? ? ? ?return (NUMBER);
? ? ? ? }
? ? ? ? if (c == '\n') return 0 ; ? ? ?------0表示输入结束，结束词法分析
? ? ? ? return (c) ;
}
?
int yyerror(char* s){
? ? ? ?fprintf(stderr,"%s\n",s);
? ? ? ?return 0 ;
}
? ? ? ?上面的yylex，可以通过lex来实现，这里为手工实现。
? ? ? ?同过main函数可以看出，执行yyparse，这个为yacc这类的工具产生的的方法，就是根据文法执行%%之间的用户定义的操作。
? ? ? ?每个在L A L R ( 1 )分析栈中的符号值都可通过使用以$开始的伪变量来引用。$ $代表刚才被识别出来的非终结符的值，也就是在文法规则左边的符号。伪变量$ 1、$ 2、$ 3等等都代表了文法规则右边的每个连续的符号。
? ? ? ?个人理解就是当文法匹配，执行｛｝里面的语句。
? ? ? ?执行一下看看效果，bison -y calc.y ?gcc y.tab.c -o test ----y.tab.c为自动产生的c文件
? ? ? ?执行./test?
? ? ? ?程序已经可以跑了，当输入12+4回车时，结果已经出来了。
? ? ? ?把main函数的注释去掉，用bison -y -t 产生c文件，再用gcc y.tab.c -o test 编译
? ? ? ?执行./test?
显示如下：
Starting parse
Entering state 0
Reading a token: 12+3 ? ---此处为手工输入的值
Next token is token NUMBER ()
Shifting token NUMBER ()
Entering state 1
Reducing stack by rule 7 (line 19): ? -----19行为factor : NUMBER { $$ = $1 ;}
? ?$1 = token NUMBER ()
-> $$ = nterm factor ()
Stack now 0
Entering state 6
Reducing stack by rule 6 (line 17): ?-----17行为factor { $$ = $1 ;}
? ?$1 = nterm factor ()
-> $$ = nterm term ()
Stack now 0
Entering state 5
Reading a token: Next token is token '+' () ?---解析到+号
Reducing stack by rule 4 (line 14): ? ----14行为term { $$ = $1 ;}
? ?$1 = nterm term ()
-> $$ = nterm exp ()
Stack now 0
Entering state 4
Next token is token '+' ()
Shifting token '+' ()
Entering state 9
Reading a token: Next token is token NUMBER ()
Shifting token NUMBER ()
Entering state 1
Reducing stack by rule 7 (line 19): ?-----19行为factor : NUMBER { $$ = $1 ;}
? ?$1 = token NUMBER ()
-> $$ = nterm factor ()
Stack now 0 4 9
Entering state 6
Reducing stack by rule 6 (line 17): ?-----17行为factor { $$ = $1 ;}
? ?$1 = nterm factor ()
-> $$ = nterm term ()
Stack now 0 4 9
Entering state 13
Reading a token: Now at end of input.
Reducing stack by rule 2 (line 12): ? ----12行为exp : exp '+' term { $$ = $1 + $3 ;}
? ?$1 = nterm exp ()
? ?$2 = token '+' ()
? ?$3 = nterm term ()
-> $$ = nterm exp ()
Stack now 0
Entering state 4
Now at end of input.
Reducing stack by rule 1 (line 10): ----10行为command : exp { printf("%d\n", $1);}
? ?$1 = nterm exp ()
15
-> $$ = nterm command ()
Stack now 0
Entering state 3
Now at end of input.
Stack now 0 3
Cleanup: popping nterm command ()
? ? ? yacc这东西还挺神奇，java也有个javacc，也能实现同样的功能，amoeba中有用到。