Reformowanie gramatyki w celu usunięcia przesunięcia zmniejsz konflikt w if-then-else

Jak usunąć konflikt shift-reduce dla bison dla danej gramatyki?

 selection-stmt -> if ( expression ) statement |
                      if ( expression ) statement else statement

Rozwiązanie dające zmodyfikowaną gramatykę byłoby wysoko cenione.

Author: akim, 2012-10-04
Source

3 answers

Jest o wiele prostsze rozwiązanie. Jeśli wiesz, jak działają parsery LR, to wiesz, że konflikt dzieje się tutaj: 

if ( expression ) statement * else statement

Gdzie gwiazda oznacza bieżącą pozycję kursora. Pytanie, na które parser musi odpowiedzieć, brzmi: "powinienem przesunąć, czy powinienem zmniejszyć". Zwykle chcesz powiązać else z najbliższym if, co oznacza, że chcesz teraz przesunąć else token. Redukcja teraz oznaczałaby, że chcesz, aby else czekała, aby związać się z "starszym" if.

Teraz ty chcesz "powiedzieć" generatorowi parsera, że "gdy występuje konflikt przesuń/zmniejsz między tokenem "else" a regułą "stm - > if (exp) stm", wtedy token musi wygrać". Aby to zrobić, "podaj nazwę" pierwszeństwa Twojej reguły (np. "then") i określ, że "then" ma mniej pierwszeństwa niż "else". Coś w stylu: 

// Precedences go increasing, so "then" < "else".
%nonassoc "then"
%nonassoc "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

Używając składni Bizona.

Właściwie, moja ulubiona odpowiedź to nawet dać "then" i "else" ten sam priorytet. Gdy precedensy są równe, aby zerwać remis pomiędzy tokenem, który chce być przesunięty, a regułą, która chce być zmniejszona, Bison / Yacc spojrzy na asocjację. Tutaj chcesz promować prawo-asocjację, że tak powiem (dokładniej, chcesz promować "shift"), więc: {]} 

%right "then" "else" // Same precedence, but "shift" wins.
Wystarczy.
 36
Author: akim,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-12 10:27:02

Musisz uznać fakt, że środek statement w przypadku if-else nie może być (lub kończyć się) zwisającym if (lub if bez else.) Najprostszym sposobem na to jest podzielenie reguły stmt na dwie części: 

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if ->
    if ( expression ) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if |
    ...other statements not ending with dangling if...
stmt-ending-with-dangling-if ->
    if ( expression ) stmt |
    if ( expression ) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if |
    ...other statements ending with dangling if...

Każda inna reguła stmt -> whatever Gdzie whatever nie kończy się na stmt wchodzi w reguła stmt-not-ending-with-if, podczas gdy każda stmt reguła, która kończy się na stmt, jest dzielona na dwie wersje; Wersja {[10] } w regule not-ending-with-if i wersja dangling-if w regule dangling-if zasada.

Edit

Bardziej kompletna gramatyka z innymi produkcjami: 

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if :
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if |
    WHILE '(' expr ')' stmt-not-ending-with-dangling-if |
    DO stmt WHILE '(' expr ')' ';' |
    expr ';' |
    '{' stmt-list '}'
stmt-ending-with-dangling-if:
    IF '(' expr ')' stmt |
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if |
    WHILE '(' expr ')' stmt-ending-with-dangling-if

Zasady takie jak WHILE (expr) stmt są dzielone na dwie części( ponieważ kończą się na stmt), podczas gdy zasady takie jak expr; nie.

 4
Author: Chris Dodd,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-10-04 18:22:36

Make if else higher level than normal statements, like: 

statements:
  statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
  if ( statement )
;
IfElse:
  IfStat else statement
;
 0
Author: harry,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-07-24 09:57:47