Как структурировать код YACC для поддержки необязательных нетерминалов - PullRequest
Новая
       2

Как структурировать код YACC для поддержки необязательных нетерминалов

1 голос
/ 06 февраля 2011

Как лучше всего моделировать необязательные данные в yacc?У меня есть следующее утверждение: 

StmtBlock           :    '{' VariableDeclList StmtList '}' {  $$ = new StmtBlock($2, $3); }
                    ;

Оба, VariableDeclList и StmtList являются необязательными (epsilon), поэтому я смоделировал их следующим образом: 

VariableDeclList    :    VariableDeclList VariableDecl  { ($$=$1)->Append($2); }
                    |    { $$ = new List<VarDecl*>; }

и 

StmtList            :    StmtList Stmt { ($$=$1)->Append($2); }
                    |    { $$ = new List<Stmt*>; }
                    ;

Единственная проблема - когда я думаю, что это вызывает сдвиг / уменьшение конфликтов.Когда я пытаюсь скомпилировать мой код, мой файл y.ouput имеет следующее: 

State 74 conflicts: 1 shift/reduce
...
state 74

   38 StmtBlock: '{' VariableDeclList . StmtList '}'
   39 VariableDeclList: VariableDeclList . VariableDecl

    T_Bool        shift, and go to state 2
    T_Int         shift, and go to state 3
    T_Double      shift, and go to state 4
    T_String      shift, and go to state 5
    T_Identifier  shift, and go to state 8

    T_Identifier  [reduce using rule 18 (Epsilon)]
    $default      reduce using rule 18 (Epsilon)

    VariableDecl  go to state 80
    Variable      go to state 13
    Type          go to state 34
    Epsilon       go to state 81
    StmtList      go to state 82
...

Есть ли более правильный способ для моделирования этого?

1 Ответ

0 голосов
/ 06 февраля 2011

Как вы заметили, это вызовет конфликты сдвига / уменьшения, если Stmt и VariableDecl не могут быть различены по их первому токену - в вашем примере a T_Identifierможет начаться либо.Есть несколько вещей, которые вы можете попробовать:

  • объединить два списка в VariableDeclOrStmtList , который может содержать либо Stmt , либо VariableDecl перемешивается любым способом.Это более общий подход, чем у вас, поэтому вам потребуется дополнительная проверка, чтобы убедиться, что VariableDecls после первого Stmt

  • Используйте дополнительную информацию, чтобы определить разницу - либо используйте режим GLR бизона, либо что-то вроде btyacc , которое может отложить принятие решения, является ли Stmt или VariableDecl пока не увидит достаточно, чтобы решить

  • Используйте разные жетоны в начале этих конструкций, чтобы однозначно дифференцировать их.Это могут быть как настоящие токены на вашем языке, так и синтетические токены, которые лексер вставляет на основе какого-то дополнительного контекста (что означает, что в лексере нужно больше ориентироваться).

edit

Для первого предложения у вас будет следующее правило: 

VarDeclOrStmtList : VarDeclOrStmtList VariableDecl { ($$=$1)->Append($2); }
                  | VarDeclOrStmtList Stmt         { ($$=$1)->Append($2); }
                  | { $$ = new List<Node *>; }
                  ;

, где Node - это общий базовый класс VarDecl и Stmt.Затем в вашем действии StmtBlock вызовите функцию, которая проходит через List<Node *>, разбивая ее на List<VarDecl *> и List<Stmt *> и выдавая сообщение об ошибке, если оно не правильно сформировано.

...