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

эм, читая текс, ожидал увидеть анонимуса в авторах...

А как насчет лиспа? Что такое контекст в данном контексте, сори за тафтологию? Лиспы с динамическим биндингом, похоже, контекстозавиcимы:

(define fu (lambda() x))
(define context1 (lambda() (let (x 1) (fu))))
(define context2 (lambda() (let (x 2) (fu))))

(print (context1)) ; 1
(print (context2)) ; 2

Казалось бы, какая связь между контекстностью _грамматики_ и динамическим биндингом (контекст вычисления)?

Вот если бы ты (ридер) макросы сюда припахал, то да :)

В этом смысле, объекты в JS тоже контекстозависимы

ob = {fu: function(){return this.x}}
context1 = {x: 1, fu: ob.fu}
context2 = {x: 2, fu: ob.fu}
console.log(context1.fu()) // 1
console.log(context2.fu()) // 2

Это, вроде бы, означает, что контексто-зависимыми являются вообще большинство ЯП

Да вроде большинство контекстно-свободны. Ну разве где встроены мощные макросы / шаблоны / синтаксис зависит от рантайма (perl begin-block, tcl). Не знаю, если ли реальные регулярные яп.

По идее, простейшие s-expr описываются (да поправят меня знающие) праволинейной грамматикой, например:

S -> T
T -> 0..9
T -> 'N
N -> + | - | * | / | A..z
S -> (NA
A -> )
A ->  SA

если ли реальные регулярные яп

Справедливости ради стоит отметить, что регулярная грамматика — это частный случай контексто-зависимой грамматики. ЕМНИП контексто-зависимая грамматика не обязана быть регулярной.

Ну тогда уж сразу вложенные классы: регулярная ⊂ КС ⊂ КЗ ⊂ (не помню название).

perl begin-block

пффф.. begin-block - фигня. Там есть вещи покруче, вот это например - http://www.perlmonks.org/?node_id=663393

http://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html

и аналогичный пруф про c++. Хотя компиляторы это обходят ограничением на глубину вложенности темплейтов емнип.

чушь какая-то.

1. что за «вычислители не-тьюринга»? Это какие? Где используются? При чём тут они?

2. что значит «контекстно-независимый ЯП»? За кой ляд нужен ЯП, который невозможно распознать, и определить правильность/неправильность?

Прикинь, если модели вычислений, которые слабее машины Тьюринга.

Используются они, например, в Agda и Coq.

Ну, возможно, тут имеется в виду под вычислителем любой парсер. А вообще, кроме тьюринг машин существует куча формализмов: лямбда-калькулус, комбинаторная логика, машина Поста, рефал и все-все-все.

«контекстно-независимый ЯП»

Может имелись контекстно-свободные грамматики? Ну с ними-то, если что, всё как раз проще, чем с контекстными.

За кой ляд нужен ЯП, который невозможно распознать, и определить правильность

Потому что есть программисты, которые пишут код головой, а не руками.

А практическая применимость в чем? (да, мне лень гуглить)

По-моему в этом треде многие путают синтаксис языка (текст программы) с семантикой (смысл языковых конструкций). Например в С++ выражение a+b контекстно-свободно с точки зрения синтаксиса и контекстно-зависимо с точки зрения семантики. Но по-моему традиционно термины о контекстной зависимости применяются именно к синтаксиу языка.

По-моему в этом треде многие путают синтаксис языка (текст программы) с семантикой

Примеры высказываний? Ну кроме тех, что относятся к осло-ветке:

1. что за «вычислители не-тьюринга»?

a+b контекстно-свободно с точки зрения синтаксиса

Как понять «контекстно-свободно с точки зрения синтаксиса»? Что это такое? Синтаксис и грамматика — это че одно и тоже? Если так, то a+b не контекстно-свободно, поскольку подстановка зависит от контекста. Выражение f(a, b) --> a+b будет контекстно-свободным, а там, где есть неявная подстановка, никакой контекстно-свободности не может быть по определению.

Например в С++ выражение a+b контекстно-свободно с точки зрения синтаксиса

Почему?

По-моему в этом треде многие путают синтаксис языка (текст программы) с семантикой (смысл языковых конструкций). Например в С++ выражение a+b контекстно-свободно с точки зрения синтаксиса и контекстно-зависимо с точки зрения семантики. Но по-моему традиционно термины о контекстной зависимости применяются именно к синтаксиу языка.

