compiler-construction - 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

你的语法有歧义:

"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" 4 次才能匹配输入，同时有一层嵌套。如果有另一个级别，整个过程将重复两次，因此 ANTLR 将解析最后一部分八次。

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