Раз зашел разговор про грамматике, то такой вопрос: как формализовать/классифицировать

следующую грамматику.
Есть CFG, добавим к ней ограничения вида

1. какое-то правило может быть использовано только один раз
2. использование какого-то правила требует, что-бы в процессе разбора было использовано какое-то другое правило.
3. Можно придумать много подобных ограничений на использование правил
4. Новы правила не создаются, старые не удаляются.

По идее, это может быть облегченная версия Adaptive grammar.
Встречается еще термин Constraint grammar, но это что-то из области компьютерной лингвистики и не похоже на то, что я описываю.

Как можно формализовать подобную грамматику/проблемную область?
Что можно почитать поглубже на эту тему?
Интересны, в первую очередь, эффективные методы парсинга такой грамматики.

А зачем их классифицировать? И почему надо сверяться с классификатором Хомского?..

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

> По идее, это может быть облегченная версия Adaptive grammar. Не очень похоже, IMHO. Как раз из-за четвёртого пункта, который является ключевым для adaptive grammar. Больше похоже (по мере убывания сходства) на Ordered Grammars, или Coupled Grammars, или Tree Adjoining Grammars (эти уж совсем далеко). > но это что-то из области компьютерной лингвистики Вы так говорите, как будто это что-то плохое (TAG из списка выше скорее из неё, например). ;) > Что можно почитать поглубже на эту тему? Можно начать со всё того же источника...

> Возможно даже, что выхода из КС класса не будет Скорее всего, будет (почти всегда так бывает, но запросто может получиться и какой-то урод выход "вбок", вроде PEG).

Что значит может быть использовано только один раз?

Я про Хомского ничего не говорил. Задача, возможно, может быть решена каким-нибудь constraint solver, или ложится на Adaptive automata или на что-то еще … Ну а Хомский с его “творчеством” - это отдельная тема для большого разговора.

Да, я как раз про большой разговор

В процессе разбора правило может быть использовано только один раз. Дважды оно использовано быть не может. Можно сказать, что оно удаляется, но реально его удалять не надо, достаточно ограничить использование. Таких ограничений можно много разных придумать …

Можно не абстрактный, а более конкретный пример. Чтобы понятно было в чем идея и зачем с вашей точки зрения оно надо

>> По идее, это может быть облегченная версия Adaptive grammar. > Не очень похоже, IMHO. Как раз из-за четвёртого пункта, который является ключевым для adaptive grammar. IMHO, добавлени/удаление правил можно переформулировать как enable/disable constrain. Ну а если добавляется правило, которое до этого было не известно, то это - grammar induction. IMHO, это уже совсем другая проблемная область.

>> но это что-то из области компьютерной лингвистики > Вы так говорите, как будто это что-то плохое (TAG из списка выше скорее из неё, например). ;) Я не против компьютерной лингвистики и очень много чего перечитал из нее, но то, что в ней делается, быстрее похоже на алхимию (варение золота из ртути). Грубо говоря, люди, пользуясь минимальными знаниями пытаются выдумывать разные теории. У них там сектанство а не наука.

> но то, что в ней делается, быстрее похоже на алхимию (варение золота из ртути). Ну... возможно, просто в прикладной компьютерной лингвистике сейчас ажиотаж, поэтому (как это зачастую бывает) туда пришло много малограмотных "специалистов" — поэтому голоса тех, кто на самом деле в чём-то разбирается, сейчас просто "тонут" в этом шуме. :( > У них там сектанство а не наука. Но этот самый шум — это оно, да (я помню, как читал тут какой-то чат таких "практиков" , но вскоре отписался — я не могу так много хохотать, честное слово). ;)

Звучит как субструктурные логики

Почему PEG - урод? Разве этот формализм не новое название DCG? Ну добавили приятного syntax sugar и убрали атрибуты, а так все тот же DCG, четверть века спустя ...

По той же причине, почему ! считается уродством в прологе.

Это язык (DSL), который, похоже, описывает определенную проблемную область. Саму предметную область я не хочу обсуждать. Какая-то конструкция может быть использована только один раз, попытка ее использовать еще раз не валидна и должна парситься иначе.

