menhir - связывает узлы AST с местоположениями токенов в исходном файле
Я использую Menhir для разбора DSL. Мой парсер строит AST, используя сложную коллекцию вложенных типов. Во время более поздней проверки типов и других проходов в отчетах об ошибках, сгенерированных для пользователя, я хотел бы сослаться на позицию исходного файла, где это произошло. Это не ошибки синтаксического анализа, и они генерируются после завершения синтаксического анализа.
Наивным решением было бы снабдить все типы AST дополнительной информацией о местоположении, но это сделало бы работу с ними (например, построение или сопоставление) ненужной неуклюжей. Какова установленная практика для этого?
2 ответа
Вам нужно каким-то образом прикрепить информацию о местоположении к вашим узлам. Обычным решением является кодирование вашего узла AST в виде записи, например,
type node =
| Typedef of typdef
| Typeexp of typeexp
| Literal of string
| Constant of int
| ...
type annotated_node = { node : node; loc : loc}
Поскольку вы используете записи, вы все равно можете использовать сопоставление с образцом без чрезмерных синтаксических издержек, например,
match node with
| {node=Typedef t} -> pp_typedef t
| ...
В зависимости от вашего представления, вы можете выбрать между обертыванием каждой ветви вашего типа по отдельности, обтеканием всего типа или рекурсивно, как в примере Frama-C @Isabelle Newbie.
Аналогичный, но более общий подход заключается в расширении узла не с помощью местоположения, а только с помощью уникального идентификатора и использования окончательной карты для добавления произвольных данных в узлы. Преимущество этого подхода состоит в том, что вы можете расширять свои узлы произвольными данными, поскольку вы фактически экстернализуете атрибуты узлов. Недостатком является то, что вы не можете гарантировать целостность атрибута, поскольку конечные карты не являются полными. Таким образом, сложнее сохранить инвариант, который, например, у всех узлов есть местоположение.
Поскольку каждый объект, выделенный для кучи, уже имеет неявный уникальный идентификатор, адрес, можно прикрепить данные к объектам, выделенным для кучи, без фактического переноса их в другой тип. Например, мы все еще можем использовать тип node и использовать конечные карты для добавления к ним произвольных фрагментов информации, при условии, что каждый узел является объектом кучи, т. е. определение узла не содержит константных конструкторов (в случае, если оно есть, вы можете обойти его добавление фиктивного значения единицы, например, | End может быть представлен как | End of unit,
Конечно, говоря адрес, я не имею в виду буквально физический или виртуальный адрес объекта. OCaml использует движущийся GC, поэтому фактический адрес объекта OCaml может измениться во время выполнения программы. Более того, адрес, как правило, не является уникальным, поскольку после освобождения объекта его адрес может быть захвачен совершенно другим объектом.
К счастью, после добавления эфемер в последнюю версию OCaml это больше не проблема. Более того, эфемерон будет хорошо играть с GC, так что если узел больше недоступен, его атрибуты (например, расположение файлов) будут собираться GC. Итак, давайте обосновать это на конкретном примере. Предположим, у нас есть два узла c1 а также c2:
let c1 = Literal "hello"
let c2 = Constant 42
Теперь мы можем создать отображение местоположения из узлов в местоположения (мы будем представлять последнее как просто строки)
module Locations = Ephemeron.K1.Make(struct
type t = node
let hash = Hashtbl.hash (* or your own hash if you have one *)
let equal = (=) (* or a specilized equal operator *)
end)
Locations Модуль предоставляет интерфейс типичной императивной хэш-таблицы. Итак, давайте использовать это. В парсере, когда вы создаете новый узел, вы должны регистрировать его местоположение в глобальном locations значение, например,
let locations = Locations.create 1337
(* somewhere in the semantics actions, where c1 and c2 are created *)
Locations.add c1 "hello.ml:12:32"
Locations.add c2 "hello.ml:13:56"
А позже вы можете извлечь местоположение:
# Locations.find locs c1;;
- : string = "hello.ml:12:32"
Как видите, хотя решение приятно в том смысле, что оно не затрагивает тип данных узла, поэтому остальная часть вашего кода может легко и просто сопоставить шаблон с ним, оно все еще немного грязное, так как требует глобальное изменчивое состояние, которое трудно поддерживать. Кроме того, поскольку мы используем адрес объекта в качестве ключа, каждый вновь созданный объект, даже если он был логически получен из исходного объекта, будет иметь различную идентичность. Например, предположим, что у вас есть функция, которая нормализует все литералы:
let normalize = function
| Literal str -> Literal (normalize_literal str)
| node -> node
Это создаст новый Literal узел из исходных узлов, поэтому вся информация о местоположении будет потеряна. Это означает, что вам нужно обновлять информацию о местоположении, каждый раз, когда вы выводите один узел из другого.
Другая проблема с эфемерами заключается в том, что они не могут пережить маршалинг или сериализацию. Т.е., если вы сохраните свой AST где-нибудь в файле, а затем восстановите его, все узлы потеряют свою идентичность, и location стол станет пустым.
Говоря о "монадическом подходе", который вы упомянули в комментариях. Хотя монады магические, они все равно не могут волшебным образом решить все проблемы. Они не являются серебряными пулями:) Чтобы прикрепить что-либо к узлу, нам все равно нужно расширить его дополнительным атрибутом - либо информацией о местоположении напрямую, либо идентификатором, с помощью которого мы можем косвенно прикрепить свойства. Монада может быть полезна для последнего, поскольку вместо глобальной ссылки на последний присвоенный идентификатор мы можем использовать монаду состояния для инкапсуляции нашего генератора идентификаторов. И ради полноты, вместо использования монады состояния или глобальной ссылки для генерации уникальных идентификаторов, вы можете использовать UUID и получать идентификаторы, которые не только уникальны при запуске программы, но и универсально уникальны, в том смысле, что нет других объектов в мире с таким же идентификатором, независимо от того, как часто вы запускаете свою программу (в нормальном мире). И хотя похоже, что для генерации UUID не используется какое-либо состояние, под капотом он по-прежнему использует императивный генератор случайных чисел, так что это своего рода обман, но все же его можно рассматривать как чисто функциональный, поскольку он не содержит наблюдаемых последствия.
Я не знаю, является ли это наилучшей практикой, но мне нравится подход, используемый в абстрактном синтаксическом дереве системы Frama-C; см. https://github.com/Frama-C/Frama-C-snapshot/blob/master/src/kernel_services/ast_data/cil_types.mli
Этот подход использует "слои" записей и алгебраических типов, вложенных друг в друга. Записи содержат мета-информацию, такую как исходные местоположения, а также алгебраический "узел", с которым вы можете сопоставить.
Например, вот часть представления выражений:
type ...
and exp = {
eid: int; (** unique identifier *)
enode: exp_node; (** the expression itself *)
eloc: location; (** location of the expression. *)
}
and exp_node =
| Const of constant (** Constant *)
| Lval of lval (** Lvalue *)
| UnOp of unop * exp * typ
| BinOp of binop * exp * exp * typ
...
Так, учитывая переменную e типа exp, вы можете получить доступ к его исходному местоположению с e.elocи сопоставление с образцом в его абстрактном синтаксическом дереве в e.enode,
Так просто, "верхний уровень" совпадений по синтаксису очень прост:
let rec is_const_expr e =
match e.enode with
| Const _ -> true
| Lval _ -> false
| UnOp (_op, e', _typ) -> is_const_expr e'
| BinOp (_op, l, r, _typ) -> is_const_expr l && is_const_expr r
Чтобы глубже соответствовать выражению, вы должны пройти запись на каждом уровне. Это добавляет некоторый синтаксический беспорядок, но не слишком много, поскольку вы можете сопоставлять паттерны только с одним интересующим вас полем записи:
let optimize_double_negation e =
match e.enode with
| UnOp (Neg, { enode = UnOp (Neg, e', _) }, _) -> e'
| _ -> e
Для сравнения, на чистом AST без метаданных это будет примерно так:
let optimize_double_negation e =
match e.enode with
| UnOp (Neg, UnOp (Neg, e', _), _) -> e'
| _ -> e
Я считаю, что подход Frama-C хорошо работает на практике.