Современные языки все еще используют генераторы парсеров?

Я исследовал о наборе компиляторов GCC на википедии здесь , когда это придумал:

GCC начал использовать парсеры LALR, сгенерированные с помощью Bison, но постепенно переключился на рукописные парсеры с рекурсивным спуском; для C ++ в 2004 году и для C и Objective-C в 2006 году. В настоящее время все внешние интерфейсы используют рукописные парсеры рекурсивного спуска

Таким образом, по последнему предложению (и насколько я доверяю Википедии) я могу определенно сказать, что "C (gcc), C ++ (g ++), Objective-C, Objective-C ++, Fortran (gfortran), Java (gcj), Ada (GNAT), Go (gccgo), Pascal (gpc), ... Меркурий, Modula-2, Modula-3, PL / I, D (gdc) и VHDL (ghdl) "- все интерфейсы, которые не больше использовать генератор парсеров. То есть все они используют рукописные парсеры.

Тогда мой вопрос: повсеместна ли эта практика? В частности, я ищу точные ответы на «есть ли у стандартной / официальной реализации x рукописный синтаксический анализатор» для x в [Python, Swift, Ruby, Java, Scala, ML, Haskell]? (На самом деле, информация о любых других языках также приветствуется здесь.) Я уверен, что смогу найти это самостоятельно после многих копаний. Но я также уверен, что сообщество легко ответит на это. Благодарность!

java ruby haskell parsing swift-language eatonphil
источник

Точка данных: CPython имеет генератор синтаксического анализатора LALR (pgen). Не знаю об остальном.

Точка данных: Ghc (haskell) использует генератор синтаксического анализатора LALR (happy), как и OCaml.

Твен ван Лаарховен

Должно быть «Делать современные высокопроизводительные компиляторы ...» или подобное, потому что язык - это спецификация, а не реализация, в то время как компилятор использует или не использует сгенерированный машиной синтаксический анализатор.

dmckee

@dmckee, да, ты прав. Однако наименование начинает становиться длинным и менее значимым. Не стесняйтесь редактировать его, если вы более креативны, чем я!

eatonphil

Что касается ML: MLton использует генератор синтаксических анализаторов, специфичный для ML, я на 90% уверен, что SML / NJ делает то же самое, хотя я менее знаком с ним. Вы можете или не можете считать это «рукописным».

Патрик Коллинз

Ответы:

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

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

Кроме того, старые унаследованные языки, такие как C11 или C ++ 11 (которые концептуально устарели, даже если их последней редакции всего три года) вовсе не являются контекстно-свободными. Работать с этой чувствительностью к контексту в грамматиках для генераторов синтаксических анализаторов (т. Е. Бизонов или даже менгиров ) чрезвычайно сложно.

Василий Старынкевич
источник

Concur. Хорошее восстановление после синтаксического анализа ошибок (когда вы не хотите останавливать синтаксический анализ при самой первой ошибке, как старый Borland Pascal) и создание сообщений об ошибках хорошего качества (включая подсказки и предложения по их устранению, как этого хотят люди) являются контекстом по своей сути -чувствительные, эвристические задачи. Они могут быть сделаны на выходе генератора парсера, в некоторой степени, но это не очень удобно.

Джонатан Юнис

Dealing with that context sensitiveness in grammars for parser generators is boringly difficult, Это также более или менее невозможно, поскольку эти инструменты генерируют парсеры без контекста. Правильное место для проверки наличия всех контекстно-зависимых ограничений - после того, как вы сгенерировали дерево разбора, если используете такие инструменты.

dtech

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

Сам двигатель парсера страдает на фронте производительности из-за своей универсальности. Любой рукописный код всегда будет значительно быстрее, чем движки табличного парсера.

Вторая область, в которой генераторы / механизмы синтаксического анализа сталкиваются с трудностями, заключается в том, что все настоящие языки программирования чувствительны к контексту, часто довольно тонкими способами. Языки LR не зависят от контекста, а это означает, что есть много тонкостей в позиционировании и среде, которые невозможно правильно передать в синтаксисе. Приписанные грамматики пытаются обратиться к базовым языковым правилам, таким как «объявить перед использованием» и т. Д. Встраивание этой чувствительности к контексту в рукописный код очень просто.

BobDalgleish
источник

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

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

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

BobDalgleish

C и C ++ нуждаются в информации таблицы символов во время синтаксического анализа (или принимают гораздо менее конкретное дерево разбора, где не делается различий, например, между выражениями выражений и объявлениями переменных). Но я не думал об этом. Такие языки, как Java, Lisps, JavaScript, Ruby, Python, Go, Rust, Scala, Swift, Haskell (и, возможно, еще несколько, может быть, C # и ML тоже?), Не нуждаются в такой информации для создания того типа AST, который вам нужен хочу в любом случае. Многие из них на самом деле имеют грамматику LL (1) или даже грамматику LALR.

цитаты для всех реальных языков являются контекстно-зависимыми, пожалуйста?

PSR