4

我正在为咖啡脚本语法编写 Antlr/Xtext 解析器。现在才刚刚开始，我只是移动了原始语法的一个子集，而且我被表达式所困。这是可怕的“规则表达式具有非 LL(*) 决策”错误。我在这里找到了一些相关的问题，Help with left factoring a grammar to remove left recursion和ANTLR Grammar for expressions。我还尝试了 How to remove global backtracking from your grammar，但它只是演示了一个我在现实生活中无法使用的非常简单的案例。关于ANTLR Grammar Tip: LL() and Left Factoring的帖子给了我更多的见解，但我仍然无法掌握。

我的问题是如何修复以下语法（对不起，我无法简化它并仍然保留错误）。我想麻烦制造者是term规则，所以我很感激对它进行本地修复，而不是改变整个事情（我试图保持接近原始语法的规则）。也欢迎指针提示如何在您的脑海中“调试”这种错误的语法。

grammar CoffeeScript;

options {
  output=AST;
}

tokens {
  AT_SIGIL; BOOL; BOUND_FUNC_ARROW; BY; CALL_END; CALL_START; CATCH; CLASS; COLON; COLON_SLASH; COMMA; COMPARE; COMPOUND_ASSIGN; DOT; DOT_DOT; DOUBLE_COLON; ELLIPSIS; ELSE; EQUAL; EXTENDS; FINALLY; FOR; FORIN; FOROF; FUNC_ARROW; FUNC_EXIST; HERECOMMENT; IDENTIFIER; IF; INDENT; INDEX_END; INDEX_PROTO; INDEX_SOAK; INDEX_START; JS; LBRACKET; LCURLY; LEADING_WHEN; LOGIC; LOOP; LPAREN; MATH; MINUS; MINUS; MINUS_MINUS; NEW; NUMBER; OUTDENT; OWN; PARAM_END; PARAM_START; PLUS; PLUS_PLUS; POST_IF; QUESTION; QUESTION_DOT; RBRACKET; RCURLY; REGEX; RELATION; RETURN; RPAREN; SHIFT; STATEMENT; STRING; SUPER; SWITCH; TERMINATOR; THEN; THIS; THROW; TRY; UNARY; UNTIL; WHEN; WHILE;
}

COMPARE : '<' | '==' | '>';
COMPOUND_ASSIGN : '+=' | '-=';
EQUAL : '=';
LOGIC : '&&' | '||';
LPAREN  :   '(';
MATH : '*' | '/';
MINUS : '-';
MINUS_MINUS : '--';
NEW : 'new';
NUMBER  :   ('0'..'9')+;
PLUS : '+';
PLUS_PLUS : '++';
QUESTION : '?';
RELATION : 'in' | 'of' | 'instanceof'; 
RPAREN  :   ')';
SHIFT : '<<' | '>>';
STRING  :   '"' (('a'..'z') | ' ')* '"';
TERMINATOR : '\n';
UNARY : '!' | '~' | NEW;
// Put it at the end, so keywords will be matched earlier
IDENTIFIER :    ('a'..'z' | 'A'..'Z')+;

WS  :   (' ')+ {skip();} ;

root
  : body
  ;

body
  : line
  ;

line
  : expression
  ;

assign
  : assignable EQUAL expression
  ;

expression
  : value
  | assign
  | operation
  ;

identifier
  : IDENTIFIER
  ;

simpleAssignable
  : identifier
  ;

assignable
  : simpleAssignable
  ;

value
  : assignable
  | literal
  | parenthetical
  ;

literal
  : alphaNumeric
  ;

alphaNumeric
  : NUMBER 
  | STRING;

parenthetical
  : LPAREN body RPAREN
  ;

// term should be the same as expression except operation to avoid left-recursion
term
  : value
  | assign
  ;

questionOp
  : term QUESTION?
  ;

mathOp
  : questionOp (MATH questionOp)*
  ;

additiveOp
  : mathOp ((PLUS | MINUS) mathOp)*
  ;

shiftOp
  : additiveOp (SHIFT additiveOp)*
  ;

relationOp
  : shiftOp (RELATION shiftOp)*
  ;

compareOp
  : relationOp (COMPARE relationOp)*
  ;

logicOp
  : compareOp (LOGIC compareOp)*
  ;

operation
  : UNARY expression
  | MINUS expression
  | PLUS expression
  | MINUS_MINUS simpleAssignable
  | PLUS_PLUS simpleAssignable
  | simpleAssignable PLUS_PLUS
  | simpleAssignable MINUS_MINUS
  | simpleAssignable COMPOUND_ASSIGN expression
  | logicOp
  ;

更新：最终解决方案将使用 Xtext 和外部词法分析器，以避免处理重要空白的复杂性。这是我的 Xtext 版本的一个片段：

CompareOp returns Operation:
  AdditiveOp ({CompareOp.left=current} operator=COMPARE right=AdditiveOp)*;

