手写SQL解析器：Lex/Yacc实现从CREATE到SELECT的全链路编译原理实践

简介：本资源是西安电子科技大学《编译原理》课程配套上机实践报告，面向计算机专业本科生及编译技术初学者，聚焦编译器前端与数据库管理系统（DBMS）的交叉实践，解决词法/语法分析器设计与轻量级DBMS实现的核心能力训练问题。压缩包为单个82KB的Word文档（.doc），完整涵盖项目概况、Lex/Yacc词法语法分析实现细节（含正规式定义与VC++6.0环境配置）、DBMS物理结构设计（数据存储与索引雏形）及核心功能（建库、建表、增删改查、事务基础），并附有详细目录与上机心得反思。内容预览显示报告结构严谨，含12页主体内容与模块化小节，体现从理论到工程落地的完整闭环。目前已有1332人学习下载，适合用于课程作业参考、编译原理实验复盘、DBMS原理验证及自主项目思路拓展。

1. 这不是一份交差报告，而是一个能跑通的 SQL 解析器原型：从 CREATE TABLE 到 SELECT * FROM，全链路手写 Lex/Yacc，VC++6.0 下零依赖编译，连空格和单引号都得自己抠——适合想真正搞懂「编译器怎么把一句 SQL 变成可执行动作」的硬核初学者

你有没有试过在命令行里敲下CREATE TABLE user(id INT, name CHAR(20));，然后程序真的“听懂”了，并打印出Operation is ok？不是调用 SQLite，不是封装 JDBC，而是从正则匹配第一个字母开始，到语法树归约出create_st → CREATE TABLE Name '(' create_field ')'，全程自己定义 token、自己写冲突消解、自己处理Name和NUMBER的识别优先级。这份 2011 年的上机报告，表面是西电某位同学的课程作业，实则是极简但完整的编译原理工程切片：它用不到 500 行 C 代码 + 两份.l/.y规则文件，在 VC++6.0 这个古董环境里，跑通了词法→语法→主循环的最小可行闭环。它不实现磁盘存储，不处理事务，但每一条SELECT ... WHERE a > 5 AND b = 'test'都会真实触发conditions → conditions AND conditions的递归归约；每一个INSERT INTO t VALUES (1, 'abc')都会走完insert_atom_commalist → insert_atom ',' insert_atom的完整推导。如果你正卡在“书上说 LL(1) 要消除左递归，可我写的 yacc 总报 shift/reduce 冲突”，或者“lex 为什么把数字当成标识符”，这份材料就是你的调试沙盒——所有坑都已踩过，所有修复都写在注释里，所有结构都暴露在struct Token3和YYSTYPE的裸定义中。别被标题里的“报告”二字骗了，这是一份带血丝的源码包，不是作文。

2. 环境复现与构建流程：VC++6.0 + ParserWizard 生成器 + 手动补丁，三步还原 2011 年原生编译现场

2.1 开发环境还原：为什么必须是 VC++6.0，而不是 VS2022？

这不是怀旧，是技术约束。项目正文明确写着 “Genareator 和 VC++6.0 编译环境”，而mylexer.h/myparser.h头文件中大量使用了YYFAR*、yyparserptr->yylvalptr这类 16 位远指针语法，这是 VC++6.0 对老式 Lex/Yacc 兼容层的特有约定。现代 MinGW 或 Clang 会直接报error C2065: 'YYFAR' : undeclared identifier。更关键的是内存模型：VC++6.0 默认使用small模型（代码+数据共 64KB），而 ParserWizard 生成的yyparse()函数内部堆栈分配方式依赖此模型。若强行用 VS2022 编译，即使加-DYYFAR=宏绕过声明错误，运行时也会在parser.yyparse()中因栈溢出崩溃——因为conditions递归规则深度超过 8 层时，VS 的栈帧管理与 VC6 不兼容。

提示：不要尝试用 flex/bison 替代。ParserWizard 是 2000 年代初的国产图形化 Lex/Yacc 生成器，其输出格式（如%name mylexer、yyparserptr结构体）与 GNU 工具链不兼容。强行替换会导致#include "mylexer.h"找不到yylex()声明，或yyparse()参数类型不匹配。

2.2 文件组织与依赖关系：5 个核心文件构成最小闭环

