Est-il possible de créer une grammaire très permissive en utilisant Menhir?

Question

J'essaie d'analyser certains éléments de Verilog - je suis principalement intéressé par l'extraction de définitions de modules et d'instanciations.

en Verilog un module est défini comme:

module foo (...) endmodule; 

Et un module est instancié dans l'une des deux façons différentes:

foo fooinst (...); 
foo #(...list of params...) fooinst (....); 

A ce stade, je ne suis intéressé à la nom du module défini ou instancié; 'foo' dans les deux cas ci-dessus.

Compte tenu de cette grammaire menhir (verParser.mly):

%{ 

    type expr = Module of expr 
      | ModInst of expr 
      | Ident of string 
      | Int of int 
      | Lparen 
      | Rparen 
      | Junk 
      | ExprList of expr list 

%} 

%token <string> INT 
%token <string> IDENT 
%token LPAREN RPAREN MODULE TICK OTHER HASH EOF 



%start expr2 
%type <expr> mod_expr 
%type <expr> expr1 
%type <expr list> expr2 

%% 


mod_expr: 
    | MODULE IDENT LPAREN { Module (Ident $2) } 
    | IDENT IDENT LPAREN  { ModInst (Ident $1) } 
    | IDENT HASH LPAREN  { ModInst (Ident $1) }; 

junk: 
    | LPAREN { } 
    | RPAREN { } 
    | HASH { } 
    | INT { }; 

expr1: 
    | junk* mod_expr junk* { $2 } ; 

expr2: 
    | expr1* EOF { $1 }; 

Lorsque je tente ce dans le menhir interpretter il fonctionne très bien extraire le module instantion:

MODULE IDENT LPAREN 
ACCEPT 
[expr2: 
    [list(expr1): 
    [expr1: 
     [list(junk):] 
     [mod_expr: MODULE IDENT LPAREN] 
     [list(junk):] 
    ] 
    [list(expr1):] 
    ] 
    EOF 
] 

Il fonctionne très bien pour le instanciation d'un seul module:

IDENT IDENT LPAREN 
ACCEPT 
[expr2: 
    [list(expr1): 
    [expr1: 
     [list(junk):] 
     [mod_expr: IDENT IDENT LPAREN] 
     [list(junk):] 
    ] 
    [list(expr1):] 
    ] 
    EOF 
] 

Mais bien sûr, s'il y a un IDENT t apparaît avant tout d'eux, il rejettera:

IDENT MODULE IDENT LPAREN IDENT IDENT LPAREN 
REJECT 

... et bien sûr il y aura des identifiants dans un fichier Verilog réel avant ces defs. J'essaie de ne pas avoir à spécifier complètement une grammaire Verilog, mais je veux construire la grammaire lentement et progressivement pour finir par analyser de plus en plus le langage.

Si j'ajoute IDENT à la règle de courrier indésirable, cela résout le problème ci-dessus, mais la règle d'instanciation de module ne fonctionne pas car la règle de courrier indésirable capture maintenant l'IDENT.

Est-il possible de créer une règle très permissive qui contournera les éléments que je ne veux pas faire correspondre, ou est-il généralement nécessaire de créer une grammaire complète pour faire quelque chose comme ça?

Est-il possible de créer une règle qui me permettrait de correspondre:

MODULE IDENT LPAREN stuff* RPAREN ENDMODULE 

où "choses *" correspond à tout d'abord, mais RPAREN?

Quelque chose comme:

stuff: 
    | !RPAREN { } ; 

Je l'ai utilisé parseurs PEG dans le passé qui permettrait des constructions de ce genre.

Answer 1

J'ai décidé que le PEG convient mieux à une grammaire permissive et non exhaustive. Nous avons pris un coup d'œil à peg/leg et a pu très rapidement mis en place une grammaire de la jambe qui fait ce que je dois faire:

start = (comment | mod_match | char) 

line = < (('\n' '\r'*) | ('\r' '\n'*)) > { lines++; chars += yyleng; } 
module_decl = module modnm:ident lparen (!rparen .)* rparen { chars += yyleng; printf("Module decl: <%s>\n",yytext);} 
module_inst = modinstname:ident ident lparen { chars += yyleng; printf("Module Inst: <%s>\n",yytext);} 
     |modinstname:ident hash lparen { chars += yyleng; printf("Module Inst: <%s>\n",yytext);} 

mod_match = (module_decl | module_inst) 
module  = 'module' ws    { modules++; chars +=yyleng; printf("Module: <%s>\n", yytext); } 
endmodule = 'endmodule' ws    { endmodules++; chars +=yyleng; printf("EndModule: <%s>\n", yytext); } 

kwd = (module|endmodule) 
ident = !kwd<[a-zA-z][a-zA-Z0-9_]+>- { words++; chars += yyleng; printf("Ident: <%s>\n", yytext); } 

char = .     { chars++; } 
lparen = '(' - 
rparen = ')' - 
hash = '#' 

- = (space | comment)* 
ws = space+ 
space = ' ' | '\t' | EOL 
comment = '//' (!EOL .)* EOL 
      | '/*' (!'*/' .)* '*/' 
EOF = !. 
EOL = '\r\n' | '\n' | '\r' 

Aurochs est peut-être aussi une option, mais je suis préoccupé par l'utilisation de la vitesse et de la mémoire d'un Aurochs analyseur généré. peg/leg produit un analyseur en C qui devrait être assez rapide.