Устав ждать когда 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) не внушает оптимизма.

В виду того, что он еще и не откликается на прямые обращения я нахожусь просто в замешательстве. Дальше ждать уже невозможно. Эдак мы просрем все на свете.

Данное расширение надо доделать в ближайшее время. Так что прошу тебя откликнуться.
Если у тебя какие-то технические проблемы, то погляди на мою реализацию. Она проста и прекрасно работает. Не надо делать вселенский всемогутер. Нам нужно просто работающее решение. Потом будет намного проще довести его до ума.

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, и то что мы им разбирали был скорее достаточно свободным файлом конфигурации чем языком программирования.

Здравствуйте, hi_octane, Вы писали:
а если
_>

_>grammar gr1
_>{
_>  expr : Ast = extension_point_name<< num >>;
_>}
_>

то как тогда добавить add , sub , mul , mod , div, pow
в НЕЗАВИСИМЫХ макросах?
ну вот не нужен мне mod, мне надо задействовать только макросы sub и pow, например...
и тогда pow не знает(не открыто пространство имён, нету сборки и т.п) что такое extension_point_name.mod...

Здравствуйте, catbert, Вы писали:

C>Здравствуйте, Аноним, Вы писали:

А>>И шаманил он долго.
А>>Именял Юнинги. И надо у него было от первого часть и от второго.
А>>И пошел он на ....

C>Даже в таком ужасном случае можно разделить класс на два partial-а и открыть в разных файлах разные юзинги.

Именно это я и называю шаманством.

Здравствуйте, YF, Вы писали:

Приоритет числом указывать совершенно неудобно.

Я вижу очень редкую необходимость задания приоритета, разве что для оптимизации. Единственный случай который приходит мне на ум, это добавление постфиксов с чем-то типа опций к готовым конструкциям языка.

foreach (...)
{
   ...
}
otherwise {}

Для этого надо свое правило поставить ранее правила "foreach", это и нужно указать в макросе. Чтобы тот кто его читает мог понять, что имелл ввиду автор. А не читал [Priority(NNN)] и гадал, с какой же целью там стоит именно это число.

Других юзкейсов задания приоритета я пока придумать не могу (производительность не в счет, там смешные проседания в очень специфичных случаях). Если кто знает — пишите, синтаксис должны определять именно юзкейсы использования.

В принципе и этот юзкейс, в теории можно обойти чем-то типа Expr "otherwise" Expr и последующим анализом выражений в макросе. Это будет костыльно конечно, но зато сами макросы без приоритетов станут проще.

Здравствуйте, VladD2, Вы писали:

Народ! Я эту тему создал не потешить свое самолюбие или халявных оценок срубить. Мне нужен отклик... мнения!

Давайте по активнее!

И так дано два подхода:
1. Определяем сортировку расширяемых правил некоторым способом и используем стандартный для PEG механизм приоритетного выбора.
2. Используем принцип "кто длиннее тот и папа" (т.е. побеждает правило которое разобрало большую часть входной строки).

Нужны аргументы за и против обоих подходов. А так же конкретные синтаксические решения для первого случая.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, VladD2, Вы писали:

VD>Народ! Я эту тему создал не потешить свое самолюбие или халявных оценок срубить. Мне нужен отклик... мнения!

VD>Давайте по активнее!

VD>И так дано два подхода:
VD>1. Определяем сортировку расширяемых правил некоторым способом и используем стандартный для PEG механизм приоритетного выбора.
VD>2. Используем принцип "кто длиннее тот и папа" (т.е. побеждает правило которое разобрало большую часть входной строки).

VD>Нужны аргументы за и против обоих подходов. А так же конкретные синтаксические решения для первого случая.

в языках match бывает 2х типов:
1. В порядке записи
2. Выбирается наиболее подходящий.

Какой по вашему используется чаще?

Вообще пока я не видел сообщения об ошибках как делаются...

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, 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;
Принять приоритет по умолчанию, если он не задан в правиле явно.