整个项目实际可运行部分仅由以下 5 个文件组成（其余如define.h为宏定义集合，无逻辑）：

注意：main.c中的int main(void)函数体存在致命缺陷——它调用了lexer.yycreate(&parser)，但 VC++6.0 下该函数未定义。正确做法是删除此行，改为标准 Lex/Yacc 交互模式：yylex()返回 token，yyparse()通过全局yylval获取属性值。

2.3 构建三步法：从 .l/.y 到可执行文件的完整链路

第一步：用 ParserWizard 生成初始框架

• 启动 ParserWizard（需从旧资源站下载 v2.1 版本）
• 新建项目 → 选择 “Lex & Yacc” 模式 → 输入mylexer.l和myparser.y路径
• 在 “Options” 中勾选 “Generate C Code”、“Use FAR pointers” → 点击 “Build All”
• 输出mylexer.c和myparser.c（注意：不是.cpp！VC++6.0 的 C 编译器不支持 C++ 语法）

第二步：手动修补关键缺陷
在mylexer.c末尾添加yywrap()实现（否则yylex()在 EOF 时无限循环）：

// mylexer.c 末尾追加 int yywrap() { return 1; // 告诉 yylex() 输入结束 }

在myparser.c中修正yyparse()的初始化逻辑（删除原文中错误的yycreate调用）：

// 替换 main.c 中的错误初始化段 int main(void) { printf("DBMS Parser Ready. Enter SQL commands (type 'EXIT;' to quit):\n"); while (1) { int result = yyparse(); // 直接调用，无需 create if (result != 0) { printf("Parse error. Try again.\n"); // 清空输入缓冲区，避免残留字符干扰下次解析 int c; while ((c = getchar()) != '\n' && c != EOF); } else { printf("OK\n"); } } return 0; }

第三步：VC++6.0 工程配置

• 新建 “Win32 Console Application” 工程
• 将mylexer.c、myparser.c、main.c加入工程
• Project → Settings → C/C++ 选项卡 → Category 选 “General” → 在 “Preprocessor definitions” 中添加YY_NO_UNISTD_H（禁用 unistd.h，VC6 不支持）
• Link 选项卡 → Object/library modules 中添加libc.lib（确保 C 标准库链接）
• 编译 → 生成parser.exe

注意：若出现unresolved external symbol _yylex错误，检查mylexer.c是否被设为 “Exclude from build”；若报syntax error : missing ';' before 'type'，确认所有变量声明都在函数开头（VC6 不支持 C99 的混合声明）。

3. 词法分析模块拆解：Name/ID/NUMBER三重标识符的识别优先级与单引号玄学修复

3.1 正则规则的隐式优先级：为什么NUMBER总被Name截胡？

看原文mylexer.l中这两条规则：

[0-9]+ {return NUMBER;} [a-zA-Z][_a-zA-Z0-9]+ {return ID;} [a-zA-Z][_0-9a-zA-Z()\.\*]* {printf("%s",yytext);return Name;}

表面看NUMBER规则在前，应优先匹配数字。但 Lex 的匹配原则是最长匹配（longest match）+ 规则顺序（first match）。当输入123abc时：

• [0-9]+匹配123（长度 3）
• [a-zA-Z][...]匹配123abc？不，首字符1不是字母，跳过
• 问题出在第三条Name规则：[a-zA-Z]要求首字符为字母，所以123abc不会被Name匹配

真正翻车的是abc123：

• ID规则[a-zA-Z][_a-zA-Z0-9]+匹配abc123（长度 6）
• Name规则[a-zA-Z][_0-9a-zA-Z()\.\*]*也匹配abc123（长度 6）
• 两者长度相同，Lex 按规则书写顺序取第一个 →ID被返回

但Name规则里有printf("%s",yytext)，这是调试输出，不是语义动作！它导致abc123被打印两次（一次printf，一次后续处理），且Nametoken 未被正确归约。更糟的是，NUMBER规则[0-9]+在ID/Name之后，当输入123时，ID和Name都因首字符非字母失败，NUMBER才生效 —— 这没问题。问题在于Name规则中的*量词允许零次匹配，导致空字符串也被捕获，引发不可预测行为。

3.2 单引号处理的血泪经验：课本没写的转义细节

原文提到：“在识别单引号时由于没有使用斜线标示，导致无法识别”。看原始规则：

