règles de grammaire bison pour un langage pascal personnalisé

Question

J'essaye de faire un compilateur pour un langage personnalisé pascal en utilisant bison et flex et je finis par obtenir des erreurs de syntaxe pour les programmes qui devraient être corrects selon ma grammaire personnalisée.

Ma grammaire personnalisée:

<program>  ::=  program id 
<block> 
<block>  ::=  { 
<sequence> 
} 
<sequence>  ::=  <statement> (; <statement>)* 
<brackets-seq> ::=  { <sequence> } 
<brack-or-stat> ::=  <brackets-seq> | 
<statement> 
<statement>   ::=  ε | 
       <assignment-stat> | 
       <if-stat> | 
       <while-stat> 
<assignment-stat> ::=  id := <expression> 
<if-stat>  ::=  if (<condition>) 
<brack-or-stat> 
<elsepart> 
<elsepart>  ::=  ε | 
else <brack-or-stat> 
<while-stat>  ::=  while (<condition>) 
<brack-or-stat> 
<expression>  ::=  <optional-sign> <term> (<add-oper> <term>)* 
<term>  ::=  <factor> (<mul-oper> <factor>)* 
<factor>  ::=  constant | 
(<expression>) | 
id 
<condition>  ::=  <boolterm> (and <boolterm>)* 
<boolterm>  ::=  <boolfactor> (or <boolfactor>)* 
<boolfactor>  ::= not [<condition>] | 
[<condition>] | 
       <expression> <relational-oper> <expression> 
<relational-oper> ::=  == | < | > | <> | <= | >= 
<add-oper>  ::=  + | - 
<mul-oper>  ::=  * |/
<optional-sign>  ::=  ε | <add-oper> 

Ma mise en œuvre de la grammaire sur le bison:

%{ 
    #include <stdio.h> 
    #include <string.h> 
    int yylex(void); 
    void yyerror(char *s); 
%} 

%union { 
    int i; 
    char *s; 
}; 

%token <i> INTEGERNUM 

%token PROGRAM; 
%token OR; 
%token AND; 
%token NOT; 
%token IF; 
%token ELSE; 
%token WHILE; 
%token PLUS; 
%token MINUS; 
%token MUL; 
%token DIV; 
%token LSB; 
%token RSB; 
%token LCB; 
%token RCB; 
%token LEFTPAR; 
%token RIGHTPAR; 
%token ID; 
%token INT; 
%token ASSIGN; 
%token ISEQUAL; 
%token LTHAN; 
%token GTHAN; 
%token NOTEQUAL; 
%token LESSEQUAL; 
%token GREATEREQUAL; 

%left '+' '-' 
%left '*' '/' 

%% 

program: 
     PROGRAM ID block 
     ; 

block: 
     LCB RCB 
     |LCB sequence RCB 
     ; 

sequence: 
     statement ';'sequence 
     |statement ';' 
     ; 

bracketsSeq: 
     LCB sequence RCB 
     ; 

brackOrStat:   
     bracketsSeq 
     |statement 
     ; 

statement: 
     assignmentStat 
     |ifStat 
     |whileStat 
     | 
     ; 

assignmentStat: 
     ID ':=' expression 

ifStat: 
     IF LEFTPAR condition RIGHTPAR brackOrStat elsepart 
     ; 

elsepart: 
     ELSE brackOrStat 
     | 
     ; 

whileStat: 
     WHILE LEFTPAR condition RIGHTPAR brackOrStat 
     ; 

expression: 
     addOper expression 
     |expression addOper expression 
     |term 
     ; 

term: 
     term mulOper term 
     |factor 
     ; 

factor: 
     INT 
     |LEFTPAR expression RIGHTPAR 
     |ID 
     ; 

condition: 
     condition AND condition 
     |boolterm 
     ; 

boolterm: 
     boolterm OR boolterm 
     |boolfactor 
     ; 

boolfactor: 
     NOT LSB condition RSB 
     |LSB condition RSB 
     |expression relationalOper expression 
     ; 

relationalOper: 
     ISEQUAL 
     |LTHAN 
     |GTHAN 
     |NOTEQUAL 
     |LESSEQUAL 
     |GREATEREQUAL 
     ; 

addOper: 
     PLUS 
     |MINUS 
     ; 

mulOper: 
     MUL 
     |DIV 
     ; 

optionalSign 

     |addOper 
     ; 


%% 

int main(int argc, char **argv) 
{ 
      extern FILE *yyin; 
      ++argv, --argc; /* skip over program name */ 
      if (argc > 0) 
        yyin = fopen(argv[0], "r"); 
      else 
        yyin = stdin; 

      do 
       yyparse(); 
      while(!feof(yyin)); 
}  

Ma mise en œuvre de flex est assez simple où je reviens juste des jetons pour chaque symbole ou un identifiant nécessaire.

En utilisant ma mise en œuvre du programme simple:

program circuit 
{ 
    a:=b; 
} 

Je finissent par obtenir une erreur de syntaxe. Plus précisément lorsque l'analyse syntaxique atteint le point juste après := selon mes impressions de débogage J'utilise:

$ ./a.exe verilog.txt 
text = program 
text = circuit val = circuit 
text = { 
text = a val = a 
text = := 
syntax error 

C'est la première fois que je l'utilise flex et bison donc je devine que je fait une mauvaise mise en œuvre de ma grammaire originale à bisons depuis après la commande ./bison.exe -dy comp.y je reçois:

conflits bison 64 changement/réduire

Toutes les idées seraient utiles. Merci!

Answer 1

Cette règle:

assignmentStat: ID ':=' expression 

utilise un jeton « : = » qui bison donne un code distinct de tout autre ordre d'idées, et que votre lexer n'a aucun moyen de savoir, de sorte que vous êtes presque certainement pas revenir il. Vous êtes probablement revenir ASSIGN pour la séquence de caractères « : = », si vous voulez:

assignmentStat: ID ASSIGN expression 

Pour les quarts-de réduire les conflits, ils veulent dire que l'analyseur ne correspond pas exactement à la langue que vous avez spécifié, mais plutôt un sous-ensemble (déterminé par le décalage par défaut au lieu de réduire). Vous pouvez utiliser l'option -v de bison pour obtenir une impression complète de la machine d'état de l'analyseur (y compris tous les conflits) dans un fichier .output. Vous pouvez ensuite examiner les conflits et déterminer comment vous devriez changer la grammaire pour correspondre à ce que vous voulez. Lorsque je lance bison sur votre exemple, je ne vois que 9 conflits de décalage/réduction, tous issus de règles de style expr: expr OP expr, qui sont ambiguës (récursives à gauche ou à droite). La résolution par défaut (shift) les rend tous récursifs, ce qui n'est peut-être pas ce que vous voulez. Vous pouvez soit changer la grammaire pour qu'elle ne soit pas ambiguë, soit utiliser les outils de résolution de priorité prédéfinis de bison pour les résoudre.