compiler-construction - 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

这就是所谓的悬空问题。 解析文本:

      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
    ..........
;

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

许多解析器生成器允许您在遇到标记时“强制转换”。如果您强制改变原始语法中的 else 关键字，您将获得相同的效果。如果确实可以的话，我不知道如何为 ANTLR 说这些。

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