我的 antlr 4 左递归表达式不保留表达式优先顺序

Question

我为antlr4定义了如下简单的左递归表达式语法：

grammar BugExample;

// Rule Definitions

value: expression EOF ;

real:
    '-'? CONSTANT    #constantReal |
    FLOAT            #variableReal
;

variable: IDENTIFIER ;

expression:  // Precedence (highest to lowest)
    real             #realExpression      |
    variable         #variableExpression  |
//  expression '!'   #factorialExpression |
    '-' expression   #inversionExpression
;


// Token Definitions

FRACTION: '.' ('0'..'9')* '1'..'9' ;

CONSTANT: 'e' | 'pi' ;

FLOAT: INTEGER FRACTION? ('e' INTEGER)? ;

IDENTIFIER: ('a'..'z'|'A'..'Z') ('a'..'z'|'A'..'Z'|'0'..'9')* ;

SPACE: (' '|'\t'|'\r'|'\n')+ -> channel(HIDDEN) ;

fragment
NATURAL: '1'..'9' ('0'..'9')* ;

fragment
INTEGER: '0' | '-'? NATURAL ;

注意表达式类型中注释掉的阶乘表达式。另请注意，FLOAT 标记的定义允许负值，因此负实数表达式应优先于反转表达式。注释掉阶乘表达式后，生成的 JS 解析器确实将负常量“-e”正确解析为真正的表达式。但是，如果我们取消对阶乘表达式的注释并重新生成解析器，“-e”会突然被解析为反转表达式。这是显示它的测试代码：

'use strict';

var language = require('../BugExample');
var testCase = require('nodeunit').testCase;

module.exports = testCase({
    'Test Parser': function(test) {
        var testValues = ['5.27e-15', '-5.3e22','e', '-e', 'expo', '-expo'];
        var expectedResults = [
            'RealExpressionContext',      // positive real number
            'RealExpressionContext',      // negative real number
            'RealExpressionContext',      // positive real constant
            'RealExpressionContext',      // positive real constant
            'VariableExpressionContext',  // variable value
            'InversionExpressionContext'  // negative variable value
        ];
        test.expect(testValues.length);
        for (var i = 0; i < testValues.length; i++) {
            var value = testValues[i];
            console.log('\nTesting: ' + value);
            var expression = language.parseValue(value).getChild(0);
            test.strictEqual(expression.constructor.name, expectedResults[i]);
        }
        test.done();
    }
});

事实证明，添加 any 留下了 "Definitive Antlr 4 Reference" 中列出的以表达式开头的递归子规则类型，例如"binary"、"ternary" 和 "unary suffix" 表达式，将导致此问题。我只针对生成的 JS 解析器验证了这一点。当我查看生成的解析器代码时，出现问题时，expression() 函数中 case 块的顺序似乎随机化，而当阶乘表达式被注释掉时，它们按优先顺序排列。不确定是不是这个原因，代码太复杂了，我看不懂 ;-)

我将显示此示例的 JavaScript 项目放置在 GitHub： https://github.com/derknorton/antlr4-bug-example

要对其进行测试，请执行以下操作：

git clone https://github.com/derknorton/antlr4-bug-example
cd antlr4-bug-example
npm install
grunt generate build
# it should work correctly
# then edit test/TestBugExample.js  to remove commented factorial expression
grunt generate build
# it should now show the problem

希望我已经为 antlr4 专家提供了足够的细节来确定问题。任何帮助将不胜感激。

Answer 1

原来这个问题出在 antlr 4 解析器生成器的早期版本上。我的 Grunt.js 文件正在使用尚未更新为使用最新版本的 antlr4 的 grunt-antlr4 任务。它使用的是 4.5.1 版。该问题似乎已在该版本之后得到解决。此实现的完整详细信息记录在此处：https://github.com/antlr/antlr4/issues/2201

我的 antlr 4 左递归表达式不保留表达式优先顺序

My antlr 4 left recursive expression not preserving the expression precedence order

javascript

recursion

parsing

node.js

antlr4