1

我正在为具有 if-elsif-else 语句并且似乎无法使我的语法明确的语言实现解析器。我们的编译器类获得了一份关于使用匹配/不匹配方法解决 if-else 语句的悬空 else 问题的讲义，如下所示：

%token IF EXP ELSE XX

stmts: stmts stmt ';'
     | stmt ';' 
     ; 

stmt : matched
     | unmatched
     ;

matched: IF '(' EXP ')' matched ELSE matched
      | XX
      ;

unmatched : IF '(' EXP ')' matched 
      | IF '(' EXP ')' unmatched
      | IF '(' EXP ')' matched ELSE unmatched
      ;

为我们的语言提供的语法文档被定义为具有涉及 if - elsif- else 的产生式，其中：

selectionStmt → IF simpleExpression THEN statement elsifList 
      | IF simpleExpression THEN statement elsifList ELSE statement

elsifList → elsifList ELSIF simpleExpression THEN statement
      | *empty*

其中小写字母是产生式，大写字母是终结符。

这些提供的产生式是模棱两可的，必须在野牛的语法实现中解决。这是我在将其实际实施到 Bison 中所取得的进展：

statement: stmtMatched
     | selectionStmtUnmatched

elsifList: elsifList ELSIF simpleExpression THEN statement
     | %empty

stmtMatched: IF simpleExpression THEN stmtMatched elsifList ELSE 
stmtMatched
       | otherStatement

selectionStmtUnmatched: IF simpleExpression THEN statement elsifList
       | IF simpleExpression THEN stmtMatched elsifList ELSE 
selectionStmtUnmatched

otherStatement: expressionStmt
          | compoundStmt
          | iterationStmt
          | returnStmt
          | breakStmt

关于更改语法以适应 elsif 产生式的任何建议，类似于使用匹配和不匹配的语句来解决悬空的 if-else 问题并摆脱任何移位/减少和减少/减少错误？

编辑 1：我在更简单的语法版本上取得了更多进展，以确保 elsifLists 只能遵循匹配的语句：

stmt: matched
| unmatched

matched: IF '(' EXP ')' THEN matched elsifList ELSE matched
   | %empty

unmatched: IF '(' EXP ')' THEN matched elsifList
     | IF '(' EXP ')' THEN unmatched
     | IF '(' EXP ')' THEN matched elsifList ELSE unmatched

elsifList: elsifList ELSIF EXP THEN stmt
     | %empty

但我仍然遇到转移/减少冲突：

State 12

    3 matched: IF '(' EXP ')' THEN matched elsifList . ELSE matched
    5 unmatched: IF '(' EXP ')' THEN matched elsifList .
    7          | IF '(' EXP ')' THEN matched elsifList . ELSE unmatched
    8 elsifList: elsifList . ELSIF EXP THEN stmt

    ELSE   shift, and go to state 13
    ELSIF  shift, and go to state 14

    ELSE      [reduce using rule 5 (unmatched)]
    ELSIF     [reduce using rule 5 (unmatched)]
    $default  reduce using rule 5 (unmatched)

编辑 2：我在简单语法方面取得了足够的进展，以确保 elsif 语句之前有匹配的语句。生成的语法是：

stmt: matched
    | unmatched

matched: IF '(' EXP ')' THEN matched elsifList ELSE matched
       | %empty

unmatched: IF '(' EXP ')' THEN matched elsifList
         | IF '(' EXP ')' THEN unmatched
         | IF '(' EXP ')' THEN matched elsifList ELSE unmatched

elsifList: elsifList ELSIF EXP THEN matched
         | %empty

我已经更新了实际语言的解析器的实际语法，以确保不匹配的语句不能跟在 elsifList 之后，并且 elsifLists 只能跟在匹配的语句之后：

statement :     stmtMatched |
                selectionStmtUnmatched
                ;


otherStatement : expressionStmt 
                | compoundStmt 
                | iterationStmt 
                | returnStmt
                | breakStmt
                ;

elsifList :     elsifList ELSIF simpleExpression THEN stmtMatched 
                | %empty
                ;

stmtMatched : IF simpleExpression THEN stmtMatched elsifList ELSE stmtMatched
            | otherStatement
            ;

selectionStmtUnmatched : IF simpleExpression THEN stmtMatched elsifList
                | IF simpleExpression THEN selectionStmtUnmatched 
                | IF simpleExpression THEN stmtMatched elsifList ELSE selectionStmtUnmatched

不过，由此产生的语法仍然给我 2 次移位/减少冲突：

State 164

   44 elsifList: elsifList . ELSIF simpleExpression THEN stmtMatched
   46 stmtMatched: IF simpleExpression THEN stmtMatched elsifList . ELSE stmtMatched
   48 selectionStmtUnmatched: IF simpleExpression THEN stmtMatched elsifList .
   50                       | IF simpleExpression THEN stmtMatched elsifList . ELSE selectionStmtUnmatched

   ELSIF  shift, and go to state 167
   ELSE   shift, and go to state 168

   ELSIF     [reduce using rule 48 (selectionStmtUnmatched)]
   ELSE      [reduce using rule 48 (selectionStmtUnmatched)]
   $default  reduce using rule 48 (selectionStmtUnmatched)
4

1 回答 1

0

您讲义中的语法不允许在else. 这是为什么？

 

 

 

这是因为elsemust 绑定到最接近的 not-yet-matched if。您可能想尝试手动执行一些解析树以了解其工作原理。要点是在 unmatched 语句中，有一个 unmatchedif应该else绑定到。因此，可以通过消除跳过 unmatched 的可能性来消除歧义if。

现在，当我们添加时会发生什么变化elsif？不多。两者elsif和else必须绑定到最接近的尚未匹配的ifor elsif。并且保证的方式和简单的情况完全一样。我们需要确保匹配之前的语句。elsif

但是您的语法只要求匹配第一个语句之前的语句。 elsif所以歧义仍然存在。

作为提示：修复非常简单。您只需要以不同的方式进行分组。

于 2020-02-15T23:53:37.507 回答