LINUX.ORG.RU

Грамматики ЯП по Хомскому.

 


2

4

Пытаюсь рзобраться сейчас с сабжем, в частности с грамматикой TCL. И на обном из сайтов столкнулся вот с таким: " Tcl не является языком, который можно описать статической грамматикой. Он относится к классу так называемых контекстно-зависимых языков, для которых традиционными (основанными на формах Бэкуса-Наура и их модификациях) грамматиками «распознавание» всех возможных формально правильных предложений принципиально неосуществимо. Донэл Феллоуз (Donal Fellows) об этой отличительной черте Tcl высказал следующее мнение: формально правильные Tcl-предложения не могут быть распознаны никаким иным вычислителем, кроме машины Тьюринга. "

Источник: http://itc.ua/articles/drevnyaya_novaya_budushhaya_prodolzhenie_16346/

Это выдается там, вроде, за фичу тикля, но на другом сайте встретил:

context-sensitive languages — most programming languages

Это, вроде бы, означает, что контексто-зависимыми являются вообще большинство ЯП. Помогите разобраться. И может быть кто-нибудь встречал какую-нибудь таблицу ЯП с классификацией реальных ЯП по грамматикам (по Хомскому).


Ответ на: комментарий от anonymous

Да ладно. Ты просто, видно, не видел, как Емулек в одном посте сперва заявил, что рациональные/действительные числа не образуют кольцо,

там числа были совсем другие. Другое множество. Которое кольцо не образует.

emulek
()
Ответ на: комментарий от anonymous

лень искать. Это ты другого анонимуса души. ЕМНИП речь там шла(в начале) об эквивалентности двух алгоритмов.

emulek
()
Ответ на: комментарий от emulek

там числа были совсем другие. Другое множество. Которое кольцо не образует.

Во-во - я про это. «рациональные числа не образуют кольца» - «щито, простите?» - «нет, нет, я не имел ввиду, что рациональные числа не образуют кольца, я имел ввиду совсем другое множество!»

anonymous
()
Ответ на: комментарий от anonymous

Да вот: как статически доказать эквивалентость двух произвольных алгоритмов (комментарий)

читаем: «ВНЕЗАПНО: множество вещественных(натуральных, целых, рациональных, и т.п.) чисел кольцом НЕ является.»

и чтобы никто не засомневался в безграмотности, емулек даже потом поясняет, почему не является: «дык определи деление на ноль. Ноль является элементом множества «целых, рациональных», однако результат деления не определён. Значит кольцо не замкнуто. Значит не кольцо.»

так-то!

anonymous
()
Ответ на: комментарий от emulek

Неоднозначность состоит в том, будет ли это АСТ «expression->(identifier binary-op identifier)» или АСТ «definition -> type * identifier»

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

anonymous
()
Ответ на: комментарий от anonymous

Во-во - я про это. «рациональные числа не образуют кольца» - «щито, простите?» - «нет, нет, я не имел ввиду, что рациональные числа не образуют кольца, я имел ввиду совсем другое множество!»

я же не виноват, что в том дискуссе оппонент называл «множеством рациональных чисел» какую-то HEX, которая даже не кольцо?

emulek
()
Ответ на: комментарий от anonymous

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

в таком случае, этот твой парсер не сможет отличить код php от кода C/C++. Я правильно понимаю? Т.е. по твоему, у php синтаксис эквивалентен C/C++, да?

Если «нет», то приведи пример, в каком месте «нет».

emulek
()
Ответ на: комментарий от emulek

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

anonymous
()
Ответ на: комментарий от emulek

в таком случае, этот твой парсер не сможет отличить код php от кода C/C++

Конечно, сможет.

Т.е. по твоему, у php синтаксис эквивалентен C/C++, да?

Нет, у них разная грамматика.

Если «нет», то приведи пример, в каком месте «нет».

ну например: class yoba {blah-blah-blah} - синтаксически корректно на пехепе, но не на сишке.

anonymous
()
Ответ на: комментарий от anonymous

Так что вопрос «полноты» описания сводится к тому, какие именно ошибки в термах мы будет считать существенными

о чем и толкую

MyTrooName ★★★★★
()
Ответ на: комментарий от MyTrooName

хаскель тьюринг-полный. отсюда вывод - не контекстно-свободный, т.е. контекстно-зависимый (в лучшем случае)

А Brainfuck? Тоже контекстно-зависимый?

hateyoufeel ★★★★★
()
Ответ на: комментарий от MyTrooName

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

anonymous
()
Ответ на: комментарий от anonymous

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

MyTrooName ★★★★★
()
Ответ на: комментарий от anonymous

Ошибкой алгоритма может являться, но ошибкой правил языка не является.

anonymous
()
Ответ на: комментарий от anonymous

Я в курсе. Я лишь упрощаю задачу для товарища MyTrooName.

hateyoufeel ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.