@Yaroslav_Schekin можете, пожалуйста, растолковать где проходит граница между неоднозначной КС

грамматикой, для которой мы потом делаем disambiguation на основе информации из контекста, и КЗ-грамматикой, которая однозначно разбирает нужный язык?

Кстати, такой теоретический вопрос: а может ли быть любая кз грамматика записана как неоднозначная кс грамматика?

> Теоретически — ни в какой, это просто грамматики разных языков. Вот это — ключевой момент, тут Вы совершенно правы. Т.е. с т.з. формальной лингвистики не существует никакой этой вашей "семантики", есть только один принцип: язык — это множество строк (последовательностей токенов, точнее), и данная строка либо входит в это множество, либо нет. Программы/алгоритмы, определяющие это, называются recognizers (acceptors, detectors...), кстати. Parser же — это просто алгоритм (программа), определяющий [хотя бы одну] последовательность применения продукций грамматики, в результате которой из стартового нетерминала получается данная строка. Далее, грамматики определяются на произвольных токенах (что там "внизу", формальную лингвистику не интересует вообще — вот в качестве "страшного" примера: токены могут выделяться на основании анализа исходного потока "символов", каждый из которых является программой+её входом, путём решения halting problem для каждой такой пары — и на выходе будут просто токены "0" и "1"). В таком случае определить язык, состоящий из всех останавливающихся программ, тривиально. ;) > где проходит граница между неоднозначной КС грамматикой, для которой мы потом делаем disambiguation на основе информации из контекста, и КЗ-грамматикой, которая однозначно разбирает нужный язык? Поэтому формально она проходит прямо по их определениям. Т.е. если для чего-то (на данных токенах!) определена КС-грамматика, т.е. выражение для множества последовательностей, составляющих данный язык (который, возможно, даже inherently ambiguous) — это КС, однозначна она или нет. А если на данном множестве tokens задать такую КС-грамматику, которая выражает именно этот язык, невозможно, но возможно задать CDG — это КЗ-язык, вот и всё. И да, мощность КЗ-грамматик часто сильно недооценивают. Очень хорошая цитата в тему (выделения мои, если что): A more prosaic and practical example can be found in the successive sets of Java programs that can be generated by the various grammar types. . The set of all lexically correct Java programs can be generated by a regular grammar. A Java program is lexically correct if there are no newlines inside strings, comments are terminated before end-of-file, all numerical constants have the right form, etc. . The set of all syntactically correct Java programs can be generated by a context-free grammar. These programs conform to the (CF) grammar in the manual. . The set of all semantically correct Java programs can be generated by a CS grammar. These are the programs that pass through a Java compiler without drawing error messages. . The set of all Java programs that would terminate in finite time when run with a given input can be generated by an unrestricted phrase structure grammar. Such a grammar would, however, be very complicated, since it would incorporate detailed descriptions of the Java library routines and the Java run-time system. . The set of all Java programs that solve a given problem (for example, play chess) cannot be generated by a grammar (although the description of the set is finite). Note that each of the above sets is a subset of the previous set.

Предположим, что язык Си - множество всех программ, корректных с точки зрения стандарта (т.е. семантически). Вопрос: У си есть неоднозначности, которые разрешаются методом lexer hack - это значит, что грамматика си неоднозначна, но не кз? А вот тот факт, что нам необходимо помнить про идентификаторы и сохранять семантику программы (например не допускать использование необъявленных идентификаторов) говорит о том, что язык Си контекстно-зависим?

> (т.е. семантически). Тогда именно КЗ (см. цитату про Java). Т.е. если Вы имеете в виду, что программа: int main(void) { printf(a); } в этот язык не входит.

Н.Вирт писал, что в своё время, не нашёл грамматики ЯП Java. Т.е. сделали задним числом?

Конечно: переменная "а" не объявлена. ( А если в Java так можно, но такой хокей / GW Basic "нам не нужен" )

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

Остаётся посмотреть "дни рождения" грамматик ( заодно и авторство)

А если так https://cs.stackexchange.com/questions/29321/are-constituency-grammars-and-dependency-grammars-two-different-types-of-context

Что "если так"? Я не понял вопроса, извините...

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

Что там отличается от описанного мной, конкретно? И да, Вы не путаете формальную лингвистику с обычной (из которой взяты два примера non-Chomsky systems в этом вопросе), случайно? ;)

А, нет, показалось. Интервенция памяти от прочтения сотни сообщений...