Shift réduire les conflits
https://stackoverflow.com/questions/196179
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai du mal à comprendre le décalage / réduire le conflit pour une grammaire que je sais sans ambiguïté. Le cas est l'un des types if else, mais ce n'est pas le problème du problème, car j'ai des clauses END obligatoires qui délimitent les blocs de code.
Voici la grammaire de gppg (c'est un compilateur compilateur de type Bison ... et ce n'était pas un écho):
%output=program.cs
%start program
%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%
program : statements
;
statements : /*empty */
| statements stmt
;
stmt : flow
| THINGS
;
flow : '#' IF '(' ')' statements else
;
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Voici la sortie du conflit:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 10: else -> elseifs
Shift "'#'": State-22 -> State-23
Items for From-state State 22
10 else: elseifs .
-lookahead: '#', THINGS, EOF
11 elseifs: elseifs . '#' ELSEIF statements else
Items for Next-state State 23
11 elseifs: elseifs '#' . ELSEIF statements else
// End conflict information for parser
J'ai déjà tout échangé, et je sais comment le résoudre, mais cette solution implique de renoncer à la récursivité de gauche sur 'elseif' pour une récursivité de droite.
J'ai parcouru toute la documentation rare que j'ai trouvée sur Internet à propos de ce problème (je poste quelques liens à la fin) et je n'ai toujours pas trouvé de solution élégante. Je connais ANTLR et je ne veux pas en parler maintenant. Veuillez limiter votre solution aux analyseurs syntaxiques Yacc / Bison.
J'apprécierais des solutions élégantes, j'ai réussi à le faire en éléminant les règles / * empty * / / et en dupliquant tout ce qui nécessitait une liste vide, mais dans la grammaire plus large dans laquelle je travaillais.
Voici quelques liens:
http://nitsan.org/~maratb/cs164/bison.html
http://compilers.iecc.com/comparch/article/98- 01-079
La solution
Votre règle ELSEIF révisée ne comporte pas de marqueur pour une condition; elle devrait normalement avoir "(" et ")" ajoutée.
Plus sérieusement, vous avez maintenant une règle pour
elsebody : else
| elseifs else
;
et
elseifs : /* Nothing */
| elseifs ...something...
;
Le "rien" n'est pas nécessaire; il est implicitement pris en charge par le 'elsebody' sans les 'elseifs'.
Je serais très enclin à utiliser les règles 'opt_elseifs', 'opt_else' et 'end':
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
Je n’ai pas lu cela avec un générateur d’analyseur, mais je trouve cela relativement facile à comprendre.
Autres conseils
Je pense que le problème réside dans la clause elseifs.
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Je pense que la première version n'est pas obligatoire, car la clause else renvoie quand même à elseifs:
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
Que se passe-t-il si vous changez d'alternative?:
elseifs : '#' ELSEIF statements else
;
La réponse de Jonathan ci-dessus semble être la meilleure solution, mais comme cela ne fonctionne pas pour vous, voici quelques suggestions que vous pouvez essayer et qui vous aideront à corriger l'erreur.
D'abord, avez-vous envisagé de faire du symbole de hachage / symbole une partie des jetons eux-mêmes (c'est-à-dire #END, #IF, etc.)? Pour qu'ils soient enlevés par le lexer, ce qui signifie qu'ils ne doivent pas nécessairement être inclus dans l'analyseur.
Deuxièmement, je vous exhorte à réécrire les règles sans dupliquer les flux de jetons. (Partie du principe «ne vous répétez pas»). Ainsi, la règle " '#' Autres déclarations ELSEIF " ne devrait exister qu’à un seul endroit de ce fichier (et non deux comme ci-dessus).
Enfin, je vous suggère d’examiner la priorité et l’associativité des jetons IF / ELSEIF / ELSE. Je sais que vous devriez être capable d’écrire un analyseur syntaxique qui n’exige pas cela, mais c’est peut-être ce dont vous avez besoin dans ce cas.
Je change toujours de sujet, et ma question initiale comportait des erreurs car la séquence elseifs comportait toujours un autre à la fin, ce qui était faux. Voici une autre prise à la question, cette fois-ci, je reçois deux conflits d’atténuation / réduction:
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
Les conflits sont désormais les suivants:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 12: elseifs -> /* empty */
Shift "'#'": State-10 -> State-13
Items for From-state State 10
7 flow: '#' IF '(' ')' statements . elsebody
4 statements: statements . stmt
Items for Next-state State 13
10 else: '#' . ELSE statements '#' END
11 else: '#' . END
7 flow: '#' . IF '(' ')' statements elsebody
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
Shift "'#'": State-24 -> State-6
Items for From-state State 24
13 elseifs: elseifs '#' ELSEIF statements .
-lookahead: '#'
4 statements: statements . stmt
Items for Next-state State 6
7 flow: '#' . IF '(' ')' statements elsebody
// End conflict information for parser
Les règles vides ne font qu'aggraver le gppg, j'ai peur. Mais ils semblent si naturels que je continue à les utiliser.
Je sais déjà que la bonne récursivité résout le problème comme le dit 1800 INFORMATION . Mais je cherche une solution avec une récursivité gauche sur la clause elseifs .
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
Je pense que cela devrait laisser recurse et toujours se terminer.
OK - voici une grammaire (non minimale) pour if blocks. Je l'ai extrait de mon code (appelé adhoc, basé sur hoc de Kernighan & Plauger's "The UNIX Programming Environment"). Cette esquisse de grammaire est compilée avec Yacc sans aucun conflit.
%token NUMBER IF ELSE
%token ELIF END
%token THEN
%start program
%%
program
: stmtlist
;
stmtlist
: /* Nothing */
| stmtlist stmt
;
stmt
: ifstmt
;
ifstmt
: ifcond endif
| ifcond else begin
| ifcond eliflist begin
;
ifcond
: ifstart cond then stmtlist
;
ifstart
: IF
;
cond
: '(' expr ')'
;
then
: /* Nothing */
| THEN
;
endif
: END IF begin
;
else
: ELSE stmtlist END IF
;
eliflist
: elifblock
| elifcond eliflist begin /* RIGHT RECURSION */
;
elifblock
: elifcond else begin
| elifcond endif
;
elifcond
: elif cond then stmtlist end
;
elif
: ELIF
;
begin
: /* Nothing */
;
end
: /* Nothing */
;
expr
: NUMBER
;
%%
J'ai utilisé 'NUMBER' comme élément factice, au lieu de THINGS, et j'ai utilisé ELIF au lieu de ELSEIF. Il comprend un THEN, mais c'est optionnel. Les opérations "begin" et "end" ont été utilisées pour saisir le compteur de programme dans le programme généré - et devraient donc pouvoir être retirées sans que cela ne le gêne.
Il y avait une raison pour laquelle je pensais que je devais utiliser la récursion droite au lieu de la récursion gauche normale - mais je pense que cela avait à voir avec la stratégie de génération de code que j'utilisais, plutôt qu'autre chose. Le point d'interrogation dans le commentaire était dans l'original; Je me souviens de ne pas en être heureux. Le programme dans son ensemble fonctionne - il s'agit d'un projet qui est en veilleuse depuis une dizaine d'années (hmmm ... j'ai travaillé à la fin de 2004 et au début de 2005; avant cela, c'était en 1992 et 1993).
Je n'ai pas passé le temps à comprendre pourquoi cette compilation est sans conflit et ce que j'ai décrit précédemment ne le fait pas. J'espère que ça aide.
