如何在ANTLR中递归检查给定上下文的子上下文并执行规则校验

我正在处理一个规模较大的语法，其CFG存在循环但无无限递归。需要实现检查逻辑：若某个特定上下文出现，它的所有子上下文中不能包含指定目标上下文，否则抛出错误。

示例语法 #

Sentence
:   Nouns 'AND' Sentence
|   Pronouns 'AND' Sentence
|   'WITH APPLESAUCE'
;

Nouns  
:   Names
|   Places
|   Animals
|   Things
;

Names
:   word 'AND' Sentence
;
    
word
:   (A-Z) (a-z)* // 任意单词
;

核心需求 #

若某个Sentence包含Names，则该Names规则对应的Sentence子节点中，不能再包含其他Names：

• 无效输入：word 'AND' Names 'AND' 'WITH APPLESAUCE'（Names嵌套了Names）
• 有效输入：word 'AND' Places 'AND' 'WITH APPLESAUCE'（Names的子Sentence中是Places，符合规则）

解决方案：遍历ANTLR解析树实现检查 #

ANTLR生成解析树后，可通过遍历解析树的方式实现嵌套检查，以下是具体步骤和代码示例：

1. 利用解析树监听器/访问器 #

通过自定义ANTLR监听器，在进入Names节点时，检查其内部Sentence子节点的所有后代是否包含Names。

2. Java代码示例 #

// 自定义监听器，继承语法自动生成的BaseListener
public class NestedNamesValidationListener extends YourGrammarBaseListener {

    @Override
    public void enterNames(YourGrammarParser.NamesContext ctx) {
        // 获取Names规则内的Sentence子节点
        YourGrammarParser.SentenceContext nestedSentence = ctx.Sentence();
        if (nestedSentence != null && hasNestedNames(nestedSentence)) {
            throw new IllegalArgumentException(
                String.format("非法嵌套：位置%d-%d的Names内部不能包含其他Names", 
                    ctx.getStart().getStartIndex(), ctx.getStop().getStopIndex())
            );
        }
    }

    // 递归检查节点的所有后代是否存在NamesContext
    private boolean hasNestedNames(ParseTree node) {
        for (int i = 0; i < node.getChildCount(); i++) {
            ParseTree child = node.getChild(i);
            if (child instanceof YourGrammarParser.NamesContext) {
                return true;
            }
            if (hasNestedNames(child)) {
                return true;
            }
        }
        return false;
    }
}

3. 使用监听器验证解析树 #

解析完成后，用监听器遍历解析树执行检查：

// 假设已完成词法分析，得到CommonTokenStream tokens
YourGrammarParser parser = new YourGrammarParser(tokens);
ParseTree parseTree = parser.sentence();

NestedNamesValidationListener validator = new NestedNamesValidationListener();
ParseTreeWalker.DEFAULT.walk(validator, parseTree);

其他语言实现思路 #

如果使用Python、C#等其他ANTLR支持的语言，逻辑一致：

• 找到所有Names对应的上下文节点
• 对每个Names节点，提取其内部的Sentence子节点
• 递归遍历该Sentence节点的所有后代，判断是否存在Names节点，存在则抛出错误

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