В boost::spirit есть директивы которые позволяют задать порядок разбора: longest_d, shortest_d. Синтаксис примерно такой:

rule=longest_d[rule1|rule2|rule3]
shortest=shortest_d[rule1|rule2|rule3]

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]

У нас речь идет о расширяемых правилах. Так что такой синтаксис не пригоден.

P>а если
_>>

_>>grammar gr1
_>>{
_>>  expr : Ast = extension_point_name<< num >>;
_>>}
_>>

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.$). Приклеиваешь то что хочешь используя такой модификатор, и паришься именованными приоритетами только в том случае если конфликт реально возникает.

Кроме того, в случае сурового конфликта имён, неразрешимого при помощи модификаторов начала и конца, разработчику главной грамматики можно ввести несколько именованных пустых правил. Тогда у точек расширения будет чуть больший простор по приклеиванию в нужное место.

В любом случае указание простых числовых приоритетов — это путь к неустранимым граблям как для того кто разрабатывает исходную грамматику, так и для тех кто разрабатывает расширения.

Здравствуйте, hi_octane, Вы писали:

_>Если объявлять точки расширения каким-то образом, позволяющим указать имя самой точки расширения и группу токенов которые она расширяет:

_>

_>grammar gr1
_>{
_>  expr : Ast = extension_point_name<< add / sub / mul / mod / div >>;
_>}
_>

Что такое группы токенов я вообще не понял. Зачем нужна extension_point_name<<, тоже не ясно.

_>То добавлять например новый оператор 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 если ему надо.

Что-то как-то все это очень сложно и не интуитивно.

Тогда уж проще описывать порядок разбора правил в атрибутах:

Expr : Ast;
...
Div is Expr = ...;

[ParseBefore(Div)]
Mod is Expr = ...;

Но это не сработает в случае когда имеются два независимых расширения объявленных в разных модулях. В прочем, тут пойдет только отдельное указание порядка непосредственно в том месте где эти два расширения применяются (т.е. при парсинге файла в котором открыты оба расширеня). Например, так:

[ParseBefore(Div)]
Order for Expr: Mod, Div, X;

При этом указывается, что Mod должен разбираться раньше Div и X, а Div раньше X. Порядок разбора остальных правил остается прежним (за исключением тех на которые подействовало изменение порядка описанных правил).

1. Уровень операций + и — одинаковый!!!
a+b-c=>(a+B)-c
a-b+c=>(a-B)+c

Так что нельзя брать только before

возможно вариант с порядком вида был бы лучше 10.-10.5.-3

VD>Что такое группы токенов я вообще не понял. Зачем нужна extension_point_name<<, тоже не ясно.
extension_point_name<< ... >> — это могло бы быть просто имя точки расширения. Вдруг надо одно правило включить в 3 разных места с разными приоритетами. Ситуация гипотетическая, но мало ли Вот я и заморочился тем что у точек расширения должны быть имена, и приоритеты должны указываться в каждой точке расширения независимо и т.п. В общем забей, сейчас мне кажется это овер-инжинеринг с моей стороны. Такую ситуацию проще разрулить сделав 3 клона одного правила с разными именами и навешать аттрибуты уже на этих клонов.

VD>

VD>[ParseBefore(Div)]
VD>Order for Expr: Mod, Div, X;
VD>

VD>При этом указывается, что Mod должен разбираться раньше Div и X, а Div раньше X. Порядок разбора остальных правил остается прежним (за исключением тех на которые подействовало изменение порядка описанных правил).

С аттрибутами мне нравится. Разве что стоило бы добавить ещё какой-нить модификатор позволяющий указать приоритет опционально. Например [ParseBefore(Div?)]. Т.е. если расширение Div подключено, то включаться перед ним, если нет — то куда там попало по умолчанию. Это поможет хотя-бы в рамках стандартного набора библиотек идущих с компилятором, которые в принципе друг о друге представление имеют но при этом относительно независимы, разруливать возможные конфликты не заставляя пользователей в каждом проекте указывать "Order for".

