ANTLR if-else 歧义错误

Question

我正在尝试为一种简单的编程语言创建 ANTLR 语法。

它有类似 C 语言的 if 语句：

program
    : statement* EOF
    ;

statement
    : block                                                                 # blockStatement
    | SEMI                                                                  # emptyStatement
    | assignment                                                            # assignmentStatement
    | declaration                                                           # variableDeclarationStatement
    | 'if' parExpression ifBody=statement ('else' elseBody=statement)?      # ifStatement
    ..........
    ;

block
    : '{' statement* '}'
    ;

expression
    : literal                                                           # literalExpression
    | Identifier                                                        # variableReference
    ..........
    ;

parExpression : '(' expression ')';

assignment : Identifier assignmentOp expression SEMI;

SEMI : ';';

Identifier : (LETTER | '_') (LETTER | DIGIT | '_')* ;

它似乎工作正常但是当我运行和 DiagnosticErrorListener 我得到错误

reportAttemptingFullContext d=1 (statement), input='else', Line 3:0
reportContextSensitivity d=1 (statement), input='else', Line 3:0
reportAttemptingFullContext d=1 (statement), input='else', Line 5:0
reportContextSensitivity d=1 (statement), input='else', Line 5:0

对于这样的代码

if (flag1)
    x = 42;
else if (flag2)
    x = 43;
else
    x = 44;

我不确定我是否理解这里有什么问题，但据我所知，在其他情况下（例如 if (a) if (b) ... else ...），此语法可能有歧义。

我该如何解决？

Answer 1

这称为 悬空 else 问题。正在解析文本：

      if (flag1)
         if (flag2) x=2;
            else x=3;

可以通过两种方式匹配您的语法：

      if (flag1)
         if (flag2) x=2;
         else x=3; // belongs to if (flag2)

和

      if (flag1)
         if (flag2) x=2;
      else x=3; // belongs to if (flag1)

因为您将 else 子句设置为可选匹配项。这意味着语法规则提供了歧义匹配，这是您从 ANTLR 收到的投诉。

你想要的是强制else匹配最近的未闭合if语句；这是大多数编程语言中 if ... else 的解释。

你要修改语句解析规则：

statement
    : non_if_statement
    | if_statement
;

if_statement
    : 'if' parExpression 
         ifBody= ( non_if_statement 'else' elseBody=statement
                   | if_statement )
;  

non_if_statement
    :block                                                                 
    | SEMI
    | assignment 
    | declaration
    ..........
;

写起来有点笨拙，但应该可以。

许多解析器生成器允许您在遇到标记时 "force a shift"。如果您强制改变原始语法中的 else 关键字，您将获得相同的效果。我不知道如何对 ANTLR 这么说，如果你真的可以的话。

[Lischke 说如果你忽略这个错误，你可能会用你原来的语法得到正确的结果。我认为他是对的;那是因为解析器生成器被迫选择两种解释之一作为它接受的解释。]

Answer 2

看起来可以在 ANTLR 中使用这个语义谓词来避免这个警告：

'if' parExpression ifBody=statement ('else' elseBody=statement | {_input.LA(1) != ELSE}?)

（来自这个回答）

另外据我所知 https://github.com/antlr/antlr4/issues/42 自 2013 年以来存在更好的方法：ifStmt : 'if' ID stmt (options{sll=true;} : 'else' stmt | ); 但它对我不起作用。

ANTLR if-else 歧义错误

ANTLR if-else ambiguity errors

compiler-construction

grammar

antlr

antlr4