Зубр уменьшает / уменьшает конфликт в грамматике

Question

Я строю грамматику в зубре, и у меня есть ар / г конфликт (который я знаю, где он находится), но я не знаю, как это исправить. Буду признателен за любую возможную помощь.

Часть моего кода, которая включает конфликт:

orismos2: %empty
|orismos orismos2
|error {yyerrok;yyclearin;};

orismos: orismosmetablitwn
|orismossunartisis
|prwtotuposunartisis;

orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON ;

tuposdedomenwn: INT
|BOOL
|STRING;

listametablitwn: ID nid ;

nid: %empty
|pid nid
|error {yyerrok;yyclearin;};

pid: COMMA ID ;

orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn;

prwtotuposunartisis: kefalidasunartisis SEMICOLON;

kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET;

typos_synartisis: INT
|BOOL
|VOID;

Я сделал выходной файл, в котором я вижу все конфликты.

Часть файла, которая включает конфликты:

State 21 conflicts: 1 reduce/reduce
State 22 conflicts: 1 reduce/reduce


Grammar

   10 orismos2: %empty
   11         | orismos orismos2
   12         | error

   13 orismos: orismosmetablitwn
   14        | orismossunartisis
   15        | prwtotuposunartisis

   16 orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON

   17 tuposdedomenwn: INT
   18               | BOOL
   19               | STRING

   20 listametablitwn: ID nid

   21 nid: %empty
   22    | pid nid
   23    | error

   24 pid: COMMA ID

   25 orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn

   26 prwtotuposunartisis: kefalidasunartisis SEMICOLON

   27 kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET

   28 typos_synartisis: INT
   29                 | BOOL
   30                 | VOID


State 21

   17 tuposdedomenwn: INT .
   28 typos_synartisis: INT .

    ID        reduce using rule 17 (tuposdedomenwn)
    ID        [reduce using rule 28 (typos_synartisis)]
    $default  reduce using rule 17 (tuposdedomenwn)


State 22

   18 tuposdedomenwn: BOOL .
   29 typos_synartisis: BOOL .

    ID        reduce using rule 18 (tuposdedomenwn)
    ID        [reduce using rule 29 (typos_synartisis)]
    $default  reduce using rule 18 (tuposdedomenwn)

Я действительно все перепробовал, но не могу устранить конфликты... Любые идеи или предложения приветствуются!

Большое спасибо!!

Answer 1

Ключ здесь: …

orismos → (13) orismosmetablitwn → (16) tuposdedomenwn listametablitwn
orismos → (14) orismossunartisis → (25) kefalidasunartisis … → (27) typos_synartisis …
orismos → (15) prwtotuposunartisis → (26) kefalidasunartisis … → (27) typos_synartisis …

Также:

tuposdedomenwn → NUMBER | BOOL | STRING
listametablitwn → ID …
kefalidasunartisis → typos_synartisis ID …
typos_synartisis → NUMBER | BOOL | VOID

Итак, вот некоторые выводы из orismos:

orismos → orismosmetablitwn → tuposdedomenwn listametablitwn → NUMBER ID …
orismos → orismossunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID …
orismos → prwtotuposunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID …

Скажем, мы находимся в контексте, где orismis возможно, и мы только что видели NUMBER и теперь мы смотрим на ID, Все три из приведенных выше выводов возможны. Но есть небольшая проблема: в первом NUMBER происходит от tuposdedomenwn в то время как во вторых двух это происходит от typos_synartisis, Прежде чем мы сможем сделать что-нибудь с IDнам нужно знать, какое из двух производных уменьшить, но мы никак не можем это знать, пока не увидим токен после ID,

Это означает, что грамматике нужно два токена упреждения, поэтому парсер LALR(1) не может ее проанализировать.

Простейшим решением было бы объединить два нетерминала, представляющих наборы типов, создавая нетерминал, который допускает все четыре варианта:

tuposdedomenwn: NUMBER | BOOL | STRING | VOID

Затем вам нужно будет выполнить семантическую проверку, чтобы убедиться, что переменная не объявлена VOID ни объявленная функция STRING, (Почему ваши функции не могут возвращать строки? Это кажется немного ограничивающим.) Эта стратегия принятия верхнего индекса языка, а затем выполнения семантических проверок во время построения AST или даже позже, очень распространена; например, это единственный способ обеспечить декларацию перед использованием переменных.

Но если вы не хотите выполнять семантическую проверку, вы можете просто отложить сокращение, создав нетерминалы, состоящие из типа данных и ID, Это привело бы к чему-то вроде:

tupodedomenon_kai_metavlites
       : INT ID
       | BOOL ID
       | STRING ID
       | tupodedomenon_kai_metavlites ',' ID

tupo_synartisis_kai_metavliton
       : INT ID
       | BOOL ID
       | VOID ID

orismos: orismosmetablitwn
       | orismossunartisis
       | prwtotuposunartisis

orismosmetablitwn
       : tupodedomenon_kai_metavlites ';'

orismossunartisis
       : kefalidasunartisis tmimaorismwn tmimaentolwn

prwtotuposunartisis
       : kefalidasunartisis ';'

kefalidasunartisis
       : tupo_synartisis_kai_metavliton '(' c ')'

С этим изменением нет необходимости уменьшать NUMBER (или другой тип); ID может быть сдвинут, и затем будет выполнено приведение к одной или другой возможности на основе следующего токена: как объявление переменной, если следующий токен ; или же ,и как объявление функции, если следующий токен (,