Лучшие практики для написания парсера языка программирования

Question

Есть ли рекомендации, которым я должен следовать при написании парсера?

Answer 1

Полученная мудрость заключается в использовании генераторов синтаксических анализаторов + грамматик, и это кажется хорошим советом, потому что вы используете строгий инструмент и, по-видимому, уменьшаете усилия и вероятность ошибок при этом.

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

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

Преимущества: -

• Упрощенная сборка
• Лучшая производительность
• Лучшее управление выходом
• Может справиться с небольшими отклонениями, например, работать с грамматикой, которая не на 100% не зависит от контекста

Я не говорю, что грамматика всегда непригодна, но зачастую выгоды минимальны и часто взвешиваются с затратами и рисками.

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

Answer 2

Несколько советов:

• Знай свою грамматику - запиши ее в удобной форме
• Выберите правильный инструмент. Сделайте это из C ++ с Spirit2x, или выберите внешние инструменты синтаксического анализа, такие как antlr, yacc или все, что вам подходит
• Вам нужен парсер? Может быть, регулярного выражения будет достаточно? Или, может быть, взломать Perl-скрипт, чтобы добиться цели? Написание сложных парсеров требует времени.

Answer 3

Сначала прочитайте большую часть книги Дракона .

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

Answer 4

Не злоупотребляйте регулярными выражениями - хотя они имеют свое место, у них просто нет возможности обрабатывать какие-либо реальные операции синтаксического анализа. Вы можете толкнуть их, но в конечном итоге вы врежетесь в стену или получите неразрешимый беспорядок. Вам лучше найти генератор синтаксического анализатора, который может обрабатывать больший набор языков. Если вы действительно не хотите разбираться в инструментах, вы можете взглянуть на парсеры рекурсивного спуска - это действительно простой шаблон для написания от руки небольшого парсера. Они не такие гибкие и мощные, как генераторы больших синтаксических анализаторов, но имеют гораздо более короткую кривую обучения.

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

Answer 5

Да. Попробуй сгенерировать это, а не писать. Попробуйте использовать yacc, ANTLR, Flex / Bison, Coco / R, генератор GOLD Parser и т. Д. Используйте ручную запись синтаксического анализатора, только если ни один из существующих генераторов синтаксического анализатора не соответствует вашим потребностям.

Answer 6

• Выберите правильный тип парсера, иногда будет достаточно Рекурсивного потомка, иногда вам следует использовать парсер LR (также есть много типов парсеров LR).
• Если у вас сложная грамматика, создайте абстрактное синтаксическое дерево.
• Постарайтесь очень хорошо определить, что входит в лексер, что является частью синтаксиса и что является предметом семантики.
• Постарайтесь сделать синтаксический анализатор как можно менее связанным с реализацией лексера.
• Обеспечить хороший интерфейс для пользователя, чтобы он не зависел от реализации синтаксического анализатора.

Answer 7

Во-первых, не пытайтесь применять одни и те же методы для анализа всего. Существует множество возможных вариантов использования, начиная с IP-адресов (немного специального кода) и заканчивая программами на C ++ (для которых требуется промышленный анализатор с обратной связью из таблицы символов), а также с пользовательского ввода (который должен обрабатываться быстро) для компиляторов (которые обычно могут позволить себе потратить немного времени на разбор). Вы можете указать, что вы делаете, если хотите получить полезные ответы.

Во-вторых, запомните грамматику. Чем сложнее, тем более формальной должна быть спецификация. Попытайтесь ошибиться из-за того, что вы слишком формальны.

В-третьих, это зависит от того, что вы делаете.