les bisons se déplacent au lieu de se réduire. Avec des erreurs de réduction/réduction

Question

Dans ma langue, je peux écrire

a = 1

b = 2
if true { } else { }
if true { } **Here is the problem**
else {}

Ma grammaire ne prend pas en charge les retours à la ligne entre les déclarations. Un else ne peut être utilisé qu'avec un if. Lorsque j'ajoute optionalNL dans ma règle

IfExpr:
  IF rval optionalNL codeBlock optionalNL ELSE codeBlock
| IF rval optionalNL codeBlock

L'optionNL avant le else provoque 3 réductions/réductions. La raison en est qu'il peut réduire en utilisant la deuxième règle de IfExpr ou réduire en exprLoop où il permet de nombreuses nouvelles lignes entre les expressions.

Peu importe ce que je fais (j'ai essayé d'écrire %prec avant optionalNL et ELSE), il se réduit toujours à exprLoop ce qui fait que bison me donne une erreur synaxe sur else. Comment puis-je dire à Bison de décaler à ce point (vers optionalNL else) au lieu de réduire ? (vers exprLoop causant else comme une erreur).

fichier d'exemple à tester avec

%%
program:
      exprLoop;
exprLoop:
      exprLoop2 expr
    | exprLoop2
exprLoop2:
    | exprLoop2 expr EOS
    | exprLoop2 EOS
    ;   
expr:
      'i' Var optEOS '{' '}'
    | 'i' Var optEOS '{' '}' optEOS 'e' '{' '}'
EOS: '\n'   ;
Var: 'v';
optEOS: | optEOS EOS

%%

//this can be added to the lex file
[iev]                   { return *yytext; }

y.output http://www.pastie.org/707448

Alternative .y et sortie. Vous pouvez le voir regarder devant vous en voyant un \n et ne sait pas s'il faut réduire la règle ou continuer. Je change l'ordre des règles pour obtenir des résultats différents. Mais soit il s'attend toujours à un \n ou s'attend toujours à ce qu'il y ait une autre règle qui finit toujours par être ignorée. état 15

    9 expr: 'i' Var optEOS '{' '}' .  [$end, '\n']
   10     | 'i' Var optEOS '{' '}' . 'e' '{' '}'
   11     | 'i' Var optEOS '{' '}' . '\n' 'e' '{' '}'

    'e'   shift, and go to state 16
    '\n'  shift, and go to state 17

    '\n'      [reduce using rule 9 (expr)]
    $default  reduce using rule 9 (expr)

Merci à Kinopiko pour sa réponse

J'ai modifié son code pour qu'il n'y ait pas de conflits, puis j'ai travaillé à le rendre plus flexible. Voici mes fichiers

test.y

%{
#include <stdio.h>
%}

%%

program: expr                                   { printf ("First expr\n"); }
       | program expr                           { printf ("Another expr\n"); }

expr:
      if optEOS                                 { printf ("IF only\n"); }
    | if optEOS else optEOS                     { printf ("IF/ELSE\n"); }

if:   'i' Var optEOS '{' optEOS '}'
else: 'e' optEOS     '{' optEOS '}'
EOS:  '\n'
Var:  'v'
optEOS:
          | EOS optEOS                          { ;}//printf ("many EOS\n"); }
%%

int main(int argc, char **argv)
{
    int i;

    printf("starting\n");

    if(argc < 2) {
        printf("Reading from stdin\n");
        yyparse();
        return 0;
    }
    for(i = 1; i < argc; i++) {
        FILE *f;
        char fn[260];
        sprintf(fn, "./%s", argv[i]);
        f = fopen(fn, "r");
        if(!f) {
            perror(argv[i]);
            return (1);
        }
        printf("Running '%s'\n", argv[i]);
        yyrestart(f);
        yyparse();
        fclose(f);
        printf("done\n");
    }
    return 0;
}

test.y