我的策略是首先在没有可用 AST 的情况下制作一个可以工作的 Antlr 解析器。（好吧，如果这是一种可行的方法，那么值得提出一个单独的问题。）所以我现在不关心令牌，它们被包括在内是为了使开发更容易。

我知道原始语法是LR。我不知道在变身为LL时我能离它有多近。

UPDATE2 和解决方案：我可以通过从 Bart 的回答中获得的见解来简化我的问题。这是一个有效的玩具语法，用于处理带有函数调用的简单表达式来说明它。之前的评论expression显示了我的洞察力。

grammar FunExp;

ID: ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
NUMBER: '0'..'9'+;
WS: (' ')+ {skip();};

root
  : expression
  ;

// atom and functionCall would go here,
// but they are reachable via operation -> term
// so they are omitted here
expression
  : operation
  ;

atom
  : NUMBER
  | ID
  ;

functionCall
  : ID '(' expression (',' expression)* ')'
  ;

operation
  : multiOp
  ;

multiOp
  : additiveOp (('*' | '/') additiveOp)*
  ;

additiveOp
  : term (('+' | '-') term)*
  ;

term
  : atom
  | functionCall
  | '(' expression ')'
  ;
4

1 回答 1

4

当您从语法生成词法分析器和解析器时，您会看到以下错误打印到控制台：

错误（211）：CoffeeScript.g:52:3：[致命]规则表达式具有非 LL(*) 决策，因为可以从 alts 1,3 访问递归规则调用。通过左分解或使用句法谓词或使用 backtrack=true 选项来解决。

警告（200）：CoffeeScript.g:52:3：决策可以使用多种选择匹配输入，例如“{NUMBER, STRING}”：1、3

结果，该输入禁用了备选方案 3

（我已经强调了重要的部分）

这只是第一个错误，但您从第一个开始，如果运气好的话，当您修复第一个错误时，第一个错误下面的错误也会消失。

上面发布的错误意味着当您尝试使用从语法生成的解析器解析 aNUMBER或 a时，解析器在规则STRING中结束时可以采用两种方式：expression

表达
  : 值 // 选择 1
  | 分配 // 选择 2
  | 操作 // 选择 3
  ;

也就是说，选项 1 和选项 3 都可以解析 aNUMBER或 a STRING，正如您可以通过解析器可以遵循的“路径”来匹配这两个选项：

选择1：

表达
  价值
    文字
      字母数字：{NUMBER，STRING}

选择3：

表达
  手术
    逻辑运算
      关系操作
        移位操作
          加法运算
            数学运算
              问题操作
                学期
                  价值
                    文字
                      字母数字：{NUMBER，STRING}

在警告的最后一部分，ANTLR 通知您，无论何时解析 aNUMBER或 a ，它都会忽略选项 3 STRING，从而导致选项 1 匹配此类输入（因为它是在选项 3 之前定义的）。

所以，要么 CoffeeScript 语法在这方面是模棱两可的（并以某种方式处理这种模棱两可），要么你的实现是错误的（我猜是后者:)）。您需要修正语法中的这种歧义：即不要让expression选项 1 和 3 都匹配相同的输入。

我注意到你的语法中还有另外 3 件事：

1

采用以下词法分析器规则：

新：'新'；
...
一元：'！' | '~' | 新的;

请注意，令牌UNARY永远不会与文本匹配，'new'因为令牌NEW是在它之前定义的。如果你想让UNARYmacth 这样做，请删除NEW规则并执行以下操作：

一元：'！' | '~' | '新的';

2

在某些情况下，您会在一个单一的令牌中收集多种类型的令牌，例如LOGIC：

逻辑：'&&' | '||';

然后在解析器规则中使用该标记，如下所示：

逻辑运算
  ：比较操作（逻辑比较操作）*
  ;

但是，如果您要在稍后阶段评估这样的表达式，您不知道该LOGIC标记匹配什么 ('&&'或'||')，您必须检查该标记的内部文本以找出它。你最好做这样的事情（至少，如果你在稍后阶段进行某种评估）：

和 ： '＆＆';
或：'||';

...

逻辑运算
  : compareOp ( AND compareOp // 更容易计算，你知道它是一个 AND 表达式
              | OR compareOp // 更容易计算，你知道它是一个 OR 表达式
              )*
  ;

3

您正在跳过空格（没有制表符？）：

WS : (' ')+ {skip();} ;

但是 CoffeeScript 不是像 Python 那样用空格（和制表符）缩进它的代码块吗？但也许你会在稍后阶段这样做？

我刚刚看到您正在查看的语法是 jison 语法（它或多或少是 JavaScript 中的野牛实现）。但是野牛，因此 jison，生成LR 解析器，而 ANTLR 生成LL 解析器。所以试图贴近原始语法的规则只会导致更多的问题。

于 2011-11-25T10:16:58.763 回答