Как партизаны Pratt сравниваются с другими типами парсеров и почему они так мало используются?

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

Почему партизаны Pratt так мало используются? Имеют ли они какие-либо серьезные ограничения или недостатки, о которых я не знаю? Как именно они сравниваются с другими типами парсеров? Когда мне и когда не следует использовать их?

Ответ 1

Очень мало различий между парсером Pratt и так называемым парсером "шунтирующий двор" (который содержит гораздо более длинную статью в Википедии); основное отличие состоит в том, что Pratt использует рекурсию и, следовательно, стек, тогда как Djikstra ( "шунтирующий двор" ) содержит явный стек. Помимо этого, они выполняют точно такую же последовательность операций. Я полагаю, что выражение Джикстры алгоритма чаще встречается из-за рекурсофобии.

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

Книга Дракона включает альгортм, который будет генерировать таблицу приоритетов оператора из грамматики. Как отмечается, тот факт, что алгоритм преуспевает, не обязательно означает, что синтаксический анализатор приоритета оператора будет анализировать точно такой же язык. Там более интересная информация, которую я, конечно, забыл; если вас интересует алгоритм, это одно из мест, которые вы могли бы посмотреть. Он включает в себя интересное представление о том, и > операторы отношения интенсивностей могут быть сгенерированы, если посмотреть на вывод, если вы окружаете результат производства с помощью < и > очевидным образом.

В целом, мой опыт заключается в том, что большую часть времени, когда вы находите сообщение в блоге, говорящее "Боже мой, я только что наткнулся на X, и это здорово и почему больше людей не знают об этом????", ответ: "Пожалуйста, не думайте, что ваше невежество универсально". Но, может быть, я сейчас в циничном настроении.

Кстати, парсер Lua представляет собой ручной рекурсивный синтаксический анализатор, который использует синтаксический анализ стиля Pratt для разбора выражений; что довольно распространенная техника, я думаю, и вы, вероятно, найдете ее в других местах, хотя вам, возможно, придется пробраться через код, чтобы увидеть шаблон.