Кстати, раз уж я открыл эту замечательную книгу — вспомнил,

что хотел спросить (если кто разбирался):

Почему авторы Scannerless Generalized-LR parsing и SDF3 (Eelco Visser et al) считают, что это удачный формализм?

Ведь с т.з. computer linguistics он относится к non-Chomsky grammars / systems (см. классификацию в той же "Parsing Techniques: A Practical Guide") — а их немало (и потенциально можно их придумывать бесконечно); и для практики, казалось бы, они ценны тогда, когда обладают какими-то хорошими свойствами.

Что касается SGLR, если я правильно понял (я признаю, что скорее всего не прочитал всех статей про него):
. Результатом parsing является parsing forest, а это (опять-таки, с т.з. computer linguistics) указывает на "слабость" формализма.
. Вообще, parsing power у него ненамного выше CFG.
. Он не может автоматически выявлять неоднозначные грамматики.
. Время/сложность разбора у него как асимптотически (и особенно практически, если я правильно понял) [очень] плохие.
. У меня сложилось впечатление, что в фундаменте формализма всё ещё есть какие-то нерешённые проблемы (я забыл — то ли с reject productions, то ли c follow restrictions), из-за которых результат parsing вообще (в некоторых случаях) не детерминирован.

Что касается "хороших" свойств, то это:
. Единый синтаксис, похожий на традиционную EBNF.
. Возможность создавать composite languages ("расширенные" языки на основании существующих, за счёт scannerless).

И мне лично это не кажется удачным сочетанием свойств.
Может, я что-то неправильно понял, или упустил, или какие-то из вышеперечисленных недостатков были устранены в новых исследованиях?

Для чего нужны подобные формализмы? Для верифицированного парсинга?

Кстати, как написано в уже упомянутой книге: "the existence of non-Chomsky grammars points to user dissatisfaction with the traditional Chomsky hierarchy... ease of use is the issue". Ну и да, несмотря на мощь CDG, их практически невозможно использовать на практике — крайне "нечеловеческий" (очень неудобный) формализм. Ну и все вышеупомянутые недостатки у них есть (и деревьев разбора в них тоже нет, кстати), а вот достоинств никаких нет.

А что именно нечеловеческого?

Я же писал именно о context-sensitive grammars, а не о каких-то эквивалентных (либо близких, либо превосходящих) им по мощности. > Коньюктивные и булевы грамматки не контекстно-свободны... индексные грамматики не контекстно-свободные, etc. И все они — non-Chomsky grammars, не так ли? > Ничего из этого не является чем-то чудовищным. Да, и всё это появилось и используется потому, что эквивалентные им классические type 1 (или 0) grammars Хомского как раз являются чем-то чудовищным. > что может быть нечеловеческим, так это их описание в виде порождающих правил, ну так просто не нужно использовать порождающие грамматики Я как раз и приводил цитаты, которые указывают на ту же проблему (и проблемы (и не порождающих грамматик, кстати — разве в самом принципе есть что-то плохое?) на этом далеко не заканчиваются — опять-таки, см. тот же источник, например). > Есть языковые уравнения, есть CLFP и ILFP, есть DCG, наконец. И это всё тоже non-Chomsky grammars. Т.е. все эти примеры как раз в пользу процитированной мной точки зрения. ;)