Antlr4 相邻令牌优先级

Question

我运行在构建复杂语法时遇到了问题。下面是一个宠物语法来说明它：

grammar test;

start: (r1 | r2 | .)*
r1: A B
r2: B C

// A B C are tokens

当出现以下输入时：

ABC

解析树如下所示：

start
|   \
r1   C
| \
A  B

但我真正想要的是它看起来像这样：

start
|   \
A   r2
    | \
    B  C

我已经尝试重新排序规则并添加 <assoc=right>，但除了删除规则 r1 之外似乎没有任何效果，这是不正确的，因为我期望 AB 和 BC 是有效的输入。我错过了什么？

编辑

上面的问题描述似乎过于简单化了实际问题，所以我会提供更多细节：

r3: rA r4          // prefers rA(classB classC) over (rA classB)classC
r4: classB? classC // also used elsewhere other than r3

rA: // rules to build A subtree, ends with classB? in 'some' cases
classB: B1 | B2 | ... | Bm
classC: C1 | C2 | ... | Cn

我发现以下 'kind of' 有效：

r3: rA Bx classC | ...

但以下不是：

r3: <assoc=right> rA r4 | ... // still builds (rA classB)classC

我想知道是否有一种方法可以在能够利用 r4 及其相关代码的同时正确构建树（并且避免为 [=22= 的所有实例添加另外 m 行） ])?

PS。 rA 很昂贵，因此像上面那样在 r3 中扩展 B 代币会使性能下降。

Answer 1

我怀疑您会发现您确实在与递归下降解析器的工作方式作斗争。

当解析器尝试匹配 rA 时，它将尝试匹配尽可能多的输入标记，并且不会远程知道父后续规则（即当前规则的“下一个兄弟”）。（assoc = right 不会让规则查找它的父级和下一个兄弟级，它旨在为求幂之类的事情构建正确的解析树。）

因此，您需要使用诸如语义谓词之类的东西来“阻止”错误的备选方案进行匹配，方法是向前看得足够远以确定它是否应该真正匹配 r4（例如） .

对于您的示例，以下语法将输入“AB!C2”解析为

grammar test
    ;
start: r3 EOF;
r3
    : rA r4 // prefers rA(classB classC) over (rA classB)classC
    ;
r4
    : classB? classC // also used elsewhere other than r3
    ;
rA // rules to build A subtree, ends with classB? in 'some' cases
    : A C1
    | A
    | {!( //
        _input.get(_input.index()).getType() == C1 || //
         _input.get(_input.index()).getType() == C2) //
      }? A classB?
    ;
classB: B1 | B2;
classC: C1 | C2;

A:     'A';
B1:    'B1';
B2:    'B2';
C1:    'C1';
C2:    'C2';
WS:    [ \n\r] -> skip;
OTHER: .;

但是，这是假设您可以通过向前看规则可能检查的第二个标记来确定 r4 规则匹配。从维护和理解的角度来看，我怀疑这是完全站不住脚的。

您可以略微通过包含使用@parser::members 能力的函数来提高可维护性。这允许您的谓词具有更复杂的逻辑，同时又不会严重破坏实际语法。

grammar test
    ;
@parser::members {
    private int[] laValues = new int[] { C1, C2 };

        private boolean r4Follows() {
            int la = _input.get(_input.index()).getType();
            for (int i = 0; i < laValues.length; i++) {
                if (la == laValues[i])
                    return true;
            }
            return false;
        }
}
start: r3 EOF;
r3
    : rA r4 // prefers rA(classB classC) over (rA classB)classC
    ;
r4
    : classB? classC // also used elsewhere other than r3
    ;
rA // rules to build A subtree, ends with classB? in 'some' cases
    : A C1
    | A
    | A classB {!r4Follows()}?
    ;
classB: B1 | B2;
classC: C1 | C2;

