Using ocamllex/ocamlyacc to parse part of a grammar

Question

I've been using regexes to go through a pile of Verilog files and pull out certain statements. Currently, regexes are fine for this, however, I'm starting to get to the point where a real parser is going to be needed in order to deal with nested structures so I'm investigating ocamllex/ocamlyacc. I'd like to first duplicate what I've got in my regex implementation and then slowly add more to the grammar.

Right now I'm mainly interested in pulling out module declarations and instantiations. To keep this question a bit more brief, let's look at module declarations only.

In Verilog a module declaration looks like:

module modmame ( ...other statements ) endmodule;

My current regex implementation simply checks that there is a module declared with a particular name ( checking against a list of names that I'm interested in - I don't need to find all module declarations just ones with certain names). So basically, I get each line of the Verilog file I want to parse and do a match like this (pseudo-OCaml with Pythonish and Rubyish elements ):

foreach file in list_of_files:
  let found_mods = Hashtbl.create 17;
  open file 
  foreach line in file:
    foreach modname in modlist
    let mod_patt=  Str.regexp ("module"^space^"+"^modname^"\\("^space^"+\\|(\\)") in 
    try
      Str.search_forward (mod_patt) line 0
      found_mods[file] = modname; (* map filename to modname *)
    with Not_found -> ()

That works great. The module declaration can occur anywhere in the Verilog file; I'm just wanting to find out if the file contains that particular declaration, I don't care about what else may be in that file.

My first attempt at converting this over to ocamllex/ocamlyacc:

verLexer.mll:

rule lex = parse
  | [' ' '\n' '\t']               { lex lexbuf }
  | ['0'-'9']+ as s               { INT(int_of_string s) }
  | '('                           { LPAREN }
  | ')'                           { RPAREN }
  | "module"                      { MODULE }
  | ['A'-'Z''a'-'z''0'-'9''_']+ as s  { IDENT(s) }
  | _                             { lex lexbuf }
  | eof

verParser.mly:

%{ type expr =  Module of expr | Ident of string | Int of int %}

%token <int> INT
%token <string> IDENT
%token  LPAREN RPAREN MODULE EOF

%start expr1
%type <expr> expr1

%%

expr:   
| MODULE IDENT LPAREN    { Module( Ident $2) };

expr1:   
| expr EOF { $1 };

Then trying it out in the REPL:

# #use "verLexer.ml" ;; 
# #use "verParser.ml" ;; 
# expr1 lex (Lexing.from_string "module foo (" ) ;;
- : expr = Module (Ident "foo")

That's great, it works!

However, a real Verilog file will have more than a module declaration in it:

# expr1 lex (Lexing.from_string "//comment\nmodule foo ( \nstuff" ) ;;
Exception: Failure "lexing: empty token".

I don't really care about what appeared before or after that module definition, is there a way to just extract that part of the grammar to determine that the Verilog files contains the 'module foo (' statement? Yes, I realize that regexes are working fine for this, however, as stated above, I am planning to grow this grammar slowly and add more elements to it and regexes will start to break down.

EDIT: I added a match any char to the lex rule:

      | _                             { lex lexbuf }

Thinking that it would skip any characters that weren't matched so far, but that didn't seem to work:

 # expr1 lex (Lexing.from_string "fof\n module foo (\n" ) ;;
 Exception: Parsing.Parse_error.

score 4 · Accepted Answer · answered Aug 22 '12 at 05:35

A first advertisement minute: instead of ocamlyacc you should consider using François Pottier's Menhir, which is like a "yacc, upgraded", better in all aspects (more readable grammars, more powerful constructs, easier to debug...) while still very similar. It can of course be used in combination with ocamllex.

Your expr1 rule only allows to begin and end with a expr rule. You should enlarge it to allow "stuff" before or after expr. Something like:

junk:
| junk LPAREN
| junk RPAREN
| junk INT
| junk IDENT

expr1:
| junk expr junk EOF

Note that this grammar does not allow the module token to appear in the junk section. Doing so would be a bit problematic as it would make the grammar ambiguous (the structure you're looking for could be embedded either in expr or junk). If you could have a module token happening outside the form you're looking form, you should consider changing the lexer to capture the whole module ident ( structure of interest in a single token, so that it can be atomically matched from the grammar. On the long term, however, have finer-grained tokens is probably better.

see my edit above to the lexer to match any character. Is this a good approach as well? (It didn't seem to work as expected, though) — aneccodeal, Aug 22 '12 at 15:58
@aneccodeal I'm not familiar with the semantics of `_` in ocamllex, but if it also captures `eof` I wouldn't be surprised to get errors here. It's a bit hard to debug a lexing error by looking only at the result of parsing (furthermore with a not-rock-solid grammar), maybe you should have a look at the resulting token stream directly -- but I don't remember what's the most direct way to display it with `ocamllex`, it may be non-trivial, you'll have to figure that out. — gasche, Aug 22 '12 at 19:49
is it true that in menhir I can do something like: expr1: junk* expr junk* EOF {$2}; Meaning that I can match 0 or more 'junk' before and after the expr? That does seem useful. — aneccodeal, Aug 22 '12 at 20:06

score 3 · Answer 2 · answered Aug 22 '12 at 21:02

As suggested by @gasche I tried menhir and am already getting much better results. I changed the verLexer.ml to:

{
  open VerParser
}
rule lex = parse
  | [' ' '\n' '\t']               { lex lexbuf }
  | ['0'-'9']+ as s               { INT(int_of_string s) }
  | '('                           { LPAREN }
  | ')'                           { RPAREN }
  | "module"                      { MODULE }
  | ['A'-'Z''a'-'z''0'-'9''_']+ as s  { IDENT(s) }
  | _  as c                       { lex lexbuf }
  | eof                           { EOF }

And changed verParser.mly to:

%{ type expr =  Module of expr | Ident of string | Int of int
           |Lparen | Rparen  | Junk %}

%token <int> INT
%token <string> IDENT
%token  LPAREN RPAREN MODULE EOF

%start expr1
%type <expr> expr1


%%

expr:
  | MODULE IDENT LPAREN    { Module( Ident $2) };

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

expr1:
| junk* expr junk* EOF { $2 };

The key here is that menhir allows a rule to be parameterized with a '*' as in the line above where I've got 'junk*' in a rule meaning match junk 0 or more times. ocamlyacc doesn't seem to allow that.

Now when I tried it in the REPL I get:

# #use "verParser.ml" ;;
# #use "verLexer.ml" ;;
# expr1 lex (Lexing.from_string "module foo ( " ) ;;
- : expr = Module (Ident "foo")
# expr1 lex (Lexing.from_string "some module foo ( " ) ;;
- : expr = Module (Ident "foo")
# expr1 lex (Lexing.from_string "some module foo (\nbar " ) ;;
- : expr = Module (Ident "foo")
# expr1 lex (Lexing.from_string "some module foo (\n//comment " ) ;;
- : expr = Module (Ident "foo")
# expr1 lex (Lexing.from_string "some module fot foo (\n//comment " ) ;;
Exception: Error.
# expr1 lex (Lexing.from_string "some module foo (\n//comment " ) ;;

Which seems to work exactly as I want it to.

Using ocamllex/ocamlyacc to parse part of a grammar

2 Answers2