Недавно я задавал вопрос по поводу PEG и Packrat. На сегодня я, почитав различные работы по PEG и Packrat, сформировал мнение о них. Чем и хочу поделиться.
Вкратце, в чем суть Пакрата. PEG парсится рекурсивным нисходящим парсером с откатами (Recursive descent parser with backup). Проблема в том, что в плохих случаях получается экспоненциальная сложность.
Демонстрируется это элементарно. Возьмем грамматику:
Используется нотация 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.
Причем и это будет не лучший вариант. Еще лучше переписать грамматику следующим образом:
и мемоизировать только правило CustomAttrsAndModifiers. Тога эффективность прасера будет близка к аналогичному написанному вручную.
Собственно легко понять как оптимизировать конкретную грамматику, но для создания эффективного построителя парсеров нужно как-то формализовать выявление правил требующих мемоизации. Подспудно чувствую, что это правила не удовлетворяющие LL(1)-автомату. Но тут нужно отдельное исследование.
Проблема в том, что построение ДКА для LL(1) во время парсинга может оказаться слишком затратной операцией. Таким образом оптимизация на базе построения ДКА может оказаться не приемлема для языков с динамически расширяемым синтаксисом вроде Немерле.
Кроме того в PEG есть еще один источник неэффективности. Это последовательный перебор правил в операторе выбора — "/". Во многих случаях по первому входному символу можно будет с сразу определить набор правил которые будут удовлетворять входному символу, а следовательно можно отбросить просмотр правил которые точно не будут разобраны успешно. По сути это идея применения LL(1)-автомата, но ограничено (только для входа в правило). Эта оптимизация опять таки противоречит духу динамичности, но возможно ее все же можно будет реализовать в рантайме если каждое правило будет экспортировать "предсказание" — набор символов с которых может начинаться правило.
Кроме того возможно не следует отказываться от наличия лексера. С одной стороны PEG подкупает возможностью построения безлексерной грамматики, и тем самым неограниченым расширением грамматики, но с другой эффетивность мемоизации слишком низка. Лексер основанный на принципах ДКА знчительно эффективнее Парката или неоптимизированного рекурсивного парсера с откатами.
Еще одной возможной оптимизацией может быть следующий подход.
Думаю, что довольно часто будет встречаться случай когда для некоторого входного символа будет разбираться определенный набор подправил (доступных не напрямую, а из других подправил). Примером тому может служить как раз приведенная выше грамматика. В ней в начале разбора подстрока "[Attr(x)] public" всегда будет разбираться как последовательность правил CustomAttrs Modifier. При этом других допустимых альтернатив не будет. Если это возможно предсказать, то в точке разбора правила TypeDef можно сразу проверять наличие мемоизированного результата парсинга этих правил. В случае их наличия можно смело прокручивать строку на конец этого участка (его длинна должна храниться в кэше) и далее возможено использовать LL(1)-автомат для выбора решения какое правило нужно парсить.
Другими словами вместо хранения в кэше сочетаний позиции в потоке и правила, можно будет хранить результат разбора для конкретной позиции. А это уменьшает объем требуемой для мемоизации памяти и следовательно поднимает скорость всего алгоритма.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Теперь о проблемах...
Вот тут изложены идеи полутора десятков оптимизаций для packrat: Better Extensibility through Modular Syntax
реализация (на Java): http://www.cs.nyu.edu/~rgrimm/xtc/xtc-core.zip
Полученные парсеры работают примерно со скоростью ANTLR 2.7 потребляя в 2 раза больше памяти.
VD>Мемоизировать все — это тупиковый вариант. Он конечно O(n), но n там заоблачное. Расход памяти O(p*n) где "p" — количество правил в грамматике, а "n" — количество символов во входном потоке (файле). А это полные вилы. Скорость ниже плинтуса.
VD>Проанализировав все это я пришел к выводу, что PEG можно применять только если добиться того, что мемоизация будет происходить только в там где она действительно необходима. Например если у нас есть взять приведенную выше грамматику, то мемоизировать в ней нужно только правило CustomAttrs и Modifier.
Rats! по умолчанию он мемоизирует все(при этом расход памяти оптимизациями сокращен в 5-10 раз). Результатом вполне можно пользоватся: на мегабайт исходника нужно примерно 300 мег памяти. Потом (при необходимости) можно провести ручную дооптимизацию: пометить правила, которые не нужно мемоизировать. Это, в общем, работает.
Здравствуйте, z00n, Вы писали:
Z>Здравствуйте, VladD2, Вы писали:
VD>>Теперь о проблемах... Z>Вот тут изложены идеи полутора десятков оптимизаций для packrat: Z>Better Extensibility through Modular Syntax Z>реализация (на Java): http://www.cs.nyu.edu/~rgrimm/xtc/xtc-core.zip Z>Полученные парсеры работают примерно со скоростью ANTLR 2.7 потребляя в 2 раза больше памяти.
Это "Rats!"? В нем оптимизации сделаны несколько не с того конца. В нем думаю что можно не мемоизировать, а не о том, что нужно мемоизировать. А это, на мой взгляд, не верный подход.
Работу по нему я читал.
Z>Rats! по умолчанию он мемоизирует все
И это в корне не верно, на мой взгляд.
Z>(при этом расход памяти оптимизациями сокращен в 5-10 раз). Результатом вполне можно пользоватся: на мегабайт исходника нужно примерно 300 мег памяти.
Мне кажется это многовато. К тому же это неминуемо замедлит парсинг.
Z> Потом (при необходимости) можно провести ручную дооптимизацию: пометить правила, которые не нужно мемоизировать. Это, в общем, работает.
Согласен. Но есть не мало работ демонструющих, что часто без мемоизации разультат получается лучше. Если грамматика близка к LL(1), то мемоизация всего подряд (даже с оптимизациями) может только навредить. Возможно, что обратный подход дал бы больше толку.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>Если попытаться отпарсить строку "[Attr(x)] public enum {}" рекурсивным методом с откатами, то разбирая правила ClassDef, StructDef и EnumDef парсер будет каждый раз разбирать правала CustomAttrs и Modifier.
Если построить минимизированный НКА по этим правилам, то эти первые одинаковые состояния просто склеятся в процессе минимизации и никаких возвратов не будет.
И что касается динамики: можно сразу строить минимизированный НКА, добавляя правила по ходу пьесы.
Здравствуйте, vdimas, Вы писали:
V>Если построить минимизированный НКА
Это что то новое в теории конечных автоматов?
Минимизированный НКА — это ДКА. Об этом я уже говорил. Проблема в том, что само динамическое построение ДКА — это затраты времени и резкое усложнение реализации.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
V>>Если построить минимизированный НКА
VD>Это что то новое в теории конечных автоматов? VD>Минимизированный НКА — это ДКА.
Не всегда, а только в случае, если эквивалентные цепочки, разбираемые по разным правилам, будут означать тождественность этих правил.
Например:
A -> a | c
B -> b | c
S -> A
S -> B
Если на входе будет 'a' или 'b', то имеем детерминированный разбор, а если 'c', то либо объявляем конфликт, либо объединяем правила A и B в некое новое, а иначе никакого ДКА не пролучишь.
Здравствуйте, vdimas, Вы писали:
V>Если на входе будет 'a' или 'b', то имеем детерминированный разбор, а если 'c', то либо объявляем конфликт, либо объединяем правила A и B в некое новое, а иначе никакого ДКА не пролучишь.
Естественно. Но наличие S -> A и S -> B говорит о том, что КА не минимальный.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
V>>Если на входе будет 'a' или 'b', то имеем детерминированный разбор, а если 'c', то либо объявляем конфликт, либо объединяем правила A и B в некое новое, а иначе никакого ДКА не пролучишь.
VD>Естественно. Но наличие S -> A и S -> B говорит о том, что КА не минимальный.
"S -> A" это нотация вывода, т.е. всего лишь условие задачи, но никак не описание переходов. По-хорошему, эту нотацию еще надо перевести в язык регулярных выражений, из которого удобно строить КА. Просто такой нотацией я показал состояния, которые будут однозначно соответствовать конечным состояниям автомата в модели Мура. Алгоритм минимизации КА должен пометить эти состояния как особые (различимые) и не допустить их склейки. А в случае необходимости оной для получения ДКА выдавать предупреждение "конфликт".
В общем, для PEG грамматики, которая допускает вложенные и рекурсивные определения (в отличие от регулярной), эти A и B могли участвовать и других правилах вывода (а не S -> A, как я показал). В этом случае и получался НКА, который имел один переход из предыдущего (не указанного здесь) состояния по 'a' и 'b', и имел бы два перехода по 'c'. Конфликт вполне мог бы решаться в духе PEG — приоритезацией.
Здравствуйте, vdimas, Вы писали:
V>По-хорошему, эту нотацию еще надо перевести в язык регулярных выражений, из которого удобно строить КА.
Это что-то новое в теории КА и CFG. Раньше считалось, что из регулярной грамматик построить рекурсивную грамматику невозможно в принципе. Так что кому-то из нас нужно подучить марчасть для продолжения осмысленной дискуссии.
Алгоритм 2.2. Преобразование НКА в ДКА
Вход: НКА M = (Q, T , F , H , Z ) .
Выход: ДКА M ′ = (Q′, T , F ′, H , Z ′) .
Шаг 1. Пометить первый столбец таблицы переходов M ′ ДКА начальным
состоянием (множеством начальных состояний) НКА M .
Шаг 2. Заполняем очередной столбец таблицы переходов M ′ , помечен-
ный символами D , для этого определяем те состояния M , которые могут быть
достигнуты из каждого символа строки D при каждом входном символе x . По-
местить каждое найденное множество R (в том числе ∅ ) в соответствующие
позиции столбца D таблицы M ′ , т.е.:
F ′( D, x) = {s | s ∈ F (t , x) для некоторого t ∈ D }.
Шаг 3. Для каждого нового множества R (кроме ∅ ), полученного в
столбце D таблицы переходов M ′ , добавить новый столбец в таблицу, поме-
ченный R .
Шаг 4. Если в таблице переходов КА M ′ есть столбец с незаполненными
позициями, то перейти к шагу 2.
Шаг 5. Во множество Z ′ ДКА M ′ включить каждое множество, поме-
чающее столбец таблицы переходов M ′ и содержащее q ∈ Z НКА M .
Шаг 6. Составить таблицу новых обозначений множеств состояний и оп-
ределить ДКА M ′ в этих обозначениях.
V>Просто такой нотацией я показал состояния, которые будут однозначно соответствовать конечным состояниям автомата в модели Мура. Алгоритм минимизации КА должен пометить эти состояния как особые (различимые) и не допустить их склейки. А в случае необходимости оной для получения ДКА выдавать предупреждение "конфликт".
В нашем случае объеденение состояний не проблема. У нас упрощенный автомат который должен всего лишь предсказать те правила которые имеет смысл проверять для конкретного входного символа.
Реально задача выливается в создании простейшего НКА и его преобразовании в ДКА алгоритмом Кнута.
Проблем только в том, что это резко усложняет исходный алгоритм и делает трудным динамическое его использование.
V>В общем, для PEG грамматики, которая допускает вложенные и рекурсивные определения (в отличие от регулярной),
Еще раз. Регулярные грамматики тут вообще не причем. Ты зря их сюда приплел. В нашем случае речь нужно вести о LL(1)-предсказателе.
V>эти A и B могли участвовать и других правилах вывода (а не S -> A, как я показал). В этом случае и получался НКА, который имел один переход из предыдущего (не указанного здесь) состояния по 'a' и 'b', и имел бы два перехода по 'c'. Конфликт вполне мог бы решаться в духе PEG — приоритезацией.
Нет нужды решать конфликт. Два перехода надо сливать в один но при этом в узел надо помещать информацию о том, что в нем возможен разбор двух правил.
Еще раз подчеркиваю, что для оптимизации PEG (точнее Пакрат-алгоритма) нет нужды создавать полный LL(чего угодно)-автомат. Нам нужен только один первый его шаг! Предсказатиель (предположим табличный) должен всего лишь ответить на один поставленный вопрос — "какие правила нужно пробовать разобрать для конкретного символа в данном месте грамматики?".
То есть вместо одной огромной таблицы переходов нам нужно создавать множество очень простых и маленьких табличек определяющих какие из альтернативных правил нужно пробовать разобрать. Причем если правил более одного, то имеет смысл мемоизировать результат разбора.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
V>>По-хорошему, эту нотацию еще надо перевести в язык регулярных выражений, из которого удобно строить КА.
VD>Это что-то новое в теории КА и CFG. Раньше считалось, что из регулярной грамматик построить рекурсивную грамматику невозможно в принципе. Так что кому-то из нас нужно подучить марчасть для продолжения осмысленной дискуссии.
VD>Для справки НКА переводится в ДКА путем всем известного алгоритма описанного Кнутом много лет назад. Вот первое попавшееся описание в гугле: VD>http://window.edu.ru/window_catalog/pdf2txt?p_id=1561
Влад, вместо ликбеза читай внимательно оппонента, а то сразу становится очень скучно. К тому же алгоритмов минимизации больше одного.
1. Приведенный пример легко приводим к рег. выражениям.
2. Ты спорол глупость насчет "S -> A и S -> B говорит о том, что КА не минимальный", я тебя мягко поправил без претензий на ликбез, ибо нотация и переходы — это несколько разные вещи.
3. Рекурсивность правила не означает его неприводимости к классу регулярных грамматик, зависит от конкретных правил.
4. Существует т.н. язык расширенных регулярных выражений, в котором могут участвовать "нетерминалы" в правилах, при условии, что полученная система после раскрытия приводима к рег. выражениям.
Вот по последнему пункту я прилично возился в свое время, поэтому представляю (хочется думать) проблематику PEG.
VD>Проблем только в том, что это резко усложняет исходный алгоритм и делает трудным динамическое его использование.
5. есть алгоритм построения сразу минимизированного ДКА по рег. выражениям, никаких проблем. Именно вариацию последнего для построения НКА я и предлагаю использовать в случае PEG, ибо PEG и рег. выражения более чем близки.
В принципе, т.к. у меня есть кое-какие наработки, дай мне просто интересующую систему правил на PEG, и я попробую реализовать то самое поэтапное добавление правил. (единственная просьба — правило не должно содержать отрицания, т.к. этот момент пока не сделан и не охота отвлекаться)
V>>В общем, для PEG грамматики, которая допускает вложенные и рекурсивные определения (в отличие от регулярной),
VD>Еще раз. Регулярные грамматики тут вообще не причем. Ты зря их сюда приплел. В нашем случае речь нужно вести о LL(1)-предсказателе.
С какой стати LL(1)? В общем случае LL(k), и это к — произвольно, поэтому LL(k) здесь не очень удобен.
VD>Нет нужды решать конфликт. Два перехода надо сливать в один но при этом в узел надо помещать информацию о том, что в нем возможен разбор двух правил.
Это если A и B больше не участвуют ни в каких других правилах, а иначе там не все так просто.
VD>То есть вместо одной огромной таблицы переходов нам нужно создавать множество очень простых и маленьких табличек определяющих какие из альтернативных правил нужно пробовать разобрать. Причем если правил более одного, то имеет смысл мемоизировать результат разбора.
Если правил больше одного в каждой ячейке таблицы — то это и есть НКА.
Нет смысла делать кучу табличек, ибо и в одной не может быть больше состояний, чем суммарная длина правил (в символах), а в минимизированном варианте в общем случае и того меньше. В общем, давай системку интересующих правил, попробую показать, что имел ввиду.
-----------
PEG-система — вообще идеальный вариант для вынашиваемой давно идеи — автоматического выделения регулярного подмножества из правил.
Здравствуйте, VladD2, Вы писали:
VD>На сегодня я, почитав различные работы по PEG и Packrat, сформировал мнение о них. Чем и хочу поделиться.
Думаю в тему:
IronMeta is an implementation of Alessandro Warth's OMeta metaprogramming system in C#. It provides a packrat parser generator that generates parsers for Parsing Expression Grammars that operate on arbitrary streams of objects.
Здравствуйте, vdimas, Вы писали:
V>В принципе, т.к. у меня есть кое-какие наработки, дай мне просто интересующую систему правил на PEG, и я попробую реализовать то самое поэтапное добавление правил. (единственная просьба — правило не должно содержать отрицания, т.к. этот момент пока не сделан и не охота отвлекаться)
Классика не выражаемая регулярными грамматиками (PEG):
Expr <- '(' Expr ')' / Additive
Additive <- Multitive '+' Additive / Multitive '/' Additive
Multitive <- Num '*' Multitive / Num '/' Multitive
Num <- [0..9]
Предположим, что данные правила могут расширяться динамически для добавления новых операторов и задания их приоритетов.
Таким образом перед Additive, между Additive и Multitive, а также после Multitive могут быть добавлены новые операторы.
К примеру, при добавлении оператора с приоритетом между Additive и Multitive грамматика изменится следующим образом:
V>С какой стати LL(1)? В общем случае LL(k), и это к — произвольно, поэтому LL(k) здесь не очень удобен.
В общем случае LL(*) с неограниченным заглядыванием вперед, но так как нам нужно предсказывать только переход на правило, а не разбор всего правила, то хватит LL(1)-предсказателя.
V>Если правил больше одного в каждой ячейке таблицы — то это и есть НКА.
Это если переходов по одному символу больше одного. А у переход на конец один, но конец может содержать список правил PEG-а, которые в терминах КА не выражается.
V>Нет смысла делать кучу табличек, ибо и в одной не может быть больше состояний, чем суммарная длина правил (в символах), а в минимизированном варианте в общем случае и того меньше. В общем, давай системку интересующих правил, попробую показать, что имел ввиду.
Правила вверху, но общая таблица будет слишком большой. Плюс ее невозможно создать, так как грамматику нужно собирать динамически.
V>----------- V>PEG-система — вообще идеальный вариант для вынашиваемой давно идеи — автоматического выделения регулярного подмножества из правил.
Да. Но не всегда это нужно. Для того же немерля я склоняюсь к тому, чтобы просто использовать универсальный лексер.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Achill, Вы писали:
A>Думаю в тему: A>
IronMeta is an implementation of Alessandro Warth's OMeta metaprogramming system in C#. It provides a packrat parser generator that generates parsers for Parsing Expression Grammars that operate on arbitrary streams of objects.
Здравствуйте, Achill, Вы писали:
A>Думаю в тему: A>
IronMeta is an implementation of Alessandro Warth's OMeta metaprogramming system in C#. It provides a packrat parser generator that generates parsers for Parsing Expression Grammars that operate on arbitrary streams of objects.
Поглядел. Это прямолинейная реализация расширенного Packrat из работы:
Alessandro Warth, James R. Douglass, Todd Millstein (January 2008) (PDF). Packrat Parsers Can Support Left Recursion. Viewpoints Research Institute. http://www.vpri.org/pdf/tr2007002_packrat.pdf. Retrieved on 2008-10-02.
Данная реализация поддерживает левую рекурсию.
Однако судя по коду (реализация сделана на комбинаторах и итераторах) и в упор не видимых оптимизаций работать этот парсер будет не шустро.
В прочем, как пример реализации — очень не плохо.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
По-хорошему, эту нотацию еще надо перевести в язык регулярных выражений, из которого удобно строить КА. Просто такой нотацией я показал состояния, которые будут однозначно соответствовать конечным состояниям автомата в модели Мура. Алгоритм минимизации КА должен пометить эти состояния как особые (различимые) и не допустить их склейки. А в случае необходимости оной для получения ДКА выдавать предупреждение "конфликт". 