В данном случае я, наверное, не прав. Нужны правила по применению правил. Иногда надо запрещать использовать какие-то правила, иногда надо требовать, что-бы какие-то правила были использованы в процессе разбора. Подобные условия могут быть достаточно сложными.

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

Потому, что: 0. Несмотря на внешнее сходство с EBNF, принцип работы совсем другой, что на практике приводит к написанию PEG методом проб и ошибок (т.е. распознаваемый язык "тихо" (см. пункт 1) получается совсем не тем, что ожидал автор). Проблема в т.ч. в том, что в процессе написания CFG добавление продукций не может привести к тому, чтобы какие-то ранее распознаваемые sentences более не распознавались, а вот в PEG — запросто. И несмотря на наличие computational model для PEG (scaffolding automaton) лично мне поведение PEG от этого понятнее не становится. ;) 1. Решает проблему с головной болью неоднозначностью с помощью отрубания головы приоритетного выбора (который, опять-таки, на практике зачастую приводит совсем не к тому, чего ожидал автор PEG). 2. Что касается мощности — несмотря на способность распознавать некоторые CDG (кстати, записать некоторые из них куда труднее, чем кажется на первый взгляд, см. пункт 1), [почти наверняка] не может распознавать некоторые языки, распознаваемые CFG; также невозможно написать PEG, создающие parse trees нужного вида для некоторых языков type 2. 3. Не может в left recursion. 4. Из-за синтаксических предикатов в нём "всего лишь" есть парадоксы (что означает "S ← !S", например?), из-за них и третьего пункта вводится понятие well-formed... но установить соответствие ему произвольной PEG алгоритмически невозможно (если я правильно помню). Когда я писал про "выход вбок", я имел в виду второй пункт. > Разве этот формализм не новое название DCG? Хмм... это новое название TDPL (Birman, A., and Ullman, J. D. Parsing algorithms with backtrack. Information and Control 23, 1973), нет?

Ну и, опять-таки, это очень похоже на Ordered Grammars, разве нет? Смотрите: Ordered grammars produce non-CF languages by restricting the CF production process... It is not clear whether this is a good idea in practice, but the ideas involved are certainly interesting ... When using a CF grammar to produce a sentence, one is free to apply any production rule at any time, provided the required non-terminal is present in the sentential form. 1. One type of ordered grammars restrict this freedom by requiring that the sequence of applied rules must obey a second grammar, the control grammar. Here, the rules in the original CF grammar are considered tokens in the control grammar, and a sequence of rules produced by the control grammar is called a control sequence. 2. In a marked ordered grammar one member in the right-hand side of each CF rule is marked as the next one to be substituted. The control sequence must then provide the proper rule, and must end exactly when we find a marked terminal or a marked ε; otherwise the production is a blind alley. Ну и так далее.

"Правила применения правил" напоминают про стратегии в Stratego... 🤔

Методологически - да, похоже. Правила для трансформации отделены от метода обхода дерева. Выбор, какие правила применять, тоже отделен от самих правил. Но тут-то как раз все просто. Отделение функции от данных, к которым она применяется - это старый добрый Visitor (он же и способ обхода дерева) и т.д.

> Хмм... это новое название TDPL (Birman, A., and Ullman, J. D. Parsing algorithms with backtrack. Information and Control 23, 1973), нет? В этой статье слегка смущают два параграфа: (a) As recursive descent parsing algorithms involve backtracking, care must be exercised when designing the parser, else the backtracking would cause the time required for parsing to grow exponentially with the input length. We give an "Early-type" tabular parsing method (see [Earley, 1970], [Aho and Ullman, 1972]) which will find a parse in time proportional to the input length for any input recognized by a T S or gTS. (b) Both the TS and gTS can define noncontext free languages. Thus, it is interesting to investigate the class of languages defined by these schemes. In particular, we show that all deterministic context free languages can be recognized in either T S or gTS. Coupled with the linear recognition time result mentioned above, we thus have one of the largest subclasses of the context free languages known to be linear time recognizable. Может я, конечно, что-то упустил, но, IMHO, там про Earley Parser.

> 1. В Prolog всё работает именно так ... > 3. Не может в left recursion. Может. Правило нужно вручную трансформировать. > 4. well-formed - нет левой рекурсии. Классика для LL-грамматик. Наличие таковой определяется опытным путем. В DCG всё точно также, единственно, там нет операторов *+?. Не удобно вручную все эти конструкции писать, но постепенно привыкаешь. Еще нет and-predicate. Lookahead - это просто список терминалов.

