이 yacc 파일에서 shift/reduce 충돌을 찾는 방법은 무엇입니까?

Question

다음 파일에서 yacc을 사용하려고하면 오류가 발생합니다 : 1 shift/reduce 어떻게 충돌을 찾아 해결할 수 있습니까?

/* C-Minus BNF Grammar */ 

%token ELSE 
%token IF 
%token INT 
%token RETURN 
%token VOID 
%token WHILE 

%token ID 
%token NUM 

%token LTE 
%token GTE 
%token EQUAL 
%token NOTEQUAL 
%% 

program : declaration_list ; 

declaration_list : declaration_list declaration | declaration ; 

declaration : var_declaration | fun_declaration ; 

var_declaration : type_specifier ID ';' 
       | type_specifier ID '[' NUM ']' ';' ; 

type_specifier : INT | VOID ; 

fun_declaration : type_specifier ID '(' params ')' compound_stmt ; 

params : param_list | VOID ; 

param_list : param_list ',' param 
      | param ; 

param : type_specifier ID | type_specifier ID '[' ']' ; 

compound_stmt : '{' local_declarations statement_list '}' ; 

local_declarations : local_declarations var_declaration 
        | /* empty */ ; 

statement_list : statement_list statement 
       | /* empty */ ; 

statement : expression_stmt 
      | compound_stmt 
      | selection_stmt 
      | iteration_stmt 
      | return_stmt ; 

expression_stmt : expression ';' 
       | ';' ; 

selection_stmt : IF '(' expression ')' statement 
       | IF '(' expression ')' statement ELSE statement ; 

iteration_stmt : WHILE '(' expression ')' statement ; 

return_stmt : RETURN ';' | RETURN expression ';' ; 

expression : var '=' expression | simple_expression ; 

var : ID | ID '[' expression ']' ; 

simple_expression : additive_expression relop additive_expression 
        | additive_expression ; 

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ; 

additive_expression : additive_expression addop term | term ; 

addop : '+' | '-' ; 

term : term mulop factor | factor ; 

mulop : '*' | '/' ; 

factor : '(' expression ')' | var | call | NUM ; 

call : ID '(' args ')' ; 

args : arg_list | /* empty */ ; 

arg_list : arg_list ',' expression | expression ; 

Answer 1

mientefuego는 문법에 고전적인 "dangling else"문제가 있음을 지적했습니다. 충돌을 일으키는 규칙에 우선 순위를 지정하여 문제를 해결할 수 있습니다. 충돌을 일으키는

규칙은 다음과 같습니다

selection_stmt : IF '(' expression ')' statement 
       | IF '(' expression ')' statement ELSE statement ; 

먼저 시작 ELSE 만들고 LOWER_THAN_ELSE (의사 토큰) 비 연관으로 :이 LOWER_THAN_ELSE 이상 ELSE 더 우선 순위를 제공

%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE 

단순히 LOWER_THAN_ELSE 때문에 먼저 선언됩니다.

다음

selection_stmt : IF '(' expression ')' statement %prec LOWER_THAN_ELSE ; 
       | IF '(' expression ')' statement ELSE statement ; 

이 더 높은 우선 순위가 변화에 주어진다 :

는 그런 충돌하는 규칙에 당신은 어느 이동에 우선 순위를 지정하거나 행동을 줄일 수 있습니다. 나는 위에서 언급 한 수정을 통합하고 아래의 완전한 문법을 ​​나열했습니다 :

/* C-Minus BNF Grammar */ 

%token ELSE 
%token IF 
%token INT 
%token RETURN 
%token VOID 
%token WHILE 

%token ID 
%token NUM 

%token LTE 
%token GTE 
%token EQUAL 
%token NOTEQUAL 

%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE 
%% 

program : declaration_list ; 

declaration_list : declaration_list declaration | declaration ; 

declaration : var_declaration | fun_declaration ; 

var_declaration : type_specifier ID ';' 
       | type_specifier ID '[' NUM ']' ';' ; 

type_specifier : INT | VOID ; 

fun_declaration : type_specifier ID '(' params ')' compound_stmt ; 

params : param_list | VOID ; 

param_list : param_list ',' param 
      | param ; 

param : type_specifier ID | type_specifier ID '[' ']' ; 

compound_stmt : '{' local_declarations statement_list '}' ; 

local_declarations : local_declarations var_declaration 
        | /* empty */ ; 

statement_list : statement_list statement 
       | /* empty */ ; 

statement : expression_stmt 
      | compound_stmt 
      | selection_stmt 
      | iteration_stmt 
      | return_stmt ; 

expression_stmt : expression ';' 
       | ';' ; 

selection_stmt : IF '(' expression ')' statement %prec LOWER_THAN_ELSE ; 
       | IF '(' expression ')' statement ELSE statement ; 

iteration_stmt : WHILE '(' expression ')' statement ; 

return_stmt : RETURN ';' | RETURN expression ';' ; 

expression : var '=' expression | simple_expression ; 

var : ID | ID '[' expression ']' ; 

simple_expression : additive_expression relop additive_expression 
        | additive_expression ; 

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ; 

additive_expression : additive_expression addop term | term ; 

addop : '+' | '-' ; 

term : term mulop factor | factor ; 

mulop : '*' | '/' ; 

factor : '(' expression ')' | var | call | NUM ; 

call : ID '(' args ')' ; 

args : arg_list | /* empty */ ; 

arg_list : arg_list ',' expression | expression ; 

Answer 2

처음에는 state machine output from yacc이 표시됩니다. 시프트되거나 감소 할 수있는 상태는 시프트/감소 충돌을 나타냅니다. 하나를 찾아 문법을 다시 작성하여 충돌을 해결하십시오.

Answer 3

어쩌면 당신은 yacc -v <filename>을 시도해야합니다, 그것은 세부 사항의 출력을 생성합니다.

여기에서 테스트했는데 고전적인 "dangling else"문제에서 문법 설명이 실패합니다.

this Wikipedia article을 살펴보십시오.

Answer 4

This 문서 ardsrk에 의해 게시 된 하나의 대안 솔루션을 제공합니다.

Answer 5

에헴,이 문제에 대한 정답은 보통 : 아무것도을하지 않는다.

불투명 한 문법이있는 은으로 예상됩니다. 그들은 오류이 아니며, 충돌이입니다.

줄이기를 선호하면 충돌을 해결할 수 있습니다.이 문제는 표준 문제가 해결되지 않은 경우에만 발생합니다. 정확히 N 충돌이있을 때 당신은 S/R 충돌 경고를하지 않도록

그리고 들소는 심지어 %를 가지고는 N 문을 기대합니다.