грамматика С++ контекстно-свободная

Как же классические примеры:

A x(b); //C++
a * b; // C, C++

Я может разучился в С++, но совсем не понял про пример с A*B.

очевидно потому, что есть оператор «унарная звёздочка», и имеет он совсем иной смысл, нежели «бинарная звёздочка». (есть кстати ещё унарный минус, но его только совсем наркоманы перезагружают).

для сишечки можно вывести просто правило: если выражение контекстно-зависимое, то это говнокод

????

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

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

A<sometype>::name * b;

Чтобы понять, перед нами умножение двух переменных или же объявление указателя, нужно знать, во что раскровается A<sometype>::name - в переменную или в тип. А для этого надо выполнить вычисление (раскрытие) шаблона A<> для аргумента sometype. А язык шаблонов в крестах тьюринг-полон. В итоге:

1) парсер для построения синтаксического дерева должен знать семантику всей предыдущей программы;

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

Такие вот выводы.

третий вариант — мне насрать на твой говнокод, и я его даже не пытался прочитать. И на то, что я его не понимаю, мне тоже насрать.

Вот пример: d65761285dff1daf5eb5c9d0ca29713c. Это md5 от короткой фразы по-русски про тебя. Путём нехитрых подстановок и проверок я думаю ты её можешь прочитать. А будешь? Да я более чем уверен — не будешь. Точно также и я отношусь к твоему гипотетическому коду, который ты даже и не выложил.

третий вариант — мне насрать

А ты (lol) разве не заметил, что это и есть первый вариант? Мда, с логикой у плюсового быдла тоже туговато.

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

На уровне грамматик унарные и бинарные операторы с одинаковым символом легко описываются, в чем проблема?

(есть кстати ещё унарный минус, но его только совсем наркоманы перезагружают).

Хватит нести ерунду про перегрузку операторов, это не имеет отношения к грамматике языка.

1) насколько он КС-свободный

Там разбито на две части: Quote-monad (если правильно понимаю, нужна чтоб запоминать декларации, типа gensym в лиспе) - для конструирования кода: все оборачивается конструкторами функций / типов / переменных - тут как обычный хаскель. И quasi-quotes - здесь quote-monad ведет себя как код - тут может быть какой угодно edsl (в т.ч. и кз).

2) гомоиконный ли?

Очень сомневаюсь.

И quasi-quotes - здесь

Точнее вот эта часть $(...)

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

в грамматике C/C++ имеется ещё Over9000 меест, в котором возможен ещё более причудливый говнокод. А что это доказывает-то?

без говнокода x-- - --x; тред будет неполон.

на С невозможно построить контекстно-зависимое выражение

А это: Грамматики ЯП по Хомскому. (комментарий)

A<sometype>::name * b;

Теперь понял, спасибо. Тут даже без шаблона есть контекстная зависимость type *var.

Тут даже без шаблона есть контекстная зависимость type *var.

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

на С невозможно построить контекстно-зависимое выражение

да ладно. Выше в треде полно таких выражений. Да, ещё type*→void*→type* — тоже грамматически очень правильный говнокод.

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

для строгой тьюринг-полноты программа должна иметь возможность быть любой длинны. IRL это не так. Т.ч. остановится-то оно остановится. Но не факт, что скоро.

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

А что это _доказывает_-то?

Успокойся уже, доказывать тебе еще что-то. Тебе (пытались) _объяснить_ для чего могут понадобиться нашлепки над парсером (например, если компилятор использует yacc, ему придется отдельно приплясывать).

без говнокода x-- - --x;

Не могли бы вы пояснить, какое отношение имеет это выражение к грамматике?

x-- - --x;

Синтаксически однозначное выражение.

На уровне грамматик унарные и бинарные операторы с одинаковым символом легко описываются, в чем проблема?

тебе выше уже объяснили, что проблема в том, что a может быть типом, и в этом контексте * унарная.

Хватит нести ерунду про перегрузку операторов, это не имеет отношения к грамматике языка.

унарный минус не имеет, т.к. не может появится в момент объявления объекта.

x-- - --x;

Синтаксически однозначное выражение.

у этого выражения 4 значения(синтаксически). Т.е. компилятор(по стандарту) может понимать данное выражение любым из 4х способов. Каким именно — не определено, а значит _может_ зависеть от контекста(и кстати IRL для gcc таки зависит).

у этого выражения 4 значения(синтаксически). Т.е. компилятор(по стандарту) может понимать данное выражение любым из 4х способов.

Разупорись и почитай стандарт.

на С невозможно построить контекстно-зависимое выражение

да ладно. Выше в треде полно таких выражений. Да, ещё type*→void*→type* — тоже грамматически очень правильный говнокод.

