Генераторы парсеров и Ragel ... Создание собственного D Parser - PullRequest
10 голосов
/ 18 января 2011

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

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

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

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

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

Спасибо!

Ответы [ 3 ]

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

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

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

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

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

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

13 голосов
/ 27 марта 2011

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

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

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

1 голос
/ 08 апреля 2011

Может быть:

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

или

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

...