手写公式解析器：词法分析、递归下降与AST求值实践

简介基于Visual C与MFC实现的数学公式解析器完整源码面向需要处理字符串数学表达式的C开发者、编译原理学习者和科学计算工具使用者可帮助理解词法分析、语法分析及表达式求值流程。压缩包仅46KB共28个文件主体为6个.h头文件和5个.cpp源文件并包含可直接运行的可执行程序、Visual Studio工程配置、资源脚本及代码辅助文档便于直接编译调试。源码基于CString类完成分词与解析支持sin、cos、tan、exp等函数以及多变量输入覆盖运算符优先级、括号匹配、函数参数解析等关键技术并附有函数解析、公式读取等辅助模块适合作为解析器设计的完整实例。目前已有757人学习下载对研究MFC字符串处理或表达式解析的开发者具有不错的参考价值。1. 为什么自己动手写公式解析器调库之外的另一种选择先说个直白的结论哪怕在GitHub上随手能搜到一堆表达式求值库我个人仍然建议你在VC环境下亲手实现一个数学公式解析器。原因不复杂——很多所谓现成库要么是C#或Java写的要么依赖STL的重型组件放到老旧的VC 6.0或者MFC工程里光是一堆编译错误就能耗掉一个下午。更关键的是公式解析器这东西本质上是个迷你编译器剥开来看就是词法分析语法分析求值三个环节你亲手写一遍对递归、状态机、运算符优先级这些东西的理解会上升一个层次。有朋友可能会说那就用std::map存变量、用strtod转数字、再用双栈算法调度场算法求值不也能跑吗能跑但可维护性和扩展性差很多。双栈算法适合一次性求值一旦你需要支持用户自定义函数、需要缓存语法树、需要把表达式翻译成指令序列它就会变得很别扭。我在项目里采用的是词法分析器递归下降解析器抽象语法树AST求值的结构这套结构在编译器领域叫手写递归下降代码量不大逻辑却非常清晰。再补充一点市面上不少解析器源码喜欢用extern C __declspec(dllexport)把整个引擎做成一个黑盒DLL接口就一个double Evaluate(LPCTSTR expr)确实省事。但如果你没读过内部实现一旦出了括号不匹配但结果却是对的这种诡异问题你连排查的方向都没有。自己做一遍至少你知道错误信息该从哪里抛出来。2. 词法分析器设计从CString字符串到Token流2.1 Token结构体与类型定义词法分析Lexer干的事情很简单把用户输入的字符串比如sin(pi/6)2*x^2切分成一个个有含义的Token也就是单词。我这里定义的Token类型不算多但覆盖了绝大多数公式场景enum TokenType { TOKEN_NUMBER, // 数字如 3.14 TOKEN_IDENTIFIER, // 变量名或函数名如 x、sin TOKEN_PLUS, // TOKEN_MINUS, // - TOKEN_MUL, // * TOKEN_DIV, // / TOKEN_POW, // ^ TOKEN_LPAREN, // ( TOKEN_RPAREN, // ) TOKEN_COMMA, // , 用于多参数函数 TOKEN_END // 输入结束 }; struct Token { TokenType type; double numberValue; // TYPE_NUMBER 时有效 CString textValue; // TYPE_IDENTIFIER 时有效保留函数名/变量名 int position; // 在原始字符串中的位置用于报错 };这里有个容易被忽视的设计position字段。它看起来只是记录位置实际在调试时帮了大忙。比如用户输入2*(34缺少右括号解析器报错时可以精准告诉用户第7个字符附近括号不匹配 而不是甩一句冰冷的表达式错误。2.2 逐字符扫描的核心逻辑在我的实现里词法分析器是逐字符扫描输入的CString。VC环境下建议用CString::GetAt(i)而不是[]操作符前者越界时行为是确定的后者可能导致崩溃。扫描时遵循以下几个基本原则遇到空白字符空格、\t直接跳过。遇到数字字符用strtod从当前位置将整个数字读出来并将字符串指针推进到数字末尾。这里顺带支持了3.14、.5、1e-3这类写法——用strtod比手写数字解析要靠谱得多。遇到字母或下划线_继续读后续字母、数字、下划线组成完整标识符。然后查一张函数名映射表判断它是内置函数如sin、cos、sqrt还是普通变量。遇到运算符和括号直接生成对应Token。遇到无法识别的字符抛出异常CFormulaException并携带出错位置。核心代码骨架大概是这样的bool CFormulaLexer::NextToken(Token token) { int len m_expr.GetLength(); // 跳过空白 while (m_pos len _istspace(m_expr[m_pos])) { m_pos; } if (m_pos len) { token.type TOKEN_END; return true; } TCHAR ch m_expr[m_pos]; token.position m_pos; // 数字 if (_istdigit(ch) || ch _T(.)) { TCHAR* pEnd NULL; token.numberValue _tcstod(m_expr.Mid(m_pos), pEnd); m_pos (int)(pEnd - (LPCTSTR)m_expr.Mid(m_pos)); token.type TOKEN_NUMBER; return true; } // 标识符变量或函数名 if (_istalpha(ch) || ch _T(_)) { int start m_pos; while (m_pos len (_istalnum(m_expr[m_pos]) || m_expr[m_pos] _T(_))) { m_pos; } token.textValue m_expr.Mid(start, m_pos - start); token.type TOKEN_IDENTIFIER; return true; } // 运算符与括号 switch (ch) { case _T(): token.type TOKEN_PLUS; break; case _T(-): token.type TOKEN_MINUS; break; // ... 其他符号 } m_pos; return true; }注意_tcstod在多字节字符集MBCS与Unicode字符集下都能编译通过。在VC 6.0时代很多人还在用atof它不能告诉你数字消耗了多少字符后续位置推进会很麻烦所以建议用_tcstod。2.3 多字节字符集下的中文字符处理陷阱有一类坑属于非程序逻辑问题但很致命使用了中文字符比如中文括号、中文运算符×。MBCS下中文以双字节形式存在逐字符用_istalpha判断时偶尔会把中文的首字节识别为字母。我的处理办法是统一在中英文环境下做一次预处理把中文符号替换成英文符号同时规整化全角数字expr.Replace(_T(), _T(()); expr.Replace(_T(), _T())); expr.Replace(_T(×), _T(*)); expr.Replace(_T(÷), _T(/));这一步在日常使用中体验提升非常大尤其是在做桌面计算器类软件时用户几乎不会特意切换输入法状态。3. 递归下降解析器用文法规则解决优先级问题3.1 文法设计四层结构搞定所有优先级表达式解析最核心的问题是运算符优先级。数学里23*4必须先算乘法-2^2到底是(-2)^2还是-(2^2)2^3^2是左结合还是右结合这些问题看起来很基础但处理不好就会出大bug。我采用的四层递归下降文法从高优先级到低优先级依次是expression : term (( | -) term)* term : factor ((* | /) factor)* factor : unary (^ factor)? // 幂运算右结合 unary : (- | )* primary // 一元正负号 primary : NUMBER | IDENTIFIER ( args? ) | ( expression )解释一下为什么这样分层expression和term处理左结合的加减乘除因为a-b-c应当等于(a-b)-c也就是从左往右算。factor单独借用了unary和^并且^的递归调用指向factor自身这就实现了右结合。比如2^3^2按照右结合解析为2^(3^2)结果才是512而不是64。这一点和多数数学软件的约定一致。unary支持一元负号并且允许多重负号比如--5是合法的。primary是解析的终点它处理括号嵌套、数字字面量、变量和函数调用。3.2 每个节点都被存成AST节点解析过程构建出抽象语法树。节点定义如下struct ASTNode { enum NodeType { CONSTANT, VARIABLE, UNARY_OP, BINARY_OP, FUNCTION } type; // 常量和变量 double constantValue; CString variableName; // 运算符 enum Operator { OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_POW, OP_NEG } op; // 函数 CString funcName; std::vectorASTNode* children; ASTNode() : type(CONSTANT), constantValue(0), op(OP_ADD) {} ~ASTNode() { for (size_t i 0; i children.size(); i) { delete children[i]; } } };children存储子节点。对于一元负号children只有一个元素对于二元运算children有两个元素对于函数调用children的个数取决于函数参数个数。AST构建完成后求值阶段就是一次深度优先遍历。3.3 递归下降解析的关键实现这里给出factor的实现片段它最能体现递归下降的精髓ASTNode* CFormulaParser::ParseFactor() { ASTNode* node ParseUnary(); if (m_currentToken.type TOKEN_POW) { Advance(); // 跳过 ^ ASTNode* right ParseFactor(); // 递归调用实现右结合 ASTNode* binaryNode new ASTNode(); binaryNode-type ASTNode::BINARY_OP; binaryNode-op ASTNode::OP_POW; binaryNode-children.push_back(node); binaryNode-children.push_back(right); return binaryNode; } return node; }注意这里ParseFactor内部先调用ParseUnary再判断^如果当前运算符是^就递归调用ParseFactor本身。递归调用的存在使得2^3^2被解释为2^(3^2)。如果这里改成调用ParseUnary就成了左结合结果会变成(2^3)^2。3.4 括号与函数参数的递归调用primary处理括号和函数调用的逻辑也很直观ASTNode* CFormulaParser::ParsePrimary() { if (m_currentToken.type TOKEN_NUMBER) { ASTNode* node new ASTNode(); node-type ASTNode::CONSTANT; node-constantValue m_currentToken.numberValue; Advance(); return node; } if (m_currentToken.type TOKEN_IDENTIFIER) { CString name m_currentToken.textValue; Advance(); // 检查后面是不是左括号是则视为函数调用 if (m_currentToken.type TOKEN_LPAREN) { Advance(); ASTNode* funcNode new ASTNode(); funcNode-type ASTNode::FUNCTION; funcNode-funcName name; if (m_currentToken.type ! TOKEN_RPAREN) { // 解析第一个参数 funcNode-children.push_back(ParseExpression()); // 后续参数用逗号分隔 while (m_currentToken.type TOKEN_COMMA) { Advance(); funcNode-children.push_back(ParseExpression()); } } // 期待右括号 if (m_currentToken.type ! TOKEN_RPAREN) { throw CFormulaException(_T(缺少右括号), m_currentToken.position); } Advance(); return funcNode; } else { // 否则当作变量 ASTNode* varNode new ASTNode(); varNode-type ASTNode::VARIABLE; varNode-variableName name; return varNode; } } if (m_currentToken.type TOKEN_LPAREN) { Advance(); ASTNode* node ParseExpression(); if (m_currentToken.type ! TOKEN_RPAREN) { throw CFormulaException(_T(缺少右括号), m_currentToken.position); } Advance(); return node; } throw CFormulaException(_T(意外的Token), m_currentToken.position); }从这里能看出来函数调用max(1,2,3)会被解析成一个FUNCTION节点children里装三个表达式节点这比在词法阶段就把函数名分门别类要灵活得多。4. 求值引擎遍历AST得到最终结果4.1 使用double作为统一数值类型异常处理与精度问题AST构造完毕后求值就是一个简单的后序遍历。遍历到常量节点返回常量变量节点通过符号表查找值函数节点先递归求各参数再调用实现运算符节点对左右子树求值后再做运算。核心代码大致如下double CFormulaEvaluator::EvaluateNode(const ASTNode* node) { switch (node-type) { case ASTNode::CONSTANT: return node-constantValue; case ASTNode::VARIABLE: { CMapStringToDouble::CPair* pair m_symbolTable.PLookup(node-variableName); if (!pair) { throw CFormulaException(_T(未定义的变量: ) node-variableName, 0); } return pair-value; } case ASTNode::UNARY_OP: { double val EvaluateNode(node-children[0]); return (node-op ASTNode::OP_NEG) ? -val : val; } case ASTNode::BINARY_OP: { double left EvaluateNode(node-children[0]); double right EvaluateNode(node-children[1]); switch (node-op) { case ASTNode::OP_ADD: return left right; case ASTNode::OP_SUB: return left - right; case ASTNode::OP_MUL: return left * right; case ASTNode::OP_DIV: if (right 0.0) { throw CFormulaException(_T(除零错误), 0); } return left / right; case ASTNode::OP_POW: return pow(left, right); } break; } case ASTNode::FUNCTION: { return CallFunction(node-funcName, node-children); } } return 0.0; }这里我把符号表设计成CMapStringToDouble因为这是MFC/VC环境下最简单也最不容易出错的键值对容器。如果你在用std::mapCString, double在Unicode环境下写_T(x)作为key时要留意比较器是否区分大小写——CMapStringToDouble默认不区分大小写用起来更友好。4.2 变量符号表与多参数函数的灵活扩展对于内置函数我维护了一张静态函数注册表把函数名映射到函数指针这样扩展新函数只需要加一行注册条目而不是改一大段switch-casetypedef double (*MathFunctionPtr)(const std::vectordouble args); struct FunctionEntry { CString name; int minArgs; int maxArgs; MathFunctionPtr funcPtr; }; static const FunctionEntry BUILTIN_FUNCTIONS[] { { _T(sin), 1, 1, MathSin }, { _T(cos), 1, 1, MathCos }, { _T(sqrt), 1, 1, MathSqrt }, { _T(max), 1, 100, MathMax }, { _T(min), 1, 100, MathMin }, // 新增函数只需在这里注册 };MathMax的实现可以写成double MathMax(const std::vectordouble args) { double result args[0]; for (size_t i 1; i args.size(); i) { if (args[i] result) result args[i]; } return result; }这种注册表方式在写嵌入式公式引擎或者给上位机软件做参数配置面板时非常实用。用户要log(a,b)、atan2(y,x)你只需要新增函数实现并在注册表里加一行。4.3 角度与弧度的全局开关三角函数使用弧度还是角度在数值计算软件里是个高频需求。我的做法是在求值引擎里设一个全局开关m_angleMode用户通过界面下拉框切换。sin这类函数在内部做一次换算double MathSin(const std::vectordouble args) { double x args[0]; if (g_angleMode ANGLE_DEGREE) { x x * 3.14159265358979323846 / 180.0; } return sin(x); }这里我不建议在解析阶段做角度换算因为同一变量可能在多个函数里被使用一旦全局切换模式解析结果就需要全部重建。放在函数内部求值时换算全局切换时只改一个标志变量所有公式都立即生效。这一点在做交互式界面时会明显体会到好处比如用户拖了一个参数滑杆然后反复切换角度/弧度界面不用重新编译公式。5. 错误处理与VC工程里的调试心得5.1 异常抛出与错误定位策略表达式解析器最容易让用户崩溃的情形就是输入了错误的公式但不知道错在哪。我的做法是全程使用自定义异常CFormulaException携带错误位置和描述信息class CFormulaException { public: CFormulaException(const CString message, int position) : m_message(message), m_position(position) {} CString m_message; int m_position; };在界面层捕获异常后可以高亮显示出错位置对应的字符。如果配合CRichEditCtrl还可以把出错位置的字符设置为红色这比弹一个MessageBox体验好太多。我在解析器客户端就是这么处理的try { ASTNode* root parser.Parse(expression); double result evaluator.Evaluate(root); delete root; // 显示 result } catch (CFormulaException ex) { // 在输入框高亮错误位置 m_edit.SetSel(ex.m_position, ex.m_position 1); AfxMessageBox(ex.m_message); }5.2 我在VC 6.0下踩过的三个具体坑写这个解析器时我用过一段时间VC 6.0这个老古董编译器有几个问题尤其值得注意第一模板库支持不完善。std::vector在VC 6.0下能编译但如果你把std::vectorASTNode*作为成员变量然后在析构函数里写for(auto p : nodes) delete p;VC 6.0的STL对auto支持不完全。稳妥做法是全部用下标遍历或者干脆用CArrayASTNode*, ASTNode*。第二Debug版与Release版的浮点行为不一致。这主要体现在VC 6.0默认的浮点运算精度控制是/Op精确模式还是/fp:precise的问题。遇到pow(-8, 1.0/3.0)这类计算Debug下可能返回-2Release下却返回NaN。这是因为幂运算内部使用了exp(log(x))路径负数取对数自然出错。我的解决方案对整数次幂做特判如果指数是整数直接用循环乘法。第三Unicode与多字节字符集下CString的隐式转换差异。在Unicode工程里CString转const char*必须用CW2A宏直接用(LPCTSTR)转出来的地址可能是乱码。处理不当会导致词法分析器拿到错误的字符流。我建议如果做跨平台或者长期维护干脆在解析器内部全部使用std::wstring只在界面层使用CString减少互相转换的次数。5.3 常见错误场景与排错指南错误场景可能原因排查方式输入23被接受一元加号处理过于宽松检查unary层是否允许连续一元运算符必要时限制只允许一元负号输入sin(2)输出错误角度/弧度模式未统一确认全局m_angleMode是否在设置界面时同步到引擎输入2^(1/2)结果报错VC 6.0浮点库对负底数幂支持差对非整数指数增加底数为负时的虚数结果判断输入x5;2*x不支持缺少语句分隔符支持在表达式层面增加分号与赋值语句解析输入超长表达式导致栈溢出递归过深限制输入长度或改用显式栈的迭代解析6. 扩展应用把解析器封装成DLL供其他模块复用解析器本身做成静态库或者直接编译进exe都行但考虑到实际项目中公式解析器可能被多个模块共用我更推荐把它封装成一个MFC扩展DLL导出核心类接口。这么做的好处是界面模块、报表模块、数据采集模块都可以引用同一个解析引擎公式解析逻辑只有一份不会出现两个模块各自实现一份导致行为不一致的问题。我遇到的一个真实需求是现场设备参数上报后需要根据几十条预设公式批量计算质量指标。这些公式由工艺员在配置界面自由修改公式里用到设备ID对应的变量比如#TEMP_01、#PRESS_05。我在DLL里实现了一个CFormulaEngine类对外暴露三个方法class AFX_EXT_CLASS CFormulaEngine { public: bool RegisterVariable(const CString name, double value); bool ParseFormula(const CString expr, int errorPos, CString errorMsg); double Calculate(); };RegisterVariable在每次计算前批量推送最新变量值。ParseFormula把表达式编译成内部AST返回错误位置。Calculate执行求值。这里有个值得参考的设计公式编译和求值分离。工艺员在界面上修改公式后系统立即调用ParseFormula做语法检查有错当场提示。等到真正的数据到达只需要反复调用Calculate解析过程零开销。对于一秒内要算几百条公式的场景这种性能优势非常明显。6.1 导出类需要注意的接口兼容性在VC里写MFC扩展DLL导出类必须在类声明前加AFX_EXT_CLASS。如果你在4.2节中使用std::vectordouble作为函数参数类型要注意DLL与调用方必须是同一个CRT版本否则跨模块传递STL容器会崩溃。我的做法是DLL导出接口全部使用C内置类型或CString内部再转成std::vector。虽然多了一次拷贝但换来了编译器和运行库的兼容性在有两三个老工程同时引用的环境里值得。6.2 与外部系统集成的实际案例参数化报表工具我之前在做一个参数化报表工具时把公式解析器接进了报表引擎。报表模板里允许用户写类似KPI_A(本月营收)/KPI_B(去年营收)*100-100这样的表达式KPI_A和KPI_B不是内置函数而是由报表引擎预注册的指标函数。实现思路是在BUILTIN_FUNCTIONS之外增加一个动态注册入口void CFormulaEngine::RegisterFunction(const CString name, int minArgs, int maxArgs, MathFunctionPtr funcPtr);报表引擎启动时扫描KPI配置表把所有指标名动态注册成函数。解析器层面完全不用改动函数调用的解析和求值逻辑天然支持这种扩展函数模式。这比我一开始设计的把所有指标名当变量、在求值前做字符串替换的方案要干净得多也彻底避免了变量名冲突问题。7. 实测性能与优化空间最后说一下性能。纯解析部分一条20个字符左右的公式在普通配置的Windows机器上从词法分析到AST构建大约耗时几十微秒。求值阶段由于是AST直接遍历每条公式的求值时间可以低至几微秒。如果要计算上万条公式瓶颈反而会出现在数据源IO上而不是解析器本身。如果确实有极致性能需求可以考虑两个优化方向AST节点对象池避免高频解析时反复new/delete节点导致的内存碎片。我在解析器里用一个std::vectorASTNode* m_nodePool统一分配解析完成后一次性释放可以把分配开销降低30%左右。直接生成字节码把AST编译成一段简单的栈式字节码求值时不再需要递归遍历树结构。这种方式对同一表达式反复求值的场景尤其有效但代码复杂度明显上升。我个人只有在一个实时性要求较高的仿真工具里用到了字节码方案其余场景AST方案完全够用。不过说实话绝大多数项目中用户手输公式的频率远没有高到需要字节码优化AST求值已经足够。8. 写在最后这套解析器还能往哪里延伸我在实际使用中最大的体会是一旦拥有了可靠的词法分析、语法分析、AST求值这套基础能力公式解析器的很多变体就变得很简单了多行公式支持在表达式层增加分号分隔支持a1; b2; ab这种脚本式写法需要增加一个语句列表概念AST里每个语句对应一个子节点。单位换算在词法分析阶段识别mm、cm、kg等后缀换算统一到SI单位后再参与运算很适合机械设计或自动化行业的参数计算工具。公式反向求根比如用户想知道当结果等于500时x是多少这需要先构建AST再使用牛顿迭代法或二分法在变量域上搜索。这类功能我后来真的做出来了核心就是复用AST的求值接口不断修改变量值反复调用Evaluate直到结果收敛。没有一套干净的AST结构这种反向功能几乎无法实现。所以我说不要小看这个数学公式解析器源码它本质上是一个微型编译器的前端加后端。你把这个工程吃透再去接触JSON解析器、模板引擎、甚至SQL解析器都会觉得很多概念似曾相识。这种举一反三的能力比单纯跑通源码、拿到一个能算加减乘除的demo要值钱得多。本文还有配套的精品资源点击获取