Опитвам се да намеря конфликт Shift/Reduce в граматиката

Имам следната граматика (Yacc), която е началото на прост C компилатор, започвам от прост израз if:

S : E
  ;

E : COND_NO_ELSE
  ;

COND_NO_ELSE : IF BOOL_EXP BLOCK
;

BLOCK : LC EXP RC

BOOL_EXP : LP EXP BOOL_OP EXP RP
     ;

BOOL_OP : LT_OP
     | GT_OP
     | LE_OP
     | GE_OP
     | EQ_OP
     | NE_OP
     ;

MATH_OP : PLUS_OP
    ;

EXP : IDENTIFIER
    | EXP MATH_OP EXP
    ;

Ето скенера на лексикалния анализатор за съответните правила:

"="       { yylval.string = strdup(yytext); return ASSIGN;}
"+"       { yylval.string = strdup(yytext); return PLUS_OP;}
"-"       { yylval.string = strdup(yytext); return MINUS_OP;}
"*"       { yylval.string = strdup(yytext); return MULTIPLY_OP;}
"/"       { yylval.string = strdup(yytext); return DIV_OP;}
"%"       { yylval.string = strdup(yytext); return MOD_OP;}

"<"       { yylval.string = strdup(yytext); return LT_OP;}
">"       { yylval.string = strdup(yytext); return GT_OP; }
"<="       { yylval.string = strdup(yytext); return LE_OP; }
">="       { yylval.string = strdup(yytext); return GE_OP; }
"=="       { yylval.string = strdup(yytext); return EQ_OP; }
"!="       { yylval.string = strdup(yytext); return NE_OP; }
"("       { yylval.string = strdup(yytext); return LP; }
")"       { yylval.string = strdup(yytext); return RP; }
"{"       { yylval.string = strdup(yytext); return LC; }
"}"       { yylval.string = strdup(yytext); return RC; }
if { return IF; }

Знам, че конфликтът започна, когато добавих MATH_OP (имах всички математически оператори от и получих 5 конфликта, след което премахнах всички освен PLUS_OP и получих 1 конфликт за преместване/намаляване).

използвах флага -v за изходния файл, както беше предложено тук, и проверих този въпрос, но не твърде много ми прилича на граматиката...

Как мога да намеря конфликта?


parsing compilation grammar yacc bison
person argamanza    schedule 16.12.2016    source източник

Отговори (1)


arrow_upward
2
arrow_downward

Вашата граматика включва продукцията:

EXP : EXP MATH_OP EXP

което по своята същност е двусмислено. Да предположим, че имате два оператора:

1 + 2 * 3

Очевидно горното е EXP MATH_OP EXP (защото няма друга опция), но това ли е

[EXP: 1 + 2] [MATH_OP *] [EXP: 3]

or is it

[EXP: 1] [MATH_OP +] [EXP: 2 * 3]

Тези два анализа очевидно имат различна семантика и граматиката позволява и двете.

Дори ако имате един оператор, има неяснота (всъщност същата неяснота), въпреки че се случва с обичайната дефиниция на + оценката да бъде същата. (Би било различно с единичния оператор -, което прави неяснотата малко по-ясна.)

Има две нормални стратегии за създаване на граматика на yacc/bison за аритметични изрази:

  1. Изрично посочете как трябва да се анализират изразите. (Пример от Уикипедия).

  2. Използвайте декларации за приоритет, за да ограничите имплицитно анализа. (Пример от ръководството на bison.)

Първата стратегия е по-словна, но по-гъвкава; вероятно е по-добре, ако се опитвате да научите как работи анализирането на LR, защото е изрично. Втората стратегия е по-компактна и може би по-лесна за четене (тъй като много случайни читатели разбират списъците с приоритет на операторите по-добре от контекстно-свободните граматики), но разбирането как работи в детайли е малко повече работа.

И в двата случая не можете просто да съберете всички оператори в един нетерминал като MATH_OP, защото операторите с различни приоритети са синтактично различни.

В този сайт ще намерите и много уместни въпроси и отговори.

Между другото, много рядко е полезно да се предаде стойността на низа на чисто синтактичен токен като + към анализатора. Анализаторът няма нужда от тази стойност, тъй като вече знае типа на токена, така че strdup() е ненужен излишък и съответното free() пречи на граматическите действия (също така, не е очевидно къде да го поставите). Ако смятате, че имате нужда от низовете, за да проследите граматичните действия, вижте съоръженията за отстраняване на грешки на bison, които са много по-лесни за използване и по-надеждни от пръскането на printfs във вашия анализатор. Ако изобщо не използвате семантичната стойност за операторите, тогава очевидно не е нужно да си правите труда да дублирате низ и след това да освободите или изтече паметта.

person rici    schedule 16.12.2016