Недавно я задавал вопрос по поводу PEG и Packrat. На сегодня я, почитав различные работы по PEG и Packrat, сформировал мнение о них. Чем и хочу поделиться.
Вкратце, в чем суть Пакрата. PEG парсится рекурсивным нисходящим парсером с откатами (
Recursive descent parser with backup). Проблема в том, что в плохих случаях получается экспоненциальная сложность.
Демонстрируется это элементарно. Возьмем грамматику:
CustomAttrs <- '[' CustomAttr (',' CustomAttr)* ']'
CustomAttr <- ident ( ('(' Expr (',' Expr)* ')')? )? // правило Expr парсит выражение языка и здесь не приводится
Modifier <- "public" / "private" / "protected"
TypeDef <- ClassDef / StructDef / EnumDef
ClassDef <- CustomAttrs* Modifier* "class" ident { }
StructDef <- CustomAttrs* Modifier* "struct" ident { }
EnumDef <- CustomAttrs* Modifier* "enum" ident { }
Используется нотация PEG, но она очень близка к EBNF-нотации из ANTLR. По сути это смесь BNF и регулярных выражений.
Если попытаться отпарсить строку "[Attr(x)] public enum {}" рекурсивным методом с откатами, то разбирая правила ClassDef, StructDef и EnumDef парсер будет каждый раз разбирать правала CustomAttrs и Modifier. И это без учета разбора лексем, где повторений будет значительно больше.
Предложенный Фордом Packrat-парсер мемоизует (сохраняет в хэш-таблице) результат вычисления всех правил для каждой позиции входного потока и тем самым предотвращает повторный разбор одних и тех же правил. При повторном разборе правил вместо их парсинга просто делается проверка нет ли в кэше результата разбора этого правила для данной позиции входного потока. Так что при откате правила CustomAttrs Modifier не будут разбираться трижды. Вместо этого из кэша будет вынут результат разбора и количество символов которое нужно пропустить во входном потоке чтобы добраться продолжить разбор.
Теперь о проблемах...
Мемоизировать все — это тупиковый вариант. Он конечно O(n), но n там заоблачное. Расход памяти O(p*n) где "p" — количество правил в грамматике, а "n" — количество символов во входном потоке (файле). А это полные вилы. Скорость ниже плинтуса.
Без мемоизации — это будет банальный рекурсивный нисходящий парсер с откатами (бэктрекингом), что в некоторых случаях будет давать экспоненциальное время разбора. На LL(1)-грамматиках же (а немерловая грамматика очень близка к ней) парсер без мемоизации покажет тоже O(n), но при этом "n" будет очень маленьким, так что общая скорость будет значительно выше чем у Пакрата.
Проанализировав все это я пришел к выводу, что PEG можно применять только если добиться того, что мемоизация будет происходить только в там где она действительно необходима. Например если у нас есть взять приведенную выше грамматику, то
мемоизировать в ней нужно только правило CustomAttrs и Modifier.
Причем и это будет не лучший вариант. Еще лучше переписать грамматику следующим образом:
CustomAttrs <- '[' CustomAttr (',' CustomAttr)* ']'
CustomAttr <- ident ( ('(' Expr (',' Expr)* ')' )? )?
Modifier <- "public" / "private" / "protected"
CustomAttrsAndModifiers <- CustomAttrs* Modifier*
TypeDef <- ClassDef / StructDef / EnumDef
ClassDef <- CustomAttrsAndModifiers "class" ident { }
StructDef <- CustomAttrsAndModifiers "struct" ident { }
EnumDef <- CustomAttrsAndModifiers "enum" ident { }
и мемоизировать только правило CustomAttrsAndModifiers. Тога эффективность прасера будет близка к аналогичному написанному вручную.
Собственно легко понять как оптимизировать конкретную грамматику, но для создания эффективного построителя парсеров нужно как-то формализовать выявление правил требующих мемоизации. Подспудно чувствую, что это правила не удовлетворяющие LL(1)-автомату. Но тут нужно отдельное исследование.
Проблема в том, что построение ДКА для LL(1) во время парсинга может оказаться слишком затратной операцией. Таким образом оптимизация на базе построения ДКА может оказаться не приемлема для языков с динамически расширяемым синтаксисом вроде Немерле.
Кром
е того в PEG есть еще один источник неэффективности. Это последовательный перебор правил в операторе выбора — "/". Во многих случаях по первому входному символу можно будет с сразу определить набор правил которые будут удовлетворять входному символу, а следовательно можно отбросить просмотр правил которые точно не будут разобраны успешно. По сути это идея применения LL(1)-автомата, но ограничено (только для входа в правило). Эта оптимизация опять таки противоречит духу динамичности, но возможно ее все же можно будет реализовать в рантайме если каждое правило будет экспортировать "предсказание" — набор символов с которых может начинаться правило.
Кроме того возможно не следует отказываться от наличия лексера. С одной стороны PEG подкупает возможностью построения безлексерной грамматики, и тем самым неограниченым расширением грамматики, но с другой эффетивность мемоизации слишком низка. Лексер основанный на принципах ДКА знчительно эффективнее Парката или неоптимизированного рекурсивного парсера с откатами.
Еще одной возможной оптимизацией может быть следующий подход.
Думаю, что довольно часто будет встречаться случай когда для некоторого входного символа будет разбираться определенный набор подправил (доступных не напрямую, а из других подправил). Примером тому может служить как раз приведенная выше грамматика. В ней в начале разбора подстрока "[Attr(x)] public" всегда будет разбираться как последовательность правил CustomAttrs Modifier. При этом других допустимых альтернатив не будет. Если это возможно предсказать, то в точке разбора правила TypeDef можно сразу проверять наличие мемоизированного результата парсинга этих правил. В случае их наличия можно смело прокручивать строку на конец этого участка (его длинна должна храниться в кэше) и далее возможено использовать LL(1)-автомат для выбора решения какое правило нужно парсить.
Другими словами вместо хранения в кэше сочетаний позиции в потоке и правила, можно будет хранить результат разбора для конкретной позиции. А это уменьшает объем требуемой для мемоизации памяти и следовательно поднимает скорость всего алгоритма.