Shift Réduire les conflits

Question

Je n'arrive pas à résoudre un problème de réduction de conflit dans ma grammaire. J'ai essayé d'ajouter -v pour lire la sortie du problème et il me guide vers l'état 0 et mentionne que mes INT et FLOAT sont réduits à variable_definitions par la règle 9. Je ne vois pas le conflit et j'ai du mal à trouver une solution.

%{ 
#include <stdio.h> 
#include <stdlib.h> 
%} 

%token INT FLOAT 
%token ADDOP MULOP INCOP 
%token WHILE IF ELSE RETURN 
%token NUM ID 
%token INCLUDE 
%token STREAMIN ENDL STREAMOUT 
%token CIN COUT 
%token NOT 
%token FLT_LITERAL INT_LITERAL STR_LITERAL 


%right ASSIGNOP 
%left AND OR 
%left RELOP 

%% 
program: variable_definitions 
     | function_definitions 
     ; 
function_definitions: function_head block 
     | function_definitions function_head block 
     ; 
identifier_list: ID 
     | ID '[' INT_LITERAL ']' 
     | identifier_list ',' ID 
     | identifier_list ',' ID '[' INT_LITERAL ']' 
     ; 
variable_definitions: 
     | variable_definitions type identifier_list ';' 
     ; 
type:   INT 
     | FLOAT 
     ; 
function_head: type ID arguments 
     ; 
arguments: '('parameter_list')' 
     ; 
parameter_list: 
     |parameters 
     ; 
parameters: type ID 
     | type ID '['']' 
     | parameters ',' type ID 
     | parameters ',' type ID '['']' 
     ; 
block:  '{'variable_definitions statements'}' 
     ; 
statements: 
     | statements statement 
     ; 
statement: expression ';' 
     | compound_statement 
     | RETURN expression ';' 
     | IF '('bool_expression')' statement ELSE statement 
     | WHILE '('bool_expression')' statement 
     | input_statement ';' 
     | output_statement ';' 
     ; 
input_statement: CIN 
     | input_statement STREAMIN variable 
     ; 
output_statement: COUT 
     | output_statement STREAMOUT expression 
     | output_statement STREAMOUT STR_LITERAL 
     | output_statement STREAMOUT ENDL 
     ; 
compound_statement: '{'statements'}' 
     ; 
variable:  ID 
     | ID '['expression']' 
     ; 
expression_list: 
     | expressions 
     ; 
expressions: expression 
     | expressions ',' expression 
     ; 
expression: variable ASSIGNOP expression 
     | variable INCOP expression 
     | simple_expression 
     ; 
simple_expression: term 
     | ADDOP term 
     | simple_expression ADDOP term 
     ; 
term:   factor 
     | term MULOP factor 
     ; 
factor:  ID 
     | ID '('expression_list')' 
     | literal 
     | '('expression')' 
     | ID '['expression']' 
     ; 
literal:  INT_LITERAL 
     | FLT_LITERAL 
     ; 
bool_expression: bool_term 
     | bool_expression OR bool_term 
     ; 
bool_term: bool_factor 
     | bool_term AND bool_factor 
     ; 
bool_factor: NOT bool_factor 
     | '('bool_expression')' 
     | simple_expression RELOP simple_expression 
     ; 
%% 

Answer 1

Votre définition d'un program est qu'il est soit une liste de définitions variables ou une liste de définitions de fonction (program: variable_definitions | function_definitions;). Cela me semble un peu étrange. Et si je veux définir à la fois une fonction et une variable? Dois-je écrire deux programmes et les lier ensemble?

Ce n'est pas la cause de votre problème, mais le corriger résoudrait probablement aussi le problème. La cause immédiate est que function_definitions est une ou plusieurs définitions de fonction alors que variable_definitions correspond à zéro ou plusieurs définitions de variables. En d'autres termes, le cas de base de la récursivité function_definitions est une définition de fonction, tandis que le cas de base variable_definitions est la séquence vide. Ainsi, une liste de définitions de variables commence par une séquence vide.

Mais les définitions de fonctions et de variables commencent par type. Ainsi, si le premier jeton d'un programme est int, il peut s'agir du début d'une définition de fonction avec le type de retour int ou une définition variable de type int. Dans le premier cas, l'analyseur doit décaler le int afin de produire le cas de base function_definitions :; dans ce dernier cas, il convient de réduire immédiatement un variable_definitions cas de base vide.

Si vous vouliez vraiment qu'un programme soit des définitions de fonctions ou des définitions de variables, mais pas les deux. vous devrez faire variable_definitions avoir la même forme que function_definitions, en changeant le cas de base de vide à type identifier_list ';'. Ensuite, vous pouvez ajouter une production vide à program afin que l'analyseur puisse reconnaître les entrées vides.

Mais comme je le disais au début, vous voulez probablement un programme pour une suite de définitions, dont chacun pourrait être soit une variable ou une fonction:

program: %empty 
     | program type identifier_list ';' 
     | program function_head block 

---

Par ailleurs, vous interprétez mal le fichier de sortie produit par -v. Elle montre les actions suivantes pour l'état 0:

INT shift, and go to state 1 
FLOAT shift, and go to state 2 

INT  [reduce using rule 9 (variable_definitions)] 
FLOAT  [reduce using rule 9 (variable_definitions)] 

Ici, INT et FLOAT sont possibles lookaheads. Donc, l'interprétation de la ligne INT [reduce using rule 9 (variable_definitions)] est "si le lookahead est INT, réduire immédiatement en utilisant la production 9". La production 9 produit la séquence vide, de sorte que la réduction réduit les jetons de zéro en haut de la pile de l'analyseur en un variable_definitions. Les réductions n'utilisent pas le jeton lookahead, donc après la réduction, le jeton lookahead est toujours INT.

Cependant, l'analyseur syntaxique ne le fait pas car il a une action différente pour INT, qui consiste à le décaler et à passer à l'état 1, comme indiqué par la première ligne de début INT. Les parenthèses [...] indiquent que cette action n'est pas prise parce que c'est un conflit et que la résolution du conflit était une autre action.Donc, l'interprétation la plus précise de cette ligne est "si ce n'était pas pour l'action précédente sur INT, le lookahead INT provoquerait une réduction en utilisant la règle 9."