Comments 14
Спасибо за статью. По теме парсеров интересует два вопроса:
- можно ли использовать goyacc;
- когда использовать свой парсер, а когда использовать генератор парсеров.
P.S. Я не пробовал, это скорее вопрос, нежели предложение.
На GoDays 2020 был доклад "Writing a parser in Go, the C way".
UPD видео Writing a parser in Go, the C way | Tobias Guggenmos
Есть как минимум 2 версии goyacc. Та, на которую вы ссылаетесь и более новая: https://gitlab.com/cznic/goyacc.
Реальное применение можно увидеть в проекте github.com/z7zmey/php-parser. В NoVerify как раз используется такой парсер, сгенерированный goyacc.
Аргументы в пользу использования генератора парсеров (имхо):
- У вас уже есть грамматика на руках.
- Вам важна производительность парсера.
- Сложно написать парсер вручную.
Хотя стоит заметить, goyacc не генерирует слишком быстрый парсер, там будет очень много аллокаций. Но может его нужно просто правильно готовить.
То есть:
- Да, можно.
- Смотрите по ситуации.
Хотя бы разок написать парсер ручками точно полезно. :)
Потом это быстро надоест и вы будете уже более взвешенный выбор принимать, зная плюсы и минусы обоих подходов.
А ещё алгоритм Пратта — это не новый подход. :)
Но он вроде бы не очень популярен.
В prometheus парсер на goyacc
Алгоритм Пратта — тоже рекурсивный спуск, просто с определённым подходом (расширением?), чтобы более красиво обработать произвольные выражения.
Если без какой-то системы делать, парсер будет выглядеть как запутанный код.
Конкретных примеров под рукой нет, но почти все мои первые парсеры с рекурсивным спуском были ужасны. Я даже не уверен, что они правильно обрабатывали приоритеты операций, кажется, для этого я использовал Shunting-yard, который тоже мне не с первого дня дался. До ассоциативности я, возможно, в те дни даже не доходил. :)
Парсеры Пратта довольно аккуратно решают эту проблему.
Но опять же, возможно вы очень опытный специалист в области парсинга, тогда любой ваш парсер будет хорошо выглядеть. Но это не означает, что концепции рекурсивного спуска достаточно, чтобы написать всё элегантно.
Может, стоило написать, что создать хороший парсер выражений по одному лишь описанию рекурсивного спуска можно, но это требует или опыта, или дисциплины.
Спасибо, весьма познавательно.
Код в gist'е понятен (спасибо, что скинули его в дополнение к коду Вирта, иначе было бы сложнее). Мне субъективно больше нравятся парсеры Пратта тем, что там, на мой взгляд, лучше разделена логика парсинга.
Есть ещё возможность динамически определять грамматику и дополнять её программно: почти вся логика парсера сосредоточена в отображениях {токен => обработчик}. Не то, чтобы очень мне лично было полезно, но, выражаясь по-английски, it's fascinating. :)
P.S. — удалил из статьи абзац, который вы цитировали в первом комментарии. :)
В конце статьи я ссылаюсь на Pratt Parsers: Expression Parsing Made Easy . В целом, я старался в одно предложение выразить это:
You can do this with recursive descent, but it’s a chore. You have to write separate functions for each level of precedence (JavaScript has 17 of them, for example), manually handle associativity, and smear your grammar across a bunch of parsing code until it’s hard to see.
Зачем я это вообще пытался добавить? Изначально это планировалось переводом, а потом уже осталось как артефакт после множественных редактирований.
Впрочем, я в своём компиляторе делаю обычный рекурсивный спуск. Даже Фабрис Белляр в его знаменитом TCC не стал заморачиваться и сделал то же самое. Хотя ему вообще пришлось всю грамматику C вручную переписывать под рекурсивный спуск, потому что в «официальном» виде она для этого непригодна.
Я бы сейчас дорого дал, чтобы понять, как рекурсивным спуском и без AST изящно разобрать цепной вызов методов. Я у себя добавил к
selector'ам скобки с аргументами. Но вышла неприятность. Синтаксис классического Паскаля отлично ложится на семантику: designator всегда означает адрес, factor — значение, а переход от designator'а к factor'у — просто разыменование. Однако когда появляются методы, то они могут вернуть адрес, а могут и просто число. В первом случае это вроде бы designator, а во втором — только factor.С введением причин для минусов к статье начинаешь пытаться искать корни проблемы.
Я не до конца понимаю, почему несколько людей отметили материал меткой "Низкий технический уровень материала". Если это более заметно со стороны, мне честно было бы интересно узнать, что подрывает техническую сторону статьи.
Эта статья по оценкам получилась провальной и демотивирует в том числе то, что я не знаю, как можно было бы сделать лучше.
Парсеры Пратта для чайников