С и С++ полностью и исчерпывающе описываются внешней формальной грамматикой. Если некий текст строго соответсвует формальной грамматике С/С++ - то он 100% является программой на С/C++. То есть С/С++ контекстно свободны.

тебе выше уже объяснили, что проблема в том, что a может быть типом, и в этом контексте * унарная.

Ненене, ты соскакиваешь. Унарная звездочка — это когда ты лезешь за объектом, лежащим за указателем (*ptr). В случае type *var звездочку вообще не имеет смысла рассматривать в роли оператора.

унарный минус не имеет, т.к. не может появится в момент объявления объекта.

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

И quasi-quotes

Ой не так: [|..|] для помещения обычного когда в Q-monad - имеет отношение к гомоиконности. // Q - для коструирования, $(..) - для применения (внутри абы что). Все рассредоточено, не знаю, тянет ли на гомоиконность.

С и С++ полностью и исчерпывающе описываются внешней формальной грамматикой. Если некий текст строго соответсвует формальной грамматике С/С++ - то он 100% является программой на С/C++. То есть С/С++ контекстно свободны.

Что значит «внешней»? По исходнику на крестах невозможно построить синтаксическое дерево с использование автомата, реализующего КС-грамматику.

Пруф:

void f()
{
    a b(c);
}

С и С++ полностью и исчерпывающе описываются внешней формальной грамматикой.

что значит «полностью»? Что значит «исчерпывающе»? Ты считал сколько в стандарте UB?

С и С++ полностью и исчерпывающе описываются внешней формальной грамматикой

... контекстно-зависимой.

Пилять, какое отношение UB имеют к синтаксису? Брысь из темы, не мешай умным людям вести разговор. Иди уроки делай.

у этого выражения 4 значения(синтаксически).

У этого выражения единственное AST.

компилятор(по стандарту) может понимать данное выражение любым из 4х способов

Компилятор может, парсер - нет.

Ты считал сколько в стандарте UB?

UB не относится к грамматике языка.

что значит «полностью»? Что значит «исчерпывающе»?

Любой текст соотв.формальной грамматике является кодом С/С++ и наоборот.

это значит что по формальному описанию ты можешь дать строгое отношение текста к языку. То есть сказать - вот этот вот конкретный текст является кодом C/C++. Насколько код семантически правилен(приводятся-ли типы,все ли параметры на месте и проч.) и можно ли по нему построить правильный AST, скомпилять и будет ли он вообще работать и делать то что ты подразумевал - совершенно другой вопрос, не имеющий отношения к топику, грамматикам языков и классификации Хомски.

к примеру языки описываемые http://www.antlr3.org/grammar/list.html являются контекстно-свободными. Конечно если сами грамматики написаны правильно :-)

Пилять, какое отношение UB имеют к синтаксису?

та никакого. a+b и в африке a+b, даже если в данном контексте a,b — указатели!

Брысь из темы, не мешай умным людям вести разговор. Иди уроки делай.

слышь, один из «умных», прочитай сначала что такое «синтаксис», а что такое «грамматика».

У этого выражения единственное AST.

нет, ВНЕЗАПНО: 3(точнее дерево одно, а обойти его можно тремя различными допустимыми способами). И ещё один способ не выразим через AST.

Компилятор может, парсер - нет.

парсер это часть компилятора.

тред не читай,своими словами отвечай.

тикл в этом смысле похож на форт(где немедленое слово само может дальше пока не надоест разбирать вход, и можно находу заменить ридер также) и лишпик(его принтер ,а главное ридер)

и вообще это характерно для любого интерпретатора которых может саморасширятся.

про контексто-независимость - это только на этапе синтаксического анализа ( тот же бнф) - попытка же строго увязать контекст привела к такому монстру как Алгол68 с его ацкой двухуровневой.

в реальных(прог) языках дерево разбора всё равно затем нагружают контекстом.

зы.

для большинства языков программирования не достаточно 1го стека (как источника памяти - магазина) для их работы - всё просто.

То есть сказать - вот этот вот конкретный текст является кодом C/C++. Насколько код семантически правилен(приводятся-ли типы,все ли параметры на месте и проч.) и можно ли по нему построить правильный AST, скомпилять и будет ли он вообще работать и делать то что ты подразумевал - совершенно другой вопрос, не имеющий отношения к топику, грамматикам языков и классификации Хомски.

«Построить AST» и «определить, принадлежит ли входной текст множеству, порождаемому грамматикой» - с практической точки зрения задачи эквивалентные. Еще раз повторяю: для C++ эта задача при помощи КС-грамматики не решается.

ибо ident binop ident что есть Exp

тикл в этом смысле похож на форт(где немедленое слово само может дальше пока не надоест разбирать вход, и можно находу заменить ридер также) и лишпик(его принтер ,а главное ридер)

