antlr - coffeescript 表达式的左分解语法

Question

我正在写 Antlr/Xtext parser for coffeescript grammar .还处于开始阶段，我只是移动了 original grammar 的一个子集，我被表达方式困住了。这是可怕的“规则表达式具有非 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 和外部词法分析器来避免 intricacies of handling significant whitespace .这是我的 Xtext 版本的一个片段:

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

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

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

更新2和解决方案:
我可以通过从 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 ')'
  ;

Answer 1

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

error(211): CoffeeScript.g:52:3: [fatal] rule expression has non-LL(*) decision due to recursive rule invocations reachable from alts 1,3. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

warning(200): CoffeeScript.g:52:3: Decision can match input such as "{NUMBER, STRING}" using multiple alternatives: 1, 3

As a result, alternative(s) 3 were disabled for that input

(我已经强调了重要的部分)

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

上面发布的错误意味着当您尝试解析 NUMBER 时或 STRING使用从您的语法生成的解析器，当解析器出现在 expression 中时，它可以采用两种方式。规则:

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

即选项 1 和选项 3 都可以解析 NUMBER或 STRING ，正如您可以通过解析器可以遵循的“路径”来匹配这两个选择:

选择1:

表达
值(value)
文字
字母数字:{NUMBER，STRING}

选择3:

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

在警告的最后一部分，ANTLR 会通知您，无论何时出现 NUMBER，它都会忽略选项 3。或 STRING将被解析，导致选项 1 匹配此类输入(因为它是在选项 3 之前定义的)。

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

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

1

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

新:'新'；
...
一元:'!' | '~' |新的;

请注意， token UNARY永远无法匹配文本 'new'由于 token NEW在它之前定义。如果你想让 UNARY算了，删除 NEW规则并做:

一元:'!' | '~' | '新的';

2

在某些情况下，您会在一个单独的 token 中收集多种类型的 token ，例如 LOGIC :

逻辑:'&&' | '||';

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

逻辑运算
:比较操作(逻辑比较操作)*
;

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

和 : '＆＆';
或:'||';

...

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

3

您正在跳过空格(没有制表符？):

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

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

我刚看到 the grammar you're looking at是 jison 语法(它或多或少是 JavaScript 中的 bison 实现)。但是野牛，因此 jison，生成 LR parsers而 ANTLR 生成 LL parsers .所以试图贴近原始语法的规则只会导致更多的问题。