Афихеть

В Идее есть лимитированная поддержка AOP. Там есть небольшой язычок для описания мест в коде, его парсер писал я примерно с год назад. По ходу написания случайно изобрел парсер-комбинаторы, потом понял, что код получается не очень читабельным, и совсем не дебаживаемым. После основного написания периодически выяснялось, что язычок умеет чуть больше, чем я, приходилось этот парсер подхачивать, в итоге он приобрел совсем жуткий вид.

И вот когда, наконец, в релизе еще один юзер заметил еще одну неподдерживаемую фичу в языке, я таки решил посмотреть, как же такую неоднозначную грамматику парсят сами создатели. Скачал исходники, нашел там парсер их Джавы, и... Что я вижу? Классы PrefixParser и InfixParser, метод ExprParser#parse с параметром-приоритетом, ну и вааще. Итого, они используют Пратта! При этом в коде он нигде не упоминается, но это типичный он. Ну, чуть измененный, притом не так, как у меня... Возможно, они его сами изобрели. Возможно, нет. Не знаю. Но сам факт!

Ложка дегтя. Так они парсят только Жаву. Сам аоп парсится обычным рекурсивным спуском.

Развлекся

Есть у нас в Идее язык по имени QL, эдакая упрощенная версия SQL, диалекты которой используются в EJB и Hibernate. На вид несложный, однако в парсере периодически приходится туговато. Парсер, естественно, написан рекурсивным спуском, двумя с половиной разными людьми, и выглядит достаточно страшно. Я, в качестве добровольного каникулярного развлечения, попытался написать то же самое с использованием Праттовского метода. Тожесамовость измеряется duck-критерием: есть 141 тест, и на них нужно выдавать такое же дерево, что и старый парсер. В код старого парсера я смотрел нечасто, поэтому то, что незатестировано, соответственно, не воспроизведено.

Занял этот процесс полтора рабочих дня (хороших таких дня, когда практически никто не отвлекает). При этом в середине я очередной раз осознал, что интерфейс мне не нравится, и в очередной раз переписал фреймворк, теперь он работает чуть по-другому, чем описано в предыдущем посте. И вот итоги.

Код парсера занимает меньше места: 1032 строки в старом против 620 в новом. При этом есть 14 стандартных постфиксных субпарсера и 21 инфиксный, все они выражаются здесь одной строчкой, в оригинальном парсере - побольше (строчек 5 в среднем, я думаю).

Читать новый парсер и проще и сложнее одновременно. Сложнее потому, что он необычен, непривычен, и потому, что нужно очень хорошо себе представлять стек исполнения во время парсинга многих токенов. В рекурсивном спуске обычно хватает названия метода, парсящего текущий нетерминал, и, может быть, каких-нибудь флажковых параметров. Здесь периодески нужно знать, какие узлы слева уже построились, и при построении каких узлов процесс парсинга вызывался рекурсивно. Самая жестокая моя проверка в этой области звучит так: если наш токен парсится первым в этом стековом фрейме, в следующем слева от нас есть запятая, перед которой мы распарсили декларацию переменной, то идентификатор мы парсим как TypeReference. А иначе (тоже не всегда) - как ReferenceExpression.

Теперь почему читать проще. Потому что поток управления проще. Интереса ради я сравнил количество управляющих ключевых слов, которые смог придумать. Итак:

keyword       old       new 
------------------------------
if            >107      57
else if       28        1
else          12        6
while (все)   16        15
while (true)  3         11 (типа простой цикл)
break         6         11
for (java 5)  0         3
return        65        35

Переменные    47        37
Вызовы mark() 28        13

Максимальный уровень блочной вложенности в новом парсере 4, в старом - 7 (к счастью, только в одном месте, в среднем же примерно одинаково).

Вообще, конечно, Пратту такое и не снилось. Он статью писал вообще-то даже не про парсеры, а про языки. Что если придумать язык, который таким вот парсером парсится легко и без проблем, то и человеку он будет совсем понятным. А когда нетерминалы не определяются одним-единственным токеном однозначно, то это есть плохо и непонятно. Отсюда мораль - QL - это не самый понятный для человека язык (согласен, особенно joins).