구문 트리 구현 시프트 사용/충돌 감소

Question

내 parser.y 파일에 충돌이 없었습니다. 그러나 구문 트리를 구성하는 동작을 도입하면 12 개의 새로운 시프트/감소 충돌이 발생했습니다. 너희들이 이것에 대해 어떤 생각을 갖고 있니?

아래로 내 parser.y 및 컴파일 로그가 있습니다.

Parser.y :

%{ 
#include <stdio.h> 
#include "main.h" 
#include "iks_ast.h" 
%} 

%union { 
    struct item_t *symbol; 
    struct node *tree; 
} 

%error-verbose 

/* Declaração dos tokens da linguagem */ 
%token TK_PR_INT 
%token TK_PR_FLOAT 
%token TK_PR_BOOL 
%token TK_PR_CHAR 
%token TK_PR_STRING 
%token TK_PR_IF 
%token TK_PR_THEN 
%token TK_PR_ELSE 
%token TK_PR_WHILE 
%token TK_PR_DO 
%token TK_PR_INPUT 
%token TK_PR_OUTPUT 
%token TK_PR_RETURN 
%token TK_OC_LE 
%token TK_OC_GE 
%token TK_OC_EQ 
%token TK_OC_NE 
%token TK_OC_AND 
%token TK_OC_OR 
%token<symbol> TK_LIT_INT 
%token<symbol> TK_LIT_FLOAT 
%token<symbol> TK_LIT_FALSE 
%token<symbol> TK_LIT_TRUE 
%token<symbol> TK_LIT_CHAR 
%token<symbol> TK_LIT_STRING 
%token<symbol> TK_IDENTIFICADOR 
%token TOKEN_ERRO 

%left TK_OC_OR TK_OC_AND 
%left '<' '>' TK_OC_LE TK_OC_GE TK_OC_EQ TK_OC_NE 
%left '+' '-' 
%left '*' '/' 

%nonassoc LOWER_THAN_ELSE 
%nonassoc TK_PR_ELSE 

%start programa 

%type<symbol> decl_var 
%type<symbol> cabecalho 
%type<tree> programa 
%type<tree> def_funcao 
%type<tree> expressao 
%type<tree> controle_fluxo 
%type<tree> comando 
%type<tree> chamada_funcao 
%type<tree> entrada 
%type<tree> saida 
%type<tree> lista_expressoes 
%type<tree> lista_expressoes_nao_vazia 
%type<tree> retorna 
%type<tree> bloco_comando 
%type<tree> seq_comando 
%type<tree> atribuicao 
%type<tree> vetor_indexado 

%% 

programa: decl_global programa {$$ = $2;} 
    | def_funcao programa {$$ = create_node(IKS_AST_PROGRAMA); $$ = insert_child($$,$1); $1 = AST_link($1,$2);} 
    | {$$=NULL;} 
    ; 

decl_global: decl_var ';' 
    | decl_vetor ';' 
    | decl_var {error("Faltando o ';' no final do comando.", $1->line); return IKS_SYNTAX_ERRO;} 
    ; 

decl_local: decl_var ';' decl_local 
    | 
    ; 


/* Declaracao de variaveis e tipos*/ 
decl_var 
    : tipo_var TK_IDENTIFICADOR {$$ = $2;} 
    ; 

decl_vetor 
    : tipo_var TK_IDENTIFICADOR '[' TK_LIT_INT ']' 
    ; 


tipo_var: TK_PR_INT 
     | TK_PR_FLOAT 
     | TK_PR_BOOL 
     | TK_PR_CHAR 
     | TK_PR_STRING 
     ; 

/* Declaracao de funcao */ 
def_funcao: cabecalho decl_local bloco_comando {$$ = create_node(IKS_AST_FUNCAO); $$ = insert_child($$,$3);} 
    | cabecalho decl_local bloco_comando ';' {error("Declaração de função com ';' no final do comando.\n",$1->line); return IKS_SYNTAX_ERRO;} 
    ; 

chamada_funcao 
    : TK_IDENTIFICADOR '(' lista_expressoes ')' {$$ = AST_ident_exp(IKS_AST_CHAMADA_DE_FUNCAO,$1,$3);} 
    ; 

cabecalho: decl_var '(' lista_parametros ')' {$$ = $1;} 
    ; 

lista_parametros: lista_parametros_nao_vazia 
    | 
    ; 

