Глава 12 . Генераторы синаксических и лексических анализаторов (ocamllex, ocamlyacc)

ocamllex создает лексический анализатор из набора регулярных выражений и связанных с ними семантических действий в стиле lex. Если входной файл называется lexer.mll, команда

ocamllex lexer.mll

сгенерирует файл lexer.ml c кодом Caml для лексического анализатора. В этом файле на каждое вхождение в определении лексического анализатора создается одна функция с тем же именем, что и вхождение. Аргументом для таких функций служит буфер анализатора, а возвращают они семантический атирибут, соотвествующий вхождению.

Буферы анализатора - это абстрактный тип данных, реализованный в модуле стандартной библиотеки Lexing. Функции Lexing.from_channel, Lexing.from_string и Lexing.from_function создают лексические буферы, принимающие данный из канала ввода, строки символов или функции чтения, соотвественно (см. описание модуля Lexing).

При использовании с синтаксичесим анализатором, сгенерированным ocamlyacc семантические действия вычисляют значение типа token, определенное этим анализатором (см. описание ocamlyacc ниже).

Формат определения лексического анализатора таков:

{ заголовок }
let ident = regexp ...
rule entrypoint =
  parse regexp { action }
      | ...
      | regexp { action }
and entrypoint =
  parse ...
and ...
{ концевик }

Комментарии ограничиваются (* и *) как обычно в Caml.

Заголовок и концевик - это произвольный текст Caml и фигурных скобках. Оба раздела необязательны. Если они заданы, текст заголовка копируется в начало генерируемого файла, а текст концевика - в конец. Обычно заголовок содержит директивы open, необходимые для действий, и при необходимости вспомогательные функии.

Между заголовком и вхождениями можно определить по именам часто используемые регулярные выражения. Они записываются в форме let ident = regexp. В этом случае идентификатор ident в дальнейшем будет использоваться как сокращение для regexp.

Имена вхождений должны быть допустимыми идентификаторами для значений Caml (начинающимися с буквы в строчном регистре). Каждое вхождение сановится функцией Caml, принимающей один аргумент типа Lexing.lexbuf - из него читаются и сравниваются с регулярным выражением, соответсвующим правилу, символы, пока префикс не совпадет с одним из правил. Затем вычисляется соответствующее действие, которое и будет значением, возвращаемым функией.

Если префикс ввода совпадет с несколькими регулярными выражениями, результат опредялется правилось "длиннейшего совпаления" - выбирается регулярное выражение, удовлетворяющее максимальному количеству символов. При связке выбирается ранее совпавшее регулярное выражение.

Регулярные выражения записываются в стиле lex с добавками Caml-подобного синтаксиса.

'char'

Символьная константа с тем же синтаксисом, что и соответствующий класс Objective Caml. Совпадает с указанным символом.

_

(Подчеркивание.) Совпадает с любым символом.

eof

Совпадает с концом ввода лексического анализатора.

На некоторых системах с интерактивным вводом, за концом файла могут следовать дополнительные символы. ocamllex не сможет правильно обработать регулярное выражение для такой ситуации.

"string"

Строковая константа с тем же синтаксисом, что и соответствующий класс Objective Caml. Совпадает с указанной последовательностью символов.

[character-set]

Совпадает с любым единичным символом из набора. Допустимые наборы таковы: единичные символьные константы 'c', диапазоны символов 'c₁' - 'c₂' (все символы от c₁ до c₂ включительно) или объединение двух и больше наборов.

[^character-set]

Любой символ, не входящий в данный набор.

regexp*

(Повторение.) Ноль и более совпадающих строк.

regexp+

(Строгое повторение.) Одна и более совпадающая строка.

regexp?

(Вариант.) Пустая стока или строка, совпадающая с regexp

regexp₁|regexp₂

(Альтернатива.) Любая строка, совпадающая либо с regexp₁, либо с regexp₂.

regexp₁ regexp₂

(Объединение.) Совпадает с последовательностью двух строк, первая из который совпадает с regexp₁, а вторая - с regexp₂.

(regexp)

То же самое, что и regexp.

ident

Ссылка на регулярное выражение, связанное с ident ранее определением let ident = regexp.

Что касается приоритета, то наивысший у * и +, затем следует ?, затем объединение и, наконец, | (альтернатива).

Действием может быть любое выражение Caml. Оно вычисляется в зависимости от контекста, когда идентификатор lexbuf связывается с текущим буфером лексического анализатора. Некоторые распространенные случаи использования lexbuf, а также операции с буферами анализатора, определенные в модуле стандартной библиотеки Lexing приведены ниже.

Lexing.lexeme lexbuf

Возвращает совпавшую строку.

Lexing.lexeme_char lexbuf n

Возвращает n-ный символ совпавшей строки. Для первого символа n = 0.

Lexing.lexeme_start lexbuf

Вовзращает абсолютную позицию начала совпавшей строки во входном тексте. Первый считанный символ входного текста имеет позицию 0.

Lexing.lexeme_end lexbuf

Вовзращает абсолютную позицию конца совпавшей строки во входном тексте. Первый считанный символ входного текста имеет позицию 0.