Нет. Парсер тикля фиксирован, и ничего никуда не расширяется.

в реальных(прог) языках дерево разбора всё равно затем нагружают контекстом.

Ерунду написал. «В реализациях языков» ты хотел сказать.

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

UB не относится к грамматике языка.

относится.

Любой текст соотв.формальной грамматике является кодом С/С++ и наоборот.

код, который UB является C/C++?

это значит что по формальному описанию ты можешь дать строгое отношение текста к языку. То есть сказать - вот этот вот конкретный текст является кодом C/C++.

это невозможно в общем случае. Кроме A*B в стандарте ещё Over9000 скользких мест чисто грамматически. Даже просто A может означать не только сущность переменную, а так же другую грамматическую сущность «указатель на функцию» или «массив». Есть ещё l-value и r-value, и я не очень понимаю, как ты их различаешь бекз контекста? Или они по твоему эквивалентны, да?

к примеру языки описываемые http://www.antlr3.org/grammar/list.html являются контекстно-свободными. Конечно если сами грамматики написаны правильно :-)

мало-ли какие списки кто составляет...

относится.

Тяжелый случай.

код, который UB является C/C++?

Если ты себе ружьём отстрелишь яйца, является ли ружьё ружьём?

относится.

Ты вообще понимаешь, что такое язык? Если я напишу какую-нибудь абсолютно бессмысленную или имеющую множество значений фразу, формально она будет написана не на русском языке?

«Построить AST»

если у тебя порядок обхода AST однозначный, то получается несколько деревьев из одной программы. Т.ч. «построить» недостаточно, надо ещё выбрать нужное. С чего ты взял, что они(деревья) «эквивалентные»?

То же a+b даёт как минимум два дерева, и никто не может утверждать, что они эквивалентны.

однако синтаксис однострока:

команда море_ада_в_котором_запускают_..._и_играют_в_крестики_нолики терминатор_команды.

где команда ранее обьявленая команда которой фиксированный тикл_парсер передаёт её аргументТМ с которым команда и своим окружением(контекстом исполнения) может сотворить что угодно.

поэтому_то(т.е в том числе) тикл и люб всякими нердами - ибо синтаксис конкретной команды определяется(может) самой командной.

если у тебя порядок обхода AST однозначный, то получается несколько деревьев из одной программы. Т.ч. «построить» недостаточно, надо ещё выбрать нужное. С чего ты взял, что они(деревья) «эквивалентные»?

Зачем обходить АСТ? Все, он построен, грамматика пройдена. Во время оптимизаций и генерации кода можно строить еще множество деревьев, но это уже совсем другая история.

То же a+b даёт как минимум два дерева, и никто не может утверждать, что они эквивалентны.

Очень интересно увидеть эти деревья.

Если я напишу какую-нибудь абсолютно бессмысленную или имеющую множество значений фразу, формально она будет написана не на русском языке?

я не знаю. Смотря кто парсит, смотря что за фраза.

Фраза «Гло́кая ку́здра ште́ко будлану́ла бо́кра и курдя́чит бокрёнка» на русском? Я затрудняюсь ответить.

если у тебя порядок обхода AST однозначный, то получается несколько деревьев из одной программы. Т.ч. «построить» недостаточно, надо ещё выбрать нужное. С чего ты взял, что они(деревья) «эквивалентные»?

Блеать, бессмысленный набор слов. Я всерьёз усомнился: это живой человек писал, или копипаста с http://vesna.yandex.ru/ ? Тот самый случай, когда пациент не в состоянии осознать меру собственной некомпетентности.

Слушай, ты вот сам только что продемонстрировал отличие грамматики от семантики. Грамматически, ты пишешь по-русски. Но по смыслу сплошное UB.

Зачем обходить АСТ?

а зачем ты их строил?

Очень интересно увидеть эти деревья.

(+ a b)

(+ b a)

команда море_ада_в_котором_запускают_..._и_играют_в_крестики_нолики терминатор_команды.

где команда ранее обьявленая команда которой фиксированный тикл_парсер передаёт её аргументТМ с которым команда и своим окружением(контекстом исполнения) может сотворить что угодно.

поэтому_то(т.е в том числе) тикл и люб всякими нердами - ибо синтаксис конкретной команды определяется(может) самой командной.

Ты только забыл, что «море_ада» должно быть корректным TCL-выражением (сбалансированным по скобкам и так далее), иначе твоя программа вылетит на этапе парсинга

бессмысленный набор слов

да, это тебе не котиков разглядывать, тут ещё и думать надо. Ещё знать и уметь «строить AST»...

патрик, благослови анонимуса. вера в тебя (анонимуса) восстановлена