lista_parametros_nao_vazia: parametro ',' lista_parametros_nao_vazia 
    | parametro 
    ; 

parametro: decl_var 
    ; 

comando: bloco_comando {$$ = $1;} 
    | controle_fluxo {$$ = $1;} 
    | atribuicao {$$ = $1;} 
    | entrada {$$ = $1;} 
    | saida {$$ = $1;} 
    | retorna {$$ = $1;} 
    | decl_var ';' {$$ = NULL;} 
    | chamada_funcao {$$ = $1;} 
    | ';' {$$ = NULL;} 
    ; 

bloco_comando: '{' seq_comando '}' {$$ = create_node(IKS_AST_BLOCO); $$ = insert_child($$,$2);} 
    ; 

seq_comando: seq_comando comando {$$ = AST_link($1,$2); } 
    | /* empty */ {//não sei se precisa 
       $$ = NULL;} 
    ; 

/* Atribuicoes de variaveis */ 
atribuicao: TK_IDENTIFICADOR '=' expressao {$$ = AST_ident_exp(IKS_AST_ATRIBUICAO,$1,$3);} 
    | vetor_indexado '=' expressao {$$ = create_node(IKS_AST_ATRIBUICAO); $$ = insert_child($$,$1); $$ = insert_child($$,$3); } 
    ; 

vetor_indexado 
    : TK_IDENTIFICADOR '[' expressao ']' { $$ = AST_ident_exp(IKS_AST_VETOR_INDEXADO,$1,$3);} 
    ; 

/* Entrada e Saida (Input e Output) */ 
entrada 
    : TK_PR_INPUT TK_IDENTIFICADOR {$$ = create_node(IKS_AST_INPUT); $$ = AST_input($$,$2);} 
    ; 

saida 
    : TK_PR_OUTPUT lista_expressoes_nao_vazia {$$ = create_node(IKS_AST_OUTPUT); $$ = insert_child($$,$2);} 
    ; 

lista_expressoes_nao_vazia: expressao ',' lista_expressoes_nao_vazia {$$ = AST_link($1,$3);} 
    | expressao {$$ = $1;} 
    ; 

retorna: TK_PR_RETURN expressao ';' {$$ = create_node(IKS_AST_RETURN); $$ = insert_child($$,$2);} 
    ; 

/* Fluxo de Controle */ 
controle_fluxo 
    : TK_PR_IF '(' expressao ')' TK_PR_THEN comando %prec LOWER_THAN_ELSE {$$ = AST_if($3,$6,NULL);} 
    | TK_PR_IF '(' expressao ')' TK_PR_THEN comando TK_PR_ELSE comando {$$ = AST_if($3,$6,$8);} 
    | TK_PR_WHILE '(' expressao ')' TK_PR_DO comando {$$ = AST_while(IKS_AST_WHILE_DO,$3,$6);} 
    | TK_PR_DO comando TK_PR_WHILE '(' expressao ')' {$$ = AST_while(IKS_AST_DO_WHILE,$2,$5);} 
    ; 

