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

Question

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

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

Ваша проблема в том, что ваш вклад - это просто серия Exprs, бегите вместе без какого-либо разделителя между ними. Это означает, что:

4 - 2

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

4
-2

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

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

---

Я уверен, что это появляется где-то еще на SO, но я не могу найти его. Итак, вот как вы запрещаете использование унарного минуса в начале выражения, чтобы вы могли запускать выражения вместе без разделителей. Нетерминальные пусковые 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)