Выбор генератора парсера
Ладно, я понимаю, что этот вопрос может звучать довольно основано на мнении, однако, поскольку у меня есть несколько конкретных критериев выбора, я думаю, что он хорошо подошел бы для SO. И вот я здесь…
В прошлом я довольно много работал над созданием компиляторов / интерпретаторов (очевидно, в основном для хобби), и по какой-то причине я застрял с Lex / Yacc (или Flex / Bison, я совершенно не понимаю, как они их теперь называют … лол).
Однако, поскольку я сейчас играю с еще одним проектом переводчика-любителя, я решил попробовать что-то другое, чтобы избежать того, что мне не нравится в Lex / Yacc.
Итак, а именно:
- Лучше C ++ — дружеский (чем C-friendly)
- Хорошая документация (желательно с некоторыми уже реализованными грамматиками + инструкции по их компиляции / использованию — звучит довольно очевидно, а?)
- Может быть LALR, LL (*), рекурсивный спуск, мне все равно (нота: входной сигнал относительно того, какой тип вы бы предпочли и для каких типов реализаций был бы хорош; Я никогда не понимал их плюсы и минусы, если честно, хотя я знаю, к чему они относятся)
- Объединение части Lexer и грамматики парсера в одном файле совсем не плохо; никогда не понимал, почему его нужно разделить на две части.
- И последнее, но не менее важное: у меня всегда были проблемы с … проблемами. Я имею в виду — по крайней мере, что касается Lex / Yacc, сообщения об ошибках разбора более или менее загадочны (
Syntax Error… Yuhuu!) И редко они помогают диагностировать проблему. (Ну, если вы не тот, кто разработал переводчик … смеется). Итак, есть ли что-нибудь лучше, чем Lex / Yacc в отношении Отчет об ошибках?
Хорошо, я надеюсь, что это не было слишком многословно. Я весь во внимании! 🙂
Решение
Я просто собираюсь ответить на последний вопрос, с небольшим изменением:
По крайней мере, что касается Lex / Yacc, сообщения об ошибках разбора более или менее загадочны (синтаксическая ошибка … Yuhuu!) и редко помогают диагностировать проблему. (Ну, если вы не тот, кто разработал переводчик … смеется). Итак, есть ли
что-нибудь лучше чемлучший способ использовать Lex / Yacc относительно сообщений об ошибках?
Ну, начнем с использования современной версии бизона, которая имеет достаточно полный руководство онлайн (и вполне возможно, установлен с исполняемым файлом, в зависимости от того, как вы устанавливаете Bison). В частности, начните с этих объявлений:
%define parse.error verbose
%define parse.lac full
Это по крайней мере заменит загадочную ошибку «синтаксическая ошибка» списком «ожидаемых» типов токенов.
Затем убедитесь, что ваши типы токенов имеют значимые имена, потому что они будут представлены пользователю как часть сообщения об ошибке. Если вы привыкли использовать IDENTIFIER как терминал, то вы, вероятно, в порядке, но сообщение «Ожидаемый TOK_YY_ID» немного вызывающе. Вы можете объявить читаемым для терминала в type объявление:
%type TOK_YY_ID "identifier"Это займет у вас только так далеко. Во многих случаях знание того, что «ожидалось», достаточно для понимания синтаксической ошибки, но иногда полезно быть более явным. В таких случаях полезно определить error правила. Правильно понять это — скорее искусство, чем наука, но это верно для всех подходов к отчету об ошибках / восстановлению; ключ заключается в том, чтобы постараться быть как можно более конкретным в отношении того, как выглядит ошибочный синтаксис, и не более конкретным, чем необходимо.
Один интересный подход к отчету об ошибках — использовать текущее состояние синтаксического анализатора и маркер предпросмотра (оба из которых видны в момент сообщения об ошибках) для поиска пользовательского сообщения об ошибке, если оно существует. Я думаю, что этот подход был частью фольклора компилятора в течение долгого времени, и я уверен, что видел несколько статей об этом за десятилетия. Вот сравнительно недавняя статья Расс Кокс.
Другие решения
Я строю генераторы парсеров и парсеры с 1969 года.
Рекурсивный спуск, YACC и JavaCC — типичные ответы, которые вы слышите.
Это генераторы парсера вашего дедушки, и они страдают от ограничений в грамматике, которую они примут. Неизменно, (особенно в случае переполнения стека), некоторые бедняги спрашивают, «как мне решить эту проблему сдвига / уменьшения» (для генераторов синтаксического анализатора LR, таких как YACC) или «как устранить рекурсию слева» (для генераторов синтаксического анализа с рекурсивным спуском или LL, например, JavaCC). Хуже того, они не могут обрабатывать грамматики, которые действительно имеют синтаксическую неоднозначность, как это происходит в большинстве сложных языков.
РВО (и GLL) парсеры позволяют вам писать контекстно-свободные грамматики … и анализировать их без суеты и суеты. Это реальный повышение производительности. Есть цена: вы можете получить неоднозначный анализ, но есть способы справиться с этим. (видеть это обсуждение проблем синтаксического анализа в C ++, которые ни YACC, ни JavaCC не могут решить самостоятельно).
Бизон (широко доступен) имеет Опция GLR; используй это! Недавние многоязычные инструменты манипулирования программами, похоже, используют GLL или GLR. Наш инструментарий реинжиниринга программного обеспечения DMS использует GLR и анализирует C ++ (полный C ++ 14 в вариантах MS и GNU!), Java, COBOL и множество других сложных языков; GLR был одним из лучших технических решений, которые я сделал в своей карьере. Stratego использует GLR. Я думаю, что RascalMPL использует GLL. Генератор парсера Elkhound GLR Скотта Макпика основан на C ++ и генерирует, я уверен, код C ++ (OP запросил ответ на основе C ++).
Горячие темы в эти дни — PEG и ANTLR4. Они лучше, чем парсеры LL или LR, но все же дают одно горе, пытаясь сформировать грамматику. (С PEG вы должны упорядочить продукцию, предполагая, что вы можете найти такой порядок, для обработки неоднозначных правил с приоритетами. С ANTLR4 у вас все еще есть определенные указатели для разрешения неоднозначности; не знаю, как он обрабатывает бесконечные заглядывания). AFAIK, никто не создавал практические парсеры C ++ с любой из этих технологий, поэтому они не оправдывают свою репутацию.
Я думаю, что GLR и GLL — ответы намного лучше.
Интересный вопрос — не уверен, что у меня есть отличный ответ на ваш актуальный вопрос, но мой «комментарий» слишком длинен для комментария …
Я работаю в компиляторе Pascal, и я в значительной степени написал Lexer, Tokenizer и Parser (включая создание AST для создания генератора кода для LLVM) примерно в 1100 строк, если можно так выразиться, довольно «приятно «кода C ++ — все вручную. Он гораздо более дружелюбен к генерированию хороших сообщений об ошибках и помогает в этом. Недостает несколько битов, и у меня еще много работы, прежде чем мой компилятор будет завершен, но я могу скомпилировать довольно сложный код.
Признаюсь, я никогда не использовал Lex / Yacc или Flex / Bison для чего-то настоящего. Я иногда смотрел на это, но мне трудно использовать эти инструменты, и вы либо заканчиваете тем, что взяли сгенерированный код и изменили его (плохая идея с автоматически сгенерированным кодом), либо с плохой обработкой ошибок, и трудно отладить код сверху того, что. Но потом я потратил около двух часов, пытаясь найти ошибку, вызванную «преждевременным употреблением» точки с запятой, что, в свою очередь, приводило к тому, что парсер терялся в потоке токенов …