Есть ли какие-то передовые методы, которым я должен следовать при написании парсера?
Лучшие практики написания парсера языка программирования
Ответы (7)
Принято считать, что использовать генераторы синтаксического анализатора + грамматики, и это кажется хорошим советом, потому что вы используете строгий инструмент и, по-видимому, уменьшаете усилия и вероятность ошибок при этом.
Чтобы использовать генератор синтаксического анализатора, грамматика должна быть контекстно-свободной. Если вы разрабатываете язык для анализа, вы можете это контролировать. Если вы не уверены, это может стоить вам больших усилий, если вы начнете разбираться в грамматике. Даже если на практике это не зависит от контекста, если грамматика не огромна, может быть проще написать рекурсивный приличный синтаксический анализатор.
Отсутствие контекста не только делает возможным генератор синтаксического анализатора, но также значительно упрощает синтаксические анализаторы, написанные вручную. В итоге вы получаете одну (или две) функции на фразу. То есть, если вы систематизируете и четко называете код, увидеть не намного сложнее, чем грамматику (если ваша IDE может показать вам иерархию вызовов, тогда вы сможете в значительной степени увидеть, что такое грамматика).
Преимущества:-
- Более простая сборка
- Лучшая производительность
- Лучший контроль вывода
- Справляется с небольшими отклонениями, например работать с грамматикой, которая не на 100% контекстно-зависима
Я не говорю, что грамматика всегда непригодна, но часто преимущества минимальны и часто перевешиваются затратами и рисками.
(Я считаю, что аргументы в их пользу кажутся привлекательными и что у них есть общая предвзятость, поскольку это способ показать, что кто-то более грамотен в компьютерных науках.)
Несколько советов:
- Знай свою грамматику - запиши в подходящей форме
- Выберите подходящий инструмент. Сделайте это из C ++ с помощью Spirit2x или выберите внешние инструменты синтаксического анализа, такие как antlr, yacc или что-то еще, что вам подходит.
- Вам нужен парсер? Может хватит regexp? Или, может быть, взломать Perl-скрипт, чтобы добиться цели? Написание сложных синтаксических анализаторов требует времени.
Не злоупотребляйте регулярными выражениями - пока они имеют свое место, они просто не в состоянии обрабатывать какой-либо настоящий синтаксический анализ. Вы можете толкнуть их, но в конечном итоге вы столкнетесь с стеной или попадете в непослушный беспорядок. Лучше найти генератор синтаксического анализатора, который может обрабатывать более широкий набор языков. Если вы действительно не хотите разбираться в инструментах, вы можете взглянуть на парсеры с рекурсивным спуском - это действительно простой шаблон для написания небольшого парсера от руки. Они не такие гибкие и мощные, как большие генераторы синтаксических анализаторов, но у них гораздо более короткая кривая обучения.
Если у вас нет очень жестких требований к производительности, постарайтесь разделить слои - лексер читает отдельные токены, синтаксический анализатор объединяет их в дерево, а затем семантический анализ проверяет все и связывает ссылки, а затем последняя фаза для вывода всего производится. Разделение различных частей логики упростит дальнейшее сопровождение.
Сначала прочтите большую часть книги о драконах.
Парсеры не являются сложными, если вы знаете, как их создавать, но они НЕ из тех вещей, на которые, если вы потратите достаточно времени, вы в конечном итоге добьетесь их. Лучше опираться на существующую базу знаний. (В противном случае ожидайте, что напишете это и выбросите несколько десятков раз).
Ага. Попробуйте создать его, а не писать. Рассмотрите возможность использования yacc, ANTLR, Flex / Bison, Coco / R, генератора парсеров GOLD и т. Д. Прибегайте к написанию парсера вручную только в том случае, если ни один из существующих генераторов парсеров не соответствует вашим потребностям.
- Выберите правильный тип парсера, иногда будет достаточно рекурсивного потомка, иногда вам следует использовать парсер LR (также существует много типов парсеров LR).
- Если у вас сложная грамматика, постройте абстрактное синтаксическое дерево.
- Постарайтесь очень хорошо определить, что входит в лексический анализатор, что является частью синтаксиса и что является вопросом семантики.
- Постарайтесь сделать синтаксический анализатор как можно менее связанным с реализацией лексера.
- Предоставьте пользователю хороший интерфейс, чтобы он не зависел от реализации парсера.
Во-первых, не пытайтесь применять одни и те же методы для анализа всего. Существует множество возможных вариантов использования, от чего-то вроде IP-адресов (немного специального кода) до программ на C ++ (которым нужен синтаксический анализатор промышленного уровня с обратной связью из таблицы символов) и от пользовательского ввода (который необходимо очень тщательно обрабатывать). fast) компиляторам (которые обычно могут позволить себе потратить немного времени на синтаксический анализ). Вы можете указать, что вы делаете, если хотите получить полезные ответы.
Во-вторых, имейте в виду грамматику для анализа. Чем она сложнее, тем более формальной должна быть спецификация. Попытайтесь ошибиться в том, чтобы быть слишком формальным.
В-третьих, это зависит от того, что вы делаете.