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中有用到。