开发工具编程语言编译器【免费下载链接】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点击查看免费下载导读本文围绕 doc/left-recursion.md 展开系统讲解 ANTLR 4 如何处理文法中最自然的表达方式——左递归规则left-recursive rules。你将理解为什么算术表达式、C 语言声明符等构造可以用左递归直接书写而不会陷入上下文无关文法的二义性困境掌握 ANTLR 4 通过语义谓词 优先级参数将其重写为等价非左递归规则的底层原理并学会使用assocright控制右结合运算符如赋值、三目运算符以及了解从 4.0/4.1 迁移到 4.2 时需要注意的关联性语法变化。所有结论均可对照仓库 tool/src/org/antlr/v4/analysis/ 下的源码与 tool-testsuite/test/org/antlr/v4/test/tool/TestLeftRecursionToolIssues.java 中的测试用例验证。为什么需要左递归算术表达式的自然表达某些最常见的语言构造其最自然的表达方式就是左递归的。典型例子包括 C 语言声明符declarators和算术表达式。在传统自顶向下top-down文法中算术表达式必须按优先级拆分成多个层级term、factor、primary……写起来繁琐而左递归规格虽然通常存在二义性但写起来要容易得多。下面是一个包含左递归表达式规则的 ANTLR 4 文法示例原文示例stat: expr expr ; // e.g., xy; 或 xf(x); | expr ; // e.g., f(x); 或 f(g(x)); ; expr: expr * expr | expr expr | expr ( expr ) // f(x) | id ;在纯粹的上下文无关文法context free grammar中这样的规则是二义的因为对于输入12*3既可以解释为先做加法也可以解释为先做乘法——两种解释都符合文法结构但语义完全不同。ANTLR 4 的贡献在于它能把这条规则自动改写成非左递归且无二义的等价形式改写所依赖的核心工具是语义谓词semantic predicates。重写原理语义谓词 优先级参数ANTLR 4 将上述expr规则重写为下面这种带优先级参数的等价形式原文示例expr[int pr] : id ( {4 $pr}? * expr[5] | {3 $pr}? expr[4] | {2 $pr}? ( expr[0] ) )* ;谓词的作用是解决二义性它比较当前运算符的优先级与前一个运算符的优先级即递归调用时传入的pr。一条expr[pr]展开只能匹配那些优先级达到或超过pr的子表达式。以12*3为例最外层以优先级 0 调用expr[0]读取1后进入循环遇到其优先级 3 ≥ 0谓词通过于是以expr[4]递归匹配右侧子表达式2*3在内层遇到*其优先级 4 ≥ 4谓词通过继续递归expr[5]匹配3返回时2*3作为一个整体成为的右操作数乘法先于加法执行。从源码看谓词和参数化规则的生成由 tool/src/org/antlr/v4/analysis/LeftRecursiveRuleAnalyzer.java 完成其中precedence(int alt)L403-L405按numAlts - alt 1计算每个算符备选的优先级nextPrecedence(int alt)L407-L412则在左结合时返回p 1、右结合时返回p这正是重写后expr[4]、expr[5]这些参数取值的来源。生成规则的文本模板位于 tool/resources/org/antlr/v4/tool/templates/LeftRecursiveRules.stgrecRule模板把基础备选primary alts作为一条规则的主体把全部运算符备选放进一个( ... )*循环recRuleAlt模板则为每个运算符备选生成{pred}?\popPrec\ alt.altText这样的谓词 优先级选项形式。可见文档中的手写重写示例与工具实际产出的结构完全一致。形式化规则ANTLR 4.2 起的三类备选自 4.2 版本起ANTLR 官方的左递归消除规则相比 4.0/4.1 做了简化其分类依据是递归调用在备选中的位置详见 ALL(*) 技术报告可在仓库外检索该报告二元表达式Binary备选中递归调用既作为第一个元素、又作为最后一个元素出现。例如expr * expr。后缀表达式Suffix递归调用作为备选的第一个元素但不是最后一个元素。例如expr ( expr )、expr 、数组下标expr [ expr ]。前缀表达式Prefix递归调用作为备选的最后一个元素但不是第一个元素。例如- expr。另外并不存在真正的三元ternary表达式——它们本质上是二元的变体这一点下文结合assocright的右结合示例说明。源码中这三类备选被分别收集LeftRecursiveRuleAnalyzer用binaryAlts、ternaryAlts、suffixAlts三个有序映射与prefixAndOtherAlts列表存储它们L45-L48其分类由语法树遍历器 tool/src/org/antlr/v4/parse/LeftRecursiveRuleWalker.g 驱动binaryAlt、prefixAlt、suffixAlt、otherAlt回调分别处理各类备选。能处理的与不能处理的重写并非对所有左递归都适用。ANTLR 4 只处理符合上述模式的直接左递归规则。以下几种情况会直接报错错误码定义见 tool/src/org/antlr/v4/tool/ErrorType.java左递归规则没有非左递归的基础备选——错误 147NO_NON_LR_ALTSleft recursive rule a must contain an alternative which is not left recursive左递归备选之后可以跟空串如a : a ID? | ID ;——错误 148EPSILON_LR_FOLLOWleft recursive rule a contains a left recursive alternative which can be followed by the empty string左递归形式不符合 ANTLR 能处理的模式例如对递归调用传参a[3] y、孤立递归引用a : a | b ;——错误 169NONCONFORMING_LR_RULErule a is left recursive but doesnt conform to a pattern ANTLR can handle间接左递归规则互相调用形成的环——错误 119LEFT_RECURSION_CYCLES由 tool/src/org/antlr/v4/analysis/LeftRecursionDetector.java 在 ATN 上检测递归环后报告。上述错误信息与触发场景均可在 tool-testsuite/test/org/antlr/v4/test/tool/TestLeftRecursionToolIssues.java 的多个测试用例中复现如testCheckForNonLeftRecursiveRule、testCheckForLeftRecursiveEmptyFollow、testLeftRecursiveRuleRefWithArg、testIsolatedLeftRecursiveRuleRef测试同时验证了非左递归备选中允许对其它规则传参testArgOnPrimaryRuleInLeftRecursiveRule等合法边界情形。关联性与assocright的用法演变4.2 之前 vs 4.2关联性选项移到备选上在 ANTLR 4.0/4.1 中右关联性说明符right associativity specifier是挂在单个 token上的。从 4.2 起由于关联性本质上作用于整个备选选项改为写在**备选alternative**上。因此如果你的 4.0/4.1 文法中使用了右结合的三目运算符就必须更新文法在相应备选上加上assocrighte : e * e | e e |assocright e ? e : e |assocright e e | INT ;这里e ? e : e之所以叫二元表达式的变体而非真正的三元表达式正是因为重写后它遵循二元备选的处理路径——ternaryAlts与binaryAlts在生成最终规则时被合并处理见 LeftRecursiveRuleTransformer.java 中recOpAlts.putAll(binaryAlts); recOpAlts.putAll(ternaryAlts);的合并逻辑。为了平滑迁移assocright仍然允许写在 token 引用上但会被忽略。这一行为在 tool-testsuite/test/org/antlr/v4/test/tool/TestToolSyntaxErrors.java 的语法错误测试中有直接体现x assocright x产生警告 157token 上的关联性选项被忽略而|assocright x * x才是合法写法。源码中的关联性处理细节关联性解析与检查位于LeftRecursiveRuleAnalyzer.setAltAssocL99-L122它读取备选的assoc选项只接受left或right两个值其它取值报非法选项错误若同一个备选上出现矛盾部分算符标 left、部分标 right则报内部错误all operators of alt X of left-recursive rule must have same associativity。结合上文nextPrecedence的实现可以理解其语义左结合默认nextPrecedence p 1即右侧递归调用的优先级比当前运算符高一级保证a - b - c解析为(a - b) - c右结合assocrightnextPrecedence p右侧递归调用沿用当前优先级保证a b c解析为a (b c)。测试中的右结合示例仓库测试文法 tool-testsuite/test/org/antlr/v4/test/tool/TestATNConstruction.javaL592-L595给出了一个全部备选都标为右结合的完整示例e :assocright e * e |assocright e e |assocright e ? e : e |assocright e e而 tool-testsuite/test/org/antlr/v4/test/tool/JavaLR.g4 中也能看到真实语言文法里assocright的典型用法如 Java 的赋值表达式备选。这些例子说明需要右结合的典型场景是赋值、三目条件? :等少数运算符。重写的完整流程从文法 AST 到 ATN将文档中的原理串起来ANTLR 4 处理左递归规则的完整流水线如下主要实现在 tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java 的translateLeftRecursiveRules检测遍历所有规则对每条规则调用LeftRecursiveRuleAnalyzer.hasImmediateRecursiveRuleRefs判断是否存在直接递归引用L263-L283分析分类用LeftRecursiveRuleWalker遍历规则树按上文三类备选模式收集信息并记录删除递归调用后需要保留的标签生成人工规则getArtificialOpPrecRule()利用 StringTemplate 模板渲染出带int _p参数、含语义谓词的重写规则文本L210-L241然后重新解析该文本生成新规则 ASTparseArtificialRule回填把所有对左递归规则的引用补上[0]参数代表顶层调用优先级为 0并在Rule对象上记录recPrimaryAlts/recOpAlts等元数据供代码生成器使用后续流水线重写后的规则进入正常的块归约、参数化循环展开、语义检查针对转换后规则会跳过已处理过的 assoc 元素选项检查和 ATN 构建流程。此外tool/src/org/antlr/v4/analysis/LeftRecursionDetector.java 在 ATN 上执行独立的环检测它从每个规则的起始状态出发跟踪RuleTransition边凡是遇到当前正在追踪的规则rulesVisitedPerRuleCheck命中即记入递归环集合最后通过leftRecursionCycles报告互相左递归的规则组L41-L55。代码生成侧tool/src/org/antlr/v4/codegen/model/LeftRecursiveRuleFunction.java 与 tool/src/org/antlr/v4/codegen/OutputModelController.java 负责把重写后的规则映射到各目标语言Java、C#、Python 等的具体函数LeftRecursiveRuleAltInfotool/src/org/antlr/v4/analysis/LeftRecursiveRuleAltInfo.java在重写前后的 AST 之间建立一一对应保证语义动作action中的标签引用仍然指向正确元素。实践建议与迁移要点直接写左递归不必手动分层只要备选符合二元 / 后缀 / 前缀模式且存在至少一个非递归基础备选ANTLR 4 就能自动消除左递归解析树中仍保留完整结构便于监听器listener或访问器visitor处理。默认左结合右结合需显式声明算术四则运算默认左结合即可只有赋值、三目等运算符需要在备选上写assocright。多个运算符共用一个备选时它们的结合性必须一致否则工具报错。迁移 4.0/4.1 文法时检查三目与赋值把原来写在 token 上的assocright移到备选开头写在 token 上的写法虽然仍被接受但会被忽略伴随警告 157不要依赖其效果。警惕不支持的模式对递归调用传参、孤立递归引用、可空后缀、间接互相左递归都会触发编译错误应按错误信息提示改写文法例如把带参递归调用改为在基础备选中对其它规则传参。查看错误与验证编译文法时注意错误 119/147/148/169见 tool/src/org/antlr/v4/tool/ErrorType.java并可在 tool-testsuite/test/org/antlr/v4/test/tool/TestLeftRecursionToolIssues.java 与 tool-testsuite/test/org/antlr/v4/test/tool/TestATNConstruction.java 中对照合法/非法用例理解边界。左递归规则是 ANTLR 4 相较传统递归下降解析器生成器的标志性能力之一它以语义谓词为桥把人类最容易书写的文法形式与机器最容易解析的非左递归形式统一起来让表达式、声明符等语言的骨架部分可以直白地写进文法而把优先级与结合性的精细控制留给assocright和默认的左结合规则去自动完成。赞分享开发工具编程语言编译器【免费下载链接】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点击查看免费下载相关推荐react-input-range事件处理详解onChange、onChangeStart与onChangeComplete应用react input range事件处理详解onChange、onChangeStart与onChangeComplete应用 react input ra如何利用fswatch递归监控机制实现大规模文件系统性能优化完整指南如何利用fswatch递归监控机制实现大规模文件系统性能优化完整指南 fswatch是一款跨平台的文件变更监控工具支持Apple OS X文件系统事件、 B开发工具CLIFlux数据解读如何通过骑行数据优化你的训练效果Flux数据解读如何通过骑行数据优化你的训练效果 你是否曾经在室内骑行训练后看着一堆数据却不知如何分析Flux室内骑行应用为你提供了全面的数据记录和分析功创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