Тут следует добавить, что выражение A * B в крестах уже не будет синтаксически контекстно-свободным. Так что в целом кресты являются контекстно-зависимым языком, требующим выполнения произвольных тьюринг-полных вычислений на этапе парсинга. (В примере A * B: A может быть шаблоном, а язык шаблонов тьюринг-полон.) Т.е. семантика от синтаксиса неотделима: чтобы правильно распарсить код, нужно знать семантику уже распарсенного кода.

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

Доказывать корректность кода.

2. что значит «контекстно-независимый ЯП»? За кой ляд нужен ЯП, который невозможно распознать, и определить правильность/неправильность?

Ты путаешь. Распознать и доказать проще контекстно-независимый ЯП.

Прикинь, если модели вычислений, которые слабее машины Тьюринга. Используются они, например, в Agda и Coq.

я знаю. Ещё в POSIX REGEX. А при чём тут это?

TCL же, как и прочие синтаксисы гомоиконных ЯП, является как раз контекстно-свободным.

Разве что на уровне списков. И толку от «свободности» такой грамматики будет меньше, чем «зависимости» оных для perl / c++ / etc. : у последних хоть как-то проверяются языковые конструкции.

Может имелись контекстно-свободные грамматики?

да, наверное...

За кой ляд нужен ЯП, который невозможно распознать, и определить правильность

Потому что есть программисты, которые пишут код головой, а не руками.

Типичная программа на Перле выглядит так, как будто программист бился головой об клавиатуру; и чаще всего оно так и есть

2. что значит «контекстно-независимый ЯП»? За кой ляд нужен ЯП, который невозможно распознать, и определить правильность/неправильность?

Ты путаешь. Распознать и доказать проще контекстно-независимый ЯП.

не капитанствуй. У ТСа взаимоисключающие параграфы. О чём я и говорю.

Tcl-предложения не могут быть распознаны никаким иным вычислителем, кроме машины Тьюринга.

1. что за «вычислители не-тьюринга»? Это какие? Где используются? При чём тут они?

А при чём тут это?

По-твоему ast обычно строится «вычислителями тьюринга»? На пустом месте создал флуд, как обычно.

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

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

нет там никакой «мощности», не ври. И попаболи тоже нет. Есть ЧСВ>>Over9000 борщевиков, которые научились писать одностроки, которые непонятны 95% их одноклассников. И которые работают только в «хакирской OS Ubuta Lenex». Пишут «helo word!». Вот и вся «мощность».

У ТСа взаимоисключающие параграфы. О чём я и говорю.

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

context-sensitive languages = most programming languages

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

А ты о каком противоречии говоришь?

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

Ну если строго, то может и большинство КЗ. Но c практической точки зрения, скорее КС с небольшими хаками парсера для обработки особых случаев (например, если не ошибаюсь: typedef в С, (-) / infix в хаскеле).

мне так кажется, что там вообще о разном речь идёт. А контекста у тебя нет, потому и получается противоречие.

О каких контекстах вообще речь? Что значит «зависимый»? Определись...

хаками парсера для обработки особых случаев (например, если не ошибаюсь: typedef в С

это ты только про контекст интерпретации типа? А другие контексты? Так по большому счёту просто foo в любом ЯП может что угодно означать.

Про борщевиков и понторезов в моем посте не было не ври. Там было про программистов головой, а не руками.

И попаболи тоже нет.

Заметно. Только индусов еще забыл приплести. Че только не скажешь, когда возразить нечего, а попа болит очень сильно.

Синтаксис и грамматика — это че одно и тоже?

Ну я встречал пару раз, что грамматикой называли только правила выявления лексем, но вроде как чаще грамматикой описывают весь синтаксис языка (часть грамматики определяет лексемы, остальная - синтаксические конструкции).

Если так, то a+b не контекстно-свободно, поскольку подстановка зависит от контекста.

Какая подстановка зависит от какого контекста? Я не вижу варианта, когда a,+,b разложатся в дерево, отличное от SEXP (+ a b). Влияние препроцессора не рассматриваем.

http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-c’s-gramma...

если по простому - доказать корректность программы на контекстно-зависимом языке можно только исполнив её над заданным контекстом. То есть запустив интерпретатор. Создание МТ которая получив на вход только программу на контекстно-зависимом языке, сможет остановится и сказать что она корректна/нет невозможно.

Для контекстно-свободных существуют и иные способы.

вы в топике привели неверно переведённые и неполные цитаты, отчего у части народа случился бугурт :-)

