Как исправить ошибку yacc: (конфликты: 3 сдвига / уменьшения) - PullRequest
Новая
       2

Как исправить ошибку yacc: (конфликты: 3 сдвига / уменьшения)

1 голос
/ 23 ноября 2011

Как исправить ошибку yacc: (конфликты: 3 сдвига / уменьшения) 

%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char *scat2(char *a1,char *a2) {
char *t;
t = malloc( strlen(a1) + strlen(a2) + 1 );
strcat( t, a1 );
strcat( t, a2 );
return t;
}
char *scat3(char *a1,char *a2,char *a3) {
return scat2(scat2(a1,a2),a3);
}
char *scat4(char *a1,char *a2,char *a3,char *a4) {
return scat2(scat3(a1,a2,a3),a4);
}
char *scat5(char *a1,char *a2,char *a3,char *a4,char *a5) {
return scat2(scat4(a1,a2,a3,a4),a5);
}
char *scat6(char *a1,char *a2,char *a3,char *a4,char *a5, char *a6) {
return scat2(scat5(a1,a2,a3,a4,a5),a6);
}
char *scat7(char *a1,char *a2,char *a3,char *a4,char *a5, char *a6, char *a7) {
return scat2(scat6(a1,a2,a3,a4,a5,a6),a7);
}
%}
%union {
char *name;
}
%start program
%token ASSIGN NEG IF THEN ELSE TRUE FALSE EQ AND LE WHILE DO SKIP
%token <name> ID INTdenotation
%type <name> stmnt_list stmnt a_expr b_expr b_exp
%type <name> sum term primary
%%
program : stmnt_list
{ printf("%s\n", $1); }
;
stmnt_list : stmnt
{ $$ = $1; }
| stmnt_list ';' stmnt
{ $$ = scat5("Comp (",$1,") (",$3,")"); }
| '(' stmnt_list ')'
{ $$ = $2; }
;
stmnt : SKIP
{ $$ = "Skip"; }
| IF b_expr THEN stmnt_list ELSE stmnt_list
{ $$ = scat7("If (",$2,") (",$4,") (",$6,")"); }
| WHILE b_expr DO stmnt_list
{ $$ = scat5("While (",$2,") (",$4,")"); }
| ID ASSIGN a_expr
{ $$ = scat5("Ass \"", $1, "\" (",$3,")"); }
;
b_expr : b_expr AND b_exp
{ $$ = scat5("And (",$1,") (",$3,")"); }
| b_exp
{ $$ = $1; }
;
b_exp : TRUE
{ $$ = "TRUE"; }
| FALSE
{ $$ = "FALSE"; }
| a_expr EQ a_expr
{ $$ = scat5("Eq (",$1,") (",$3,")"); }
| a_expr LE a_expr
{ $$ = scat5("Le (",$1,") (",$3,")"); }
| NEG b_expr
{ $$ = scat3("Neg (",$2,")"); }
| '(' b_expr ')'
{ $$ = $2; }
;
a_expr : sum
{ $$ = $1; }
;
sum : term
{ $$ = $1; }
| sum '+' term
{ $$ = scat5("Add (",$1,") (",$3,")"); }
| sum '-' term
{ $$ = scat5("Sub (",$1,") (",$3,")"); }
;
term : primary
{ $$ = $1; }
| term '*' primary
{ $$ = scat5("Mult (",$1,") (",$3,")"); }
;
primary : INTdenotation
{ $$ = scat2("N ", $1); }
| ID
{ $$ = scat3("V \"", $1,"\""); }
| '(' a_expr ')'
{ $$ = $2; }
;
%%
#include "lex.yy.c"
main()
{
yyparse();
}

1 Ответ

4 голосов
/ 23 ноября 2011

Используйте параметр -v, чтобы создать файл y.output, содержащий более подробную информацию о грамматике и конфликтах.В вашем случае у вас есть три конфликта, которые возникают из-за двух неоднозначностей в грамматике.

Во-первых, правило bexpr : NEG b_expr означает, что вход, такой как NEG a AND b, может быть проанализирован как NEG ( a AND b ) или (NEG a) AND b,Если вы хотите последнее, вы должны переместить производство NEG в primary как (например, primary : NEG primary)

В файле y.output это проявляется как конфликт в состоянии между сокращениемправило NEG и смещение правила AND, что-то вроде: 

state 26

    9 b_expr: b_expr . AND b_exp
   15 b_exp: NEG b_expr .

    AND  shift, and go to state 30

    AND       [reduce using rule 15 (b_exp)]
    $default  reduce using rule 15 (b_exp)

Вы можете видеть, как это отображается непосредственно в приведенном выше примере.

Во-вторых, у вас есть 'проблема висячих операторов в правилах IF и WHILE.Для ввода, которое выглядит примерно так: WHILE x DO a; b, он не может сказать, должны ли оба оператора быть в цикле или после него (например, это (WHILE x DO a); b или WHILE x DO (a; b);. Чтобы это исправить, вы, вероятно, хотитеиметь только один stmnt после DO или ELSE вместо stmnt_list

Если вы посмотрите в файле y.output на два других состояния конфликта, вы снова увидите это немедленно

...