Спасибо! Самое близкое по теме. Буду копать control grammars дальше ...

Да, Вы что-то упустили (и я не понял, чем Вас смущают эти параграфы). ;) Вот цитата из abstract статьи, где впервые представлен формализм PEG (Ford, Bryan (January 2004). "Parsing Expression Grammars: A Recognition Based Syntactic Foundation"): While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970, TS/TDPL and gTS/GTDPL, which are here proven equivalent in effective recognition power. > но, IMHO, там про Earley Parser. Так что нет. Отсылки к Earley Parser, кстати, встречаются много где (в описаниях), т.к. многие методы — это его частные случаи или частично используют те же идеи.

> Правило нужно вручную трансформировать. означает не может. Не понимаю, о чём тут спорить. Так и LL(1) "может" и в левую рекурсию — если трансформировать грамматику путём устранения левой рекурсии, и в разбор LL(N > 1) — если использовать левую факторизацию, и т.д. и т.п. > well-formed - нет левой рекурсии. Хмм... а парадоксы Вы где потеряли? ;)

Понятно. Спасибо. Тяжеловато читать все эти выкладки.

> Хмм... а парадоксы Вы где потеряли? ;) В статье Форда well-formed означает только отсутствие левой рекурсии

"S ← !S" означает левую рекурсию :) Только что проверил ...

(Пролистал статью) Да, действительно, спасибо! > если я правильно помню Значит, помнил неправильно. Тем не менее, парадоксы-то есть (в статье Форда они не описаны), и это дефект формализма.

Хмм... в каком смысле? Проверили где/как?

Парадокс - это например S <- !a a?

В Прологе. Я же говорю, что PEG - это почти как DCG, а DCG - это Пролог. На самом деле DCG - это функционал для работы с разностными списками, но многие, по ошибке, используют его для синт-анализа :)

Так я уже приводил пример. А теперь приведу цитату. ;) It should also be noted that negation in a production system has weird properties, and soon leads to paradoxes. The simple rule S → ¬S describes the set of strings that it does not contain; in other words, a string is in S if it is not in S. Only slightly better is the grammar S → ¬T; T → T. Since T produces nothing, S produces all strings, i.e. Σ∗. And S → 0|1 | ¬S[0|1] contains any string Z over [0|1]* provided it does not contain the string obtained by removing the last token from Z; it is unclear what that means.

Так это же не well-formed грамматика

Я, опять-таки, не вчитывался, и если well-formed = нет левой рекурсии, то только второй пример — не well-formed, нет? А что не так с первым и третьим?

Везде левая рекурсия. Упоминания внутри предикатов тоже считаются, потому что по семантике это означает повторное применение правила с тем же положением во входной строке

А, всё, увидел в статье: 7. WF(!e) if WF(e). Но "упоминания внутри предикатов тоже считаются" — это, всё же, не совсем традиционное определение левой рекурсии. ;) > потому что по семантике это означает повторное применение правила с тем же положением во входной строке В принципе, логично... но см. выше.

Ну почему по ошибке. Напротив, это очень осмысленное применение.

Там смайлик в конце стоит …

Ещё такой момент - для PEG есть алгоритм, преобразующий произвольную грамматику, не принимающую пустую строку, в эквивалентную, но без предикатов

...ок.

Это, конечно, хорошо — но недостатков PEG не устраняет. Но вообще, PEG — интересный формализм в дидактическом плане, как контрпример к распространённому интуитивному убеждению "чтобы эффективно (или удобно) решать сложные задачи с помощью X, с его помощью должно быть легко решать простые задачи". ;) Т.е. несмотря на то, что с помощью PEG невозможно решить некоторые проблемы parsing уровня "hello, world!", он широко и успешно используется на практике.

Это означает, что причина недостатков PEG не в предикатах

Формально — не в предикатах, да (т.е. 4 пункт из https://t.me/CompilerDev/102908 — ерунда). Но, опять-таки "In terms of context-free grammar, a nonterminal is left-recursive if the leftmost symbol in one of its productions is itself." Т.е. это опять в пункт 0 (принцип работы другой, определения другие). ;)