Про борщевиков и понторезов в моем посте не было не ври. Там было про программистов головой, а не руками.

было. Просто ты не понял. Пишут, ЧСХ, руками. А головой думают. Голова нужна что-бы думать, а ЯП — просто средство выражения мыслей. Если твои мысли == нечитаемое говно, то твои мысли == нечитаемое говно. Увы. И никакой «мощности» тут и в помине нет, только дешёвые понты. Самое большее, на что такой борщевик способен — зашифровать rm -rf /, ибо настолько туп, что на большее его фантазии никогда не хватало.

Заметно. Только индусов еще забыл приплести. Че только не скажешь, когда возразить нечего, а попа болит очень сильно.

мне вот интересно, ты действительно думаешь, что тикель/перловка мне непонятны, и это меня расстраивает? И что распарсить говнокод можешь только ТЫ, а все другие тебе завидуют?

У меня для тебя плохие новости: всем просто насрать.

Я не вижу варианта, когда a,+,b разложатся в дерево, отличное от SEXP (+ a b)

По идее, если '+' - перегруженный оператор, он развернется в вызов метода.

мне так кажется, что там вообще о разном речь идёт.

может быть, но вроде нет.

LANGUAGE CLASS                    EXAMPLE
--------------                    -------
regular languages                 pattern matching languages
context-free languages            simpler programming languages
context-sensitive languages       most programming languages
recursively enumerable languages  natural languages

Тут следует добавить, что выражение A * B в крестах уже не будет синтаксически контекстно-свободным. Так что в целом кресты являются контекстно-зависимым языком, требующим выполнения произвольных тьюринг-полных вычислений на этапе парсинга. (В примере A * B: A может быть шаблоном, а язык шаблонов тьюринг-полон.)

Я может разучился в С++, но совсем не понял про пример с A*B. А заявление про парсинг вообще какой-то странное, ибо парсинг — и есть обработка синтаксиса языка. Можно разжевать подробнее свою мысль для тупицы?

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

typedef int AA;
int AA;

куда ты меня послал? Что это за говнокод? При чём тут вообще сишечка?! Ты можешь понять, что это дерьмо — побочный эффект typedef, и относится к граблям, на которых учатся НЕ наступать в первые 3 недели изучения C/C++?

и это меня расстраивает?

Тут два варианта:

1. Если ты безнадежно туп, то это тебя не расстраивает.

2. Если ты не безнадежно туп, то это тебя расстраивает, и попа, таки, болит.

Разве что на уровне списков. И толку от «свободности» такой грамматики будет меньше, чем «зависимости» оных для perl / c++ / etc. : у последних хоть как-то проверяются языковые конструкции.

Ну... я не про толк, а только про термины. :)

Хотя вот я слышал краем уха про темплейт хаскель. Мне лень гуглить, но если кто в курсе, расскажите: 1) насколько он КС-свободный; 2) гомоиконный ли?

По идее, если '+' - перегруженный оператор, он развернется в вызов метода.

А нужная виртуальная функция так вообще подберется во время исполнения.

Ты говоришь уже о семантике языка, _синтаксическое_ дерево ничего не знает о перегрузках операторов, оно просто содержит узел + с листьями А и В.

UPD. Речь у нас не про деревья, ясно, я просто к тому, что грамматика описывает не поведение программы, а всевозможные синтаксические конструкции.

куда ты меня послал? Что это за говнокод? При чём тут вообще сишечка?!

Успокойтесь, гениальный разработчик. Речь о грамматике языка, если покажешь, что по стандарту нельзя - другое дело.

// И да, положи пакет со льдом на стул - может полегчает.

Типичная программа на Перле выглядит так, как будто программист бился головой об клавиатуру; и чаще всего оно так и есть

головой

Это в лучшем случае.

Я не вижу варианта, когда a,+,b разложатся в дерево, отличное от SEXP (+ a b)

а я вижу сразу два варианта:

1. сначала вычисляем a, потом b.

2. сначала вычисляем b, а потом a.

Другое дело, что по стандарту C, от контекста совершенно не зависит, как оно будет вычисляться — в любом контексте это определено. Потому на практике от контекста это ЗАВИСИТ.

С другой стороны, только говнокод контекстно-зависимый.

Т.е. я не знаю как для Tcl, а для сишечки можно вывести просто правило: если выражение контекстно-зависимое, то это говнокод. Компилятор gcc иногда предупреждает о говнокоде, но очевидно не всегда.