Решение зависших if, elsif и else в Bison без объявлений ассоциативности

Question

Я реализую синтаксический анализатор для языка, который имеет операторы if-elsif-else и не может сделать мою грамматику однозначной. Нашему классу компиляторов был предоставлен раздаточный материал по решению проблемы зависшего else для операторов if-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. Вот прогресс, которого я добился в реализации его в 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) 

Answer 1

Грамматика в вашем раздаточном материале не допускает несогласованного утверждения перед else. Это почему?

Это потому, что else должен связываться с ближайшим, еще не сопоставленным if. Вы можете попробовать сделать несколько деревьев синтаксического анализа вручную, чтобы понять, как это работает. Существенный момент состоит в том, что внутри несогласованного утверждения есть непревзойденноеif который elseследует привязать к. Таким образом, двусмысленность может быть устранена, если исключить возможность пропустить непревзойденныйif.

Что изменится, когда мы добавим elsif? Немного. Обеelsif а также else должен связываться с ближайшим, еще не сопоставленным if или elsif. И способ гарантировать это точно такой же, как и в простом случае. Нам нужно убедиться, что заявление передelsif совпадает.

Но ваша грамматика требует только, чтобы утверждение перед первым elsifбыть сопоставленным. Так что остаются неясности.

Подсказка: исправить очень просто. Вам просто нужно сделать группировку по-другому.