Здравствуйте, Аноним, Вы писали:

А>1. Уровень операций + и — одинаковый!!!

Ау! Я же раз пять повторил, что речь идет не о приоритете операторов, а о порядке разбора правил.

Здравствуйте, VladD2, Вы писали:

VD>Мне видится два решения данной проблемы:
VD>1. Введение синтаксиса задающего сортировку правил.
VD>2. Использовать стратегию "кто длиннее тот и прав", предложенную WolfHound.

3. Кто позже всех подключен using-ом, тот и прав.

Здравствуйте, hi_octane, Вы писали:

VD>>Что такое группы токенов я вообще не понял. Зачем нужна extension_point_name<<, тоже не ясно.
_>extension_point_name<< ... >> — это могло бы быть просто имя точки расширения.

К нас именем является имя правила без тела.

_>Вдруг надо одно правило включить в 3 разных места с разными приоритетами.

Зачем? Для галочки? По жизни это как раз не надо.

_>Ситуация гипотетическая, но мало ли

Вот именно — гипотетическая.

_>С аттрибутами мне нравится. Разве что стоило бы добавить ещё какой-нить модификатор позволяющий указать приоритет опционально. Например [ParseBefore(Div?)]. Т.е. если расширение Div подключено, то включаться перед ним, если нет — то куда там попало по умолчанию. Это поможет хотя-бы в рамках стандартного набора библиотек идущих с компилятором, которые в принципе друг о друге представление имеют но при этом относительно независимы, разруливать возможные конфликты не заставляя пользователей в каждом проекте указывать "Order for".

Думаю что на уровне макросов оно и так будет работать по факту наличия.

Сейчас же меня больше занимает вопрос выбора синтаксиса и самой стратегии. Ведь выбор самого длинного правила позволил бы вообще обойтись без ручного управления последовательностью работа правил. Но это дает только один способ решения конфликтов и приводит к самому медленному варианту (который в PEG бывает только в самом худшем случае).

Здравствуйте, catbert, Вы писали:

C>3. Кто позже всех подключен using-ом, тот и прав.

Наверное стоит объяснить свое мнение

1. Группа расширяющих макросов, написанная вместе, может зависеть от того, что между ними нету местечка, куда можно вставить чужие расширения. Поэтому контроль приоритетов расширяющих макросов по пространствам имен достаточен, и даже желателен.

2. В общем случае, единственная сторона, которая знает (или должна знать) обо всех используемых расширениях — пользователь кода. Поэтому лучше всего предоставить контроль именно пользователю.

3. Контроль using-ами — самый минималистичный и натуральный способ контролировать приоритеты расширений, который я мог придумать. Минималистичный в том смысле, что требует 0% дополнительного кода, а натуральный — потому что я держу пари, что если программист (без возможности найти решения в интернете) поймет, что его проблема — конфликт приоритетов в макросах, он начнет играться с using-ами.

4. Поскольку первыми всегла подключены стандартные макросы, то для их оверрайда нужен порядок именно "кто позже, тот и прав" а не "кто ранльше тот и прав". И это опять-таки натурально.

Здравствуйте, catbert, Вы писали:

C>Здравствуйте, catbert, Вы писали:

C>>3. Кто позже всех подключен using-ом, тот и прав.

C>Наверное стоит объяснить свое мнение

C>1. Группа расширяющих макросов, написанная вместе, может зависеть от того, что между ними нету местечка, куда можно вставить чужие расширения. Поэтому контроль приоритетов расширяющих макросов по пространствам имен достаточен, и даже желателен.

C>2. В общем случае, единственная сторона, которая знает (или должна знать) обо всех используемых расширениях — пользователь кода. Поэтому лучше всего предоставить контроль именно пользователю.

