Использование ocamllex/ocamlyacc для разбора части грамматики
Я использовал регулярные выражения, чтобы просмотреть кучу файлов Verilog и вытащить определенные утверждения. В настоящее время регулярные выражения подходят для этого, однако я начинаю приближаться к тому моменту, когда понадобится настоящий синтаксический анализатор для работы с вложенными структурами, поэтому я изучаю ocamllex/ocamlyacc. Я хотел бы сначала продублировать то, что у меня есть в моей реализации регулярных выражений, а затем медленно добавить больше к грамматике.
Сейчас я в основном заинтересован в извлечении деклараций и экземпляров модулей. Чтобы этот вопрос был более кратким, давайте рассмотрим только объявления модулей.
В Verilog объявление модуля выглядит так:
module modmame ( ...other statements ) endmodule;
Моя текущая реализация регулярных выражений просто проверяет, есть ли модуль, объявленный с определенным именем (проверка по списку имен, которые меня интересуют - мне не нужно находить все объявления модулей, только те, которые имеют определенные имена). Таким образом, в основном, я получаю каждую строку файла Verilog, которую я хочу проанализировать, и сопоставляю это (псевдо-OCaml с элементами Pythonish и Rubyish):
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.
2 ответа
Первая рекламная минута: вместо 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 ( Структура интереса в одном токене, так что он может быть атомарно сопоставлен с грамматикой. В долгосрочной перспективе, однако, иметь более мелкозернистые токены, вероятно, лучше.
По предложению @gasche я попробовал менгир и уже получаю гораздо лучшие результаты. Я изменил 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*' в правиле, означающем совпадение 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 " ) ;;
Который, кажется, работает именно так, как я хочу.