、左递归解析与两阶段 SLL/LL 性能优化)
ANTLR v4 设计哲学与实战 FAQ自适应 LL(*)、左递归解析与两阶段 SLL/LL 性能优化【免费下载链接】antlr4ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.项目地址: https://gitcode.com/gh_mirrors/an/antlr4本篇技术指南围绕 ANTLR v4代号 honey badger的核心设计理念与高频使用问题展开内容以 doc/faq/general.md 为主线并结合仓库内运行时与工具源码进行验证。读完本文你将掌握v4 为何能接受任何你写的语法、直接左递归为何被允许、解析树与监听器/访问器为何取代了手工 AST 与树语法以及表达式解析器变慢时如何通过 SLL/LL 两阶段解析恢复性能。为什么需要 ANTLR v4从 v3 的困境到 honey badgerANTLR v4 之所以被称为 honey badger蜜獾版本取自 YouTube 上那段无畏的 The Crazy Nastyass Honey Badger 视频——寓意 v4 对输入语法毫不在意、来者不拒。作者重写 ANTLR 的原因有三v3 内部已经变得很混乱并且依赖用 ANTLR v2 编写的语法。v2 的开源许可证不清晰导致 Eclipse 等项目因这一依赖而无法集成 v3。后来 Sam Harwell 把所有 v2 语法转换成了 v3使 v3 实现自举凭借 v3 干净的 BSD 许可证Eclipse 于 2011 年夏批准其纳入项目。作者想实验一种新的 LL(*) 变体把全部文法分析工作推迟到运行时即自适应 LL(*)adaptive LL(*)。解析器像 Java JIT 编译器一样预热运行越久速度越快。v4 是作者 25 年解析器与解析器生成器研究的结晶。自适应算法远比 v3 的静态 LL(*) 文法分析更强大v4 接受任何你给的语法唯一例外是间接左递归即 x 调用 y、y 又调用 x 的情形。自适应 LL(*)v4 的核心引擎v4 最令人兴奋的改进就是自适应解析策略它允许我们书写任何想要的语法。这在生产力上是巨大的提升因为几乎每个语法里都会出现的、更自然的表达式规则如今可以直接书写。从源码看预测模式在 runtime/Java/src/org/antlr/v4/runtime/atn/PredictionMode.java 中定义为枚举SLL、LL与LL_EXACT_AMBIG_DETECTION其 Javadoc 明确指出SLL忽略当前解析器上下文做预测是最快的模式比 ANTLR 3 的预测模式更强大但某些语法与输入组合可能出现语法错误LL允许使用当前解析器上下文解决 SLL 冲突是保证所有语法正确输入得到正确解析结果的最快模式LL_EXACT_AMBIG_DETECTION额外精确计算每个歧义决策的完整歧义候选集合适合语法开发期诊断歧义因开销大不建议生产使用。这与 v3 时代的静态分析有本质区别v3 的静态分析经常搞不明白为什么不接受用户的语法而 honey badger 直接把分析推迟到运行时绝大多数情况下不会再因为语法分析不出结果而报错。直接左递归支持写出 yacc 般自然的语法过去只有自底向上的解析器生成器如 yacc能写出如下自然的文法e : e * e | e e | INT ;ANTLR v4 如今也接受这种语法并在内部悄悄将其转换为非左递归版本。转换结果会引入带优先级参数的规则与语义谓词见 doc/left-recursion.md 中的示例expr[int pr] : id ( {4 $pr}? * expr[5] | {3 $pr}? expr[4] | {2 $pr}? ( expr[0] ) )* ;谓词通过比较当前运算符与上一运算符的优先级来消解歧义expr[pr]的展开只能匹配优先级不低于pr的子表达式。在仓库中这一转换由 tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java 完成其类注释写明移除左递归规则引用、为递归规则引用添加优先级参数、重写规则以构建 ATNRemove left-recursive rule refs, add precedence args to recursive rule refs. Rewrite rule so we can create ATN.并直接修改语法 AST。右结合运算符通过替代分支上的assocright选项指定e : e * e | e e |assocright e ? e : e |assocright e e | INT ;注意 4.0/4.1 中该选项曾位于 token 上4.2 起改为按替代分支设置旧语法若使用右结合三元运算符需要更新为assocright放在替代分支上。自动解析树与监听器/访问器动作与语法分离v4 的另一大变化是设计目标从性能转向易用性ANTLR 自动为你构建解析树并生成监听器listener与访问器visitor。这意味着可以写出不依赖内嵌动作的语法——内嵌动作裸 Java 代码等会把语法锁死在单一语言上把动作全部移出语法、放进外部 visitor 后同一份语法可以为任何存在 ANTLR target 的语言生成代码。doc/listeners.md 给出了解析树的直观流程解析树内部节点是短语名如stat叶节点始终是输入 token包含全部输入与解析器对符号分组的完整知识且默认自动构建除非调用parser.setBuildParseTree(false)关闭见 runtime/Java/src/org/antlr/v4/runtime/Parser.java。ANTLR 为每条语法规则生成一对enterXxx/exitXxx方法例如从 Java.g4 生成public interface JavaListener extends ParseTreeListenerToken { void enterClassDeclaration(JavaParser.ClassDeclarationContext ctx); void exitClassDeclaration(JavaParser.ClassDeclarationContext ctx); void enterMethodDeclaration(JavaParser.MethodDeclarationContext ctx); ... }配套生成带空实现的JavaBaseListener你只需继承并覆写感兴趣的方法然后用ParseTreeWalker.DEFAULT.walk(listener, tree)遍历JavaLexer lexer new JavaLexer(input); CommonTokenStream tokens new CommonTokenStream(lexer); JavaParser parser new JavaParser(tokens); JavaParser.CompilationUnitContext tree parser.compilationUnit(); MyListener extractor new MyListener(parser); ParseTreeWalker.DEFAULT.walk(extractor, tree);监听器与访问器的最大差异在于监听器方法由 ANTLR 提供的 walker独立调用而访问器方法必须显式visit子节点忘记调用子节点 visit 会导致相应子树不被访问。此外监听器也可通过parser.addParseListener(listener)在解析过程中即时触发见 Parser.java但解析期间不宜做复杂工作因为解析器靠抛异常处理语法错误若你的监听器代码抛出异常会破坏解析。Parser内部通过triggerExitRuleEvent()以 try/catch 捕获用户监听器异常并置listenerExceptionOccurred true后整体退出。ANTLR 3 与 4 的主要区别维度ANTLR 3ANTLR 4语法接受度静态分析常无法为某些语法生成解析器接受任何语法除间接左递归无需语法谓词与回溯左递归不支持支持直接左递归自动转换为非左递归形式树构建手工/显式 AST 构建是选项自动构建解析树AST 构建不再是选项代码生成倾向内嵌动作自动生成监听器/访问器鼓励动作外置树语法存在已移除用监听器/访问器替代语法谓词/回溯支持该语法不再支持该语法使用会得到警告语义谓词在 parser 与 lexer 规则中仍然允许作为动作存在为效率起见应尽量放在词法规则的右边缘。对于编译器场景需要 AST 而非解析树的问题官方建议是生成 LLVM 风格 SSA 形式或用监听器/访问器从解析树构造 AST参见 doc/faq/parse-trees.md。与其他解析工具相比的定位可调试性大多数解析器生成器不产出能载入调试器单步执行的代码这使自底向上与强力的 GLR 解析器生成器被普通开发者排除在外。ANTLR 生成的代码可读、可单步调试。LL(k) 类工具需要把语法扭成工具较弱策略如 LL(k)所要求的形式。PEG 工具本质上没有错误恢复能力因为它们必须等解析完整个输入才能报告错误。从应用场景看几乎没人用解析器生成器构建商业编译器人们用 ANTLR 解决日常工作——从配置文件到小型脚本语言。编译器开发者更关心解析速度、错误报告与恢复倾向手工递归下降解析器以精确控制如处理 C 中T(i)这类上下文相关结构。文档同时指出预热后 ANTLR v4 解析整个 JDK java 库仅需约 1 秒已足以与手写解析器竞争此为文档所述数据。设计决策易用性优先于性能v4 的核心决策是易用性优先性能留待以后优化简单性优先于复杂性。为此删除了显式/手工 AST 构建设施与树语法设施。作者 20 年来一直在推动树语法方向最终认定那是错误更好的做法是让解析器生成器自动建树然后用纯代码做任意树遍历——人们对 visitor 模式非常熟悉。性能实战为什么我的表达式解析器慢——两阶段 SLL/LL 解析若你的表达式解析器很慢务必使用两阶段解析第一阶段用 SLL 模式最快失败回退到 LL 模式。这正是 PredictionMode.java 中两种模式设计的意义所在——SLL 忽略解析器上下文因而更快但更弱LL 使用上下文因而更强但更慢。完整示例CharStream input CharStreams.fromPath(Paths.get(args[0])); ExprLexer lexer new ExprLexer(input); CommonTokenStream tokens new CommonTokenStream(lexer); ExprParser parser new ExprParser(tokens); parser.getInterpreter().setPredictionMode(PredictionMode.SLL); try { parser.stat(); // STAGE 1 } catch (Exception ex) { tokens.reset(); // rewind input stream parser.reset(); parser.getInterpreter().setPredictionMode(PredictionMode.LL); parser.stat(); // STAGE 2 // if we parse ok, its LL not SLL }要点先用setPredictionMode(PredictionMode.SLL)尝试快路径捕获异常后重置 token 流tokens.reset()与解析器parser.reset()切换为PredictionMode.LL重新解析若第二阶段成功说明该输入需要 LL 能力若仍失败则是真正的语法错误。LL_EXACT_AMBIG_DETECTION仅建议在语法开发期诊断歧义时使用。另外若确认语法不需要 LL可全程保持 SLL 以获得最大吞吐两阶段策略则兼顾了绝大多数情况下的速度与最坏情况下的正确性。延伸阅读doc/faq/parse-trees.md如何获取解析树子树的输入文本、编译器场景 AST 的替代方案、XPath / 树模式匹配 / 监听器访问器的选型。doc/listeners.md监听器接口生成、解析树遍历与解析期监听详解。doc/tree-matching.md解析树模式匹配与 XPath。doc/left-recursion.md左递归消除的正式规则、二元/前缀/后缀表达式分类与assocright用法。tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java左递归规则重写的工具端实现。【免费下载链接】antlr4ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.项目地址: https://gitcode.com/gh_mirrors/an/antlr4创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
ANTLR v4 设计哲学与实战 FAQ：自适应 LL(\*)、左递归解析与两阶段 SLL/LL 性能优化
ANTLR v4 设计哲学与实战 FAQ自适应 LL(*)、左递归解析与两阶段 SLL/LL 性能优化【免费下载链接】antlr4ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.项目地址: https://gitcode.com/gh_mirrors/an/antlr4本篇技术指南围绕 ANTLR v4代号 honey badger的核心设计理念与高频使用问题展开内容以 doc/faq/general.md 为主线并结合仓库内运行时与工具源码进行验证。读完本文你将掌握v4 为何能接受任何你写的语法、直接左递归为何被允许、解析树与监听器/访问器为何取代了手工 AST 与树语法以及表达式解析器变慢时如何通过 SLL/LL 两阶段解析恢复性能。为什么需要 ANTLR v4从 v3 的困境到 honey badgerANTLR v4 之所以被称为 honey badger蜜獾版本取自 YouTube 上那段无畏的 The Crazy Nastyass Honey Badger 视频——寓意 v4 对输入语法毫不在意、来者不拒。作者重写 ANTLR 的原因有三v3 内部已经变得很混乱并且依赖用 ANTLR v2 编写的语法。v2 的开源许可证不清晰导致 Eclipse 等项目因这一依赖而无法集成 v3。后来 Sam Harwell 把所有 v2 语法转换成了 v3使 v3 实现自举凭借 v3 干净的 BSD 许可证Eclipse 于 2011 年夏批准其纳入项目。作者想实验一种新的 LL(*) 变体把全部文法分析工作推迟到运行时即自适应 LL(*)adaptive LL(*)。解析器像 Java JIT 编译器一样预热运行越久速度越快。v4 是作者 25 年解析器与解析器生成器研究的结晶。自适应算法远比 v3 的静态 LL(*) 文法分析更强大v4 接受任何你给的语法唯一例外是间接左递归即 x 调用 y、y 又调用 x 的情形。自适应 LL(*)v4 的核心引擎v4 最令人兴奋的改进就是自适应解析策略它允许我们书写任何想要的语法。这在生产力上是巨大的提升因为几乎每个语法里都会出现的、更自然的表达式规则如今可以直接书写。从源码看预测模式在 runtime/Java/src/org/antlr/v4/runtime/atn/PredictionMode.java 中定义为枚举SLL、LL与LL_EXACT_AMBIG_DETECTION其 Javadoc 明确指出SLL忽略当前解析器上下文做预测是最快的模式比 ANTLR 3 的预测模式更强大但某些语法与输入组合可能出现语法错误LL允许使用当前解析器上下文解决 SLL 冲突是保证所有语法正确输入得到正确解析结果的最快模式LL_EXACT_AMBIG_DETECTION额外精确计算每个歧义决策的完整歧义候选集合适合语法开发期诊断歧义因开销大不建议生产使用。这与 v3 时代的静态分析有本质区别v3 的静态分析经常搞不明白为什么不接受用户的语法而 honey badger 直接把分析推迟到运行时绝大多数情况下不会再因为语法分析不出结果而报错。直接左递归支持写出 yacc 般自然的语法过去只有自底向上的解析器生成器如 yacc能写出如下自然的文法e : e * e | e e | INT ;ANTLR v4 如今也接受这种语法并在内部悄悄将其转换为非左递归版本。转换结果会引入带优先级参数的规则与语义谓词见 doc/left-recursion.md 中的示例expr[int pr] : id ( {4 $pr}? * expr[5] | {3 $pr}? expr[4] | {2 $pr}? ( expr[0] ) )* ;谓词通过比较当前运算符与上一运算符的优先级来消解歧义expr[pr]的展开只能匹配优先级不低于pr的子表达式。在仓库中这一转换由 tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java 完成其类注释写明移除左递归规则引用、为递归规则引用添加优先级参数、重写规则以构建 ATNRemove left-recursive rule refs, add precedence args to recursive rule refs. Rewrite rule so we can create ATN.并直接修改语法 AST。右结合运算符通过替代分支上的assocright选项指定e : e * e | e e |assocright e ? e : e |assocright e e | INT ;注意 4.0/4.1 中该选项曾位于 token 上4.2 起改为按替代分支设置旧语法若使用右结合三元运算符需要更新为assocright放在替代分支上。自动解析树与监听器/访问器动作与语法分离v4 的另一大变化是设计目标从性能转向易用性ANTLR 自动为你构建解析树并生成监听器listener与访问器visitor。这意味着可以写出不依赖内嵌动作的语法——内嵌动作裸 Java 代码等会把语法锁死在单一语言上把动作全部移出语法、放进外部 visitor 后同一份语法可以为任何存在 ANTLR target 的语言生成代码。doc/listeners.md 给出了解析树的直观流程解析树内部节点是短语名如stat叶节点始终是输入 token包含全部输入与解析器对符号分组的完整知识且默认自动构建除非调用parser.setBuildParseTree(false)关闭见 runtime/Java/src/org/antlr/v4/runtime/Parser.java。ANTLR 为每条语法规则生成一对enterXxx/exitXxx方法例如从 Java.g4 生成public interface JavaListener extends ParseTreeListenerToken { void enterClassDeclaration(JavaParser.ClassDeclarationContext ctx); void exitClassDeclaration(JavaParser.ClassDeclarationContext ctx); void enterMethodDeclaration(JavaParser.MethodDeclarationContext ctx); ... }配套生成带空实现的JavaBaseListener你只需继承并覆写感兴趣的方法然后用ParseTreeWalker.DEFAULT.walk(listener, tree)遍历JavaLexer lexer new JavaLexer(input); CommonTokenStream tokens new CommonTokenStream(lexer); JavaParser parser new JavaParser(tokens); JavaParser.CompilationUnitContext tree parser.compilationUnit(); MyListener extractor new MyListener(parser); ParseTreeWalker.DEFAULT.walk(extractor, tree);监听器与访问器的最大差异在于监听器方法由 ANTLR 提供的 walker独立调用而访问器方法必须显式visit子节点忘记调用子节点 visit 会导致相应子树不被访问。此外监听器也可通过parser.addParseListener(listener)在解析过程中即时触发见 Parser.java但解析期间不宜做复杂工作因为解析器靠抛异常处理语法错误若你的监听器代码抛出异常会破坏解析。Parser内部通过triggerExitRuleEvent()以 try/catch 捕获用户监听器异常并置listenerExceptionOccurred true后整体退出。ANTLR 3 与 4 的主要区别维度ANTLR 3ANTLR 4语法接受度静态分析常无法为某些语法生成解析器接受任何语法除间接左递归无需语法谓词与回溯左递归不支持支持直接左递归自动转换为非左递归形式树构建手工/显式 AST 构建是选项自动构建解析树AST 构建不再是选项代码生成倾向内嵌动作自动生成监听器/访问器鼓励动作外置树语法存在已移除用监听器/访问器替代语法谓词/回溯支持该语法不再支持该语法使用会得到警告语义谓词在 parser 与 lexer 规则中仍然允许作为动作存在为效率起见应尽量放在词法规则的右边缘。对于编译器场景需要 AST 而非解析树的问题官方建议是生成 LLVM 风格 SSA 形式或用监听器/访问器从解析树构造 AST参见 doc/faq/parse-trees.md。与其他解析工具相比的定位可调试性大多数解析器生成器不产出能载入调试器单步执行的代码这使自底向上与强力的 GLR 解析器生成器被普通开发者排除在外。ANTLR 生成的代码可读、可单步调试。LL(k) 类工具需要把语法扭成工具较弱策略如 LL(k)所要求的形式。PEG 工具本质上没有错误恢复能力因为它们必须等解析完整个输入才能报告错误。从应用场景看几乎没人用解析器生成器构建商业编译器人们用 ANTLR 解决日常工作——从配置文件到小型脚本语言。编译器开发者更关心解析速度、错误报告与恢复倾向手工递归下降解析器以精确控制如处理 C 中T(i)这类上下文相关结构。文档同时指出预热后 ANTLR v4 解析整个 JDK java 库仅需约 1 秒已足以与手写解析器竞争此为文档所述数据。设计决策易用性优先于性能v4 的核心决策是易用性优先性能留待以后优化简单性优先于复杂性。为此删除了显式/手工 AST 构建设施与树语法设施。作者 20 年来一直在推动树语法方向最终认定那是错误更好的做法是让解析器生成器自动建树然后用纯代码做任意树遍历——人们对 visitor 模式非常熟悉。性能实战为什么我的表达式解析器慢——两阶段 SLL/LL 解析若你的表达式解析器很慢务必使用两阶段解析第一阶段用 SLL 模式最快失败回退到 LL 模式。这正是 PredictionMode.java 中两种模式设计的意义所在——SLL 忽略解析器上下文因而更快但更弱LL 使用上下文因而更强但更慢。完整示例CharStream input CharStreams.fromPath(Paths.get(args[0])); ExprLexer lexer new ExprLexer(input); CommonTokenStream tokens new CommonTokenStream(lexer); ExprParser parser new ExprParser(tokens); parser.getInterpreter().setPredictionMode(PredictionMode.SLL); try { parser.stat(); // STAGE 1 } catch (Exception ex) { tokens.reset(); // rewind input stream parser.reset(); parser.getInterpreter().setPredictionMode(PredictionMode.LL); parser.stat(); // STAGE 2 // if we parse ok, its LL not SLL }要点先用setPredictionMode(PredictionMode.SLL)尝试快路径捕获异常后重置 token 流tokens.reset()与解析器parser.reset()切换为PredictionMode.LL重新解析若第二阶段成功说明该输入需要 LL 能力若仍失败则是真正的语法错误。LL_EXACT_AMBIG_DETECTION仅建议在语法开发期诊断歧义时使用。另外若确认语法不需要 LL可全程保持 SLL 以获得最大吞吐两阶段策略则兼顾了绝大多数情况下的速度与最坏情况下的正确性。延伸阅读doc/faq/parse-trees.md如何获取解析树子树的输入文本、编译器场景 AST 的替代方案、XPath / 树模式匹配 / 监听器访问器的选型。doc/listeners.md监听器接口生成、解析树遍历与解析期监听详解。doc/tree-matching.md解析树模式匹配与 XPath。doc/left-recursion.md左递归消除的正式规则、二元/前缀/后缀表达式分类与assocright用法。tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java左递归规则重写的工具端实现。【免费下载链接】antlr4ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.项目地址: https://gitcode.com/gh_mirrors/an/antlr4创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
代码包深度解析与实践指南)
