ANTLR 3 的两级文法

Question

我有一个语法（如果你稍微简化一下）如下所示：

options
{
    backtrack=true;
}

// parser
text: (TEXT)+;

and_level2_thing: text | '(' and_thing ')';

and_thing: and_level2_thing (OP_AND and_level2_thing)*;

and_expression: and_thing (OP_AND and_thing)*;

parse_starts_here: and_expression EOF;

// lexer
OP_AND : 'AND';
TEXT : ( '"' (~'"')* '"' );

它有两种类型的表达式组：顶层（and_thing）和内层（and_level2_thing），它们适用不同的规则，但两个级别都必须支持 AND 例如TOP_TYPE_EXPRESSION AND TOP_TYPE_EXPRESSION 和 TOP_TYPE_EXPRESSION AND (INNER_TYPE_EXPRESSION AND INNER_TYPE_EXPRESSION).

当我有以下形式的值时：

(TOP_TYPE_EXPRESSION AND (TOP_TYPE_EXPRESSION AND (TOP_TYPE_EXPRESSION AND (TOP_TYPE_EXPRESSION))))

时间开始在嵌套级别上呈指数增长，这大概是因为 AND 不明确。此表达式立即求值：

TOP_TYPE_EXPRESSION AND TOP_TYPE_EXPRESSION AND TOP_TYPE_EXPRESSION AND TOP_TYPE_EXPRESSION

如果你说这不是一种设计良好的语言 - 我完全同意，但这就是我现在所拥有的:)。有什么办法可以避免这个问题吗？

Answer 1

添加 memoize "fixes" 问题。但我确信有更好的解决方案或围绕它进行一些更有趣的讨论。

options
{
    backtrack=true;
    memoize=true;
}

Answer 2

你的语法有歧义：

"a" AND "b"

可以匹配为

parse_starts_here
  and_expression
    and_thing
      and_level2_thing
        text
      OP_AND
      and_level2_thing
        text

或

parse_starts_here
  and_expression
    and_thing
      and_level2_thing
        text
    OP_AND
    and_thing
      and_level2_thing
        text

通常，ANTLR 会警告您这种歧义，但通过声明 backtrack = true，您有效地告诉 ANTLR 尝试所有替代方案并首先使用匹配的。

在明确的文法上，ANTLR 以线性时间运行。使用回溯会导致潜在的指数时间。 memoize=true用于以使用更多内存为代价将时间减少到线性。

我建议删除 backtrack=true 选项。然后 ANTLR 会告诉你语法哪里有歧义。您可以消除歧义，或者如果不可能，请仅在需要时使用句法谓词来优先选择一个可能的匹配项而不是另一个匹配项。如果您最终使用句法谓词，memoize=true 仍然会有所帮助。

编辑-至于为什么即使两个选项都匹配也会回溯：

不会回溯，但时间还是会呈指数增长。

问题是 ANTLR 不知道它可以匹配第一个选择，直到它实际尝试匹配它（因为你没有给它任何提示）。所以它会首先尝试匹配规则，如果成功，它会实际匹配它并执行所有相关的操作（memoize 选项通过记住给定输入位置成功的特定规则而不是重复整个过程来避免这种情况匹配过程）。

示例：

"a" AND ( "b" AND "c" )

要匹配这个，ANTLR 必须：

匹配"a"
判断AND是否可以使用内层规则匹配
- 为此，它会尝试匹配内部规则
- AND匹配，(表示去and_thing
- 要匹配 and_thing，它必须：
  - 匹配 ( 和 "b"
  - 判断AND是否可以使用内层规则匹配
    - 为此，它会尝试 将内部规则与 AND "c"
    - 谓词成功 - AND "c" 匹配内部规则
  - 将内部规则与 AND "c"
  - 匹配)
- 谓词成功 - AND ( "b" AND "c" ) 匹配内部规则
将内部规则与 AND ( "b" AND "c" ) 匹配
- AND匹配，(表示去and_thing
- 要匹配 and_thing，它必须：
  - 匹配 ( 和 "b"
  - 判断AND是否可以使用内层规则匹配
    - 为此，它会尝试 将内部规则与 AND "c"
    - 谓词成功 - AND "c" 匹配内部规则
  - 将内部规则与 AND "c"
  - 匹配)

如过程中强调的部分所示，ANTLR 需要将文本 AND "c" 匹配四次才能匹配输入，同时有一层嵌套。如果有另一层，整个过程会重复两次，所以ANTLR会解析最后一部分八次。

一个相关的评论——如果你使用句法谓词而不是回溯选项，你可以微调谓词包含的内容——在某些情况下，它不需要包含被谓词的整个规则。在上面的示例中，您可以告诉 ANLTR 在遇到 OP_AND 时使用 OP_AND and_level2_thing 规则，而无需检查 and_level2_thing 是否匹配。请注意，您只能这样做，因为您知道 and_level2_thing 会匹配，否则另一个选择也会失败。如果你做错了，你最终会导致解析器迷路并拒绝输入，如果它选择了正确的选择则有效。

ANTLR 3 的两级文法

Two-level grammar with ANTLR 3

compiler-construction

antlr

antlr3