Обещают линейное время парсинга. Причем с неограниченным декларативно-выраженным заглядыванием вперед.
Вроде как даже можно динамически парсер строить (очень полезно для макросов).
Просто чудеса, да и только. А я в чудеса не верю. Какие реальные слабые места могут быть у этого чуда и чудо ли это?
В общем, приветствуются любые мысли.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Вопрос к людям разбирающимся в алгоритмах парсинга и компиляторо-строении.
Я не разбираюсь, но встречал такое мнение:
Traditionally, PEG parsers have suffered from two major flaws:
* A global table of all productions must be generated or written by hand, disallowing composable parsers implemented as libraries and in general requiring the use of a parser generator tool like pappy
* Although memory consumption is linear in the size of the input, the constant factor is very large.
Здравствуйте, palm mute, Вы писали:
PM> * A global table of all productions must be generated or written by hand, disallowing composable parsers implemented as libraries and in general requiring the use of a parser generator tool like pappy
Гм. Интересно. А у меня тут похоже получается комбинаторый парсер с правилами высшего порядка.
PM> * Although memory consumption is linear in the size of the input, the constant factor is very large.
А вот это я как раз сейчас проверю.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Кстати, из твоей ссылки:
ANTLR, a well-established parser generator by Terence Parr, now in version 3 supports extensive PEG features and combines packrat parsing with LL parsing techniques. Also supports other language targets.
Так что же получается, что LL(*) и PEG — это одно и то же?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали: VD>Вопрос к людям разбирающимся в алгоритмах парсинга и компиляторо-строении. VD>Каково ваше мнение о Parsing expression grammar?
Кстати, присоединяюсь к вопросу. Я пока не совмем понимаю, что такого особенного в PEG, поскольку сейчас они мне кажутся лишь упрощенной формой записи контекстно-свободных грамматик Хомского. Соответственно, и алгоритмы разбора должны быть теми же самыми. А судя по разделу "Interpretation of parsing expressions" википедийной статьи — получается, что PEG предполагают разбор фактически LL-парсером с возвратом, за счет которого достигается выход за рамки LL(1), а без возвратов получается тот же LL(1), вид сбоку.
Другое дело, что в той же википедии обещается "контроль над выбором дерева разбора" — т.е. над разрешением неопределенностей. Пока мне кажется, что это достигается исключительно особенностями реализации разбора: использованием упорядоченного "или", хаками вокруг левой рекурсии и т.п.
Т.е. на первый взгляд packrat — подход к накачке стероидами LL(k) грамматик, т.е. в итоге на выходе должно получиться что-то аналогичное antlr (кстати, почему-то вспоминается еще parsec), как по удобству использования, так и по перфомансу. Вот.
Поправьте меня, если я неправ. Тема эта для мне интересна, но, увы, пока я в ней плаваю.
Здравствуйте, VladD2, Вы писали:
VD>Вопрос к людям разбирающимся в алгоритмах парсинга и компиляторо-строении.
VD>Каково ваше мнение о Parsing expression grammar?
VD>http://pdos.csail.mit.edu/~baford/packrat/popl04 VD>http://www.tinlizzie.org/~awarth/papers/pepm08.pdf
VD>Обещают линейное время парсинга. Причем с неограниченным декларативно-выраженным заглядыванием вперед.
Разве на практике скорость не всегда линейная? "портят" скорость неоднозначности. А они, как правило, носят локальный характер.
Ох, если бы она была не линейная, то разобрать сколько-нибудь большой текст вызывало бы большие большие затраты времени. VD>Вроде как даже можно динамически парсер строить (очень полезно для макросов).
VD>Просто чудеса, да и только. А я в чудеса не верю. Какие реальные слабые места могут быть у этого чуда и чудо ли это?
VD>В общем, приветствуются любые мысли.
Я тоже не думаю, что это чудо
Просто ввели некоторое ограничение на выразительность грамматики ( альтернативу | заменили на альтернативу с приоритетом / ) и это позволило упростить алгоритм разбора и тем самым улучшить теоретическую оценку производительности.
Проблема подхода в том, что грамматика должна быть однозначной. Если она неоднозначная (представим, что вместо | у нас / ), то будет построено одно из деревьев разбора, которые были бы построены при других подходах.
Как я понимаю, могут использоваться немного модифицированные существующие алгоритмы разбора — как рекурсивный нисходящий (recursive descent), так и автомат (LR(*)).
Я написал парсер для своего Hyperlua на XTC Rats!, который и есть достаточно оптимизированная реализация pakrat на Java. Могу сделать несколько замечаний практического характера.
История: формализм PEG придумали (и забыли) в 70-ые. Форд вдохнул в PEG вторую жизнь в 2002, придумав для диплома алгоритм pakrat, который позволил парсить PEG за линейное время.
Время действительно линейное, но это результат жесткой мемоизации. Rats! по скорости примерно как ANTLR 2.75, но pakrat для работы требует немерянного количества памяти (x600 от размера файла для оригинальной реализации и примерно x100 для Rats!).
С другой стороны есть точка зрения, что PEG — отличный формализм, а вот pakrat практически не нужен. Я сам так считаю после того, как сравнил скорость своего парсера луа с чужим парсером написанном на lua LPEG(PEG виртуальная машина без мемоизации) — скорость была примерно одинаковая, а памяти LPEG ел на порядок меньше.
С практической точки зрения PEG — это примерно LL(*) парсер с синтаксическими предикатами как в ANTLR 3(это не случайно, Парр повзаимствовал их из PEG), но главная сила PEG в том, что грамматики можно писать модульно. GLR тоже поддерживает композицию грамматик, но во-первых GLR (практически) еще медленнее, чем PEG, во-вторых PEG поддерживает еще и пересечение и дополнение, в третьих предикаты — приятная вещь. Из минусов — проблема левой рекурсии, и в некоторм роде то, что все модульные граматтики должны быть scannerless (GLR тоже), что их замедляет.
Команда Xtc Rats! написала несколько парсеров и языков: у них есть хорошего качества парсеры Java, C, а также язык (Jennie), который позволяет писать на С внутри файлов на Java — полученный объединением грамматик С и Java. Парсер Java 1.5 получен из парсера Java 1.3 дописыванием модулей.
Здравствуйте, z00n, Вы писали: Z>Roberto Ierusalimschy (автор Lua) — рассматривает PEG как будущую замену регэкспам — при соизмеримой с PCRE скорости они намного мощнее и формальнее
Только запись длиннее. Так что пока живы шелл-скрипты и программисты-любители "одностроков", pcre будет жить.
Здравствуйте, Mr.Cat, Вы писали:
MC>Другое дело, что в той же википедии обещается "контроль над выбором дерева разбора" — т.е. над разрешением неопределенностей. Пока мне кажется, что это достигается исключительно особенностями реализации разбора: использованием упорядоченного "или", хаками вокруг левой рекурсии и т.п.
Да, упорядоченностьупрощает жизнь. Вместо разрешения конфликтов тупо берём первый же подходящий вариант разбора. "Хак" вокруг левой рекурсии такой же, как и везде, — не заходить рекурсивно дважды в одно и то же правило. Для ФБН тоже можно правила упорядочивать с целью разрешения неоднозначностей.
MC>Т.е. на первый взгляд packrat — подход к накачке стероидами LL(k) грамматик
Никакой накачки, раскрыв все скобки и введя промежуточные нетерминалы, можно привести к ФБН, и не факт, что будет LL(k) — смотря как правила составлены.
MC>Поправьте меня, если я неправ. Тема эта для мне интересна, но, увы, пока я в ней плаваю.
Мне интересным кажется сама упрощенная запись, т.к. вместо системы правил пишем выражения. Если запретить рекурсивное употребление нетерминалов, то мы получем язык расширенных регулярных выражений, а он крайне популярен для записи грамматик для лексеров. На C# у меня есть небольшая либа с переопределёнными операторами +/*/! и т.д. — как раз чтобы записывать прямо в языке эти выражения и на лету строить минимизированный ДКА для лексера. Не вижу проблем расширить ф-сть до PEG, ведь начальный НКА одинаково строится для обоих случаев.
Здравствуйте, Mr.Cat, Вы писали:
MC>Только запись длиннее. Так что пока живы шелл-скрипты и программисты-любители "одностроков", pcre будет жить.
Запись сохраняется прежняя — из более мощного легко сделать менее мощное.
Компилятор из регэкспов в LPEG входит в комплект, написан на луа и занимает 200 строк. Кстати, вся LPEG VM — dll размером 30K. Regex syntax for LPEG
Здравствуйте, vdimas, Вы писали:
MC>>Т.е. на первый взгляд packrat — подход к накачке стероидами LL(k) грамматик V>Никакой накачки, раскрыв все скобки и введя промежуточные нетерминалы, можно привести к ФБН, и не факт, что будет LL(k) — смотря как правила составлены.
Я в ответе на свое сообщение поправился.
Здравствуйте, Aleх, Вы писали:
VD>>Обещают линейное время парсинга. Причем с неограниченным декларативно-выраженным заглядыванием вперед. A>Разве на практике скорость не всегда линейная? "портят" скорость неоднозначности. А они, как правило, носят локальный характер.
Вот эту испорченность pacrat и правит, за счёт запоминания результатов lookahead.
A>Проблема подхода в том, что грамматика должна быть однозначной. Если она неоднозначная (представим, что вместо | у нас / ), то будет построено одно из деревьев разбора, которые были бы построены при других подходах.
Проблему однозначности они решают тем, что выбирают наиболее длинный вариант.
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, z00n, Вы писали: Z>>LPEG VM — dll размером 30K.
MC>LPEG VM? Я правильно понимаю, что по грамматике LPEG строит парсер на байткоде, который потом интерпретируется программой на lua?
Грамматику разбирает отдельная виртуальная машина в стиле Knuth’s parsing machine (написанная на С), из нее выведены наружу несколько рукояток написанных на Lua API.
equalcount = lpeg.P{
"S"; -- initial rule name
S = "a" * lpeg.V"B" + "b" * lpeg.V"A" + "",
A = "a" * lpeg.V"S" + "b" * lpeg.V"A" * lpeg.V"A",
B = "b" * lpeg.V"S" + "a" * lpeg.V"B" * lpeg.V"B",
} * -1
В принципе народ легко пишет на этом какие угодно парсеры, но для эстетов можно написать разные фронт-энды, фронт-энд для регэкспов (написанный на луа) входит в поставку.
VD>Обещают линейное время парсинга. Причем с неограниченным декларативно-выраженным заглядыванием вперед. VD>Вроде как даже можно динамически парсер строить (очень полезно для макросов).
Линейное время — только при мемоизации, как писали выше, т.е. packrat алгоритм. Вот только здесь написано, как народ померял производительность оригинального PEG vs packrat и выяснил, что мемоизовать нужно далеко не все.
VD>Просто чудеса, да и только. А я в чудеса не верю. Какие реальные слабые места могут быть у этого чуда и чудо ли это?
Чудо — простота и мощность. Если я правильно понял, есть PEG грамматики, которые не являются LL(1) грамматиками.
Сам парсер пишется за два дня, потом неделю оптимизируется, и используется по мере надобности.
