bison 编译sql的基本知识

一。bison是干什么的？

bison 是一个语法分析器，把用户输入的内容，根绝在.y文件中事先定义好的规则，构建一课语法分析树。（所谓的规则就是，匹配上对应字符之后，执行相应的动作。）

1.一个简单的语法例子和分析：

statement ：NAME '=' expression

expression :NUMBER '+' NUMBER

　　　　　　|NUMBER '-' NUMBER

这个语法的意思是：

冒号（：）用来间隔一条规则的左边和右边。

statement 等价于 NAME '=' expression 。

由于在语法中规定大写字母和引号的内容为终结符，所以NAME '=' 两个字符不再有含义，已经终结。

但是expression 是非终结符，根据第二行的规定，expression 又等价为两个数的加法或者两个数的减法。其中竖线（|）表示一个语法符号有两种等价方式。 NUMBER '+' NUMBER NUMBER '-' NUMBER均是终结符，所以语法解析结束。

假如现在的输入是fred=12+13. 则语法解析树如下：（圆形都是非终结符，矩形都是终结符）

2.移进规约分析

当bison处理一个语法分析树时，会创建一组状态，每个状态对应一个或者多个分析过的规则中的可能的位置。当读到的记号不足以结束一条规则的时候，就会把这个记号压入一个内部堆栈，然后切换到新状态，这个过程叫做移进。当压入栈内的所有的语法符号已经等价于一个规则的右部时，就把这些符号全部弹出，把规则的左部压入栈。这个过程叫做规约。

下面是一个例子：

fred=12+13

语法分析器一次移进一个记号。

堆栈：

fred

fred =

fred =12

fred=12 +

fred =12+13 把12+13 规约成expression，12+13弹出，expression压入

fred = expression　　　把fred = expression规约成statement　　　fred = expression弹出，statement压入

statement

3.sql语言中的语法解析过程。（以select为例）

首先，需要一个词法分析器来识别SQL中的所有关键字。

程序的运行流程：（以select为例）

1.用户输入sql语句，调用sql.tab.c中的解析函数，得到select_statement的状态。（。y文件中为sql语句定义了好多个状态。）

2.select_statement作为参数，去匹配规则，并执行相应的动作，即构建一课语法树。这个匹配的过程由yyparse（）库函数来完成！

下面这段代码是.y文件中，定义的关于select_statement部分的代码：

select_statement:

    SELECT selection table_exp

    {

        struct stnode * p = create_non_terminal_node("select_section");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }        

        $$ = p;

    }

selection:

    scalar_exp_list

    {

        struct stnode * p = create_non_terminal_node("selection");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    | '*'

    {

        struct stnode * p = create_non_terminal_node("selection");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    ;

scalar_exp_list:

    scalar_exp

    {

        struct stnode * p = create_non_terminal_node("scalar_exp_list");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    | scalar_exp_list','scalar_exp

    {

        struct stnode * p = create_non_terminal_node("scalar_exp_list");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    ;

table_exp:

    from_clause

    opt_order_by_clause

    {

        struct stnode * p = create_non_terminal_node("table_exp");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    ;

from_clause:

    FROM table_ref_list opt_where_clause

    {

        struct stnode * p = create_non_terminal_node("from_clause");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    ;

table_ref_list:

    table_ref

    {

        struct stnode * p = create_non_terminal_node("table_ref_list");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    | table_ref_list','table_ref

    {

        struct stnode * p = create_non_terminal_node("table_ref_list");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    ;

table_ref:

    table

    {

        struct stnode * p = create_non_terminal_node("table_ref");

        if(!p)

        {

            printf("error:create_non_terminal_node\n");

            return ;

        }

        if(!append_child(p, $))

        {

            printf("error:append_child\n");

            return ;

        }

        $$ = p;

    }

    ;

3.根据上面代码中的定义的规则，，，，展示下面的语法树的构建过程：

规则动作：语法树

select_statement : SELECT selection table_exp node("select_section") select_statement

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 SELECT selection table_exp

selection : scalar_exp_list node("selection") *

table_exp : from_clause opt_order_by_clause node("table_exp") from_clause opt_order_by_clause

from_clause: FROM table_ref_list opt_where_clause node("from_clause") FROM table_ref_list opt_where_clause

table_ref_list :table_ref

| table_ref_list','table_ref node("table_ref_list ") table_ref

table_ref: table node("table ") table

巴特西

bison 编译sql的基本知识

最新文章

热门文章