4

我正在为咖啡脚本语法编写 Antlr/Xtext 解析器。现在才刚刚开始,我只是移动了原始语法的一个子集,而且我被表达式所困。这是可怕的“规则表达式具有非 LL(*) 决策”错误。我在这里找到了一些相关的问题,Help with left factoring a grammar to remove left recursionANTLR 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 回答