一、介绍
在现代软件开发中，编译器和解释器是许多高级语言的基础架构。而词法分析和语法分析则是编译器前端的核心组成部分。Flex 和 Bison 作为开源的词法分析器和语法分析器生成工具，为开发者提供了高效构建语言解析系统的能力。
Flex（Fast Lexical Analyzer）是一个词法分析器生成工具，能够根据正则表达式规则生成词法分析器代码。Bison 则是一个语法分析器生成工具，能够根据上下文无关文法生成语法分析器代码。这两个工具的结合使用，能够帮助开发者快速构建完整的语言解析系统。
本教程将引导有编程基础的开发者，特别是熟悉 C 语言的读者，从零开始掌握 Flex 和 Bison 的使用方法，并最终实现一个简单的脚本语言前端。
二、环境准备：安装与配置
在开始学习 Flex 和 Bison 之前，我们需要先配置学习与开发环境。
安装 Flex 和 Bison
Linux(Ubuntu/Debian)
Flex 和 Bison 在大多数 Linux 发行版中都可以通过包管理器直接安装。
对于 Ubuntu/Debian 系统，可以使用以下命令进行安装：
sudo apt-get install flex bison
MacOS
对于 macOS 系统，可以使用 Homebrew 进行安装：
brew install flex bison
Windows
步骤 1：下载 Winflexbison
访问 Winflexbison 的官网或项目地址：
步骤 2：解压文件
下载后解压到任意目录，例如：
D:\tools\winflexbison
步骤 3：配置环境变量
- 打开：控制面板 → 系统 → 高级系统设置 → 环境变量
- 在“系统变量”中找到
Path，点击编辑 - 添加你解压的路径，例如：
D:\tools\winflexbison\bin
安装完成后，可以通过以下命令验证安装是否成功：
flex -hbison -h
如果看到输出信息，说明安装成功。
开发环境配置
为了方便开发，建议创建一个专门的工作目录，用于存放本教程的所有代码示例。可以使用以下命令创建并进入该目录：
mkdir flex-bison-tutorialcd flex-bison-tutorial
在本教程中，我们将使用标准的 C 语言开发工具链，包括 gcc 编译器。确保你的系统已经安装了 gcc：
gcc --version
如果没有安装，可以在网上搜索安装教程或者询问AI。
三、Flex 基础：词法分析器构建
词法分析原理
词法分析是编译过程的第一个阶段，其主要任务是将输入的字符流转换为有意义的词法单元（token）序列。这些 token 是语言的基本语法单元，如关键字、标识符、常量、运算符等。
词法分析器的工作原理可以简单描述为：
- 从输入流中读取字符
- 根据预定义的正则表达式模式匹配最长可能的字符序列
- 将匹配的字符序列转换为对应的 token 类型
- 返回 token 及其相关信息（如值、位置等）
Flex 作为词法分析器生成工具，能够根据用户提供的正则表达式规则自动生成高效的词法分析器代码。
Flex 程序结构
Flex 程序通常分为三个部分：定义部分、规则部分和用户子程序部分，这三个部分用两个%%分隔：
定义部分
%%
规则部分
%%
用户子程序部分
定义部分：包含选项、文字块、开始条件、转换等。其中，以%{和%}包裹的内容会被直接复制到生成的 C 代码中。
规则部分：包含正则模式行和模式匹配时执行的 C 代码。每个规则由一个正则表达式和一个动作组成。
用户子程序部分：包含在模式规则匹配时执行的 C 代码调用的函数，这部分内容会被直接复制到生成的 C 代码中。
Flex 简单示例：单词计数
让我们从一个简单的 Flex 程序开始，该程序用于统计输入中的字符数、单词数和行数。
首先，创建一个名为count.l的文件，内容如下：
%{
#include <stdio.h>
int chars = 0;
int words = 0;
int lines = 0;
%}
%%
[a-zA-Z]+ { words++; chars += strlen(yytext); }
\n { chars++; lines++; }
. { chars++; }
%%
int main() {
yylex();
printf("Chars: %d, Words: %d, Lines: %d\n", chars, words, lines);
return 0;
}
这个程序的结构如下：
- 定义部分：包含必要的头文件和全局变量声明。
- 规则部分：
- [a-zA-Z]+匹配一个或多个字母，作为单词，增加单词计数和字符计数。
- \n匹配换行符，增加字符计数和行计数。
- .匹配任意单个字符，增加字符计数。
- 用户子程序部分：包含main函数，调用yylex()启动词法分析。
要生成词法分析器并编译运行，可以使用以下命令：
flex count.l
gcc lex.yy.c -o count
./count
输入一些文本后按 Ctrl+D 结束输入，程序会输出统计结果。
Flex 生成代码简析
Flex 生成的代码主要包含以下几个部分：
- yylex()函数：词法分析器的主入口，不断从输入流中读取字符，匹配正则表达式规则，返回 token。
- yytext变量：指向当前匹配的文本。
- yyleng变量：表示当前匹配文本的长度。
- yyin变量：指向当前输入流，默认为stdin。
- yyout变量：指向当前输出流，默认为stdout。
理解这些基本元素有助于后续编写更复杂的词法分析器。
Flex 高级特性
定义部分选项
Flex 提供了多种选项来控制生成代码的行为，例如：
- %option noyywrap：禁止生成yywrap()函数，适用于不需要处理多个输入文件的情况。
- %option yylineno：自动维护行号信息，保存在yylineno变量中。
- %option reentrant：生成可重入的词法分析器，适用于多线程环境。
开始条件
Flex 允许定义不同的分析状态，称为开始条件，用于在不同上下文中使用不同的词法规则。例如：
%x COMMENT
%%
"/*" { BEGIN(COMMENT); }
<COMMENT>"*/" { BEGIN(INITIAL); }
<COMMENT>.|\n { /* 忽略注释内容 */ }
词法值传递
Flex 允许通过yylval变量将词法单元的值传递给语法分析器。例如：
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
Flex 实战：简单计算器词法分析器
现在，让我们构建一个简单计算器的词法分析器，作为后续学习 Bison 的基础。
创建calc.l文件，内容如下：
%{
#include "calc.tab.h"
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"(" { return OP; }
")" { return CP; }
\n { return EOL; }
[ \t] { /* 忽略空白字符 */ }
. { printf("未知字符: %c\n", *yytext); }
%%
这个词法分析器定义了以下 token：
- NUMBER：匹配一个或多个数字，转换为整数。
- 运算符+、-、*、/。
- 括号(和)。
- 换行符\n。
- 空白字符被忽略。
- 其他字符会被报告为未知字符。
四、Bison 基础：语法分析器构建
语法分析原理
语法分析是编译过程的第二个阶段，其主要任务是根据语言的语法规则，将词法分析器生成的 token 序列转换为抽象语法树（AST）或执行语义动作。
Bison 作为语法分析器生成工具，基于 LALR (1) 算法，能够根据用户提供的上下文无关文法生成高效的语法分析器代码。
Bison 程序结构
Bison 程序通常分为三个部分：定义部分、规则部分和用户子程序部分，同样用两个%%分隔：
定义部分
%%
规则部分
%%
用户子程序部分
定义部分：包含选项、文字块、声明（如 token 类型、优先级、结合性等）。
规则部分：包含语法规则和对应的语义动作。
用户子程序部分：包含错误处理函数等。
Bison 简单示例：计算器语法分析器
让我们继续之前的计算器示例，创建 Bison 文件calc.y：
%{
#include <stdio.h>
void yyerror(char *s);
extern int yylex();
%}
%token NUMBER
%token ADD SUB MUL DIV OP CP EOL
%left ADD SUB
%left MUL DIV
%%
calclist: /* 空规则 */
| calclist expr EOL { printf("= %d\n", $2); }
;
expr: term
| expr ADD term { $$ = $1 + $3; }
| expr SUB term { $$ = $1 - $3; }
;
term: factor
| term MUL factor { $$ = $1 * $3; }
| term DIV factor { $$ = $1 / $3; }
;
factor: NUMBER
| OP expr CP { $$ = $2; }
;
%%
void yyerror(char *s) {
fprintf(stderr, "错误: %s\n", s);
}
int main() {
printf("简单计算器. 输入表达式后按回车计算.\n");
yyparse();
return 0;
}
这个程序的结构如下：
- 定义部分：声明 token 类型和运算符优先级。
- 规则部分：
- calclist规则处理多个表达式，每个表达式后跟换行符。
- expr规则处理加法和减法。
- term规则处理乘法和除法。
- factor规则处理数字和括号内的表达式。
- 用户子程序部分：包含yyerror()错误处理函数和main()函数。
要生成语法分析器并编译运行，可以使用以下命令：
bison -d calc.y
flex calc.l
gcc lex.yy.c calc.tab.c -o calc
./calc
现在可以输入简单的算术表达式进行计算，如1+2*3，程序会输出结果。
Bison 生成代码简析
Bison 生成的代码主要包含以下几个部分：
- yyparse()函数：语法分析器的主入口，调用词法分析器获取 token，根据语法规则进行分析。
- $$变量：表示规则左部的值。
- $1、$2等变量：表示规则右部各部分的值。
- yyerror()函数：用户必须实现的错误处理函数。
Bison 高级特性
运算符优先级和结合性
在 Bison 中，可以通过%left、%right和%nonassoc声明来指定运算符的优先级和结合性。例如：
%left ADD SUB /* 左结合，优先级较低 */
%left MUL DIV /* 左结合，优先级较高 */
%right NEG /* 右结合，用于一元负号 */
抽象语法树构建
更复杂的语法分析器通常会构建抽象语法树，而不仅仅是计算结果。例如：
expr: expr ADD term { $$ = create_node(ADD_NODE, $1, $3); }
| term { $$ = $1; }
;
其中create_node()函数用于创建树节点。
错误处理和恢复
Bison 提供了error符号来处理语法错误并进行恢复：
calclist: calclist error EOL { yyerrok; }
| calclist expr EOL { printf("= %d\n", $2); }
;
Bison 实战：扩展计算器功能
让我们扩展之前的计算器，添加以下功能：
- 一元负号
- 指数运算
- 变量支持
修改calc.l以支持变量：
%{
#include "calc.tab.h"
%}
%%
[a-zA-Z] { yylval = *yytext - 'a'; return VARIABLE; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"^" { return POW; }
"(" { return OP; }
")" { return CP; }
"=" { return ASSIGN; }
\n { return EOL; }
[ \t] { /* 忽略空白字符 */ }
. { printf("未知字符: %c\n", *yytext); }
%%
修改calc.y以支持新功能：
%{
#include <stdio.h>
#include <math.h>
void yyerror(char *s);
extern int yylex();
int sym[26] = {0}; // 存储26个变量a-z的值
%}
%token NUMBER VARIABLE
%token ADD SUB MUL DIV POW ASSIGN OP CP EOL
%left ADD SUB
%left MUL DIV
%left POW
%right NEG // 一元负号
%%
calclist: /* 空规则 */
| calclist expr EOL { printf("= %d\n", $2); }
;
expr: term
| expr ADD term { $$ = $1 + $3; }
| expr SUB term { $$ = $1 - $3; }
;
term: factor
| term MUL factor { $$ = $1 * $3; }
| term DIV factor { $$ = $1 / $3; }
| term POW factor { $$ = pow($1, $3); }
;
factor: NUMBER
| VARIABLE { $$ = sym[$1]; }
| OP expr CP { $$ = $2; }
| SUB factor %prec NEG { $$ = -$2; } // 一元负号
| VARIABLE ASSIGN expr { sym[$1] = $3; $$ = $3; }
;
%%
void yyerror(char *s) {
fprintf(stderr, "错误: %s\n", s);
}
int main() {
printf("高级计算器. 支持变量、指数、一元负号.\n");
printf("示例: a=5, b=3, a + b^2 - -5\n");
yyparse();
return 0;
}
重新生成并编译：
bison -d calc.y
flex calc.l
gcc lex.yy.c calc.tab.c -lm -o calc
./calc
现在可以输入包含变量、指数和一元负号的表达式，如a=5, b=3, a + b^2 - -5，程序会正确计算并输出结果。
五、Flex 与 Bison 协同工作
Flex 与 Bison 的通信机制
Flex 和 Bison 之间通过以下方式进行通信：
- yylex()函数：由 Flex 生成，被 Bison 的yyparse()调用，返回下一个 token。
- yylval变量：由 Flex 设置，传递 token 的值给 Bison。
- yyerror()函数：由用户实现，处理语法错误。
数据类型管理
在 Flex 和 Bison 中，可以通过%union声明来管理不同类型的数据：
%union {
int int_val;
char char_val;
// 其他类型...
}
%token <int_val> NUMBER
%token <char_val> VARIABLE
这样可以确保不同类型的 token 被正确处理。
错误处理与恢复
在复杂的语言解析中，错误处理和恢复至关重要。可以通过以下方式实现：
- yyerror()函数：报告错误信息。
- error符号：在语法规则中使用error符号来匹配错误并恢复。
- yyerrok宏：重置错误状态，允许继续解析。
可重入分析器
在多线程环境中，需要使用可重入版本的 Flex 和 Bison：
- Flex：使用%option reentrant选项。
- Bison：使用%define api.pure full选项。
- 接口变化：yylex()和yyparse()函数将接受额外的上下文参数。
六、构建完整的脚本语言前端
设计语言语法
在构建完整的脚本语言前端之前，需要先设计语言的语法。假设我们要设计一个简单的脚本语言，支持以下特性：
- 变量声明和赋值
- 基本数据类型（整数、浮点数、字符串）
- 控制结构（if-else、循环）
- 函数定义和调用
- 表达式运算
可以使用 EBNF（扩展巴科斯范式）来描述语法：
program ::= { statement }
statement ::= var_decl | assign | if_stmt | while_stmt | func_decl | expr_stmt
var_decl ::= "var" IDENTIFIER (":" TYPE)? ("=" expr)? ";"
assign ::= IDENTIFIER "=" expr ";"
if_stmt ::= "if" "(" expr ")" block ("else" block)?
while_stmt ::= "while" "(" expr ")" block
func_decl ::= "func" IDENTIFIER "(" [param_list] ")" block
param_list ::= IDENTIFIER ("," IDENTIFIER)*
block ::= "{" { statement } "}"
expr_stmt ::= expr ";"
expr ::= ...
词法分析器设计
根据设计的语法，需要定义词法分析器的规则：
- 关键字：var、if、else、while、func等。
- 标识符：以字母开头的字母数字序列。
- 字面量：整数、浮点数、字符串。
- 运算符：算术、比较、逻辑运算符。
- 分隔符：括号、分号、逗号等。
语法分析器设计
根据设计的语法，需要定义语法分析器的规则：
- 优先级和结合性：正确设置运算符的优先级和结合性。
- 抽象语法树节点类型：为每种语法结构定义对应的 AST 节点。
- 语义动作：在语法规则中执行语义动作，如生成中间代码或直接执行。
抽象语法树构建
构建抽象语法树是语言前端的核心任务，可以使用结构体来定义不同类型的 AST 节点：
typedef enum {
NODE_EXPR,
NODE_VAR_DECL,
NODE_ASSIGN,
NODE_IF,
NODE_WHILE,
NODE_FUNC_DECL,
NODE_CALL,
// 其他节点类型...
} NodeType;
typedef struct Node {
NodeType type;
// 通用属性
int line;
// 具体节点属性
union {
ExprNode expr;
VarDeclNode var_decl;
AssignNode assign;
IfNode if_node;
WhileNode while_node;
FuncDeclNode func_decl;
CallNode call;
};
} Node;
代码生成与解释执行
构建完抽象语法树后，可以选择以下方式处理：
- 解释执行：直接遍历 AST 并执行相应的操作。
- 中间代码生成：将 AST 转换为中间表示（如字节码），然后由虚拟机执行。
- 目标代码生成：将 AST 直接转换为机器码。
七、进阶话题与最佳实践
错误处理优化
在实际应用中，错误处理至关重要。可以考虑以下优化：
- 错误定位：记录错误的行号和位置。
- 错误恢复策略：如同步点恢复、短语级恢复等。
- 友好的错误信息：提供有帮助的错误描述。
性能优化
对于大规模代码，性能优化必不可少：
- 词法分析优化：使用状态压缩、减少回溯等。
- 语法分析优化：缓存常见结构、减少冗余计算。
- 内存管理优化：合理使用内存池、避免频繁分配释放。
调试技巧
在开发复杂的解析器时，调试技巧非常有用：
- 跟踪输出：在关键位置添加调试输出。
- 断言检查：在代码中添加断言，确保逻辑正确性。
- 调试工具：使用 Flex 和 Bison 提供的调试选项。
现代扩展与替代方案
随着技术的发展，Flex 和 Bison 也有一些现代扩展和替代方案：
- Flex 替代品：如 re2c，生成速度更快的词法分析器。
- Bison 替代品：如 ANTLR，支持更多语法分析算法和语言。
- 集成工具链：如 LLVM，提供完整的编译工具链支持。
八、实战项目：实现简单脚本语言
项目结构规划
创建以下项目文件结构：
simple-script/
├── lexer.l
├── parser.y
├── ast.h
├── interpreter.c
└── Makefile
词法分析器实现
编写lexer.l文件：
%{
#include "parser.tab.h"
#include <string.h>
int line_num = 1;
%}
%option noyywrap
%%
"var" { return VAR; }
"if" { return IF; }
"else" { return ELSE; }
"while" { return WHILE; }
"func" { return FUNC; }
"return" { return RETURN; }
"true" { yylval.bool_val = 1; return BOOL; }
"false" { yylval.bool_val = 0; return BOOL; }
"nil" { return NIL; }
[a-zA-Z_][a-zA-Z0-9_]* {
strncpy(yylval.str_val, yytext, sizeof(yylval.str_val)-1);
yylval.str_val[sizeof(yylval.str_val)-1] = '\0';
return IDENTIFIER;
}
[0-9]+ {
yylval.int_val = atoi(yytext);
return INTEGER;
}
[0-9]+\.[0-9]* | \.[0-9]+ {
yylval.float_val = atof(yytext);
return FLOAT;
}
\"([^\\"]|\\.)*\" {
strncpy(yylval.str_val, yytext+1, sizeof(yylval.str_val)-2);
yylval.str_val[sizeof(yylval.str_val)-1] = '\0';
// 处理转义字符...
return STRING;
}
"==" { return EQ; }
"!=" { return NE; }
"<=" { return LE; }
">=" { return GE; }
"&&" { return AND; }
"||" { return OR; }
[=+\-*/%<>!&|^~] { return *yytext; }
[();{},.] { return *yytext; }
\n { line_num++; }
[ \t] { /* 忽略空白 */ }
. { fprintf(stderr, "Line %d: Unknown character '%c'\n", line_num, *yytext); }
%%
语法分析器实现
编写parser.y文件：
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ast.h"
void yyerror(char *s);
extern int yylex();
extern int line_num;
Node *root = NULL;
%}
%union {
int int_val;
float float_val;
char str_val[64];
int bool_val;
Node *node;
NodeList *nodelist;
}
%token <int_val> INTEGER
%token <float_val> FLOAT
%token <str_val> STRING IDENTIFIER
%token <bool_val> BOOL
%token VAR IF ELSE WHILE FUNC RETURN NIL
%token EQ NE LE GE AND OR
%type <node> program block statement expr
%type <nodelist> statements
%start program
%%
program: statements { root = $1; }
;
statements: statement { $$ = create_node_list($1); }
| statements statement { $$ = append_node_list($1, $2); }
;
statement: var_decl ";" { $$ = $1; }
| assign ";" { $$ = $1; }
| if_stmt { $$ = $1; }
| while_stmt { $$ = $1; }
| func_decl { $$ = $1; }
| expr ";" { $$ = $1; }
| RETURN expr ";" { $$ = create_return_node($2); }
;
var_decl: VAR IDENTIFIER ":" type { $$ = create_var_decl_node($2, $4, NULL); }
| VAR IDENTIFIER "=" expr { $$ = create_var_decl_node($2, NULL, $4); }
| VAR IDENTIFIER ":" type "=" expr { $$ = create_var_decl_node($2, $4, $6); }
;
type: IDENTIFIER { $$ = create_type_node($1); }
;
assign: IDENTIFIER "=" expr { $$ = create_assign_node($1, $3); }
;
if_stmt: IF "(" expr ")" block %prec THEN { $$ = create_if_node($3, $5, NULL); }
| IF "(" expr ")" block ELSE block { $$ = create_if_node($3, $5, $7); }
;
while_stmt: WHILE "(" expr ")" block { $$ = create_while_node($3, $5); }
;
func_decl: FUNC IDENTIFIER "(" [params] ")" block { $$ = create_func_decl_node($2, $4, $6); }
;
params: IDENTIFIER { $$ = create_param_node($1); }
| params "," IDENTIFIER { $$ = append_param_node($1, $3); }
;
block: "{" statements "}" { $$ = $2; }
;
expr: expr "||" expr { $$ = create_binary_node(OR_OP, $1, $3); }
| expr "&&" expr { $$ = create_binary_node(AND_OP, $1, $3); }
| expr "==" expr { $$ = create_binary_node(EQ_OP, $1, $3); }
| expr "!=" expr { $$ = create_binary_node(NE_OP, $1, $3); }
| expr "<" expr { $$ = create_binary_node(LT_OP, $1, $3); }
| expr ">" expr { $$ = create_binary_node(GT_OP, $1, $3); }
| expr LE expr { $$ = create_binary_node(LE_OP, $1, $3); }
| expr GE expr { $$ = create_binary_node(GE_OP, $1, $3); }
| expr "+" expr { $$ = create_binary_node(ADD_OP, $1, $3); }
| expr "-" expr { $$ = create_binary_node(SUB_OP, $1, $3); }
| expr "*" expr { $$ = create_binary_node(MUL_OP, $1, $3); }
| expr "/" expr { $$ = create_binary_node(DIV_OP, $1, $3); }
| expr "%" expr { $$ = create_binary_node(MOD_OP, $1, $3); }
| "-" expr %prec NEG { $$ = create_unary_node(NEG_OP, $2); }
| "!" expr { $$ = create_unary_node(NOT_OP, $2); }
| INTEGER { $$ = create_literal_node(INT_TYPE, &$1); }
| FLOAT { $$ = create_literal_node(FLOAT_TYPE, &$1); }
| STRING { $$ = create_literal_node(STRING_TYPE, $1); }
| BOOL { $$ = create_literal_node(BOOL_TYPE, &$1); }
| NIL { $$ = create_literal_node(NIL_TYPE, NULL); }
| IDENTIFIER { $$ = create_identifier_node($1); }
| "(" expr ")" { $$ = $2; }
| IDENTIFIER "(" [args] ")" { $$ = create_call_node($1, $3); }
;
args: expr { $$ = create_arg_node($1); }
| args "," expr { $$ = append_arg_node($1, $3); }
;
%%
void yyerror(char *s) {
fprintf(stderr, "Line %d: Error: %s\n", line_num, s);
}
int main() {
yyparse();
if (root) {
interpret(root);
free_node(root);
}
return 0;
}
抽象语法树实现
编写ast.h文件：
#ifndef AST_H
#define AST_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum {
INT_TYPE,
FLOAT_TYPE,
STRING_TYPE,
BOOL_TYPE,
NIL_TYPE,
TYPE_TYPE,
VAR_DECL_NODE,
ASSIGN_NODE,
IF_NODE,
WHILE_NODE,
FUNC_DECL_NODE,
RETURN_NODE,
BINARY_OP,
UNARY_OP,
IDENTIFIER_NODE,
CALL_NODE,
NODE_LIST
} NodeType;
typedef struct Node Node;
typedef struct NodeList NodeList;
typedef struct Node {
NodeType type;
union {
// 字面量节点
struct {
NodeType data_type;
void *value;
} literal;
// 类型节点
struct {
char type_name[64];
} type;
// 变量声明节点
struct {
char name[64];
Node *type;
Node *init_value;
} var_decl;
// 赋值节点
struct {
char name[64];
Node *value;
} assign;
// if节点
struct {
Node *condition;
Node *consequent;
Node *alternative;
} if_node;
// while节点
struct {
Node *condition;
Node *body;
} while_node;
// 函数声明节点
struct {
char name[64];
NodeList *params;
Node *body;
} func_decl;
// 返回节点
struct {
Node *value;
} ret;
// 二元运算节点
struct {
NodeType op;
Node *left;
Node *right;
} bin_op;
// 一元运算节点
struct {
NodeType op;
Node *operand;
} un_op;
// 标识符节点
struct {
char name[64];
} ident;
// 函数调用节点
struct {
char name[64];
NodeList *args;
} call;
// 节点列表
struct {
Node *head;
struct NodeList *tail;
} list;
};
} Node;
typedef struct NodeList {
Node *head;
struct NodeList *tail;
} NodeList;
Node *create_literal_node(NodeType data_type, void *value);
Node *create_type_node(char *type_name);
Node *create_var_decl_node(char *name, Node *type, Node *init_value);
Node *create_assign_node(char *name, Node *value);
Node *create_if_node(Node *condition, Node *consequent, Node *alternative);
Node *create_while_node(Node *condition, Node *body);
Node *create_func_decl_node(char *name, NodeList *params, Node *body);
Node *create_return_node(Node *value);
Node *create_binary_node(NodeType op, Node *left, Node *right);
Node *create_unary_node(NodeType op, Node *operand);
Node *create_identifier_node(char *name);
Node *create_call_node(char *name, NodeList *args);
NodeList *create_node_list(Node *node);
NodeList *append_node_list(NodeList *list, Node *node);
NodeList *create_arg_node(Node *node);
NodeList *append_arg_node(NodeList *list, Node *node);
void free_node(Node *node);
void interpret(Node *node);
#endif
解释器实现
编写interpreter.c文件：
#include "ast.h"
// 简单的符号表实现
typedef struct Symbol {
char name[64];
Node *value;
struct Symbol *next;
} Symbol;
Symbol *sym_table = NULL;
Node *lookup_symbol(char *name) {
Symbol *s = sym_table;
while (s) {
if (strcmp(s->name, name) == 0) {
return s->value;
}
s = s->next;
}
return NULL;
}
void insert_symbol(char *name, Node *value) {
Symbol *s = malloc(sizeof(Symbol));
strcpy(s->name, name);
s->value = value;
s->next = sym_table;
sym_table = s;
}
// 解释器核心函数
void interpret(Node *node) {
if (!node) return;
switch (node->type) {
case NODE_LIST:
interpret(node->list.head);
interpret(node->list.tail);
break;
case VAR_DECL_NODE:
if (node->var_decl.init_value) {
interpret(node->var_decl.init_value);
insert_symbol(node->var_decl.name, node->var_decl.init_value);
} else {
insert_symbol(node->var_decl.name, NULL);
}
break;
case ASSIGN_NODE:
interpret(node->assign.value);
insert_symbol(node->assign.name, node->assign.value);
break;
case IF_NODE:
interpret(node->if_node.condition);
if (node->if_node.condition->literal.value) {
interpret(node->if_node.consequent);
} else if (node->if_node.alternative) {
interpret(node->if_node.alternative);
}
break;
case WHILE_NODE:
while (1) {
interpret(node->while_node.condition);
if (!node->while_node.condition->literal.value) break;
interpret(node->while_node.body);
}
break;
case RETURN_NODE:
interpret(node->ret.value);
exit(0);
break;
case BINARY_OP:
interpret(node->bin_op.left);
interpret(node->bin_op.right);
switch (node->bin_op.op) {
case ADD_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value +
*(int*)node->bin_op.right->literal.value;
break;
case SUB_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value -
*(int*)node->bin_op.right->literal.value;
break;
case MUL_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value *
*(int*)node->bin_op.right->literal.value;
break;
case DIV_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value /
*(int*)node->bin_op.right->literal.value;
break;
case MOD_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value %
*(int*)node->bin_op.right->literal.value;
break;
case EQ_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value ==
*(int*)node->bin_op.right->literal.value;
break;
case NE_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value !=
*(int*)node->bin_op.right->literal.value;
break;
case LT_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value <
*(int*)node->bin_op.right->literal.value;
break;
case GT_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value >
*(int*)node->bin_op.right->literal.value;
break;
case LE_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value <=
*(int*)node->bin_op.right->literal.value;
break;
case GE_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value >=
*(int*)node->bin_op.right->literal.value;
break;
case AND_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value &&
*(int*)node->bin_op.right->literal.value;
break;
case OR_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
*(int*)node->bin_op.left->literal.value ||
*(int*)node->bin_op.right->literal.value;
break;
}
break;
case UNARY_OP:
interpret(node->un_op.operand);
switch (node->un_op.op) {
case NEG_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
-*(int*)node->un_op.operand->literal.value;
break;
case NOT_OP:
node->literal.value = malloc(sizeof(int));
*(int*)node->literal.value =
!*(int*)node->un_op.operand->literal.value;
break;
}
break;
case IDENTIFIER_NODE:
node->literal.value = lookup_symbol(node->ident.name);
break;
case CALL_NODE:
// 这里需要实现函数调用逻辑，暂时简单处理
printf("Calling function %s\n", node->call.name);
break;
case LITERAL_NODE:
// 字面量节点不需要解释
break;
default:
fprintf(stderr, "Unknown node type\n");
exit(1);
}
}
// 节点创建函数实现...（为节省篇幅，此处省略具体实现）
编译与测试
编写Makefile：
all: simple-script
simple-script: lexer.l parser.y ast.h interpreter.c
flex lexer.l
bison -d parser.y
gcc lex.yy.c parser.tab.c interpreter.c -o simple-script
clean:
rm -f lex.yy.c parser.tab.c parser.tab.h simple-script
编译并运行：
make
./simple-script
测试示例代码：
var a = 10;
var b = 20;
if (a < b) {
print("a is less than b");
} else {
print("a is greater than or equal to b");
}
while (a < 20) {
a = a + 1;
}
func add(x, y) {
return x + y;
}
print(add(a, b));
九、总结与展望
未来学习方向
如果你对编译技术感兴趣，可以继续学习以下方向：
- 高级语法分析算法：如 GLR、Earley 等。
- 中间表示和优化：如 SSA 形式、数据流分析等。
- 代码生成技术：如 LLVM IR 生成、JIT 编译等。
- 特定领域语言（DSL）：如何设计和实现特定领域的语言。
进阶资源推荐
以下是一些推荐的学习资源：
- 书籍：《Compilers: Principles, Techniques, and Tools》（龙书）、《Flex & Bison》。
- 工具文档：Flex 和 Bison 官方文档。
- 开源项目：如 LLVM、GCC、ANTLR 等。
- 在线课程：Coursera 的编译原理课程、MIT 的 6.035 等。
通过不断学习和实践，你将能够构建出更复杂、更高效的语言处理系统，为软件开发带来更多可能性。
共勉！