entrypoint lexbuf

(Где entrypoint - имя другого вхождения в том же определении анализатора.) Рекурсивно вызывает анализатор на заданном вхождении, что бывает полезно, например, для вложенных комментариев.

Все идентификаторы, начинающиеся с __ocaml_lex зарезервированы для использования ocamllex, поэтому их не следует использовать в программах.

Команда ocamlyacc создает синтаксический анализатор из контекстно независимой грамматической спецификации с соответствующими семантическими действиями в стиле yacc. Если исходный файл называется grammar.mly, то команда

ocamlyacc options grammar.mly

создаст код Caml для синтаксического анализатора, поместив его в файл grammar.ml, а также интерфейс в файле grammar.mli.

Сгенерированный модуль определяет по одной функции анализатора на каждое вхождение в грамматике. Функции получают те же имена, что и вхождения. Они принимают в качестве аргумента лексический анализатор (функцию, преобразующую буферы анализатора в токены) и буфр анализатора, а возвращают семантический атрибут соотвествующего вхождения. Функции лексического анализатора обычно генерируются программой ocamllex из соответствующшей спецификации. Буферы - это абстрактный тип данных, реализованный в модуле стандартной библиотеки Lexing. Токены же представляют собой значения конкретного типа token, определенного в интерфейсе grammar.mli, создаваемом ocamlyacc.

Определение грамматики имеет следующий формат:

%{
  заголовок
%}
  объявления
%%
  правила
%%
  концевик

В разделах объявлений и правил комментарии ограничиваются знаками /* и */, как в С, а в заголовке и концевике - символами (* и *) (как в Caml).

Заголовок и концевик содержат обычный код Caml, который копируется в неизменном виде в файл grammar.ml. Оба раздела необязятельны. Заголовок попадает в начало генерируемого файла и обычно содержит директивы open, а также вспомогательные функции для семантических действий, а концевик записывается в конец.

Объявления записываются по одному на строку. Все они начинаются со знака %.

%token symbol ... symbol

Объявляет данные сиволы как токены (терминальные символы). Они добавляются как константные конструкторы для конкретного типа token.

%token < type > symbol ... symbol

Объявляет данные символы как токены, привязывая к ним атрибует указанного типа. Они доабляются как коснтрукторы с аргументом типа type для конкретного типа token. type может быть любым выражением типа Caml, однако для всех типов, кроме встроенных, имена должны быть опредедены полностью - например Modname.typename, даже если раздел заголовка включает необходимую директиву open Modname. Дело в том, что заголовок копируется только в файл реализации .ml, а часть type - еще и в интерфейс .mli.

%start symbol ... symbol

Объявляет указанные симовлы как точки входа для грамматики. Для каждого такого вхожения в генерируемом модуле определяется функция анализатора с тем же именем. Нетерминальные символы, не объявляенные как вхождения, остаются без подобных функций. Стартовые символы должны сопровождаться типом, который определяется в директиве %type.

%type < type > symbol ... symbol

Определяет тип семантических атрибутов для данных символов. Эта часть обязательна только для стартовых символов. Типы прочих нетерминальных символов определяются при прогоне сгенерированных файлов через компилятор Objective Caml (если не используется параметр -s). Часть type может быть любыи выражением типа Caml, гно все конструкторы типа должны быть определены полностью, как уже объяснялось выше.

%left symbol ... symbol
%right symbol ... symbol
%nonassoc symbol ... symbol

Определяют приоритет и ассоциативность для данных символов. Указанные в одной строке символы получают одинаковый приоритет, который считается выше, чем у символов, объявленных ранее в строке %left, %right или %nonassoc, но ниже, чем у символов объявленных в тех же строках позднее. Они ассоциируюся влево (%left), вправо (%right) или вовсе не получают ассоциативности (%nonassoc). Символы, как правило, являются токенами, но могут быть и обычными нетерминальными для использования с директивой %prec в правилах.

Синтаксис правил выглдит прмерно так:

нетерминальные : символ ... символ {
	  семантическое действие } | ... | символ ... символ {
	  семантическое действие } ;

Кроме того, правила могут содержать директиву %prec symbol, задающую для данного символа иные приоритет и ассоциативность, чем по умолчанию.

Семантические действия - это любые выражения Caml, в результате вычисления которых можно получить семантический атрибут, связанный с указанным нетерминальным символом. Семантические действия получают доступ к семантическим атрибутам символов, перечисленных в левой части правила с помощью нотации через знак $: $1 - это атрибут первого (самого левого) символа, $2 - второго и так далее.

Как и в yacc правила могут содержать специальный символ error, указывающий на точки ресинхронизации.

Действия в середине правил не поддерживаются.

Нетерминальные символы могут быть любыми символами, допустимыми в Caml, за одним исключеним - не допускается, чтобы они заканчивались на ' (одиночную кавычку).

Восстановление после ошибок поддерживается следующим образом: при возникновении состояния ошибки (не найдено подходящее правило в грамматике) анализатор вызывает функцию parse_error с аргументом "syntax error". В реализации по умолчанию она просто возвращает значение, начиная процесс восстановления (см. ниже). В заголовке файла грамматики можно определить собственную функцию parse_error.

