Генераторы парсеров и Ragel... Создание собственного D Parser

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

Несколько вопросов:

  1. Я правильно понял?

  2. Если так, то Ragel такой инструмент?

  3. Если это так, может ли Ragel выводить парсер D в исходный код D?

Спасибо!

Источник

3 ответа

Решение

  1. Вот и все. Генераторы синтаксического анализатора преобразуют грамматику в исходный файл, который можно использовать для распознавания строк, являющихся членами языка, определенного грамматикой. Часто, но не всегда, генератору синтаксического анализатора требуется лексический анализатор, чтобы разбить текст на токены, прежде чем он выполнит свою работу. Lex и Yacc являются классическими примерами парного лексического анализатора и генератора синтаксических анализаторов.

    Современные генераторы парсеров предлагают дополнительные функции. Например, ANTLR может генерировать код для лексического анализа, грамматического анализа и даже обходить сгенерированное абстрактное синтаксическое дерево. Elkhound генерирует синтаксический анализатор, который использует алгоритм синтаксического анализа GLR. Это позволяет распознавать более широкий диапазон языков, чем не обобщенные алгоритмы синтаксического анализа. Парсеры PEG не требуют отдельного лексического анализатора.

  2. Ragel фактически генерирует лексический анализатор в форме конечного автомата. Он может распознавать обычный язык, но не контекстно-свободный язык. Это означает, что он не может распознавать большинство языков программирования, включая D.

  3. Ragel генерирует D-код, если вам нужен быстрый лексический анализатор.

Чтобы полностью понять, что генератор парсера делает для вас, вам понадобится некоторый формальный язык и теория синтаксического анализа. Есть худшие места для начала, чем Книга Дракона. Смотрите также: Учимся писать компилятор.

Если вы чувствуете себя смелым, не забудьте проверить код лексинга и синтаксического анализа, распространяемый с помощью компилятора DMD - /dmd2/src/dmd/ - lexer.c и parse.c.

Источник

Хотя Ragel основан на регулярных выражениях, это не просто генератор регулярных выражений FSM. Он позволяет рекурсию с использованием дополнительного синтаксиса вызова / возврата, а также других функций, которые позволяют анализировать нерегулярные языки. Таким образом, хотя Ragel генерирует FSM, он позволяет генерировать несколько разных FSM и предоставляет механизмы для переключения между ними в произвольных точках или с использованием специального синтаксиса машинного перехода. Это также позволяет выполнять произвольный код при переходах между состояниями.

Еще одна вещь, которая делает Ragel уникальным, это то, что он онлайн. Другими словами, его легко использовать для сканирования данных из асинхронного источника, такого как неблокирующий сокет. Он также не использует динамические ресурсы, за исключением того, что для вызова / возврата вы можете использовать статическую, автоматическую или динамическую память для стека; как пожелаешь. Там тоже нет глобального состояния.

Ragel довольно уникален. В отличие от большинства (всех?) Традиционных генераторов, он был сделан для сетевого программирования.

Источник

Может быть:

MySourceCode -> (Сканер) -> MyScannerDataFile MyScannerDataFile -> (Parser) -> MyParserDataFile MyParserDataFile -> (CodeGenerator) -> MyExecutableFile

или же:

MySourceCode -> (ScannerAndParser) -> MyScannerAndParserDataFile MyScannerAndParserDataFile -> (CodeGenerator) -> MyExecutableFile

Источник
Другие вопросы по тегам