''' {}

这行代码意图匹配单引号'，但在 Lex 中，单引号是字符字面量的界定符，'本身需转义。正确写法是：

'\'' { return SINGLE_QUOTE; } // 匹配一个单引号字符

否则 Lex 解析器会将'''解释为：第一个'开始字符字面量，中间''是非法内容，第三个'结束 —— 直接编译失败。这也是为什么报告里强调“经过仔细分析，并查看课本相关内容后得以解决”：课本中 Lex 语法章节明确要求特殊字符必须用反斜杠转义。

3.3 修复后的词法规则：三类标识符的明确边界

基于上述分析，mylexer.l应修正为：

%{ #include "myparser.h" #include "define.h" %} %% "\n" { /* 忽略换行 */ } "'" { return SINGLE_QUOTE; } // 显式转义单引号 [ \t] { /* 忽略空格制表符 */ } "CREATE" { return CREATE; } "DATABASE" { return DATABASE; } "DATABASES" { return DATABASES; } "USE" { return USE; } "SHOW" { return SHOW; } "TABLE" { return TABLE; } "TABLES" { return TABLES; } "SELECT" { return SELECT; } "DELETE" { return DELETE; } "INSERT" { return INSERT; } "VALUES" { return VALUES; } "UPDATE" { return UPDATE; } "DROP" { return DROP; } "EXIT" { return EXIT; } "NULLX" { return NULLX; } "INT" { return INT; } "CHAR" { return CHAR; } "AND" { return AND; } "OR" { return OR; } "WHERE" { return WHERE; } "INTO" { return INTO; } "SET" { return SET; } "FROM" { return FROM; } "(" { return '('; } ")" { return ')'; } ";" { return ';'; } "," { return ','; } "*" { return '*'; } ">" { return '>'; } "<" { return '<'; } "=" { return '='; } "!=" { return NE; } [0-9]+ { yylval = atoi(yytext); // 将数字字符串转为整数存入 yylval return NUMBER; } [a-zA-Z][a-zA-Z0-9_]* { // 严格 ID：字母开头，后跟字母/数字/下划线 yylval = (int)strdup(yytext); // 存储字符串地址（需后续 free） return ID; } [a-zA-Z][a-zA-Z0-9_]*\([a-zA-Z0-9_, ]*\) { // Name：带括号的函数式标识符，如 "func(1,2)" yylval = (int)strdup(yytext); return Name; } . { printf("Unrecognized character: %s\n", yytext); return ERROR; } %% int yywrap() { return 1; }

关键变更说明：

• NUMBER规则增加yylval = atoi(yytext)，将字符串转为整数值供语法分析使用
• ID规则改为[a-zA-Z][a-zA-Z0-9_]*，禁止点号.和星号*，避免与Name冲突
• Name规则限定为字母+括号内参数形式，明确区分于普通标识符
• 添加兜底规则.匹配所有未定义字符，防止静默失败

提示：strdup()在 VC++6.0 中需包含<string.h>，且返回的内存需在语法动作中free()，否则内存泄漏。这是新手最容易忽略的“玄学”坑——程序跑几次就崩，查半天发现是yylval指针堆积。

4. 语法分析模块拆解：从sts → st到conditions → conditions AND conditions的递归归约链路

4.1 产生式设计的精妙之处：sts的空产生式为何是语法树根？

看myparser.y中的起始规则：

sts: sts st {printf("Operation is ok\n");} | /* empty */ ;

这看似多此一举的空产生式| /* empty */，实则是 LR 解析器的启动开关。Yacc 生成的 LALR(1) 解析器需要一个明确的起始符号，sts作为文法开始符（start symbol），其空产生式允许解析器在输入流为空时合法结束。更重要的是，sts → sts st是左递归形式，Yacc 会自动将其转换为右结合的归约序列，确保st（单条语句）按输入顺序依次归约。例如输入：

CREATE TABLE t(id INT); SELECT * FROM t;

解析过程为：

1. CREATE TABLE t(id INT);→ 归约为st
2. sts（空） +st→ 归约为sts
3. 新sts+ 新st（SELECT）→ 归约为新sts
   最终整个输入被sts完全覆盖，触发{printf("Operation is ok\n");}。若去掉空产生式，解析器会在第一条语句后因无法匹配sts而报错。

4.2conditions递归规则的冲突消解：AND/OR 优先级与括号嵌套

原文conditions规则：

conditions: condition | '(' conditions ')' | conditions AND conditions | conditions OR conditions;

这会产生严重的 shift/reduce 冲突：当解析器看到a > 1 AND b < 2时，对AND是立即归约conditions AND conditions，还是继续移进下一个conditions？Yacc 默认按“移进”处理，导致a > 1 AND b < 2 OR c = 3被解析为(a > 1 AND b < 2) OR c = 3，符合预期。但若想支持AND优先级高于OR（如 SQL 标准），需显式声明：

%left AND %left OR

原文已有%left AND OR，但位置错误——它放在%token声明之后、%%之前，而 Yacc 要求优先级声明必须在%token之前。正确位置：

%{ #include "mylexer.h" #include "define.h" %} %left AND OR // 必须在此处声明 %left '>' '<' '=' NE %left '+' '-' %left '*' '/' %token ID NUMBER Name %token CREATE USE SHOW DROP ...

这样，Yacc 在生成状态机时，会为AND分配更高优先级，确保a > 1 AND b < 2 OR c = 3先归约AND子式，再归约OR。

4.3select_st的字段解析：select_name → '*'与table_fields → table_field的树形展开

select_st规则：

select_st: SELECT select_name FROM tables | SELECT select_name FROM tables WHERE conditions; select_name: table_fields | '*'; table_fields: table_field | table_fields ',' table_field; table_field: field | table '.' field;

这是典型的左递归列表展开。当输入SELECT id, name, age FROM user时，归约链路为：

• id→field→table_field
• name→field→table_field
• id, name→table_field ',' table_field→table_fields
• age→field→table_field
• id,name,age→table_fields ',' table_field→table_fields
  最终table_fields成为select_name的子节点，SELECT节点的子树包含三个table_field。这种设计让 AST 天然支持字段遍历，后续若扩展SELECT COUNT(*)，只需新增select_name → COUNT '(' '*' ')'规则即可。

注意：table '.' field规则支持user.id这种限定名，但原文未实现table的语义检查（如验证user表是否存在）。这是 DBMS 部分的职责，语法分析器只保证结构合法。

5. 避坑指南：VC++6.0 下 Lex/Yacc 开发的 4 条血泪经验

5.1 现象：yyparse()返回 1，但控制台无任何输出，程序直接退出

原因：main.c中未实现yywrap()，或yywrap()返回 0。Lex 在读取完输入后调用yywrap()，若返回 0，yylex()会认为还有输入，继续调用input()函数读取 —— 而 VC++6.0 的input()默认从stdin读，此时stdin已 EOF，getchar()返回EOF，yylex()进入死循环或崩溃。
解决：在mylexer.c末尾强制添加int yywrap() { return 1; }，并确保该函数在yylex()可见范围内（不能放在#ifdef YY_MAIN条件编译内）。

5.2 现象：输入SELECT * FROM t;后报syntax error，但CREATE TABLE t(id INT);正常

原因：select_name → '*'规则中，'*'是字符 token，但myparser.y的%token声明里漏掉了'*'！原文有'*' {return '*';}，但未在%token列表中声明，Yacc 会将其视为普通字符而非 token，导致select_name规则无法匹配。
解决：在%token声明块中加入'*'：

%token '(' ')' '*' '>' '<' '=' NE

5.3 现象：INSERT INTO t VALUES (1, 'abc');中的'abc'被识别为ID而非字符串字面量

原因：词法分析器未定义单引号字符串规则。原文只有SINGLE_QUOTEtoken，但没有'\'' [^']* '\''这样的字符串匹配规则，导致'abc'被拆成三个 token：SINGLE_QUOTE、ID（abc）、SINGLE_QUOTE，语法分析器无法归约为literal。
解决：在mylexer.l中添加字符串规则：

'\''[^'\n']*'\'' { // 去掉首尾单引号，存入 yylval char* s = strdup(yytext + 1); s[strlen(s)-1] = '\0'; yylval = (int)s; return STRING_LITERAL; }

并在myparser.y中声明%token STRING_LITERAL，修改literal规则：

literal: Name | NUMBER | STRING_LITERAL;

5.4 现象：编译通过，但运行时SELECT * FROM t后程序崩溃，调试显示yylval为野指针

原因：yylval类型为int（原文#define YYSTYPE int），但strdup()返回char*地址，强制转为int后存入yylval。在 32 位 VC++6.0 下int和char*都是 4 字节，看似可行；但若后续free((char*)yylval)时，yylval值已被其他 token 覆盖，free()传入非法地址。
解决：升级YYSTYPE为联合体，安全存储不同类型：

// define.h 中修改 typedef union { int ival; char* sval; struct Node* ast; } YYSTYPE; #define YYSTYPE_IS_DECLARED 1

并在mylexer.l中：

[0-9]+ { yylval.ival = atoi(yytext); return NUMBER; } [a-zA-Z][a-zA-Z0-9_]* { yylval.sval = strdup(yytext); return ID; }

语法动作中用yylval.ival或yylval.sval显式访问，杜绝类型混淆。

6. 二次开发实战：从语法解析器到可执行 DBMS 的三步改造技巧

6.1 第一步：为CREATE TABLE注入语义动作，生成内存表结构

当前create_st规则只有空动作：

create_st : CREATE DATABASE Name | CREATE TABLE Name'(' create_field ')' ;

要让它真正创建表，需在归约时执行 C 代码。首先定义内存表结构：

// define.h 中添加 typedef struct { char* name; int field_count; char** field_names; int* field_types; // 0=INT, 1=CHAR int* char_lengths; // 仅 CHAR 字段有效 } Table; Table* tables[100]; // 全局表数组 int table_count = 0;

然后修改create_st规则，注入$$（归约结果）和$n（第 n 个符号）：

create_st : CREATE TABLE Name '(' create_field ')' { // $3 是 Name token 的 yylval（char* 表名） // $5 是 create_field 归约后的字段信息（需在 create_field 规则中设置 $$） Table* t = malloc(sizeof(Table)); t->name = strdup($3); t->field_count = $5; // 假设 create_field 规则将字段数存入 $$ // ... 分配 field_names 等 tables[table_count++] = t; printf("Table '%s' created with %d fields\n", t->name, t->field_count); };

关键点：create_field规则需返回字段数，例如：

create_field: create_field ',' field_type { $$ = $1 + 1; } | field_type { $$ = 1; };

这样，每次CREATE TABLE都会真实构造一个Table对象，为后续INSERT/SELECT提供元数据。

6.2 第二步：用yylval传递上下文，让SELECT知道查哪张表

select_st规则目前是：

select_st: SELECT select_name FROM tables WHERE conditions;

其中tables是非终结符，归约后应返回表名。修改tables规则：

tables: tables ',' table { // 将多个表名存入全局变量或链表 add_to_table_list($3); } | table { clear_table_list(); add_to_table_list($1); }; table: Name { $$ = $1; }; // $1 是 Name 的 yylval（char*）

在select_st动作中，就能通过get_current_table_list()获取待查询表，再结合select_name的字段列表，构造内存扫描逻辑。

6.3 第三步：实现最简SELECT * FROM t执行引擎（10 行核心代码）

假设Table* t已存在，且内存中有一张t表的数据（用二维char** data模拟）：

// 在 select_st 动作中添加 select_st: SELECT '*' FROM tables { Table* t = find_table($4); // $4 是 tables 归约结果 if (t && t->data) { printf("id\tname\n"); // 打印表头 for (int i = 0; i < t->row_count; i++) { for (int j = 0; j < t->field_count; j++) { printf("%s\t", t->data[i][j]); } printf("\n"); } } };

这就是一个真实的、可运行的SELECT *引擎——它不连接磁盘，但完成了从语法树到数据遍历的全链路。后续扩展WHERE条件，只需在循环中插入if (eval_condition(t->data[i], $7))即可。

从那以后我每次写 parser，都强制走一遍yylex()单步调试，用printf("token=%d, text=%s\n", yylval, yytext)打印每个 token；每次加新规则，必先写一个最小测试用例（如echo "SELECT * FROM t;" | parser.exe），确保它不崩再谈功能。因为编译原理的坑不在算法多难，而在yylval类型错一位、yywrap()忘写一行、%left放错位置——这些细节不验证，后面十天都在猜哪行少了个分号。希望帮到你。

本文还有配套的精品资源，点击获取