BISON语法分析工具.doc

?自动语法分析工具Bison ?(2015-01-30 12:42:55) 转载▼ 杂谈 ????BISON用于语法分析器的自动生成，它可以很方便地生成一个所谓的抽象语法树,?树的每一个子树都代表了一个特定的语法成分，便于后期处理。这个工具可以在网上下载获得。化点时间学习这个工具的用法，并用于SQL语言的分析，可以让我们把精力专注在语法规则上，而不是具体的分析函数编写上。对整个DBMS来说，使用自动化工具进行语言处理程序的自动生成，使得语言分析模块成为最可靠最方便维护的模块之一。  BISON源文件的结构 ?????我们需要按照BISON的要求，书写BISON的源程序（gramma.y）。遵循它的规则是必须的，BISON会把它的源文件翻译为C文件。因此，BISON是编译程序的翻译器。BISON的源文件通常由八个部分组成： 一．????自由定义部分: %{ %} 这部分被BISON原封不动地复制到输出的.C文件中。通常用于定义一些在规则程序中需要使用的一些常量，函数原形等。 ?二．语法栈的联合(UNION)结构 语法分析程序使用一个堆栈来存放规约到的各个语法成分，堆栈用一个数组表示，这个数组的每个元素需要能够描述每一个语法成分，所以采用一个UNION： %union { } ?Union中的每一个项，都是一个语法规则的每一个非终结符；以整数四则表达式为例： exp : exp ‘ ’ exp ????| exp ‘-‘ exp ????| exp ‘*’ exp ????| exp ‘/’ exp ????| ‘(‘ exp ‘)’ ????| lt_integer ； lt_integer: LT_INTEGER; 这里有两个语法规则，对应了两个非终结符号: exp?是表达式，?lt_integer表示整数常量（LT_INTEGER表示词法分析程序返回的一个确认为整数的单词）。对应的，这个union可以书写为： ?%{ ?par_exp_t*??????exp; ?int?????????????lt_integer; }; ?其中par_exp_t用来描述被识别出的exp的信息，int存放被识别出的整数的值。上面的例子很简单，所以union只有两个字段；在DM6的语法分析程序中，这个UNION大约有490个字段，也就是，大概有490个语法规则产生式。当然你也可以不采用这个UNION,?那么每一个规约出来的语法成分都是一个C指针,?需要上层做类型转换来解释。 ?三．非终结符的类型声明 上面定义了分析栈的UNION类型,?还需要把字段名与语法非终结符号对应起来： %type 字段名??非终结符号 ?如上例，这部分应该写为： %type exp exp %type lt_integer lt_integer ?看上去似乎有点多余，每一行都是一个简单的重复。但前面一个表示的是UNION中对应的字段名，后一个是语法符号；如果我们把UNION改为: ?%{ par_exp_t*?eeee; int?????????iiii; }; ?那么对应的类型声明需要改为： %type eeee exp %type iiii lt_integer; ?这种不一致的写法，事实上会造成混乱，所以应该采用上面一致的写法。 ?四：单词（token）声明 语法分析的输入是连续的有确定意义的单词。下面需要声明分析程序支持的单词： %token LT_INTEGER 对于SQL语法，关键字如：SELECT, FROM, WHERE等，都可以定义为单词: ?%token KW_SELECT, KW_FROM %token KW_WHERE ?五.?确定运算符的优先级 %left ‘-‘ ‘ ’ %left ‘*’ ‘/’ %left ‘(‘ ‘)’ %left表示是左结合的，表示先规约左边的产生式，反应到表达式计算中： 1 2 3?别识别为：（（1 2）?3),?而不是?(1 (2 3)) ?优先级低的符号列在前面，高有限级的符号列在后面;同一行的表示优先级相同。所以上面的书写方式，　符合“先乘除，后加减，括号最优先”的原则。 ?除了%left以后，还有%right, %nonassoc等用来只是右结合，或者不结合等说明符号，可查看bison的详细说明。  ?六.声明语法的开始符号 %start exp 这是告知bison,?这是语法最终需要规约的非终结符号。 ? 七.语法规则定义 这是语法分析程序的核心定义部分，用%%开始,?前面已经列出了关于表达式的语法规则： %% exp : exp ‘ ’ exp ????| exp ‘-‘ exp ????| exp ‘*’ exp ????| exp ‘/’ exp ????| ‘(‘ exp ‘)’ ??