如果那么 CUP 中的其他歧义

Question

我正在 CUP 中构建语法，但我运行遇到了定义 IF-THEN-ELSE 语句的障碍。

我的代码是这样的：

start with statements;

/* Top level statements */
statements ::= statement | statement SEPARATOR statements ;
statement  ::= if_statement | block | while_statement | declaration | assignment ;
block        ::= START_BLOCK statements END_BLOCK ;

/* Control statements */
if_statement    ::= IF    expression THEN statement
                  | IF    expression THEN statement ELSE statement ;
while_statement ::= WHILE expression THEN statement ;

但是 CUP 工具抱怨 if_statement.

定义中的歧义

我发现 this article 描述了如何在不引入 endif 标记的情况下消除歧义。

所以我尝试调整他们的解决方案：

start with statements;

statements ::= statement | statement SEPARATOR statements ;

statement  ::= IF expression THEN statement
             | IF expression THEN then_statement ELSE statement 
             | non_if_statement ;

then_statement ::= IF expression THEN then_statement ELSE then_statement
                 | non_if_statement ; 

// The statement vs then_statement is for disambiguation purposes
// Solution taken from http://goldparser.org/doc/grammars/example-if-then-else.htm

non_if_statement ::= START_BLOCK statements END_BLOCK  // code block
                   | WHILE expression statement        // while statement
                   | declaration | assignment ;

很遗憾银联抱怨如下：

Warning : *** Reduce/Reduce conflict found in state #57
  between statement ::= non_if_statement (*) 
  and     then_statement ::= non_if_statement (*) 
  under symbols: {ELSE}
  Resolved in favor of the first production.

为什么这不起作用？我该如何解决？

Answer 1

这里的问题是if语句和while语句之间的交互，如果你从non-if-statement中删除while语句生产就可以看到。

问题是 while 语句的目标可以是 if 语句，然后 while 语句可以在另一个语句的 then 子句中if 声明：

IF expression THEN WHILE expression IF expression THEN statement ELSE ...

现在我们对原始问题的表现略有不同：末尾的 else 可能是嵌套 if 或外部 if.[=26= 的一部分]

解决方案是扩展受限语句（"then-statements" 在您的 link 中的区别），以包括两种不同类型的 while 语句：

statement  ::= IF expression THEN statement
             | IF expression THEN then_statement ELSE statement 
             | WHILE expression statement
             | non_if_statement ;

then_statement ::= IF expression THEN then_statement ELSE then_statement
                 | WHILE expression then_statement
                 | non_if_statement ; 

non_if_statement ::= START_BLOCK statements END_BLOCK
                   | declaration | assignment ;

当然，如果您扩展语法以包括其他类型的复合语句（例如 for 循环），您将不得不对它们中的每一个做同样的事情。

如果那么 CUP 中的其他歧义

If then else ambiguity in CUP

if-statement

grammar

ambiguous-grammar

cup