%{
#include <stdio.h>
#include "y.tab.h"
%}    
%option noyywrap
%%
[ \t]               { }
\n                  { return *yytext; }
.                   { return *yytext; }
%%
int yyerror ()
{
    printf ("syntax error\n");
    exit (1);
}

un fichier de test qui s'exécute automatiquement après la compilation

i v { } 
i v { }
e { }
i v { }

e { }
i v { 
} e {
 }
i v { }

i v { } i v { } e { }

i v
{ } i v { } e { } i v { } e { 
} i v {
 } e 
{ }

Answer 1

Je ne comprends pas très bien votre problème, alors je suis parti de zéro :

C'est ma grammaire :

%{
#include <stdio.h>
%}

%%

program: expr                                   { printf ("First expr\n") }
       | program EOS                            { printf ("Ate an EOS\n") }
       | program expr                           { printf ("Another expr\n") }

expr:
      ifeos                                     { printf ("IF only\n"); }
    | ifelse                                    { printf ("IF/ELSE\n"); }

ifelse: ifeos else
      | if else

ifeos: if EOS
     | ifeos EOS

if:   'i' Var optEOS '{' '}'
else: 'e' '{' '}'
EOS:  '\n'
Var:  'v'
optEOS:
          | EOS optEOS                          { printf ("many EOS\n") }
%%

Voici le lexer :

%{
#include <stdio.h>
#include "1763243.tab.h"
%}    
%option noyywrap
%%
[iev\{\}\n]                  { return *yytext; }
\x20                         { }
%%
int yyerror ()
{
    printf ("syntax error\n");
    exit (1);
}
int main () {
    yyparse ();
}

Voici quelques données d'essai :

i v { } 
i v { }
e { }
i v { }

e { }
i v { } e { }
i v { }

Voici le résultat :

IF only
First expr
IF/ELSE
Another expr
Ate an EOS
IF/ELSE
Another expr
Ate an EOS
IF/ELSE
Another expr
Ate an EOS
IF only
Another expr

Il existe un conflit entre le déplacement et la réduction restants.

Answer 2

Selon 'Lex & Yacc', la résolution par défaut de la réduction/réduction est la première règle définie, donc comme vous le dites, l'exprLoop l'emporte, donc je suppose qu'elle est définie en premier.

Mais le changement d'ordre peut ne pas résoudre le problème comme vous le souhaitez.

En poursuivant la lecture (page 237), il semble que vous ayez besoin de regarder plus en avant, ce qui n'est pas une option pour yacc/bison standard. Mais Bison dispose d'un GLR mode qui peuvent être utiles.

Answer 3

Une chose que vous pouvez faire est d'analyser complètement les nouvelles lignes en utilisant une règle lex pour elles. De cette façon, l'endroit où se trouvent les retours à la ligne n'a pas d'importance. C'est ce que font C/C++... les retours à la ligne sont largement ignorés.

Answer 4

Le problème est le suivant :

IfExpr:
  IF rval optionalNL codeBlock optionalNL ELSE codeBlock
| IF rval optionalNL codeBlock

nécessite un lookahead de deux jetons après le bloc de code pour voir le "else" après la nouvelle ligne, si c'est ce qu'il y a. Vous pouvez éviter cela en dupliquant l'optionalNL dans les deux règles if :

IfExpr:
  IF rval optionalNL codeBlock optionalNL ELSE codeBlock
| IF rval optionalNL codeBlock optionalNL

Maintenant, l'analyseur syntaxique n'a pas à décider entre les deux règles avant que l'optionalNL ne soit analysé, ce qui lui permet de voir le ELSE (ou son absence) dans le lookahead à un jeton.

Un inconvénient potentiel ici est que la deuxième règle if (mais pas la première) absorbera maintenant toute nouvelle ligne de queue, donc si votre grammaire pour les programmes exige une nouvelle ligne entre chaque déclaration, elle n'en trouvera pas après les ifs sans elses et elle a déjà été consommée.