Устранение зависаний if, elsif, and else в Bison без объявлений ассоциативности - PullRequest
Новая
       64

Устранение зависаний if, elsif, and else в Bison без объявлений ассоциативности

1 голос
/ 16 февраля 2020

Я реализую синтаксический анализатор для языка, который имеет операторы 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
      ;

Грамматическая документация, предоставляемая для нашего языка, определена так, чтобы в ней использовались операции - 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)

1 Ответ

0 голосов
/ 16 февраля 2020

Грамматика в вашем раздаточном материале не позволяет использовать непревзойденный оператор до else. Почему это так?

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

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

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

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

...