Генератор парсера времени исполнения Ocaml

Question

Я пишу программу, которая в основном принимает грамматику в качестве входных данных в произвольном формате (и некоторых других правилах) и генерирует программу OCaml (средство проверки), которая после компиляции может проверить, принято ли выражение в соответствии с грамматикой, и правила.

Я использую OCaml для генератора, с Менгиром, чтобы разобрать грамматику и правила. Сейчас я должен написать парсер вручную для всех грамматик, которые я хочу сгенерировать. Я хотел бы сгенерировать код для парсера автоматически, как Менгир.

Я мог бы вывести грамматику Menhir и вызвать Menhir из моей программы OCaml, но было бы утомительно иметь правильную обработку ошибок.

Есть ли способ использовать Menhir в качестве бэк-энда (дать ему грамматику для создания синтаксического анализатора во время выполнения) или есть какая-нибудь библиотека, которая может сделать это в OCaml (или C, поскольку она может быть связана с OCaml)?

Если это возможно, я хотел бы иметь возможность выражать правила также в формате, описанном грамматикой, есть ли какая-либо библиотека, которая также может генерировать интерпретаторы во время выполнения?

Answer 1

Это широкая и очень интересная междисциплинарная область исследований, поэтому я даже не буду пытаться дать исчерпывающий ответ, а вместо этого предоставлю некоторые ссылки и рекомендации (которые как бы противоречат духу SO, но, вероятно, в противном случае мы должны закрыть этот вопрос, так как слишком широк).

Несколько проектов опробовали и успешно реализовали интерактивные парсеры. Если мы сосредоточимся на проектах, написанных на OCaml, то сначала на ум придет следующее: camlp5, coq, ott. Из этого наиболее интересным и легким для понимания, на мой взгляд, является последний, Отт. Они внедрили синтаксический анализатор GLR, основанный на алгоритме сокращения рабочего списка, который, помимо других методов, описан в диссертации Скотта Макпика.

Альтернативным подходом было бы воздержаться от генерации парсера и придерживаться монадических парсеров. Поскольку монадический синтаксический анализатор определяет контекстно-зависимую грамматику в качестве значения времени выполнения, можно указать любое взаимодействие между временем выполнения и определенной грамматикой. Это на самом деле благо и отрава, так как можно определить совершенно бессмысленные грамматики с конфликтами. Но, как всегда, с великой силой приходит большая ответственность. OCaml имеет множество библиотек монадических синтаксических анализаторов, первые две, которые приходят на ум, это mparser и angstrom.