Устав ждать когда WolfHound закончит (обещанное им еще в феврале) встраивание расширяемости и поддержки алгоритма TDOP (Pratt), я был вынужден сесть за это дело сам.
За три вечера мне удалось встроить TDOP и получить работающее решение (хотя там еще есть чего доделывать и усовершенствовать).
Для начала выводы к которым я пришел за время работы:
1. TDOP неплохо интегрируется с PEG.
2. Для TDOP не нужна мемоизация. Точнее правила относящиеся к TDOP делятся на префиксные (где вначале правила есть некоторые PEG-правила) и постфиксные (где первое подправило — это обращение к расширяемому правилу). Так вот префиксные правила — это обычные правила PEG. Для них не нужна ни сила связывания, ни какая-либо другая дополнительная информация или обработка. А вот постфиксные правила подчиняются логике TDOP. И для них не нужны PEG-овские нюансы. При разборе расширяемого правило в обязательном порядке разбирается хотя бы одно префиксное правило, и ноль или больше посфиксного. При этом постфиксные правила не разбираются отдельно и рассматриваются всегда только в контексте расширяемого правила (в следствии особенностей алгоритма TDOP). В результате смысла в мемоизации разбора посфиксных правил я не вижу. Зациклиться они не могут, так как перед ними всегда разбираются префиксные правила. Так что и тут мемоизация не нужна. Отказавшись же от мемоизации посфиксных правил можно существенно упростить алгоритм, а за одно и ускорить его. По сему на мой взгляд имеет смысл мемоизировать вычисление только для префиксных правил и самих расширяемых правил.
3. Данную реализацию будет совсем не сложно заставить поддерживать динамическую расширяемость (сейчас поддерживается только статическая, т.е. в рамках одного пасера, расширяемость).
4. Очень часто суффиксные расширяющие правила содержат фиксированный набор символов (строковый литерал) во втором подправиле (первое подаравило у них всегда является рекурсивным обращением к расширяемому правилу). Это позволяет реализовать оптимизацию вынеся первый символ этого набора в неизменяемое поле объекта реализующего динамическое расширение. Это позволит организовать очень быстрый "fail" для самого частого случая использования. Тоже самое касается и префиксных правил. Но в их случае "fail-символом" будет являться первый символ грамматики правила.
Теперь о вопросах которые встали передо мной...
Основной вопрос — это как быть с порядочком разбора расширяющих правил? Поясню ситуацию. Предположим, что у нас есть грамматика где есть два расширяющих правила:
expr : Ast;
...
mul is expr = expr : 20 "*"s expr : 20;
xxx is expr = expr : 20 "*"s expr : 20 "*"s expr : 20;
Очевидно, что если использовать логику оператора приоритетного выбора PEG для разрешения неоднозначности между этими правилами, то будет выигрывать то правило которое идет первым. Так же очевидно, что если первым будет идти правило mul, то правило xxx никогда не сработает. Таким образом нужно как-то задавать последовательность в которой расширяющие правила будут встречаться внутри расширяемого.
Мне видится два решения данной проблемы:
1. Введение синтаксиса задающего сортировку правил.
2. Использовать стратегию "кто длиннее тот и прав", предложенную WolfHound.
У каждого подхода есть свои плюсы и минусы. С одной стороны второе решение выглядит хороши на первый взгляд, так как устраняет проблему целиком. Но в то же время оно сделает парсер медленнее, так как при каждом разборе расширяемого правила придется произвести попытку разбора каждого расширяющего правила. Другими словами, скорость разбора обязательно снизится. Вопрос только лишь насколько сильно. В принципе большинство попыток разбора расширяющих правил будет обламываться на первых символах. Возможно это спасет от сильной деградации производительности, особенно, если воспользоваться оптимизацией описанной в пункте четыре списка приведенного выше.
Кроме того не ясно не будет ли стратегия "кто длиннее тот и прав" приводить к не интуитивному поведению. Похоже что нет, но это только догадки.
Собственно, если выбирать стратегию 1, то нужно продумать как задавать порядок следования расширяющих правил (внутри расширяемого). Если же выбрать стратегию 2, то нужно подумать не приведет ли это к проблемам.
Собственно хотелось бы услышать мнение других по поводу того какая из стратегий разрешения неоднозначностей вам больше нравится. Ну, и приветствуются любые идеи.
ЗЫ
У меня еще тлеет надежда на то, что WolfHound все же напряжется и доделает задуманное им сам. Возможно моя работа подтолкнет его к этому. Прошу его не воспринимать мою работу как давление или конкуренцию. Я буду только рад если он доведет работу до конца сам. Хотя то что он проигнорировал мой пул-реквест с простейшими исправлениями (исправлен баг в $-строке и добавлены проекты для VS 2010) не внушает оптимизма.
В виду того, что он еще и не откликается на прямые обращения я нахожусь просто в замешательстве. Дальше ждать уже невозможно. Эдак мы просрем все на свете.
Данное расширение надо доделать в ближайшее время. Так что прошу тебя откликнуться.
Если у тебя какие-то технические проблемы, то погляди на мою реализацию. Она проста и прекрасно работает. Не надо делать вселенский всемогутер. Нам нужно просто работающее решение. Потом будет намного проще довести его до ума.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Народ! Я эту тему создал не потешить свое самолюбие или халявных оценок срубить. Мне нужен отклик... мнения!
Давайте по активнее!
И так дано два подхода:
1. Определяем сортировку расширяемых правил некоторым способом и используем стандартный для PEG механизм приоритетного выбора.
2. Используем принцип "кто длиннее тот и папа" (т.е. побеждает правило которое разобрало большую часть входной строки).
Нужны аргументы за и против обоих подходов. А так же конкретные синтаксические решения для первого случая.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [PEG] Вопросы реализации расширяемости
От:
Аноним
Дата:
30.09.11 04:53
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, VladD2, Вы писали:
VD>Народ! Я эту тему создал не потешить свое самолюбие или халявных оценок срубить. Мне нужен отклик... мнения!
VD>Давайте по активнее!
VD>И так дано два подхода: VD>1. Определяем сортировку расширяемых правил некоторым способом и используем стандартный для PEG механизм приоритетного выбора. VD>2. Используем принцип "кто длиннее тот и папа" (т.е. побеждает правило которое разобрало большую часть входной строки).
VD>Нужны аргументы за и против обоих подходов. А так же конкретные синтаксические решения для первого случая.
в языках match бывает 2х типов:
1. В порядке записи
2. Выбирается наиболее подходящий.
VD>Собственно хотелось бы услышать мнение других по поводу того какая из стратегий разрешения неоднозначностей вам больше нравится. Ну, и приветствуются любые идеи.
С чётко заданными приоритетами мне кажется лучше. Кроме того никто не мешает реализовать стратегию "кто самый длинный тот и папа", для правил у которых заданы абсолютно одинаковые приоритеты. Такие пусть и создают редкие подтормозы.
В качестве идеи — есть опыт успешного применения для PEG-подобной грамматики с откатами и расширениями особого токена, маркера невозможности отката назад.
Пример на пальцах: добавили в linq ключевое слово distinct. Допустим стала возможной запись linq-выражений вида:
from a in x select distinct a.y;
но в то же время запись
from a in x select distinct;
Разбирается старым правилом, для которого distinct не ключевое слово. Соответственно будем иметь совершенно кривое сообщение об ошибке, ну или можно синтетически подобрать ситуацию когда оно даже скомпилируется (например переменную from вместо a назвать distinct).
Для разруливания таких косяков мы вводили токен !!!, который запрещал откат после себя. Т.е. если правило в какой-то момент проходило токен '!!!', то оно должно было или разобраться дальше, или ломало всё. В данном примере если будет добавлено правило расширение 'distinct !!!' то интуитивно-понятный облом во втором правиле будет на ; с сообщением что сломалось правило-расширение distinct. Без такого токена независимо от приоритета мы обломаемся на каком-то правиле для которого distinct — даже не ключевое слово.
Нам с таким токеном стало гораздо удобнее, и в разы меньше времени тратилось ручную работу по проверке граматик, но парсер был не совсем PEG, и то что мы им разбирали был скорее достаточно свободным файлом конфигурации чем языком программирования.
Re: [PEG] Вопросы реализации расширяемости
От:
Аноним
Дата:
30.09.11 06:11
Оценка:
Вообще пока я не видел сообщения об ошибках как делаются...
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, VladD2, Вы писали:
VD>>Здравствуйте, VladD2, Вы писали:
VD>>Народ! Я эту тему создал не потешить свое самолюбие или халявных оценок срубить. Мне нужен отклик... мнения!
VD>>Давайте по активнее!
VD>>И так дано два подхода: VD>>1. Определяем сортировку расширяемых правил некоторым способом и используем стандартный для PEG механизм приоритетного выбора. VD>>2. Используем принцип "кто длиннее тот и папа" (т.е. побеждает правило которое разобрало большую часть входной строки).
VD>>Нужны аргументы за и против обоих подходов. А так же конкретные синтаксические решения для первого случая.
А>в языках match бывает 2х типов: А>1. В порядке записи А>2. Выбирается наиболее подходящий.
А>Какой по вашему используется чаще?
match это немного не то. Парсеры как правило стараются выбирать именно наиболее подходящий вариант.
Здравствуйте, Мишень-сан, Вы писали:
МС>match это немного не то. Парсеры как правило стараются выбирать именно наиболее подходящий вариант.
В PEG используется принцип "кто первый, тот и папа", т.е. если первое првило в операторе приоритетного выбора (т.е. "e1 / e2") распознало строку, то втрое даже не будет проверяться.
Выбирать наиболее подходящий вариант невозможно, так как для этого нужно анализировать грамматики и делать некий механизм сравнения результата разбора. А это противоречит принципам PEG.
Но есть еще один вариант — выбор наиболее длинного разобравшегося правила. Алгоритм очень простой. Если у нас есть несколько правил (e1 | e2 | e3), то мы тупо производим разбор каждого из них и выбираем то из них которое разобрало больше всего символов. 99% правил при этом боломаются еще на первых символах, но возможен вариант когда два правила разберутся. Вот из них и будет выбор по принципу "у кого длиннее".
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hi_octane, Вы писали:
_>С чётко заданными приоритетами мне кажется лучше. Кроме того никто не мешает реализовать стратегию "кто самый длинный тот и папа", для правил у которых заданы абсолютно одинаковые приоритеты. Такие пусть и создают редкие подтормозы.
ОК. Тогда какой для этого использовать синтаксис?
Вот у нас есть грамматика:
grammar
{
any = ['\u0000'..'\uFFFF'];
s : void = ' '*;
start : Ast = s expr !any;
expr : Ast;
rounds is expr = '('s expr ')'s;
d = ['0'..'9'];
num is expr = d+ s;
neg is expr = '-'s expr : 100;
add is expr = expr : 10 '+'s expr : 10;
sub is expr = expr : 10 '-'s expr : 10;
mul is expr = expr : 20 '*'s expr : 20;
mod is expr = expr : 20 "//"s expr : 20;
div is expr = expr : 20 '/'s expr : 20;
pow is expr = expr : 31 '^'s expr : 30;
}
Как лучше задавать приоритеты? При этом нужно учитывать, что грамматики могут расширяться извне путем добавления расширяющего парсера для правила "expr".
_>В качестве идеи — есть опыт успешного применения для PEG-подобной грамматики с откатами и расширениями особого токена, маркера невозможности отката назад.
Это мы уже предусмотрели, но пока не реализовали. У нас это называется Cut и обозначается символом #.
Но это из другой оперы. В данном случае речь идет о расширяемых правилах.
_>Пример на пальцах: добавили в linq ключевое слово distinct. Допустим стала возможной запись linq-выражений вида: _>from a in x select distinct a.y; _>но в то же время запись _>from a in x select distinct;
_>Разбирается старым правилом, для которого distinct не ключевое слово. Соответственно будем иметь совершенно кривое сообщение об ошибке, ну или можно синтетически подобрать ситуацию когда оно даже скомпилируется (например переменную from вместо a назвать distinct).
Это какой-то странный пример. Тут нужно решить будет ли distinct ключевым словом или же это будет контекстное ключевое слово. Если это контекстное ключевое слово, то distinct вполне себе может быть именем переменной. Реализация linq в C# именно так и поступает.
_>Для разруливания таких косяков мы вводили токен !!!, который запрещал откат после себя.
Тут и без этого можно обойтись если сделать distinct ключевым словом.
Ну, да ладно. Я тебе понял. Спасибо за идею. Но сейчас речь не об этом.
_>Нам с таким токеном стало гораздо удобнее, и в разы меньше времени тратилось ручную работу по проверке граматик, но парсер был не совсем PEG
Ну, да. На самом деле подобная фигня (я ее назвал точкой отсечения) — довольно известная фича в мире Пролога. Там это называется cut point. Они ее во всю используют для оптимизаций и упрощения записи некоторых решений.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>ОК. Тогда какой для этого использовать синтаксис? VD>Как лучше задавать приоритеты? При этом нужно учитывать, что грамматики могут расширяться извне путем добавления расширяющего парсера для правила "expr".
У нас приоритет задавался самому выражению. Т.е. мы не могли манипулировать отдельными ветками например как у тебя в операторе pow где первый expr имеет приоритет 31, а второй 30. Максимум могли поставить приоритет всему pow, или всему mul. Из-за этого всё время было ощущение что с таким подходом мы вот-вот нарвёмся на бяку из-за которой придётся химичить, но видно разбираемые грамматики были простые — обошлось.
Приоритеты задаваемые просто числами в самой грамматике, да ещё с шагом между ними — выглядят как-то стрёмно. Получается что человек который пишет расширение может что-то сломать сам себе накосячив с приоритетами, да и грамматика в случае её обновления может поломать расширения кому-то — всех расширений не учесть. Самое вредное что сломать она может это тихо и незаметно, и реальная проблема вылезет только в рантайме.
Предлагаю, даже если приориты задаются числами, как минимум завести константы, которые заставлять объявлять где-нить в самой грамматике, и которые поддерживали бы простейшие операции +константа, -константа. Тогда кусочек той же грамматики мог бы выглядеть так:
grammar
{
priority
{
BASE : 10;
ADD : BASE + 10;
NEG : BASE + 100;
POW_LEFT : BASE + 21;
POW_RIGHT : BASE + 20;
}
add is expr = expr : ADD '+'s expr : ADD;
neg is expr = '-'s expr : NEG;
pow is expr = expr : POW_LEFT '^'s expr : POW_RIGHT;
}
Если теперь позволить расширениям ссылаться на имена приоритетов основной грамматики, то хотя-бы удастся избежать ошибок при её рефакторинге.
В процессе написания всего этого возникла ещё идея представить значение приоритета аналогично номеру версии программ, т.е. неограниченно расширяемый вправо. Тогда возможен вариант:
grammar
{
priority
{
BASE : 10; //просто базовый приоритет, 10
ADD : BASE.10; //получается значение 10.10
NEG : BASE.100; //получается значение 10.100
POW_LEFT : BASE.31; //получается значение 10.31
POW_RIGHT : BASE.30 //получается значение 10.30
}
}
//Ну и соответственно если какому-то расширению приспичило всунуться между POW_LEFT и POW_RIGHT, оно может объявить себе приоритет
POW_EXT : POW_RIGHT.10; //получив значение приоритета 10.30.10, которое будет больше чем 10.30, но меньше чем 10.31, а главное расширяемо без страха накосячить
Вот вроде и все мысли. Повторюсь, у нас был только некоторый опыт работы с приоритетами задаваемыми для целых правил, два следующих предложения вношу в порядке мозгового штурма, и рассматривать их следует предельно критически.
Здравствуйте, hi_octane, Вы писали:
_>У нас приоритет задавался самому выражению.
Я не о тех приоритетах. Силу связывания мы и так задаем. Я под приоритетом понимаю способ задать порядок разбора расширяющих правил.
Еще раз... У нас есть правила:
expr : Ast;
rounds is expr = '('s expr ')'s;
d = ['0'..'9'];
num is expr = d+ s;
neg is expr = '-'s expr : 100;
add is expr = expr : 10 '+'s expr : 10;
sub is expr = expr : 10 '-'s expr : 10;
mul is expr = expr : 20 '*'s expr : 20;
mod is expr = expr : 20 "//"s expr : 20;
div is expr = expr : 20 '/'s expr : 20;
pow is expr = expr : 31 '^'s expr : 30;
В такой нотации порядок разбора правил не определен. Парсер, например, может сначала разбирать mul, а затем div, а может наоборот. Если грамматики этих правил будут конфликтовать, то вероятна возможность, что одно из правил никогда не будет работать.
Нам нужно придумать синтаксис который позволил бы определить порядок разбора.
Если бы мы использовали синтаксис:
expr : Ast = add / sub / mul / mod / div;
то порядок был бы определен самим расположением подравила.
Но у для расширяемости нужно описывать правила отдельно, а их приоритет (в смысле порядок разбора) задавать отдельно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Основной вопрос — это как быть с порядочком разбора расширяющих правил? Поясню ситуацию. Предположим, что у нас есть грамматика где есть два расширяющих правила:
Как разработчику, мне бы хватило возможности указать, что мое правило должно идти раньше какого-то конкретного правила (или нескольких). Правила в одном макроклассе без особых указаний — в порядке объявления.
Проблемы могут начаться, когда подключат два правила, разбирающих похожие грамматики и не знающих друг о друге. Но тут уж от них уйти не получится.
Здравствуйте, Ziaw, Вы писали:
Z>Как разработчику, мне бы хватило возможности указать, что мое правило должно идти раньше какого-то конкретного правила (или нескольких). Правила в одном макроклассе без особых указаний — в порядке объявления.
Синтаксис можешь предложить?
Z>Проблемы могут начаться, когда подключат два правила, разбирающих похожие грамматики и не знающих друг о друге. Но тут уж от них уйти не получится.
А что на счет идеи Вольфхаунда с победой правила которое разберет больше всего символов?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
Z>>Как разработчику, мне бы хватило возможности указать, что мое правило должно идти раньше какого-то конкретного правила (или нескольких). Правила в одном макроклассе без особых указаний — в порядке объявления.
VD>Синтаксис можешь предложить?
По аналогии с syntax, что-то типа: parse before MacroClass.MacroName;
Z>>Проблемы могут начаться, когда подключат два правила, разбирающих похожие грамматики и не знающих друг о друге. Но тут уж от них уйти не получится.
VD>А что на счет идеи Вольфхаунда с победой правила которое разберет больше всего символов?
Пока не показана необходимость такого подхода — отрицательно. Точно не стоит включать по умолчанию. Как вариант, указываем parse max на любом макросе и весь список обрабатывается в таком режиме.
Здравствуйте, Ziaw, Вы писали: VD>>А что на счет идеи Вольфхаунда с победой правила которое разберет больше всего символов?
Z>Пока не показана необходимость такого подхода — отрицательно. Точно не стоит включать по умолчанию. Как вариант, указываем parse max на любом макросе и весь список обрабатывается в таком режиме.
м.б. задавать приоритет правил числом, как приоритет операторов? [priority 100] xxx is expr = expr : 20 "*"s expr : 20 "*"s expr : 20;
Принять приоритет по умолчанию, если он не задан в правиле явно.
VD>Нам нужно придумать синтаксис который позволил бы определить порядок разбора.
VD>Если бы мы использовали синтаксис: VD>
VD>expr : Ast = add / sub / mul / mod / div;
VD>
VD>то порядок был бы определен самим расположением подравила.
VD>Но у для расширяемости нужно описывать правила отдельно, а их приоритет (в смысле порядок разбора) задавать отдельно.
Если объявлять точки расширения каким-то образом, позволяющим указать имя самой точки расширения и группу токенов которые она расширяет:
grammar gr1
{
expr : Ast = extension_point_name<< add / sub / mul / mod / div >>;
}
То добавлять например новый оператор pow, без ссылок на абсолютные числовые значения приоритетов, можно было бы так:
grammar gr2
{
pow is expr = ...
extend gr1
{
extension_point_name.mod =<< / pow; //добавить вариант '/ pow' после mod
extension_point_name.mod = pow;//заменить вариант mod на pow, т.е. mod больше нету
extension_point_name.mod =>> / pow; //добавить вариант '/ pow' перед mod
}
}
Ну и следующее расширение может привязываться уже к pow если ему надо.
Нужны ещё какие-то модификаторы (допустим .<< и .>>), позволяющие сослаться на начало и конец точки расширения чтобы можно было расширять не особо заморачиваясь приоритетами. Плюс если абсолютно каждое правило будет само себе точка расширения по имени самого правила, то гибкость такого парсера будет, похоже, исчерпывающей.
Здравствуйте, Ka3a4oK, Вы писали:
KK>В boost::spirit есть директивы которые позволяют задать порядок разбора: longest_d, shortest_d. Синтаксис примерно такой:
KK>rule=longest_d[rule1|rule2|rule3] KK>shortest=shortest_d[rule1|rule2|rule3]
У нас речь идет о расширяемых правилах. Так что такой синтаксис не пригоден.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
то как тогда добавить add , sub , mul , mod , div, pow
в НЕЗАВИСИМЫХ макросах?
ну вот не нужен мне mod, мне надо задействовать только макросы sub и pow, например...
и тогда pow не знает(не открыто пространство имён, нету сборки и т.п) что такое extension_point_name.mod...
P>то как тогда добавить add , sub , mul , mod , div, pow P>в НЕЗАВИСИМЫХ макросах?
P>ну вот не нужен мне mod, мне надо задействовать только макросы sub и pow, например... P>и тогда pow не знает(не открыто пространство имён, нету сборки и т.п) что такое extension_point_name.mod...
Увы, похоже нету способа договориться о приоритетах двум расширениям, каждое из которых понятия не имеет о другом. Для разруливания таких случаев нужно предусматривать какой-то механизм, позволяющий управлять приоритетами этих расширений тому, кто решил их заиспользовать вместе, и нарвался на конфликт. Тут можно и API какое-нить прикрутить, или какой-то макрос уровня сборки, который бы позволял установить приоритеты через какое-то API, или даже через порядок подключения грамматик, если угодно.
Но для простейшего случая совершенно независимых расширений, которых наверняка будет около 90%, я вроде как написал про модификаторы начала и конца точки расширения (допустим extension_point_name.<< и extension_point_name.>>, ну или можно как в регекспах extension_point_name.^ и extension_point_name.$). Приклеиваешь то что хочешь используя такой модификатор, и паришься именованными приоритетами только в том случае если конфликт реально возникает.
Кроме того, в случае сурового конфликта имён, неразрешимого при помощи модификаторов начала и конца, разработчику главной грамматики можно ввести несколько именованных пустых правил. Тогда у точек расширения будет чуть больший простор по приклеиванию в нужное место.
В любом случае указание простых числовых приоритетов — это путь к неустранимым граблям как для того кто разрабатывает исходную грамматику, так и для тех кто разрабатывает расширения.