C>3. Контроль using-ами — самый минималистичный и натуральный способ контролировать приоритеты расширений, который я мог придумать. Минималистичный в том смысле, что требует 0% дополнительного кода, а натуральный — потому что я держу пари, что если программист (без возможности найти решения в интернете) поймет, что его проблема — конфликт приоритетов в макросах, он начнет играться с using-ами.

C>4. Поскольку первыми всегла подключены стандартные макросы, то для их оверрайда нужен порядок именно "кто позже, тот и прав" а не "кто ранльше тот и прав". И это опять-таки натурально.

И шаманил он долго.
Именял Юнинги. И надо у него было от первого часть и от второго.
И пошел он на ....

Здравствуйте, Аноним, Вы писали:

А>И шаманил он долго.
А>Именял Юнинги. И надо у него было от первого часть и от второго.
А>И пошел он на ....

Даже в таком ужасном случае можно разделить класс на два partial-а и открыть в разных файлах разные юзинги.

Здравствуйте, Аноним, Вы писали:

А>Именно это я и называю шаманством.

Но это может сработать. Остальные предложения оставляют юзера вообще ни с чем.

Здравствуйте, catbert, Вы писали:

C>Здравствуйте, Аноним, Вы писали:

А>>Именно это я и называю шаманством.

C>Но это может сработать. Остальные предложения оставляют юзера вообще ни с чем.

Самое паршивое решение.
Зависимость по порядка инклудов.

Здравствуйте, catbert, Вы писали:

C>3. Кто позже всех подключен using-ом, тот и прав.

Исходное поведение using не зависит от их порядка. Было бы странно нарушать традицию.

Кроме того — это не решит проблемы, так как может получитья так, что при перестановке станут не верными "приоритеты" других правил.

Здравствуйте, VladD2, Вы писали:

VD>Основной вопрос — это как быть с порядочком разбора расширяющих правил?
VD> ...
VD>Мне видится два решения данной проблемы:
VD>1. Введение синтаксиса задающего сортировку правил.
VD>2. Использовать стратегию "кто длиннее тот и прав", предложенную WolfHound.

В проблеме не разбираюсь, но ...

Ух-ты-ж, оказывается проблема приоритетов в пег, которая мне сразу не понравилась, не такая уж и маленькая.

Первый вариант с указанием приоритетов для правил это мина замедленного действия, тк приоритеты будут указываться в разных модулях плохо согласованных в виду того что разрабатывались разными людьми-командами. Будет "перетягивание одеяла" и нехватка пространства значений приоритетов в достаточно сложных грамматиках.

Второй вариант "кажется" убьет все преимущество пег над остальными грамматиками.

Вывод: приоритет задается порядком в исходном коде. Конфликтные ситуации диагностируются во время компиляции макросов и разрешаются программистом, если это реализуемо путем сравнения префиксов и суффиксов(?).

Здравствуйте, fin_81, Вы писали:

_>Первый вариант с указанием приоритетов для правил это мина замедленного действия, тк приоритеты будут указываться в разных модулях плохо согласованных в виду того что разрабатывались разными людьми-командами.

В общем — да. Но решений без проблем просто не существует. Требования "хорошая динамическая расширяемость" и "контроль корректности" противоречат друг другу.

_>Будет "перетягивание одеяла" и нехватка пространства значений приоритетов в достаточно сложных грамматиках.

Все не так страшно как пытается нарисовать твой мозг . Дело в том, что в большинстве реальных применений просто не будет конфликтов. Мы не даром делаем расширяемость на на основе PEG, а на основе TDOP. Это очень простой алгоритм с очень четко выраженными фазами (префиксная и суффиксальная).

Скажем операторы + и ++ не вызовут никаких конфликтов, так как их грамматики будут четко отличаться.

Так что конфликты будут редко, а стало быть и приоритеты придется задавать редко.

_>Второй вариант "кажется" убьет все преимущество пег над остальными грамматиками.