В режим восстановления анализатор входит также в том случае, если одно из действий грамматики возбуждает исключение Parsing.Parse_error.

В этом режиме анализатор сбрасывает состояния из стека, пока не достигнет точки, в которой вызвавший обшибку токен может быть сдвинут. Затем токены ввода сбрасываются до тех пор, пока не будет найдено три подряд правильных токена, и начинается обработка первого из них. Если точки сдвига неверного токена найти не удается, анализатор прерывает работу, возбуждая исключение Parsing.Parse_error.

Более подробные инструкции относительно обработки ошибок содержатся в документации yacc.

Команда ocamlyacc распознает следующие параметры:

-v

Создает в файле grammar.ouput описание таблиц анализатора и отчет о конфликтах, связанных с неоднозначностями в определении грамматики.

-b prefix

Файлы создаются с именами prefix.ml, prefix.mli, prefix.output.

Во время исполнения генерированный анализатор можно отлажитвать, указав в переменной среды OCAMLRUNPARAM значение p (см. раздел 10.2). В результате исполняющий анализатор автомат с магазинной памятью трассирует его действия (сдвиг токенов, сокращение правил и т.д.). В трассировке укзываются номера правил и состотяний, которые можно расшифровать, заглянув в файл grammar.output, сгенерированный командой ocamlyacc -v.

Любимец всех времен и народов: калькулятор. Программа построчно считывает из стандартного ввода арифметические выражения и выводит результат. Это определение грамматики:

/* Файл parser.mly */
%token <int> INT
%token PLUS MINUS TIMES DIV
%token LPAREN RPAREN
%token EOL
%left PLUS MINUS        /* низший приоритет */
%left TIMES DIV         /* средний приоритет */
%nonassoc UMINUS        /* высший приоритет */
%start main             /* точка входа */
%type <int> main
%%
main:
  expr EOL                { $1 }
;
expr:
   INT                     { $1 }
 | LPAREN expr RPAREN      { $2 }
 | expr PLUS expr          { $1 + $3 }
 | expr MINUS expr         { $1 - $3 }
 | expr TIMES expr         { $1 * $3 }
 | expr DIV expr           { $1 / $3 }
 | MINUS expr %prec UMINUS { - $2 }
;

Определение лексического анализатора:

(* Файл lexer.mll *)
{
open Parser        (* Тип token определен в parser.mli *)
exception Eof
}
rule token = parse
   [' ' '\t']     { token lexbuf }     (* пропускаем пробельные символы *)
 | ['\n' ]        { EOL }
 | ['0'-'9']+     { INT(int_of_string(Lexing.lexeme lexbuf)) }
 | '+'            { PLUS }
 | '-'            { MINUS }
 | '*'            { TIMES }
 | '/'            { DIV }
 | '('            { LPAREN }
 | ')'            { RPAREN }
 | eof            { raise Eof }

Программа, объединяющая синтаксический и лексический анализаторы:

(* Файл calc.ml *)
let _ =
  try
    let lexbuf = Lexing.from_channel stdin in
    while true do
      let result = Parser.main Lexer.token lexbuf in
        print_int result; print_newline(); flush stdout
    done
  with Lexer.Eof ->
   exit 0

Компиляция:

ocamllex lexer.mll       # создает lexer.ml
ocamlyacc parser.mly     # создает parser.ml и parser.mli
ocamlc -c parser.mli
ocamlc -c lexer.ml
ocamlc -c parser.ml
ocamlc -c calc.ml
ocamlc -o calc lexer.cmo parser.cmo calc.cmo

ocamllex: transition table overflow, automaton is too big

Детерминистические автоматы, генерируемые ocamllex ограничиваются 32767 переходами. Такое сообщение означает, что определение лексического анализатора слишком сложное, и не укладывается в эти рамки. Как правило, причина в том, что определение разделяет правила для каждого ключевогого слова алфавита в языке, например, так:

rule token = parse
  "keyword1"   { KWD1 }
| "keyword2"   { KWD2 }
| ...
| "keyword100" { KWD100 }
| ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] *
               { IDENT(Lexing.lexeme lexbuf) }

Чтобы автоматы сохраняли небольшой размер, подобное определение можно переписать с одним правилом для общего "идентификатора" и хэш-таблицей подстановок, позволяющей отличать ключевые слова от идентификаторов:

{ let keyword_table = Hashtbl.create 53
  let _ =
    List.iter (fun (kwd, tok) -> Hashtbl.add keyword_table kwd tok)
              [ "keyword1", KWD1;
                "keyword2", KWD2; ...
                "keyword100", KWD100 ]
}
rule token = parse
  ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] *
               { let id = Lexing.lexeme lexbuf in
                 try
                   Hashtbl.find keyword_table s
                 with Not_found ->
                   IDENT s }

• Обзор ocamllex
• Синтаксис определения лексического анализатора
• Обзор ocamlyacc
• Синтаксис определения грамматики
• Параметры
• Пример
• Распространенные ошибки