Почему некоторые компиляторы предпочитают ручной парсер над генераторами парсеров?

Ответ 1

LR (1) и LALR (1) синтаксические анализаторы действительно очень раздражают по двум причинам:

• Генератор парсера не очень хорош в создании полезных сообщений об ошибках.
• Некоторые виды неопределенности, такие как блоки if-else C-стиля, делают запись грамматики очень болезненной.

С другой стороны, грамматика LL (1) намного лучше подходит для обеих этих вещей. Структура грамматик LL (1) делает их очень легко кодировать в качестве рекурсивных парсеров спуска, и поэтому обращение к генератору парсера на самом деле не является победой.

Кроме того, в случае Vala, анализатора и самого компилятора, представленного как библиотека, вы можете создать собственный бэкэнд для компилятора Vala с использованием библиотеки компилятора Vala и получить все проверки синтаксического анализа и проверки типов свободный.

Ответ 2

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

Вот некоторые плюсы и минусы для каждого подхода.

Генераторы парсеров

Плюсы:

• Быстро получить рабочий синтаксический анализатор (по крайней мере, если вы не знаете, как передать его код).

Минусы:

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

Обработчик ручного рекурсивного спуска

Плюсы:

• Сгенерированный код легко понять. Рекурсивные парсеры обычно имеют одну функцию, соответствующую каждой языковой конструкции, например. parseЧтобы разобрать выражение while, parseDeclaration для анализа объявления и так далее. Понимание и отладка парсера легко.
• Легко предоставить осмысленные сообщения об ошибках, восстановить ошибки и продолжить синтаксический анализ таким образом, который имеет наибольший смысл в конкретной ситуации.

Минусы:

• Потребуется некоторое время, чтобы передать код парсера, особенно если у вас нет опыта с этим материалом.

• Парсер может быть несколько медленным. Это относится ко всем рекурсивным синтаксическим анализаторам, а не только к написанным вручную. Имея одну функцию, соответствующую каждой конструкции языка для синтаксического анализа простого числового литерала, парсер может создавать десятки или более вложенных вызовов, начиная с, например, parseExpression через parseAddition, parseMultiplication и т.д. parseLiteral. Функциональные вызовы относительно недороги на языке, таком как C, но все же кулачок суммируется до значительного времени.

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

Ответ 3

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

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

Поддержание работоспособности также было проблемой. Этот патч заменил более крупный синтаксический анализатор, написанный на C/Bison/YACC (относительно немногие люди имеют значительный опыт работы с последними двумя) с меньшим парсером в Вала (который практически любой, кто заинтересован в работе над valac, вероятно, знает и ему удобнее).

Лучшая отчетность об ошибках также была целью, IIRC.

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

В качестве побочного комментария: меня интересует Вала именно потому, что мне нравится идея иметь язык с современными функциями и чистый синтаксис, но компилируется в "родной" и "неуправляемый" язык высокого уровня (C в случае Валы), До сих пор я нашел только Валу. Я думаю о том, чтобы повеселиться, сделав Vala (или похожий язык) компилируемым для С++ (поддерживаемый Qt libs). Но так как я не хочу изобретать совершенно новый язык, я думаю о том, чтобы взять какую-то существующую грамматику. Очевидно, что обработчики, созданные вручную, не имеют письменной формальной грамматики, которую я могу повторно использовать. Ваши комментарии к этой идее приветствуются (идея глупо?).

Много Вала на самом деле является отражением решений, принятых GObject, и все может работать или не работать одинаково в С++/Qt. Если ваша цель - заменить GObject/C в valac на Qt/С++, вы, вероятно, будете работать больше, чем ожидаете. Если, однако, вы просто хотите, чтобы библиотеки С++ и Qt были доступны из Vala, это, безусловно, возможно. Фактически, Лука Бруно начал работать над этим примерно год назад (см. Раздел wip/cpp). Некоторое время он не видел активности из-за нехватки времени, а не технических проблем.

Ответ 4

Согласно документации Валы: "До 0,3.1 парсер Вала был классический гибкий сканер и комбинацию парсеров Bison LALR. Но по состоянию на Commit eba85a, синтаксический анализатор представляет собой обработчик рекурсивного спуска вручную. Мой вопрос: почему?

Здесь я специально спрашиваю о Вале, хотя вопрос мог адресоваться любому компилятору, который не использует генератор парсера. Какие являются плюсами и минусами для такого перехода от генератора парсера к ручной парсер? Каковы недостатки использования генераторов парсера (Bison, ANTLR) для компиляторов?

Возможно, программисты заметили некоторые возможности для оптимизации, которые генератор синтаксического анализатора не обнаружил, и эти пути для оптимизации потребовали совершенно другого алгоритма синтаксического анализа. Альтернативно, возможно, генератор синтаксического анализатора сгенерировал код на C89, и программисты решили, что рефакторинг для C99 или C11 улучшит удобочитаемость.

В качестве побочного комментария: меня интересует Вала именно потому, что мне нравится идея иметь язык с современными функциями и чистый синтаксис, но компилируемый в "родной" и "неуправляемый" язык высокого уровня (C in случай Валы).

Простое примечание: C не является родным. Он имеет корни в переносимости, поскольку он был разработан, чтобы абстрагировать эти детали оборудования/ОС, которые заставляли программистов так много печали при переносе. Например, подумайте о боли при использовании совершенно другого fopen для каждой ОС и/или файловой системы; Я имею в виду не только функциональность, но и различные ожидания ввода и вывода, например. разные аргументы, разные возвращаемые значения. Аналогично, C11 представляет переносные потоки; Код, который использует потоки, сможет использовать один и тот же C11-совместимый код для таргетинга на все ОС, которые реализуют потоки.

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

Возможно, использовать обработчик вручную для создания кода на С++ без особых усилий, поэтому я бы не отбросил этот вариант так быстро; Старый генератор синтаксиса flex/bison может быть полезен или не может быть более полезным. Однако это не единственный вариант. В любом случае у меня возникло бы желание подробно изучить спецификацию.

Ответ 5

Любопытно, что эти авторы прошли путь от зубров до РД. Большинство людей пошли бы в противоположном направлении.

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

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