Для меня этот вопрос открытый. Я, пока, не могу пока что сказать какие эффекты могут последовать от выбора второго варианта (где длиннее тот и прав).

Единственно что точно можно сказать, что этот вариант не дает возможность вручную раруливать конфликты. С другой стороны он сам будет разруливать большую часть конфликтов вполне приемлемы образом.

_>Вывод: приоритет задается порядком в исходном коде. Конфликтные ситуации диагностируются во время компиляции макросов

К сожалению, мы можем диагностировать, во время компиляции макросов, только часть проблем. Во-первых, этому препятствует то, что макро-сборки могут собираться независимо и не знать ничего друг о друге. Во-вторых, мы не строим конечных автоматов для всех правил, и стало быть не можем предугадать наличие конфликта. Крамматики которые могут разобрать одну и ту же строку могут выглядеть совершенно по разному. Кроме того внутри, такие грамматики, так же могут содержать динамически подключенные расширения, что делает статический анализ очень ограниченным.

Таким образом мы можем контролировать конфликты в основном в рантайме. Озвученные мной стратегии и является выбором способа такого контроля.

Скажу даже больше. По сути PEG не предоставляет средств контроля проблем. Если в грамматике ошибка, и какое-то правило идет перед другим при этом не давая второму правилу вызваться, то программист создавший эту грамматику просто не узнает о наличии конфликта. Второе правило просто будет "мертвым кодом".

Вариант с самым длинным позволит выявить наличие проблемы (более одного правила разобрали входную строку и при этом сдвинулись хотя бы на один символ).

_> и разрешаются программистом, если это реализуемо путем сравнения префиксов и суффиксов(?).

Да сравнивать то их особого смысла нет. Это может дать что-то для простых случаев. Но в сложных случаях это все равно работать не будет.

Хотя, возможно, что контроль для простых случаев даст хороший результат. Над этом стоит подумать.

Здравствуйте, VladD2, Вы писали:

VD>Вариант с самым длинным позволит выявить наличие проблемы (более одного правила разобрали входную строку и при этом сдвинулись хотя бы на один символ).

Эту стратегию можно применить при проверке грамматики на "корректность". В зависимости от настроек диагностируется как предупреждение, или как ошибка, или вообще не проверяется на "корректность".

Как будут разрешаться конфликты? Не знаю. Дело в том что приоритеты не разрешают эти конфликты, они просто отрубают менее приоритетные правила, тем самым отрубают "менее правильные по приоритету" грамматические конструкции. По мне это не очень правильно, так как малое изменение приоритетов может привести к большим проблемам. Нестабильная несходящаяся система для разработки

Здравствуйте, fin_81, Вы писали:

_>Эту стратегию можно применить при проверке грамматики на "корректность". В зависимости от настроек диагностируется как предупреждение, или как ошибка, или вообще не проверяется на "корректность".

Вообще-то, формально PEG-грамматика всегда корректна. А проверить логические ошибки так вряд ли удастся.

_>Как будут разрешаться конфликты? Не знаю. Дело в том что приоритеты не разрешают эти конфликты, они просто отрубают менее приоритетные правила, тем самым отрубают "менее правильные по приоритету" грамматические конструкции. По мне это не очень правильно, так как малое изменение приоритетов может привести к большим проблемам. Нестабильная несходящаяся система для разработки

Это надуманное умозаключение. Практика уже доказала, что порядковый выбор (ordered choice) работает.

Здравствуйте, VladD2, Вы писали:

_>>Как будут разрешаться конфликты? Не знаю. Дело в том что приоритеты не разрешают эти конфликты, они просто отрубают менее приоритетные правила, тем самым отрубают "менее правильные по приоритету" грамматические конструкции. По мне это не очень правильно, так как малое изменение приоритетов может привести к большим проблемам. Нестабильная несходящаяся система для разработки

