使用ocamllex/ocamlyacc解析部分语法

Question

我一直在使用正则表达式来检查一堆Verilog文件，并提取出某些语句。目前，正则表达式对此很好，但是，我开始需要一个真正的解析器来处理嵌套结构，所以我正在研究ocamllex/ocamlyacc。我想首先复制我的regex实现中已有的内容，然后慢慢地在语法中添加更多内容。

现在，我主要对提取模块声明和实例化感兴趣。为了使这个问题更简短，让我们只看一下模块声明。

在Verilog中，模块声明如下所示：

module modmame ( ...other statements ) endmodule;

我当前的正则表达式实现只是检查是否存在使用特定名称声明的模块(对照我感兴趣的名称列表-我不需要查找所有模块声明，只查找具有特定名称的模块声明)。所以基本上，我得到了我想要解析的Verilog文件的每一行，并像这样进行匹配(使用Pythonish和Rubyish元素的伪OCaml )：

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 -> ()

这很好用。模块声明可以出现在Verilog文件中的任何地方；我只想知道文件中是否包含特定的声明，我不关心该文件中还可能有什么。

我第一次尝试将其转换为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 };

然后在REPL中尝试：

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

太棒了，它起作用了！

然而，一个真正的Verilog文件中包含的不仅仅是一个模块声明：

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

我真的不关心在模块定义之前或之后出现了什么，有没有一种方法可以只提取语法的一部分来确定Verilog文件包含'module foo (‘语句？是的，我意识到正则表达式在这方面工作得很好，然而，如上所述，我计划慢慢地增加这个语法，并向它添加更多的元素，然后正则表达式将开始分解。

编辑:我在lex规则中添加了一个匹配任意字符：

      | _                             { lex lexbuf }

认为它会跳过到目前为止没有匹配的任何字符，但这似乎不起作用：

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

Answer 1

第一个广告分钟:你应该考虑使用François Pottier的Menhir，而不是ocamlyacc，它就像一个"yacc，升级“，在所有方面都更好(更可读的语法，更强大的构造，更容易调试……)但仍然非常相似。当然，它可以与ocamllex结合使用。

您的expr1规则仅允许以expr规则开始和结束。你应该把它放大以允许在expr之前或之后的“东西”。类似于：

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

expr1:
| junk expr junk EOF

请注意，此语法不允许module标记出现在junk部分中。这样做会有点问题，因为它会使语法不明确(您要查找的结构可能嵌入在expr或junk中)。如果可以在表单之外使用module令牌，则应该考虑更改词法分析器，以便在单个令牌中捕获感兴趣的整个module ident (结构，以便可以从语法中自动匹配它。但是，从长远来看，拥有更细粒度的标记可能更好。

Answer 2

正如@gasche所建议的那样，我尝试了menhir，并且已经得到了更好的结果。我将verLexer.ml更改为：

{
  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 }

并将verParser.mly更改为：

%{ 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 };

这里的关键是，menhir允许使用'*‘将规则参数化，就像上面的代码行一样，我在规则中使用了' junk *’，这意味着匹配垃圾0次或更多次。ocamlyacc似乎不允许这样做。

现在，当我在REPL中尝试它时，我得到：

# #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 " ) ;;

这看起来就像我想要的那样。