Предотвращение левой рекурсии в ANTLR 4 от сопоставления неверных входов - PullRequest
Новая
       119

Предотвращение левой рекурсии в ANTLR 4 от сопоставления неверных входов

2 голосов
/ 16 мая 2019

Я делаю простой язык программирования. Имеет следующую грамматику: 

program: declaration+;

declaration: varDeclaration
           | statement
           ;

varDeclaration: 'var' IDENTIFIER ('=' expression)?';';
statement: exprStmt
         | assertStmt
         | printStmt
         | block
         ;

exprStmt: expression';';
assertStmt: 'assert' expression';';
printStmt: 'print' expression';';
block: '{' declaration* '}';

//expression without left recursion
/*
expression: assignment
          ;

assignment: IDENTIFIER '=' assignment
          | equality;

equality: comparison (op=('==' | '!=') comparison)*;

comparison: addition  (op=('>' | '>=' | '<' | '<=') addition)* ;

addition: multiplication (op=('-' | '+') multiplication)* ;

multiplication: unary (op=( '/' | '*' ) unary )* ;

unary: op=( '!' | '-' ) unary
     | primary
     ;
*/

//expression with left recursion
expression: IDENTIFIER '=' expression
          | expression op=('==' | '!=') expression
          | expression op=('>' | '>=' | '<' | '<=') expression
          | expression op=('-' | '+') expression
          | expression op=( '/' | '*' ) expression
          | op=( '!' | '-' ) expression
          | primary
          ;

primary: intLiteral
       | booleanLiteral
       | stringLiteral
       | identifier
       | group
       ;

intLiteral: NUMBER;
booleanLiteral: value=('True' | 'False');
stringLiteral: STRING;
identifier: IDENTIFIER;
group: '(' expression ')';

TRUE: 'True';
FALSE: 'False';
NUMBER:   [0-9]+ ;
STRING: '"' ~('\n'|'"')* '"' ;
IDENTIFIER :   [a-zA-Z]+ ;

Эта левая рекурсивная грамматика полезна, поскольку она гарантирует, что каждый узел в дереве разбора имеет не более 2 дочерних элементов. Например, var a = 1 + 2 + 3 превратится в два вложенных выражения сложения, а не в одно выражение сложения с тремя дочерними элементами. Такое поведение полезно, потому что облегчает написание интерпретатора, поскольку я могу просто сделать (очень упрощенно): 

public Object visitAddition(AdditionContext ctx) {
    return visit(ctx.addition(0)) + visit(ctx.addition(1));
}

вместо перебора всех дочерних узлов.

Однако у этой левой рекурсивной грамматики есть один недостаток, заключающийся в том, что она принимает недопустимые операторы. Например: 

var a = 3;
var b = 4;
a = b == b = a;

действительно под этой грамматикой, хотя ожидаемое поведение будет

  1. b == b анализируется первым, поскольку == имеет более высокий приоритет, чем присвоение (=).
  2. Поскольку b == b анализируется первым, выражение становится бессвязным. Сбой разбора.

Вместо этого происходит следующее нежелательное поведение: последняя строка анализируется как (a = b) == (b = a).

AST Image

Как я могу предотвратить разбор левых рекурсий, например, a = b == b = a?

Нерекурсивная грамматика распознает этот ввод правильно и выдает ошибку синтаксического анализа, которая является желаемым поведением.

...