从零构建四则运算编译器——基于 Flex Bison

目录1. 前言计算机如何理解“12*3”?2. 系统架构3. 语法分析正则表达式与数值传递3.1 定义Token3.2 动作处理4. 语法分析解决歧义与优先级4.1 优先级的分层逻辑4.2 逻辑推导5. 工程实现Linux 环境下的工具链协同5.1 环境准备与版本管理5.2 编写lexer.l5.3 编写parser.y5.4 流水线编译链路6. 补充如何编写parser.y和lexer.l6.1 文件的“三段式”骨架6.2 手把手教你写Flex文件6.3 手把手教你写Bison文件parser.y6.4 它们怎么接头7.如果你还有疑问继续看这里1. 词法分析a. 文法正则拆解b. 练习手写出一个能识别 if, else, while 以及变量名字母开头后跟字母数字的 Flex 文件2. 语法分析3. 语义动作1. 前言计算机如何理解“12*3”?对于计算机它接收到的最初只是一个无意义的字符流‘1’, ’ , ‘’, ’ , ‘2’, ‘*’, ‘3’。要让机器像人一样进行计算必须经历两个核心阶段识别单词词法分析与理解结构语法分析。本文将记录我如何利用 Flex 和 Bison 这两个经典工具从底层逻辑出发构建一个支持优先级的四则运算解析器。2. 系统架构Flex (Lexical Analyzer)负责“切词”。它扫描源代码利用正则表达式匹配出数字、加减乘除符号并将其包装成 Token记号。Bison (Syntax Parser)负责“组装”。它接收 Token 流根据预设的上下文无关文法CFG判断语法是否合法并执行相应的数学运算。两者通过一个名为yylval的全局变量进行通信。Flex 将识别出的数值存入 yylval并返回 Token 类型告知 Bison “到货了”。3. 语法分析正则表达式与数值传递在 Flex 配置文件 .l 中逻辑的核心在于如何定义规则并处理匹配结果。3.1 定义Token我们需要处理三类字符数字使用正则 [0-9] 匹配操作符、-、*、/、(、)噪音空格和制表符3.2 动作处理当匹配到数字字符串如 “123”时不能直接传递因为它是文本。转换调用 C 语言的 atoi(yytext) 将其转换为整数。传递赋值给 yylval随后返回类型 NUMBER。过滤对于空格匹配后不执行任何动作从而实现自动忽略。4. 语法分析解决歧义与优先级这是编译器最关键的部分。直接定义 exp: exp exp 会导致歧义性——面对 12*3机器不知道该先处理加法还是乘法。4.1 优先级的分层逻辑为了在语法层面强加数学优先级我们采用了分层嵌套的 CFG 结构。原理很简单越靠近底层的规则优先级越高。我们将语法划分为三个递进的层次Factor因子最高优先级。包括纯数字和被括号包围的表达式。括号具有强行改变顺序的作用因此被放在最底层。Term项中等优先级。专门处理乘法和除法。Expression表达式最低优先级。处理加法和减法。4.2 逻辑推导这种结构的严密性在于其依赖关系想计算 Expression加减必须先获取 Term 作为操作数。想计算 Term乘除必须先获取 Factor 作为操作数。这种“层级依赖”迫使 Bison 在解析12*3时必须先向下搜索并完成 2*3 的归约过程才能返回上层处理 1。这就在不使用显式判断语句的情况下通过语法结构实现了数学优先级。5. 工程实现Linux 环境下的工具链协同5.1 环境准备与版本管理在 Linux 环境下首先确保安装了必备工具并建立规范的项目结构。# 1. 安装工具sudoapt-getinstallflex bison gcc规范的目录结构lexer.l: Flex 词法规则文件。parser.y: Bison 语法规则文件。Makefile:可选用于自动化编译的脚本。5.2 编写lexer.l定义如何从乱序的字符中获取Token。%{#includeparser.tab.h// 必须引入 Bison 生成的头文件用于传递 Token 编号%}%option noyywrap%%[0-9]{yylvalatoi(yytext);returnNUMBER;}// 抓到数字转为整数存入行李箱{returnADD;}-{returnSUB;}*{returnMUL;}/{returnDIV;}({returnOP;}// 左括号){returnCP;}// 右括号\n{returnEOL;}// 换行符代表计算触发[\t]{/* 忽略空白 */}.{printf(未知字符: %s\n,yytext);}%%5.3 编写parser.y这是实现“三层滤网结构”的地方。我在文件中定义了优先级逻辑并编写了简单的 C 代码来输出结果。%{#includestdio.hvoidyyerror(char*s);intyylex();%}%token NUMBER ADD SUB MUL DIV OP CP EOL%%/* 顶层规则处理多行输入 */calclist:/* 空 */|calclist exp EOL{printf(结果 %d\n ,$2);};/* 第一层处理加减 */exp:term{$$$1;}|exp ADD term{$$$1$3;}|exp SUB term{$$$1-$3;};/* 第二层处理乘除 */term:factor{$$$1;}|term MUL factor{$$$1*$3;}|term DIV factor{$$$1/$3;};/* 第三层处理数字和括号优先级最高 */factor:NUMBER{$$$1;}|OP exp CP{$$$2;};%%voidyyerror(char*s){fprintf(stderr,错误: %s\n,s);}intmain(){printf( );yyparse();return0;}5.4 流水线编译链路在 Linux 终端我执行了以下三步走战略这体现了编译器从源代码到二进制文件的完整转化过程解析语法规范bison -d parser.y产物parser.tab.c逻辑代码和 parser.tab.hToken 声明供 Flex 使用。解析词法规范flex lexer.l产物lex.yy.c根据正则生成的扫描器 C 代码。终极链接编译gcc -o calc parser.tab.c lex.yy.c -lfl逻辑将拼图师Bison和碎纸机Flex的代码揉合在一起生成可执行程序 calc。6. 补充如何编写parser.y和lexer.l6.1 文件的“三段式”骨架无论是 Flex 还是 Bison文件都长这样被两个 %% 划分为三个区/* 第一区定义与头文件 */%{// 这里写 C 语言代码比如 #include%}%%/* 第二区核心规则段 */// 这里是 Flex 的正则匹配 或 Bison 的语法规则%%/* 第三区辅助函数 */// 比如 main 函数通常写在 Bison 里6.2 手把手教你写Flex文件打招呼你必须告诉 Flex“我抓到的情报是要送给 Bison 处理的。”所以你需要引入 Bison 自动生成的头文件%{#includeparser.tab.h// 这里的名字必须跟 bison 生成的头文件对上%}识别并汇报在这个区写正则表达式。左边是长相右边是动作。识别加号“” { return ADD; }(解释看到加号大喊一声“ADD”Bison 听到这个代号就知道该干嘛了。)识别数字重点[0-9] { yylval atoi(yytext); return NUMBER; }拆解逻辑[0-9]抓到一串数字。yytextFlex 抓到的原始字符串比如 “42”。atoi()把字符串转成整数。yylval关键 这是 Flex 和 Bison 共同拥有的“储物箱”。你把算好的 42 放进去。return NUMBER;给 Bison 发报告诉它“数字到货了”。6.3 手把手教你写Bison文件parser.yBison 是“总指挥”它决定了怎么拼拼图。第一区声明代号你得先在开头告诉 Bison情报员Flex会传回哪些代号%{#includestdio.h%}%token NUMBER ADD SUB MUL DIV// 这里的名字要跟 Flex 里的 return 对应CFG规则左边是目标右边是组成部分。6.4 它们怎么接头“我怎么知道 NUMBER 是多少号”当你运行 bison -d parser.y 时Bison 会生成一个 parser.tab.h。这个头文件里会自动写上#define NUMBER 258。因为你在 Flex 里 #include 了这个头文件所以 Flex 也知道了return NUMBER 就是 return 258。7.如果你还有疑问继续看这里要真正掌握这个实验你需要掌握一下四个核心知识板块。1. 词法分析知识点正则表达式 你得能手写出描述整数、浮点数、标识符的正则。比如[0-9] 是整数[0-9]*.[0-9] 是小数。状态机 (DFA) 了解 Flex 背后其实是把正则变成了一个自动机它根据字符一个一个跳状态。Token 的传递 明白 yytext是当前认出的字符串yylval 是要把这个字的值传给“大脑”语法分析器。下面详细讲正则。a. 文法正则拆解正则表达式怎么写看这篇博客正则表达式简明指南在本次实践中文法要求分别如下有十进制、八进制、十六进制。十进制非0开头的一串数字或者单独的0。正则0[xX][0-9a-fA-F]八进制以0开头后面跟着0-7。正则0[0-7]*十六进制前缀是0x或0X后面是数字或字母a-f正则0[xX][0-9a-fA-F]要有小数点可能有指数部分e或E情况A有小数点如3.14.13.正则[0-9]*\.[0-9]|[0-9]\.情况B有指数部分如 1e10, 1.2e-5指数部分正则[eE][-]?[0-9]组合:([0-9]*\.[0-9]|[0-9]\.)([eE][-]?[0-9])?说明前面的部分是小数后面括号里的指数部分是可选的 ?注意Flex 里的潜规则最长匹配原则Longest Match如果输入是 0x123规则 10 (匹配了第一个字符)规则 20x[0-9a-f] (匹配了全部)Flex 会选 规则 2因为它最长。第一条规则优先First Match如果两个正则都能匹配且长度一样规则 1“if”规则 2[a-z]输入 if 时Flex 会选 规则 1。所以你要把关键词如 , -, if写在通用的变量名规则前面。b. 练习手写出一个能识别 if, else, while 以及变量名字母开头后跟字母数字的 Flex 文件创建该文件为 scanner.l%{#includestdio.h%}/* 定义部分设置宏让后面的正则更清晰 */LETTER[a-zA-Z]DIGIT[0-9]IDENTIFIER{LETTER}({LETTER}|{DIGIT})*%%if{printf(Recognized keyword: IF\n);}else{printf(Recognized keyword: ELSE\n);}while{printf(Recognized keyword: WHILE\n);}{IDENTIFIER}{printf(Recognized identifier: %s\n,yytext);}[\t\n]{/* 忽略空格、制表符和换行 */}.{printf(Unknown character: %s\n,yytext);}%%/* 用户代码部分 */intyywrap(){return1;}intmain(){printf(Enter code to scan (CtrlD to exit):\n);yylex();return0;}解释根据第一条规则有限原则关键词if、else、while要写在最前面yytext是Flex自动提供的一个全局指针指向当前被匹配到的那段字符串。.为通配符Wildcard匹配除换行符 \n 以外的任何单个字符。如何运行该文件# 1. 生成 C 代码flex scanner.l# 2. 编译生成的可执行文件gcc lex.yy.c-oscanner# 3. 运行并输入内容测试./scanner# 测试输入if(a10)whileelseb1232. 语法分析知识点上下文无关文法 (CFG) 像我实验文档没放出来里那些 Exp - Exp ADD Exp。你要学会把复杂的语言拆解成层层嵌套的产生式。优先级与结合性 为什么 12*3 先算乘法在 Bison 里通过 %left 或文法分层Expr - Term - Factor来解决。移进-规约 (Shift-Reduce) 了解 Bison 是如何通过一个“栈”来工作的。当它看到 12 后面是 * 时它会决定是先“组合” 12 还是先等 2*3。3. 语义动作知识点属性文法 在 Bison 的 { … } 块里写 C 代码。递归求值 明白 $$ $1 $3 是如何把子节点的结果汇聚到父节点的。