A:     'A';
B1:    'B1';
B2:    'B2';
C1:    'C1';
C2:    'C2';
WS:    [ \n\r] -> skip;
OTHER: .;

但是，维护起来仍然很可能是一团糟。我认为最重要的是，您要尝试做的事情会造成 classB 属于哪个规则的歧义。

一个递归下降解析器，并没有真正看到歧义，它只是匹配它当时正在处理的规则（rA），它可以做到最好，并且包括拉入 classB 比赛。您必须引入一个语义谓词来防止这种情况发生，这将是非常难以管理的。

附录：

针对 ANTLR 领域中的所有神圣内容，我确实找到了一种使用实际 r4() 规则来测试令牌流当前位置的规则匹配的方法。我强烈建议您将其归档在“愚蠢的 ANTLR 技巧”下。

由于这实际上是在尝试 r4 的解析，具体取决于所涉及的复杂性，它可能会显着影响性能。

此外，我不能保证这不会仍然违反某些状态，尽管它适用于简单的示例。

注意：语义谓词的位置很重要，因为令牌流的当前索引随着规则的推进而前进。

grammar test
    ;
@parser::header {import java.util.function.Supplier;}
@parser::members {
    private BailErrorStrategy bailStrategy = new BailErrorStrategy();
    private boolean ruleMatches(Supplier<ParserRuleContext> rule) {
        boolean result = false;

        // save state
        int idx = _input.index();
        int savedState = this.getState();
        List<ParseTree> savedChildren = _ctx.children;
        _ctx.children = new ArrayList<>();
        ANTLRErrorStrategy savedErrStrategy = this.getErrorHandler();
        this.setErrorHandler(bailStrategy);
        try {
            ParserRuleContext attempt = rule.get();
            result = true;
        } catch (ParseCancellationException pce) {
            result = false;
        } finally {
            // restore state
            this.setErrorHandler(savedErrStrategy);
            _ctx.children = savedChildren;
            this.setState(savedState);
            _input.seek(idx);
        }

        return result;
    }
}
start: r3 EOF;
r3
    : rA r4? // prefers rA(classB classC) over (rA classB)classC
    ;
r4
    : classB? classC // also used elsewhere other than r3
    ;
rA // rules to build A subtree, ends with classB? in 'some' cases
    : A {!ruleMatches(this::r4)}? classB?
    | A D
    ;
classB: B1 | B2;
classC: C1 | C2;

A:     'A';
B1:    'B1';
B2:    'B2';
C1:    'C1';
C2:    'C2';
D:     'D';
WS:    [ \n\r] -> skip;
OTHER: .;

输入“AB1C1”

输入“ADC1”

输入“AC1”

输入“AB1”

（我相信现在需要我去向 ANTLR 众神牺牲一只无辜的小猫来拯救我的灵魂来发布它）

Answer 2

我在这里看到的问题是您告诉解析器生成您不想要的解析树。如果你不想要它，那么不要指定应该产生它的语法。

与 Mike Cargal 的想法类似，我认为真正的解决方案是更明确地指定您希望在最后看到的内容。这里有一些效果很好的东西（使用你最初的问题描述和 MikeC 的测试输入）：

parser grammar testparser;

options {
    tokenVocab = testlexer;
}

start: (A r2 | r1 | .)*? EOF;
r1: A B;
r2: B C;

lexer grammar testlexer;

A: 'A';
B: 'B';
C: 'C';

WHITE_SPACE: [ \u000B\t\r\n] -> skip ;
OTHER: .;

通过输入 AB!C2 我得到了这个解析三：

省略 C 这将更改为：

主要的变化是你通过为 r2 alt 添加 A 并将其放在第一位来专门化规则以使 BC 匹配他们自己的子解析树。

备注

将单个 A 向下移动到 r2 规则将打破这一点，因为这样你就告诉解析器创建一个包含 ABC 的子树（你不想要的）。

Antlr4 相邻令牌优先级

Antlr4 Adjacent Token Precedence

antlr4

备注