expressao: TK_IDENTIFICADOR {$$ = AST_ident_literal(IKS_AST_IDENTIFICADOR,$1);} 
    | TK_IDENTIFICADOR '[' expressao ']' {$$ = AST_ident_exp(IKS_AST_VETOR_INDEXADO,$1,$3);} 
    | TK_LIT_INT {$$ = AST_ident_literal(IKS_AST_LITERAL,$1);} 
    | TK_LIT_FLOAT {$$ = AST_ident_literal(IKS_AST_LITERAL,$1);} 
    | TK_LIT_FALSE {$$ = AST_ident_literal(IKS_AST_LITERAL,$1);} 
    | TK_LIT_TRUE {$$ = AST_ident_literal(IKS_AST_LITERAL,$1);} 
    | TK_LIT_CHAR {$$ = AST_ident_literal(IKS_AST_LITERAL,$1);} 
    | TK_LIT_STRING {$$ = AST_ident_literal(IKS_AST_LITERAL,$1);} 
    | expressao '+' expressao {$$ = create_node(IKS_AST_ARIM_SOMA); $$ = AST_expression($$,$1,$3); } 
    | expressao '-' expressao {$$ = create_node(IKS_AST_ARIM_SUBTRACAO); $$ = AST_expression($$,$1,$3); } 
    | expressao '*' expressao {$$ = create_node(IKS_AST_ARIM_MULTIPLICACAO); $$ = AST_expression($$,$1,$3); } 
    | expressao '/' expressao {$$ = create_node(IKS_AST_ARIM_DIVISAO); $$ = AST_expression($$,$1,$3); } 
    | expressao '<' expressao {$$ = create_node(IKS_AST_LOGICO_COMP_L); $$ = AST_expression($$,$1,$3); } 
    | expressao '>' expressao {$$ = create_node(IKS_AST_LOGICO_COMP_G); $$ = AST_expression($$,$1,$3); } 
    | '+' expressao {$$ = $2;} 
    | '-' expressao {$$ = create_node(IKS_AST_ARIM_INVERSAO); $$ = AST_expression($$,$2,NULL);} 
    | '(' expressao ')' {$$ = $2;} 
    | expressao TK_OC_LE expressao {$$ = create_node(IKS_AST_LOGICO_COMP_LE); $$ = AST_expression($$,$1,$3);} 
    | expressao TK_OC_GE expressao {$$ = create_node(IKS_AST_LOGICO_COMP_GE); $$ = AST_expression($$,$1,$3);} 
    | expressao TK_OC_EQ expressao {$$ = create_node(IKS_AST_LOGICO_COMP_IGUAL); $$ = AST_expression($$,$1,$3);} 
    | expressao TK_OC_NE expressao {$$ = create_node(IKS_AST_LOGICO_COMP_DIF); $$ = AST_expression($$,$1,$3);} 
    | expressao TK_OC_AND expressao {$$ = create_node(IKS_AST_LOGICO_E); $$ = AST_expression($$,$1,$3);} 
    | expressao TK_OC_OR expressao {$$ = create_node(IKS_AST_LOGICO_OU); $$ = AST_expression($$,$1,$3);} 
    | '!' expressao {$$ = create_node(IKS_AST_LOGICO_COMP_NEGACAO); $$ = AST_expression($$,$2,NULL);} 
    | chamada_funcao {$$ = $1;} 
    ; 

lista_expressoes: lista_expressoes_nao_vazia {$$ = $1;} 
    | {$$ = NULL;} 
    ; 
%% 

error(char *s, int line){ 
    printf("Erro na linha %d: %s", line,s); 
} 

로그 :

[ 10%] [BISON][parser] Building parser with bison 3.0.2 
parser.y: warning: 12 shift/reduce conflicts [-Wconflicts-sr] 
[ 20%] [FLEX][scanner] Building scanner with flex 2.5.35 
Scanning dependencies of target main 
[ 30%] Building C object CMakeFiles/main.dir/scanner.c.o 
scanner.l:11:1: warning: data definition has no type or storage class [enabled by default] 
scanner.l: In function ‘yylex’: 
scanner.l:84:16: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l:85:16: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l:87:16: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l:89:16: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l:91:16: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l:93:16: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l:95:17: warning: assignment makes pointer from integer without a cast [enabled by default] 
scanner.l: In function ‘install_id’: 
scanner.l:145:4: warning: return makes integer from pointer without a cast [enabled by default] 
[ 40%] Building C object CMakeFiles/main.dir/parser.c.o 
[ 50%] Building C object CMakeFiles/main.dir/src/main.c.o 
[ 60%] Building C object CMakeFiles/main.dir/src/comp_tree.c.o 
Linking C executable main 
[100%] Built target main 

Answer 1

갈등은 하나의 생산의 모든 결과이며 의미의 행동과는 아무 상관이 없다 시프트 줄일 수 있습니다.

생산은 다음과 같습니다

expressao : '!' expressao ; 

그리고 문제는 !가 우선 순위 목록에 표시되지 않는다는 것입니다.

또한 이진 버전에서 단 하나의 + 및 - 연산자를 구별하는 특정 선행 선언이 없기 때문에 문법이 예상대로 작동하지 않습니다. 결과적으로 -a*b은 (-a)*b이 아닌 -(a*b)으로 구문 분석됩니다. 물론, 정수 연산의 경우, 이것들은 같습니다만, 구문 트리를 올바로 취득하는 것이 더 깨끗합니다. 당신은 모든 %left 선언 후

%right '!' 

를 추가 한 다음 단항 + 및 - 제작의 끝에 %prec '!'을 추가하여 한 번에 이러한 문제를 모두 해결할 수 있습니다.

의미 론적 동작을 추가 할 때 문제가 왜 나타나는지 나는 알 수 없습니다. 아마도 !에 대한 작품도 추가했을 것입니다.