[Парсеры] Мысли о PEG и Packrat
От: VladD2 Российская Империя www.nemerle.org
Дата: 25.05.09 16:08
Оценка: 5 (1)
Недавно я задавал вопрос по поводу 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)-автомат для выбора решения какое правило нужно парсить.

Другими словами вместо хранения в кэше сочетаний позиции в потоке и правила, можно будет хранить результат разбора для конкретной позиции. А это уменьшает объем требуемой для мемоизации памяти и следовательно поднимает скорость всего алгоритма.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
PEG Packrat Parser оптимизации Парсер
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.