多else-if子句致解析耗时增加的问题及预编译方案咨询

问题背景 #

我们的公式语法支持if-then-else结构，语法定义如下：

parse
 : block EOF
 ;

block
 : statement*
 ;

statement
 : if_statement
 | setfunctions
 | blockcomment
 | comment
 ;

if_statement
 : comment* IF condition_block (ELSE IF condition_block)* (ELSE statement_block)?
 ;

condition_block
 : expression statement_block
 ;

statement_block
 : OBRACE (block | setfunctions*) CBRACE
 ;

setfunctions
 : setsumtags
 | setavgtags
 ;

这类公式用于设置系统中标签（对象）的计算值，我们评估公式的流程为：

1. 创建词法分析器（lexer）
2. 创建解析器（parser）
3. 创建访问器（visitor）
4. 调用解析器的parse()生成解析树
5. 调用访问器的Visit方法处理解析树

现象与疑问 #

我发现else-if子句越多，步骤4（生成解析树）的耗时越长——比如含2个else-if的脚本解析速度是含4个else-if脚本的两倍，且耗时增长并非线性。

请问：

1. 该现象是否正常？我们的操作是否存在问题？
2. 这一问题影响了系统启动时间（我们有数百甚至数千个公式需要评估），若现象正常，是否可以保存/加载预编译的解析树？我们计划在脚本创建时保存预编译版本，运行时直接加载。

回答 #

1. 解析耗时随else-if数量非线性增长是否正常？ #

这种现象是正常的，但可能和解析器的语法处理逻辑以及你的操作方式有关。

从语法定义来看，if_statement中的(ELSE IF condition_block)*是迭代式重复结构，解析器处理这类结构时，每增加一个else-if，就需要多完成一轮condition_block的匹配与解析。如果每个condition_block包含复杂的表达式，解析时的递归匹配逻辑会叠加，导致耗时呈现非线性增长——比如表达式嵌套越深，每多一个else-if的额外耗时会成倍增加。

另外，如果你的操作中每次解析公式都重复创建lexer、parser实例（即步骤1-3每次都执行），这会额外放大耗时问题。实例化解析器组件本身有初始化开销，重复执行会让解析速度明显变慢，尤其是在批量处理数百上千个公式时。这属于操作上的可优化点，建议复用lexer和parser实例，而不是每次解析都重新创建。

2. 能否保存/加载预编译的解析树？ #

完全可以，这是解决批量公式解析耗时问题的成熟方案。

解析树是内存中的结构化对象，你可以通过序列化机制（比如语言自带的序列化工具、Protobuf、JSON等）将其保存到文件或数据库中。系统启动时，直接加载序列化后的解析树，跳过词法分析、解析器创建、解析树生成的步骤，直接执行访问器的Visit方法处理即可。

实施时需要注意以下几点：

• 版本兼容性：如果后续修改了语法规则，旧的序列化解析树可能无法兼容。需要为解析树添加版本标识，加载时校验版本，不兼容则触发重新解析。
• 序列化效率：优先选择二进制序列化格式（如Protobuf），比JSON等文本格式的序列化/反序列化速度更快，避免成为新的性能瓶颈。
• 安全性：如果公式来自不可信用户，加载预编译解析树时要做安全校验，防止恶意构造的序列化数据导致程序崩溃或注入风险。

此外，你还可以考虑进一步优化：将解析后的逻辑编译成字节码或动态生成可执行代码，这样运行时的处理效率会更高，但实现复杂度也会相应提升。

内容的提问来源于stack exchange，提问作者XBond