Попытка найти конфликт сдвига / уменьшения в грамматике

У меня есть следующая грамматика (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, которые намного проще в использовании и надежнее, чем разбрасывание printf по всему парсеру. Если вы вообще не используете семантическое значение для операторов, то вам, очевидно, не нужно беспокоиться о дублировании строки, а затем освобождении или утечке памяти.

person rici    schedule 16.12.2016