bison
background
在学习SQLite过程中，SQLite中的Virtual Database Engine, 需要解释SQL语言生成字节码，执行。SQLite自行实现了Lemon的parser。我希望了解他如何执行，可以的话，build my own.
Introduction
bison 是 yacc升级版本。
bison 将 .y 文件转为 一个 .c 的语法parser
.y 语法文件
%{
Declarations // 声明区：c语言代码，头文件、全局变量、函数声明。这些内容会原样拷贝到.c文件
%}
Definitions // 定义区：符号声明。 如%token NUMBER
%%
Productions // 规则：
%%
User subroutines // 用户子程序： c代码
规则部分
非终结符 : 产生式 { 动作代码 }
| 产生式 { 动作代码 }
;
expr : expr '+' expr { $$ = $1 + $3; }
| expr '*' expr { $$ = $1 * $3; }
| '(' expr ')' { $$ = $2; }
| NUMBER { $$ = $1; }
;
解释：
| 等价于每行前面都是 expr: 。 4个规则 |
创建一个expr, 通过4个产生式，
$n：指代右边第 n 个符号的“语义值”。
$$：表示左边非终结符的“语义值”。
即如果传入3+4*5.
3->规则4->expr = 3
4,5->规则2-> expr = 20
3+4*5 -> 规则1->expr = 23
💡 expr 可以任何词代替，常写为E
Example：后缀计算
// cal.y
%{
#include <stdio.h>
#include <assert.h>
static int Pop();
static int Top();
static void Push(int val);
%}
%token T_Int
%%
S : S E '\n' { printf("=%d\n", Top()); }
|
;
E : E E '+' { Push(Pop() + Pop()); }
| E E '-' { int op2 = Pop(); Push(Pop() - op2); }
| E E '*' { Push(Pop() * Pop()); }
| E E '/' { int op2 = Pop(); Push(Pop() / op2); }
| T_Int { Push(yylval); }
;
%%
static int stack[100], count = 0;
static int Pop()
{
assert(count > 0);
return stack[--count];
}
static int Top()
{
assert(count > 0);
return stack[count - 1];
}
static int Push()
{
assert(count < sizeof(stack) / sizeof(*stack));
return stack[count++] = val;
}
int main()
{
return yyparse();
}
yylval: 传递发现的token值。
yyparse: 语法分析，按照规则执行。
yylex: 词法分析，将字符语句转为一个个token。 我们需要手动写yylex, 常常是.l 文件 （flex/lex文件）
.l 词法文件
%{
Declarations
%}
%%
Productions // 规则
%%
User subroutines
例子：
// cal.l
%{
#include "y.tab.h" // 需要包含 Yacc 生成的 token 定义
%}
%%
[0-9]+ { yylval = atoi(yytext); return T_Int; } // 识别到一个T_Int token
[-+*/\n] { return yytext[0]; }
. { /* ignore everything else */ }
%%
规则： 正则表达式-动作
yytext: 全局字符串。存放刚提供的字符串。
构建
calc: lex.yy.o y.tab.o
gcc -o calc lex.yy.o y.tab.o -ll
lex.yy.c: calc.l y.tab.c
flex calc.l
y.tab.c: calc.y
bison -vdty calc.y
calc.y => y.tab.c y.tab.h
calc.l => lex.yy.c
bison 生成语法分析。flex 生成词法分析。
执行示例：
1 2 + 4 *
语法分析是按照需要，调用yylex获取token。而不是一次性生成全部token流
Bbison 内部有一个语法栈，存储token和左边符号E（非终结符）。语法栈存的是符号E
| step | token | rule | bison stack（AST） | user action |
|---|---|---|---|---|
| 1 | 1 T_Int |
E : T_Int { Push(yylval); } |
[E] |
[1] |
| 2 | 2 T_Int |
E : T_Int { Push(yylval); } |
[E, E] |
[2] |
| 3 | + |
E : E E '+' { Push(Pop() + Pop()); } |
[E] 匹配规约 |
[3] |
bison识别表达式，AST/计算栈由user action完成。
编译器介绍
编译器几个阶段：
（词法分析+语法分析+语义分析+中间代码优化）+ 链接gcc 生成可执行文件。
Bison就是把语法/词法文件翻译成c代码。或许就是yacc名字来源。