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

Question

У меня есть грамматика для арифметического выражения, которая решает количество выражений (по одному на строку) в текстовом файле. При компиляции YACC я получаю сообщение смену 2 смены конфликтов. Но мои расчеты правильные. Если синтаксический анализатор дает правильный результат, как он разрешает конфликт сдвига/уменьшения. И в моем случае есть какой-либо способ решить эту проблему в грамматике YACC.

YACC GRAMMAR

Calc : Expr    {printf(" = %d\n",$1);} 
    | Calc Expr   {printf(" = %d\n",$2);} 
    | error    {yyerror("\nBad Expression\n ");} 
    ; 
Expr : Term    { $$ = $1;   } 
    | Expr '+' Term  { $$ = $1 + $3; } 
    | Expr '-' Term  { $$ = $1 - $3; } 
    ; 
Term : Fact    { $$ = $1;   } 
    | Term '*' Fact  { $$ = $1 * $3; } 
    | Term '/' Fact  { if($3==0){ 
       yyerror("Divide by Zero Encountered."); 
      break;} 
       else 
       $$ = $1/$3;  
        } 
    ; 
Fact : Prim    { $$ = $1;  } 
    | '-' Prim   { $$ = -$2;  } 
    ;  
Prim : '(' Expr ')'  { $$ = $2;  } 
    | Id     { $$ = $1;  } 
    ; 
Id :NUM     { $$ = yylval; } 
    ; 

Какие изменения я должен сделать, чтобы удалить такие конфликты в моей грамматике?

Answer 1

Bison/yacc разрешает конфликты смены-сдвига, выбирая shift. Это объясняется в разделе bison manual в разделе о конфликтах Shift-Reduce.

Ваша проблема заключается в том, что ваш вход представляет собой всего лишь последовательность из Expr s, работая вместе без разделителя между ними. Это означает, что:

4 - 2 

может быть одно выражение (4-2) или это может быть два выражения (4, -2). Так как бизон генерируемые парсеры всегда предпочитают перекладывать, анализатор будет выбирать, чтобы разобрать его как одно выражение, даже если бы оно было напечатано на двух линиях:

4 
-2 

Если вы хотите, чтобы позволить пользователям вводить их выражения, как, что, без какого-либо разделителя, тогда вы можете либо жить с конфликтом (поскольку он относительно мягкий), либо вы можете кодифицировать его в свою грамматику, но это немного больше. Чтобы поместить его в грамматику, вам нужно определить два разных типа: Expr: один (тот, который вы используете на верхнем уровне) не может начинаться с унарного минуса, а другой (который вы можете использовать в другом месте) разрешено начинать с унарного минуса.

Я подозреваю, что вы действительно хотите использовать новые строки или какой-либо другой разделитель выражений. Это так же просто, как перенос новой строки через ваш парсер и изменение Calc на Calc: | Calc '\n' | Calc Expr '\n'.

Я уверен, что это появляется где-то в другом месте, но я не могу его найти. Итак, вот как вы запрещаете использование унарного минуса в начале выражения, чтобы вы могли запускать выражения вместе без разделителей. В нетерминалах начиная n_ не могут начинаться с унарным минус:

input: %empty | input n_expr { /* print $2 */ } 

expr: term | expr '+' term | expr '-' term 
n_expr: n_term | n_expr '+' term | n_expr '-' term 

term: factor | term '*' factor | term '/' factor 
n_term: value | n_term '+' factor | n_term '/' factor 

factor: value | '-' factor 

value: NUM | '(' expr ')' 

Это разбирает тот же язык, грамматика, но без создания сдвига, уменьшить конфликт. Поскольку он анализирует один и тот же язык, вход

4 
-2 

все равно будет разобран как единое выражение; чтобы получить ожидаемый результат, вам нужно будет ввести

4 
(-2)