Parser Generators и Ragel ... Создание собственного D Parser

Question

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

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

1. ли я понимаю, что правильно?

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

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

Спасибо!

Answer 1

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

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

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

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

Чтобы полностью понять, что для вас делает генератор парсера, вам понадобится формальный язык и теория парсинга. Есть хуже, чем начинать, чем The Dragon Book. Смотри также: Learning to write a compiler.

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

Answer 2

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

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

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

Answer 3

Может быть:

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

или:

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