VD>Это надуманное умозаключение. Практика уже доказала, что порядковый выбор (ordered choice) работает.

Пишу про пег, а как извратили пег в немерле без понятия.

Была грамматика

S -> aBd
B -> bc

которая разбирала 'abcd'.
Потом макросописатель добавил правило

S -> aBd
B -> b // новое более приоритетное правило
B -> bc

После этого ранее разбираемая строка 'abcd' ошибочна в пег-грамматике, так как менее приоритетное но ранее работавшее правило вообще не будет участвовать в разборе, этого правила нет в новой грамматике.
Теперь вопрос: это так и задумано макросописателем или это ошибка? 50 на 50, кому-то это нужно, кому-то нет.

Здравствуйте, fin_81, Вы писали:

_>S -> aBd
_>B -> b // новое более приоритетное правило
_>B -> bc

_>После этого ранее разбираемая строка 'abcd' ошибочна в пег-грамматике, так как менее приоритетное но ранее работавшее правило вообще не будет участвовать в разборе, этого правила нет в новой грамматике.
_>Теперь вопрос: это так и задумано макросописателем или это ошибка? 50 на 50, кому-то это нужно, кому-то нет.

У нас вроде как будет:

S -> aBd
B -> b | bc // новое более приоритетное правило

Здравствуйте, catbert, Вы писали:

C>У нас вроде как будет:

C>S -> aBd
C>B -> b | bc // новое более приоритетное правило

Поправка
B -> b / bc
Оператор приоритетного выбора '/'. Второй вариант 'bc' никогда не сработает. Можно писать в несколько строк, можно через оператор приоритетного выбора, суть от этого не меняется.

Здравствуйте, fin_81, Вы писали:

_>После этого ранее разбираемая строка 'abcd' ошибочна в пег-грамматике, так как менее приоритетное но ранее работавшее правило вообще не будет участвовать в разборе, этого правила нет в новой грамматике.

Ну, и что? Человек изменил грамматику.

_>Теперь вопрос: это так и задумано макросописателем или это ошибка? 50 на 50, кому-то это нужно, кому-то нет.

А, ну да. Отличная логика. Исползуя ее можно до чего угодно договориться. Например:
Выл у человека код:

def a() { 40 }
def b(x) { x + 2 }
...
def y = b(a());

Потом человек его поменял:

def a() { 40 }
def b(x) { x + 2 }
def b(x) { x - 2 }
...
def y = b(a());

и результат поменялся. Ошибка это или так было задумано?

Да без разницы. Если это ошибка, то ее допустил программист. Для парсера это вполне корректный случай.

Человек перекрывший правило мог просто хотеть отменить не нравящуюся ему конструкцию.

Здравствуйте, Аноним, Вы писали:

А>Самое паршивое решение.
А>Зависимость по порядка инклудов.

Может в самом инклюде приоритет задаывать (т.е. расширить синтаксис инклюда)?

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, fin_81, Вы писали:

_>>После этого ранее разбираемая строка 'abcd' ошибочна в пег-грамматике, так как менее приоритетное но ранее работавшее правило вообще не будет участвовать в разборе, этого правила нет в новой грамматике.

VD>Ну, и что? Человек изменил грамматику.

Ссылаясь на название темы, человек _расширил_ грамматику, он не хотел отключать ранее работавшие конструкции и потом обратно перетаскивать ранее работавшую грамматику в свой модуль макросов с правильной расстановкой приоритетов, чтобы парсились уже работавшие конструкции.
Я выразил свое мнение, дальше спорить не буду. Мне это сильно не понравилось при переходе от антлр к пег-грамматикам с их исключающими приоритетами, меня это сильно раздражало.

Здравствуйте, Аноним, Вы писали:

А>>Самое паршивое решение.
А>>Зависимость по порядка инклудов.

А>Может в самом инклюде приоритет задаывать (т.е. расширить синтаксис инклюда)?

Можно пример синтаксиса?