改变/减少我语法中的IF-ELSE冲突

Question

我正在尝试编写一个小型解析器。不幸的是，我得到了一个"减少冲突的转变"。语法不是我的强项，我只需要完成这一件小事。以下是产生错误的简化语法：

stmts_opt -> stmts
;
stmts -> stmt 
| stmts stmt
| stmsts
;
stmt -> id 
| ITERATE content_stmt 
| IF test then content_stmt ELSE content_stmt
| IF test then content_stmt
;
content_stmt: BEGIN stmt_opt END
| stmt
;

给出修改语法的解决方案将不胜感激。

编辑：

我根据@rici的回答修改了语法，但问题仍然存在。以下是我实际的语法作品：

prog:   BEGIN_PROG def_sprogram BEGIN_EXEC  stmts_opt END_EXEC END_PROG
{ () }
;
def_sprogram:   /* empty */     { () }
| define_new def_sprogram       { () }
;

define_new:         DEFINE_NEW_INSTRUCTION ID AS content_stmt SEMI   { }
;
stmts_opt:  /* empty */     { () }
|           stmts           { () }
;
stmts:      stmt            { () }
|           stmts SEMI stmt { () }
|           stmts SEMI      { () }
;
content_stmt:  BEGIN stmts_opt END { () }
|       stmt    { () }
;
stmt:       open_stmt { () }
|           closed_stmt { () }
;
open_stmt:  ITERATE INT TIMES open_stmt { () }  
|           WHILE test DO open_stmt { () }
|           IF test THEN closed_stmt ELSE open_stmt { () }
|           IF test THEN stmt { () }
;
closed_stmt:  simple_stmt   { () }  
|           ITERATE INT TIMES closed_stmt   { () }  
|           WHILE test DO closed_stmt { () }
|           IF test THEN closed_stmt ELSE closed_stmt { () }
;

以下是我正在测试的示例：

BEGINNING-OF-PROGRAM
BEGINNING-OF-EXECUTION
IF not-next-to-a-beeper THEN
move;
IF not-facing-north THEN
turnleft;

ELSE <--- ERROR
turnleft;
IF not-facing-east THEN
IF not-facing-west THEN
turnleft;
turnoff
END-OF-EXECUTION
END-OF-PROGRAM

我在第一个ELSE中得到错误。我还试图按照@rici:的建议声明一个简单的优先级

%nonassoc THEN
%nonassoc ELSE

但这也没有解决错误。

Answer 1

"悬空else"移位减少冲突的最简单解决方案是强制解决有利于移位ELSE令牌的问题。由于camlyacc确实支持优先级声明(根据我能找到的相当粗略的文档)，这应该很简单，只需在声明部分添加以下内容(在第一个%%之前)：

%nonassoc THEN
%nonassoc ELSE

(关联性并不重要，因为在语法中没有THEN和ELSE可以关联的地方。)

如果您想使用显式的"matchinese/amatchinese"(或"open/closed statements")，请注意BEGIN stmts_opt END是一个"matchine"(或是"closed"语句)就足够了，因为它不能接受THEN。其他匹配的语句是

matched_stmt: BEGIN stmts_opt END
| ITERATE matched_stmt
| IF test THEN matched_stmt ELSE matched_stmt
| /* Any other kind of simple statement */

不匹配的语句是

unmatched_stmt: ITERATE unmatched_stmt
| IF test THEN matched_stmt
| IF test THEN unmatched_stmt
| IF test THEN matched_stmt ELSE unmatched_stmt

许多人喜欢创建包括matched_stmt和unmatched_stmt的非终端。然而，在您的情况下，您似乎不想嵌套BEGIN…END块，将这些块限制为复合语句的内容。因此，您的stmt将是上述所有，除了BEGIN stmts_opt END右侧的。