parsing - 使用 ocamllex/ocamlyacc 解析部分语法

Question

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

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

在 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( 感兴趣的结构) token ，以便它可以从语法中自动匹配。但是，从长远来看，拥有更细粒度的 token 可能会更好。