简介一份使用Flex与Bison构建的SQL解析器完整代码面向数据库内核开发者、编译技术学习者以及高校相关课程实践专注解决SQL语句从词法切分、语法分析到抽象语法树生成的完整解析链路。资源共11个文件以C源码为主体包含Bison语法规则文件、Flex词法规则文件、头文件、测试SQL脚本及相关构建产物压缩包仅54KB体量轻巧、结构清晰便于快速阅读和动手实验。目前已有690人学习下载。通过这份代码可以深入理解词法分析器如何识别SELECT、WHERE等关键字与操作符语法分析器如何依据上下文无关文法解析查询、插入、更新、删除等语句并进一步学习AST节点设计、错误提示生成以及中间表示的基础思想。代码覆盖JOIN、子查询等高级SQL特性的解析处理同时展示了Flex与Bison的配置方式、输入文件格式和生成代码的组织逻辑。适合作为自定义数据库系统的解析模块参考也是一份难得的编译器设计入门实例。1. 这份 SQL 解析器代码FlexBison 组合把 SQL 从文本变成 AST做数据库底层或者编译器相关开发的人迟早会碰上这样一个需求给你一段 SQL 字符串要把它变成程序能理解的结构化表示。自己手写递归下降解析器当然可以但工作量不小而且容易在边角语法上翻车。我这次拆的这份 SQL 解析器完整代码用的是 Flex 做词法分析、Bison 做语法分析这条经典路线两者配合把SELECT、CREATE TABLE、INSERT这类语句逐层拆解最终构建出抽象语法树AST。代码包里包含完整的 lexer.l词法规则、parser.y语法规则、AST 节点定义和主程序能直接编译运行适合想弄清 SQL 解析内部机制、或者要基于它开发自定义 SQL 引擎的人。接下来我从代码结构、关键实现、编译调试到避坑逐层拆开讲。2. Flex 词法分析lexer.l 怎么把 SQL 拆成 token2.1 三段式结构与 token 定义用 Flex 写词法分析器输入文件固定的三段式布局定义区%{ %}之间写 C 头文件和全局变量声明、规则区每个规则是正则表达式 动作代码、用户代码区放自定义函数。lexer.l 的核心思路是把 SQL 关键字、标识符、数字、字符串、操作符全部识别成 token并且把关键字映射成 Bison 里定义好的 token 编号。举个例子看一段典型定义%{ #include stdio.h #include string.h #include parser.tab.h // Bison 生成的 token 定义 extern int yylex(void); int line_num 1; // 行号追踪便于报错 %} %option noyywrap %% [ \t] { /* 跳过空白什么都不做 */ } \n { line_num; } SELECT { return SELECT; } FROM { return FROM; } WHERE { return WHERE; } INSERT { return INSERT; } INTO { return INTO; } VALUES { return VALUES; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str strdup(yytext); return IDENT; } [0-9] { yylval.ival atoi(yytext); return NUMBER; } [^]* { yylval.str strdup(yytext); return STRING; } ( { return LPAREN; } ) { return RPAREN; } , { return COMMA; } ; { return SEMICOLON; } . { printf(行 %d: 无法识别的字符 %s\n, line_num, yytext); } %%注意SELECT这类关键字规则写在[a-zA-Z_][a-zA-Z0-9_]*之前Flex 匹配时按规则出现顺序优先匹配所以输入SELECT时会先命中关键字规则返回SELECT而不是被当成IDENT。这种“关键字优先”的顺序不是可选项是必须的否则SELECT会被记成普通标识符。yylval是 Bison 定义的全局联合体YYSTYPE给 token 附带语义值。这里strdup(yytext)把标识符的文本拷贝到堆上是因为yytext指针指向的是 Flex 内部的缓冲区下一轮匹配就会被覆盖不拷贝的话拿到的都是残值。NUMBER用atoi转成整数。字符串那条规则用单引号配对第 5 章我会专门说它翻车的地方。2.2 与 Bison 的 token 对接yylex、yylval、yytext 三者怎么配合lexer.l 和 parser.y 的桥梁就三个东西yylex()函数、yylval联合体、token 宏定义。Bison 在 parser.tab.h 里生成类似#define SELECT 258这样的枚举常量lexer.l 里#include parser.tab.h之后就能直接用这些常量名。parser.tab.h是编译中间产物由 Bison 根据 parser.y 自动生成所以编译顺序必须是先跑 bison、后跑 flex否则 lexer.l 找不到头文件。yylval类型的定义在 parser.y 顶部%{ #include stdio.h #include stdlib.h #include ast.h %} %union { int ival; char *str; struct ASTNode *node; }%union里声明了几个成员Bison 会据此生成 YYSTYPE。lexer.l 里写yylval.str、yylval.ivalparser.y 的语法规则里用$1、$2取语义值时也必须对应同一个成员名。这里最容易犯的错是 lexer 里给yylval.str赋值parser 里却当$1.ival用类型不对会得到完全乱掉的内存数据很难排查。2.3 词法层面的自测方法先把 lexer.l 单独编译成一个可执行文件不接 Bison 语法分析器直接用YYDEBUG环境变量开启调试输出或者自己加一个main()循环打印 tokenint main(int argc, char **argv) { extern FILE *yyin; if (argc 1) yyin fopen(argv[1], r); int token; while ((token yylex())) { printf(token: %d, text: %s\n, token, yytext); } return 0; }这样就能拿一份 SQL 文本进来逐行看 token 切分结果。词法分析是整个解析器最底层的一环这里如果有问题不管上层语法怎么写都会得到垃圾输入。我一般会先用最小用例——一条SELECT a FROM t WHERE id 1;——把所有 token 类型都覆盖一遍再跑边界用例。3. Bison 语法规则与 AST 构建parser.y 的精髓在这3.1 语法规则如何描述 SQL 语句结构Bison 输入文件同样分四段%{ %}头部声明、%token/%union/%type定义、%%之间的语法规则、%%之后的用户代码。语法规则直接写上下文无关文法每条规则对应一个非终结符的产生式。看 CREATE TABLE 和 SELECT 的核心规则statement: create_stmt SEMICOLON { $$ $1; } | select_stmt SEMICOLON { $$ $1; } | insert_stmt SEMICOLON { $$ $1; } ; create_stmt: CREATE TABLE IDENT LPAREN column_def_list RPAREN { $$ create_ast_node(NODE_CREATE_TABLE, $3, $5, NULL); } ; column_def: IDENT TYPE { $$ create_column_def($1, $2); } ; select_stmt: SELECT select_list FROM IDENT where_opt { $$ create_ast_node(NODE_SELECT, $2, $4, $5); } ; where_opt: WHERE expr { $$ $2; } | /* empty */ { $$ NULL; } ;$$ $1是把子节点的结果往上传$1、$2这些编号对应规则里每个符号的语义值。NODE_CREATE_TABLE这种枚举值定义在 ast.h 里create_ast_node是 AST 构造函数。规则写好后Bison 会生成一个 LALR(1) 分析表来驱动解析过程——它不需要你手工写递归下降函数只需描述规则Bison 自动完成移进-归约shift-reduce过程。这里要注意的坑是优先级和冲突。SQL 里WHERE id 1 AND age 18这种表达式AND和比较操作符的优先级、结合性必须声明清楚。Bison 提供%left、%right、%precedence来声明优先级比如%left OR %left AND %left %left声明越靠后优先级越高。如果不写这些声明表达式规则会产生 shift/reduce 冲突Bison 默认选 shift但行为可能不符合 SQL 语义。编译时看到 warning 说 conflicts 时别无视这就是语法规则不严谨的信号。3.2 AST 节点设计从语法规则到树形结构AST 不是语法分析的必需品——Bison 完全可以边归约边执行代码——但把中间结果建成树后续做语义检查、优化、执行器遍历都更方便。这份代码里 ast.h 定义了统一节点结构typedef enum { NODE_SELECT, NODE_CREATE_TABLE, NODE_INSERT, NODE_COLUMN_DEF, NODE_COLUMN_REF, NODE_NUMBER, NODE_STRING, NODE_CONDITION, NODE_BINARY_EXPR } NodeType; typedef struct ASTNode { NodeType type; char *name; // 表名、列名等 int ival; // 数字值 char *sval; // 字符串值 struct ASTNode *left; struct ASTNode *right; struct ASTNode *next; // 列表节点用它串成链表 } ASTNode;create_ast_node函数给每个节点分配内存、填类型和子节点指针。next指针解决“多列定义、多个查询项”这类列表场景——真正的树是二叉树结构列表通过next串成单向链表。一片内存从解析开始分配整个 SQL 执行完成后统一释放否则每跑一条语句就漏一片内存。AST 构建可以这样验证在 parser.y 的规则动作里调用一个dump_ast()函数递归打印节点类型与值把输入 SQL 的树形结构直接打出来。3.3 错误处理机制yyerror 与错误恢复yyerror是 Bison 约定俗成的函数名语法分析过程中每次遇到非法 token 组合都会调用它。一个合格的 error 处理至少包含行号和期望说明void yyerror(const char *msg) { fprintf(stderr, 语法错误 第%d行: %s\n, line_num, msg); }更重要的是 Bison 的errortoken 和yyerrorlok。在规则里显式加error产生式可以实现错误恢复比如statement: error SEMICOLON { yyerrok; } ;意思是如果语句级解析出错就跳到下一个分号清掉内部错误状态继续解析而不是整个程序崩掉。yyerrok宏用于重置错误标志。没做错误恢复的解析器用户输错一条语句就直接终止这在真实环境里没法用。3.4 从 AST 到可执行表示的边界解析器管到 AST 为止后续生成字节码还是直接解释执行代码包没有深入。常见做法是在 AST 上做一次遍历把查询计划算出来——比如判断WHERE条件是不是等值比较、访问的表存在不存在需要连接符号表。如果你要扩展成完整数据库AST 是起点不是终点。4. 编译流程与调试手段从源码到跑通一条 SQL4.1 整套源码的文件构成与编译顺序这份代码包的文件清单一眼能看出标准项目布局。lexer.l和parser.y是唯二的“手工编写”输入文件其余lex.yy.c、parser.tab.c、parser.tab.h都是生成物。编译顺序是固定的# 第一步用 Bison 处理语法规则生成 parser.tab.c 和 parser.tab.h bison -d -o parser.tab.c parser.y # 第二步用 Flex 处理词法规则生成 lex.yy.c flex -o lex.yy.c lexer.l # 第三步把 lexer、parser、AST 实现、main 驱动一起编译成可执行文件 gcc -g -o sql_parser lex.yy.c parser.tab.c ast.c main.c -lfl-d告诉 Bison 生成头文件-o指定输出名。最后一步链接时-lfl提供 Flex 的库函数比如yywrap如果你的 lexer.l 里写了%option noyywrap这个库也可以省略。ast.c是 AST 节点操作实现main.c负责读入 SQL 文件或交互式输入循环调yyparse()。input_test.sql和input.sql是测试用例文件。我用input_test.sql跑通后再换自己的 SQL 最稳别一上来就写复杂语句。4.2 编译踩到的坑与静默失败头文件找不到时先确认 bison 确实跑过了——parser.tab.h不会凭空生成。运行时如果yyin没有正确指向输入文件yyparse()读到的就是空串解析器会直接报错。我遇到过最典型的翻车是链接阶段报yywrap未定义原因就是 lexer.l 漏写了%option noyywrap。Flex 生成的词法分析器默认需要一个yywrap()函数不声明这个选项就要自己补一个。因为报错信息不够直观我一般在main.c里加一段开工提示int main(int argc, char **argv) { extern FILE *yyin; if (argc 1) { yyin fopen(argv[1], r); if (!yyin) { perror(无法打开输入文件); exit(1); } printf(正在解析 %s ...\n, argv[1]); int ret yyparse(); printf(解析结果: %s\n, ret 0 ? 成功 : 失败); } else { printf(用法: %s sql文件\n, argv[0]); } return 0; }这样至少能区分是文件打开失败还是语法解析失败不至于两种情况看着都像“程序没反应”。解析成功的判定码0和失败码1也要记住shell 脚本里经常要拿返回值做判定。4.3 开启 Bison 调试模式看完整的移进归约过程Bison 自带调试开关不需要自己打日志。用-t重新编译 parser.y运行时设YYDEBUG1环境变量bison -d -t -o parser.tab.c parser.y ./sql_parser input_test.sql终端会输出一长串移进shift、归约reduce、goto 的动作记录。这是定位语法规则冲突的“后悔药”——哪条规则让解析器进了错误状态看日志里的状态编号和当前 token 一清二楚。但它输出量很大调试小规则时可以开跑完整 SQL 文件时建议关掉。lex.yy.c也支持yy_flex_debug但一般不需要专门开token 的输出用第 2 章那个独立 main 函数更直观。5. 避坑记录FlexBison 写 SQL 解析器的五个高频翻车点5.1 yywrap 未定义导致链接失败现象gcc最后一步链接提示undefined reference to yywrap。 原因Flex 生成的扫描器在读到 EOF 时会调用yywrap()决定是否继续读下一个文件。lexer.l 没写%option noyywrap也没有提供该函数实现。 解决在 lexer.l 定义区加%option noyywrapFlex 会生成一个默认实现返回 1表示输入结束。如果用了-lfl库里也带了这个函数但要确认库链接顺序在源码之后。5.2 字符串字面量里出现转义符或引号时 token 切错现象输入WHERE name its或者包含\的字符串时解析器把字符串拆成两截报语法错误。 原因lexer.l 里那条[^]*正则写得太天真遇到 SQL 标准里两个单引号转义的写法就断了。[^]*不匹配空串和转义序列。 解决改用 Flex 的 start condition 处理字符串状态进入字符串后逐字符消费遇到合并成一个引号字符%x str { BEGIN(str); } str { /* 转义引号当作普通字符 */ } str { BEGIN(INITIAL); return STRING; } str. { /* 普通字符拼进缓冲区 */ }顺带提一句yytext在 start condition 下同样会被覆盖字符串内容要复制到自己的缓冲里。5.3 标识符规则吃掉关键字规则顺序决定命运现象SELECT出现在标识符规则能匹配的位置上但解析器返回了IDENT导致语法规则一直不匹配。 原因Flex 匹配是按文件里规则的先后顺序来选的。标识符正则[a-zA-Z_][a-zA-Z0-9_]*写在SELECT之前那就永远轮不到关键字规则。 解决所有 SQL 关键字规则必须出现在标识符规则之前。要省事的话可以在标识符动作里查关键字表但那样性能差而且 Bison 的 token 类型会乱。保持规则顺序是正道。5.4 YYSTYPE 的类型不匹配造成 AST 字段错乱现象语法分析成功但 AST 里节点的name字段存的是乱码或者ival是个超大的数。 原因lexer.l 里yylval.str赋值的地方和 parser.y 里$n取用的成员不一致。yylval.ival和yylval.str在联合体里占用同一块内存赋值和读取错位后解释方式完全不同。 解决使用规则时强制类型检查。Bison 的%type声明可以约束每个非终结符的语义值类型例如%type node statement select_stmt create_stmt %type str IDENT %type ival NUMBER编译期就能发现类型不匹配省去运行期用 gdb 追内存的大量时间。5.5 语法冲突静默编译Bison 的默认选择不一定是你想要的现象bison编译时打印conflicts: 3 shift/reduce但没报错程序也能跑可某些 SQL 就是解析错。 原因Bison 对冲突有默认策略——shift 优先。但IF ... THEN ... ELSE、表达式优先级这些场景默认策略可能跟 SQL 语义相反。 解决认真看到每个 conflicts 警告。用-v参数生成.output文件里面有完整的 DFA 状态和冲突位置按第 4 章开-t调试跟踪现场。查清是缺优先级声明还是规则写歧义了再修正。冲突清零不是洁癖是真会咬人的。6. 进阶练习给解析器加一个 LIMIT 子句并动手验证拿到这份代码后最值得做的第一个练手扩展是给SELECT语句增加LIMIT n支持。这一改动会同时触及 lexer.l、parser.y、ast.h/ast.c 三个文件把前面几章的机制完整串一遍比换着法子跑测试有用得多。第一步lexer.l 在关键字区加一行LIMIT { return LIMIT; }注意这行必须放在标识符正则之前第 5 章的坑顺序决定优先级。第二步parser.y 里声明 token并扩展产生式%token LIMIT select_stmt: SELECT select_list FROM IDENT where_opt limit_opt { $$ create_ast_node(NODE_SELECT, $2, $4, $5); $$-limit $6; // 在 ASTNode 里加一个 int limit 字段 } ; limit_opt: LIMIT NUMBER { $$ $2; } | /* empty */ { $$ -1; } // -1 表示无限制 ;第三步ast.h 的ASTNode结构体加一个int limit字段ast.c 的create_ast_node里初始化为 -1。这一步是很多人会漏的——节点分配内存不初始化$$-limit拿到的是野值LIMIT 行为就变成玄学。写完编译用SELECT id FROM t WHERE id 10 LIMIT 5;跑一遍观察 AST dump 里的 limit 字段再跑一条不带 LIMIT 的语句确认降级为 -1 无限制。止步于“能编译能解析”还是有点亏我最后会再写一个 20 行左右的遍历函数把 AST 里的SELECT节点连表名、条件、LIMIT 打印成一条类似执行计划概要的文本。这一步等于亲手把“SQL 文本 → 结构化信息”的转化链路完整走了一遍之后要接执行器、做语法树优化或者写 ORM 的 SQL 方言翻译器思路都是同样的——改词法、改语法、改 AST。这套解析器真正劝退人的地方从来不是 Flex 或 Bison 的语法难背而是文件之间那种“改了 lexer 忘了 parser、改了 parser 忘了 AST”的连锁反应。从那以后我每次动这类代码都强制走一遍流程改词法先单独测 token改语法先查 conflicts改 AST 先看初始化——把这三板斧变成肌肉记忆解析器就是最听话的那块积木。希望帮你少走几段弯路。本文还有配套的精品资源点击获取 
长河君 · 2026/10/9 22:32:20 · 阅读 1.2k 用Flex+Bison实现SQL解析器：从文本到AST的完整拆解
简介一份使用Flex与Bison构建的SQL解析器完整代码面向数据库内核开发者、编译技术学习者以及高校相关课程实践专注解决SQL语句从词法切分、语法分析到抽象语法树生成的完整解析链路。资源共11个文件以C源码为主体包含Bison语法规则文件、Flex词法规则文件、头文件、测试SQL脚本及相关构建产物压缩包仅54KB体量轻巧、结构清晰便于快速阅读和动手实验。目前已有690人学习下载。通过这份代码可以深入理解词法分析器如何识别SELECT、WHERE等关键字与操作符语法分析器如何依据上下文无关文法解析查询、插入、更新、删除等语句并进一步学习AST节点设计、错误提示生成以及中间表示的基础思想。代码覆盖JOIN、子查询等高级SQL特性的解析处理同时展示了Flex与Bison的配置方式、输入文件格式和生成代码的组织逻辑。适合作为自定义数据库系统的解析模块参考也是一份难得的编译器设计入门实例。1. 这份 SQL 解析器代码FlexBison 组合把 SQL 从文本变成 AST做数据库底层或者编译器相关开发的人迟早会碰上这样一个需求给你一段 SQL 字符串要把它变成程序能理解的结构化表示。自己手写递归下降解析器当然可以但工作量不小而且容易在边角语法上翻车。我这次拆的这份 SQL 解析器完整代码用的是 Flex 做词法分析、Bison 做语法分析这条经典路线两者配合把SELECT、CREATE TABLE、INSERT这类语句逐层拆解最终构建出抽象语法树AST。代码包里包含完整的 lexer.l词法规则、parser.y语法规则、AST 节点定义和主程序能直接编译运行适合想弄清 SQL 解析内部机制、或者要基于它开发自定义 SQL 引擎的人。接下来我从代码结构、关键实现、编译调试到避坑逐层拆开讲。2. Flex 词法分析lexer.l 怎么把 SQL 拆成 token2.1 三段式结构与 token 定义用 Flex 写词法分析器输入文件固定的三段式布局定义区%{ %}之间写 C 头文件和全局变量声明、规则区每个规则是正则表达式 动作代码、用户代码区放自定义函数。lexer.l 的核心思路是把 SQL 关键字、标识符、数字、字符串、操作符全部识别成 token并且把关键字映射成 Bison 里定义好的 token 编号。举个例子看一段典型定义%{ #include stdio.h #include string.h #include parser.tab.h // Bison 生成的 token 定义 extern int yylex(void); int line_num 1; // 行号追踪便于报错 %} %option noyywrap %% [ \t] { /* 跳过空白什么都不做 */ } \n { line_num; } SELECT { return SELECT; } FROM { return FROM; } WHERE { return WHERE; } INSERT { return INSERT; } INTO { return INTO; } VALUES { return VALUES; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str strdup(yytext); return IDENT; } [0-9] { yylval.ival atoi(yytext); return NUMBER; } [^]* { yylval.str strdup(yytext); return STRING; } ( { return LPAREN; } ) { return RPAREN; } , { return COMMA; } ; { return SEMICOLON; } . { printf(行 %d: 无法识别的字符 %s\n, line_num, yytext); } %%注意SELECT这类关键字规则写在[a-zA-Z_][a-zA-Z0-9_]*之前Flex 匹配时按规则出现顺序优先匹配所以输入SELECT时会先命中关键字规则返回SELECT而不是被当成IDENT。这种“关键字优先”的顺序不是可选项是必须的否则SELECT会被记成普通标识符。yylval是 Bison 定义的全局联合体YYSTYPE给 token 附带语义值。这里strdup(yytext)把标识符的文本拷贝到堆上是因为yytext指针指向的是 Flex 内部的缓冲区下一轮匹配就会被覆盖不拷贝的话拿到的都是残值。NUMBER用atoi转成整数。字符串那条规则用单引号配对第 5 章我会专门说它翻车的地方。2.2 与 Bison 的 token 对接yylex、yylval、yytext 三者怎么配合lexer.l 和 parser.y 的桥梁就三个东西yylex()函数、yylval联合体、token 宏定义。Bison 在 parser.tab.h 里生成类似#define SELECT 258这样的枚举常量lexer.l 里#include parser.tab.h之后就能直接用这些常量名。parser.tab.h是编译中间产物由 Bison 根据 parser.y 自动生成所以编译顺序必须是先跑 bison、后跑 flex否则 lexer.l 找不到头文件。yylval类型的定义在 parser.y 顶部%{ #include stdio.h #include stdlib.h #include ast.h %} %union { int ival; char *str; struct ASTNode *node; }%union里声明了几个成员Bison 会据此生成 YYSTYPE。lexer.l 里写yylval.str、yylval.ivalparser.y 的语法规则里用$1、$2取语义值时也必须对应同一个成员名。这里最容易犯的错是 lexer 里给yylval.str赋值parser 里却当$1.ival用类型不对会得到完全乱掉的内存数据很难排查。2.3 词法层面的自测方法先把 lexer.l 单独编译成一个可执行文件不接 Bison 语法分析器直接用YYDEBUG环境变量开启调试输出或者自己加一个main()循环打印 tokenint main(int argc, char **argv) { extern FILE *yyin; if (argc 1) yyin fopen(argv[1], r); int token; while ((token yylex())) { printf(token: %d, text: %s\n, token, yytext); } return 0; }这样就能拿一份 SQL 文本进来逐行看 token 切分结果。词法分析是整个解析器最底层的一环这里如果有问题不管上层语法怎么写都会得到垃圾输入。我一般会先用最小用例——一条SELECT a FROM t WHERE id 1;——把所有 token 类型都覆盖一遍再跑边界用例。3. Bison 语法规则与 AST 构建parser.y 的精髓在这3.1 语法规则如何描述 SQL 语句结构Bison 输入文件同样分四段%{ %}头部声明、%token/%union/%type定义、%%之间的语法规则、%%之后的用户代码。语法规则直接写上下文无关文法每条规则对应一个非终结符的产生式。看 CREATE TABLE 和 SELECT 的核心规则statement: create_stmt SEMICOLON { $$ $1; } | select_stmt SEMICOLON { $$ $1; } | insert_stmt SEMICOLON { $$ $1; } ; create_stmt: CREATE TABLE IDENT LPAREN column_def_list RPAREN { $$ create_ast_node(NODE_CREATE_TABLE, $3, $5, NULL); } ; column_def: IDENT TYPE { $$ create_column_def($1, $2); } ; select_stmt: SELECT select_list FROM IDENT where_opt { $$ create_ast_node(NODE_SELECT, $2, $4, $5); } ; where_opt: WHERE expr { $$ $2; } | /* empty */ { $$ NULL; } ;$$ $1是把子节点的结果往上传$1、$2这些编号对应规则里每个符号的语义值。NODE_CREATE_TABLE这种枚举值定义在 ast.h 里create_ast_node是 AST 构造函数。规则写好后Bison 会生成一个 LALR(1) 分析表来驱动解析过程——它不需要你手工写递归下降函数只需描述规则Bison 自动完成移进-归约shift-reduce过程。这里要注意的坑是优先级和冲突。SQL 里WHERE id 1 AND age 18这种表达式AND和比较操作符的优先级、结合性必须声明清楚。Bison 提供%left、%right、%precedence来声明优先级比如%left OR %left AND %left %left声明越靠后优先级越高。如果不写这些声明表达式规则会产生 shift/reduce 冲突Bison 默认选 shift但行为可能不符合 SQL 语义。编译时看到 warning 说 conflicts 时别无视这就是语法规则不严谨的信号。3.2 AST 节点设计从语法规则到树形结构AST 不是语法分析的必需品——Bison 完全可以边归约边执行代码——但把中间结果建成树后续做语义检查、优化、执行器遍历都更方便。这份代码里 ast.h 定义了统一节点结构typedef enum { NODE_SELECT, NODE_CREATE_TABLE, NODE_INSERT, NODE_COLUMN_DEF, NODE_COLUMN_REF, NODE_NUMBER, NODE_STRING, NODE_CONDITION, NODE_BINARY_EXPR } NodeType; typedef struct ASTNode { NodeType type; char *name; // 表名、列名等 int ival; // 数字值 char *sval; // 字符串值 struct ASTNode *left; struct ASTNode *right; struct ASTNode *next; // 列表节点用它串成链表 } ASTNode;create_ast_node函数给每个节点分配内存、填类型和子节点指针。next指针解决“多列定义、多个查询项”这类列表场景——真正的树是二叉树结构列表通过next串成单向链表。一片内存从解析开始分配整个 SQL 执行完成后统一释放否则每跑一条语句就漏一片内存。AST 构建可以这样验证在 parser.y 的规则动作里调用一个dump_ast()函数递归打印节点类型与值把输入 SQL 的树形结构直接打出来。3.3 错误处理机制yyerror 与错误恢复yyerror是 Bison 约定俗成的函数名语法分析过程中每次遇到非法 token 组合都会调用它。一个合格的 error 处理至少包含行号和期望说明void yyerror(const char *msg) { fprintf(stderr, 语法错误 第%d行: %s\n, line_num, msg); }更重要的是 Bison 的errortoken 和yyerrorlok。在规则里显式加error产生式可以实现错误恢复比如statement: error SEMICOLON { yyerrok; } ;意思是如果语句级解析出错就跳到下一个分号清掉内部错误状态继续解析而不是整个程序崩掉。yyerrok宏用于重置错误标志。没做错误恢复的解析器用户输错一条语句就直接终止这在真实环境里没法用。3.4 从 AST 到可执行表示的边界解析器管到 AST 为止后续生成字节码还是直接解释执行代码包没有深入。常见做法是在 AST 上做一次遍历把查询计划算出来——比如判断WHERE条件是不是等值比较、访问的表存在不存在需要连接符号表。如果你要扩展成完整数据库AST 是起点不是终点。4. 编译流程与调试手段从源码到跑通一条 SQL4.1 整套源码的文件构成与编译顺序这份代码包的文件清单一眼能看出标准项目布局。lexer.l和parser.y是唯二的“手工编写”输入文件其余lex.yy.c、parser.tab.c、parser.tab.h都是生成物。编译顺序是固定的# 第一步用 Bison 处理语法规则生成 parser.tab.c 和 parser.tab.h bison -d -o parser.tab.c parser.y # 第二步用 Flex 处理词法规则生成 lex.yy.c flex -o lex.yy.c lexer.l # 第三步把 lexer、parser、AST 实现、main 驱动一起编译成可执行文件 gcc -g -o sql_parser lex.yy.c parser.tab.c ast.c main.c -lfl-d告诉 Bison 生成头文件-o指定输出名。最后一步链接时-lfl提供 Flex 的库函数比如yywrap如果你的 lexer.l 里写了%option noyywrap这个库也可以省略。ast.c是 AST 节点操作实现main.c负责读入 SQL 文件或交互式输入循环调yyparse()。input_test.sql和input.sql是测试用例文件。我用input_test.sql跑通后再换自己的 SQL 最稳别一上来就写复杂语句。4.2 编译踩到的坑与静默失败头文件找不到时先确认 bison 确实跑过了——parser.tab.h不会凭空生成。运行时如果yyin没有正确指向输入文件yyparse()读到的就是空串解析器会直接报错。我遇到过最典型的翻车是链接阶段报yywrap未定义原因就是 lexer.l 漏写了%option noyywrap。Flex 生成的词法分析器默认需要一个yywrap()函数不声明这个选项就要自己补一个。因为报错信息不够直观我一般在main.c里加一段开工提示int main(int argc, char **argv) { extern FILE *yyin; if (argc 1) { yyin fopen(argv[1], r); if (!yyin) { perror(无法打开输入文件); exit(1); } printf(正在解析 %s ...\n, argv[1]); int ret yyparse(); printf(解析结果: %s\n, ret 0 ? 成功 : 失败); } else { printf(用法: %s sql文件\n, argv[0]); } return 0; }这样至少能区分是文件打开失败还是语法解析失败不至于两种情况看着都像“程序没反应”。解析成功的判定码0和失败码1也要记住shell 脚本里经常要拿返回值做判定。4.3 开启 Bison 调试模式看完整的移进归约过程Bison 自带调试开关不需要自己打日志。用-t重新编译 parser.y运行时设YYDEBUG1环境变量bison -d -t -o parser.tab.c parser.y ./sql_parser input_test.sql终端会输出一长串移进shift、归约reduce、goto 的动作记录。这是定位语法规则冲突的“后悔药”——哪条规则让解析器进了错误状态看日志里的状态编号和当前 token 一清二楚。但它输出量很大调试小规则时可以开跑完整 SQL 文件时建议关掉。lex.yy.c也支持yy_flex_debug但一般不需要专门开token 的输出用第 2 章那个独立 main 函数更直观。5. 避坑记录FlexBison 写 SQL 解析器的五个高频翻车点5.1 yywrap 未定义导致链接失败现象gcc最后一步链接提示undefined reference to yywrap。 原因Flex 生成的扫描器在读到 EOF 时会调用yywrap()决定是否继续读下一个文件。lexer.l 没写%option noyywrap也没有提供该函数实现。 解决在 lexer.l 定义区加%option noyywrapFlex 会生成一个默认实现返回 1表示输入结束。如果用了-lfl库里也带了这个函数但要确认库链接顺序在源码之后。5.2 字符串字面量里出现转义符或引号时 token 切错现象输入WHERE name its或者包含\的字符串时解析器把字符串拆成两截报语法错误。 原因lexer.l 里那条[^]*正则写得太天真遇到 SQL 标准里两个单引号转义的写法就断了。[^]*不匹配空串和转义序列。 解决改用 Flex 的 start condition 处理字符串状态进入字符串后逐字符消费遇到合并成一个引号字符%x str { BEGIN(str); } str { /* 转义引号当作普通字符 */ } str { BEGIN(INITIAL); return STRING; } str. { /* 普通字符拼进缓冲区 */ }顺带提一句yytext在 start condition 下同样会被覆盖字符串内容要复制到自己的缓冲里。5.3 标识符规则吃掉关键字规则顺序决定命运现象SELECT出现在标识符规则能匹配的位置上但解析器返回了IDENT导致语法规则一直不匹配。 原因Flex 匹配是按文件里规则的先后顺序来选的。标识符正则[a-zA-Z_][a-zA-Z0-9_]*写在SELECT之前那就永远轮不到关键字规则。 解决所有 SQL 关键字规则必须出现在标识符规则之前。要省事的话可以在标识符动作里查关键字表但那样性能差而且 Bison 的 token 类型会乱。保持规则顺序是正道。5.4 YYSTYPE 的类型不匹配造成 AST 字段错乱现象语法分析成功但 AST 里节点的name字段存的是乱码或者ival是个超大的数。 原因lexer.l 里yylval.str赋值的地方和 parser.y 里$n取用的成员不一致。yylval.ival和yylval.str在联合体里占用同一块内存赋值和读取错位后解释方式完全不同。 解决使用规则时强制类型检查。Bison 的%type声明可以约束每个非终结符的语义值类型例如%type node statement select_stmt create_stmt %type str IDENT %type ival NUMBER编译期就能发现类型不匹配省去运行期用 gdb 追内存的大量时间。5.5 语法冲突静默编译Bison 的默认选择不一定是你想要的现象bison编译时打印conflicts: 3 shift/reduce但没报错程序也能跑可某些 SQL 就是解析错。 原因Bison 对冲突有默认策略——shift 优先。但IF ... THEN ... ELSE、表达式优先级这些场景默认策略可能跟 SQL 语义相反。 解决认真看到每个 conflicts 警告。用-v参数生成.output文件里面有完整的 DFA 状态和冲突位置按第 4 章开-t调试跟踪现场。查清是缺优先级声明还是规则写歧义了再修正。冲突清零不是洁癖是真会咬人的。6. 进阶练习给解析器加一个 LIMIT 子句并动手验证拿到这份代码后最值得做的第一个练手扩展是给SELECT语句增加LIMIT n支持。这一改动会同时触及 lexer.l、parser.y、ast.h/ast.c 三个文件把前面几章的机制完整串一遍比换着法子跑测试有用得多。第一步lexer.l 在关键字区加一行LIMIT { return LIMIT; }注意这行必须放在标识符正则之前第 5 章的坑顺序决定优先级。第二步parser.y 里声明 token并扩展产生式%token LIMIT select_stmt: SELECT select_list FROM IDENT where_opt limit_opt { $$ create_ast_node(NODE_SELECT, $2, $4, $5); $$-limit $6; // 在 ASTNode 里加一个 int limit 字段 } ; limit_opt: LIMIT NUMBER { $$ $2; } | /* empty */ { $$ -1; } // -1 表示无限制 ;第三步ast.h 的ASTNode结构体加一个int limit字段ast.c 的create_ast_node里初始化为 -1。这一步是很多人会漏的——节点分配内存不初始化$$-limit拿到的是野值LIMIT 行为就变成玄学。写完编译用SELECT id FROM t WHERE id 10 LIMIT 5;跑一遍观察 AST dump 里的 limit 字段再跑一条不带 LIMIT 的语句确认降级为 -1 无限制。止步于“能编译能解析”还是有点亏我最后会再写一个 20 行左右的遍历函数把 AST 里的SELECT节点连表名、条件、LIMIT 打印成一条类似执行计划概要的文本。这一步等于亲手把“SQL 文本 → 结构化信息”的转化链路完整走了一遍之后要接执行器、做语法树优化或者写 ORM 的 SQL 方言翻译器思路都是同样的——改词法、改语法、改 AST。这套解析器真正劝退人的地方从来不是 Flex 或 Bison 的语法难背而是文件之间那种“改了 lexer 忘了 parser、改了 parser 忘了 AST”的连锁反应。从那以后我每次动这类代码都强制走一遍流程改词法先单独测 token改语法先查 conflicts改 AST 先看初始化——把这三板斧变成肌肉记忆解析器就是最听话的那块积木。希望帮你少走几段弯路。本文还有配套的精品资源点击获取