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

Смысл высказывания на языке не является предметом формальной грамматики

ты лужа пёрнул запах цветы не

или нужны пояснения?

Мне не понятно, чем твой пример с typedef отличается от примера с запятыми. Тем что запятые идут в одном Cи стейтменте, а с typedef и функция в разных? Так для теории грамматики, стейтменты Си побоку, можно рассматривать typedef и функцию как единую входную последовательность (нетерминал), который состоит из 2 нетерминалов typedef и void f() {..} и т.д. получаем то-же что и с запятыми.

Ты говоришь, что запятая имеет разный СМЫСЛ. Но. Смысл высказывания на языке не является предметом формальной грамматики

Еще раз, мы говорим не о сферических грамматиках, а о конкретных грамматиках, задающих язык для некоторого вычислителя и т.о. любая последовательность терминалов - есть последовательность инструкций вычислителя, каждая из которых имеет для вычислителя смысл. Так что можно не разводить здесь демагогию, а просто говорить о том, что любой нетерминал после всех трансформаций получает некоторый смысл. Если смысл этих инструкций одинаковый (входная последовательность данных после вычисления преобразуется в одинаковый результат), значит преобразования одинаковы (эквивалентны). Зачем бл..ть писать тут целый этот параграф, вместо одного слова?

Какой «нетерминал» выбирать решает либастрал что-ли?

Как правило, решает LR-автомат на основе спецификации грамматики. В общем случае, любой КС-автомат.

да. В случае C/C++ в зависимости от контекста решает что значат синтаксически запятые, и если они по синтаксису разделяют параметры функций(т.е. в контексте аргументов функции), то рожает три AST. Если это «обычная запятая», то рожает одно AST.

А вот дальше — дальше действительно синтаксис заканчивается.

Смотри:

arrays.c: В функции «main»:
arrays.c:32:2: ошибка: слишком много аргументов в вызове функции «f»
  return f(10, 20);
  ^
arrays.c:25:5: замечание: declared here
 int f(int a)
     ^

int f(int a)
{
	return a++;
}

int main()
{
	return f((10, 20));
}

arrays.c: В функции «main»:
arrays.c:32:14: предупреждение: левый операнд операции `запятая' не имеет побочных эффектов [-Wunused-value]
  return f((10, 20));
              ^

ошибок нет. Хотя компилятор и предупреждает, что я говнокодер. Но с т.з. синтаксиса всё хорошо.

У тебя каша в голове. Выражение твое просто не имеет смысла, т.е. оно семантически некорректно. Твоя ошибка - это ошибка типов, а не синтаксическая ошибка. Она распознается тайпчекером. А типы - это и есть контексты. Тайпчекер распознает ошибку на основе синтаксиса. Т.е. то что происходит - это синтаксический анализ. А грамматика - это сама возможность распознать.

У тебя каша в голове.

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

в некоторых архитектурах — можно, да.

В стандарте это называется «точки следования».

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

как обычно бывает, IRL всё несколько сложнее, чем в голой теории, и синтаксис значков в C/C++ таки зависит от контекста, в котором эти значки используются. В контексте lvalue это одно значение, в контексте rvalue другое, в контексте аргументов функции — третье. Синтаксис операторов также зависит от типа.

IRL всё несколько сложнее, чем в голой теории, и синтаксис значков в C/C++ таки зависит от контекста

Так выпьем же за это!

Т.е. + это сложение, но оно РАЗНОЕ, в зависимости от слагаемых

Важно то, что + это всегда выражение, а не что-то другое.

вот ты и не угадал, указатель+указатель, это НЕ выражение, а HEX. Причём именно синтаксически, ибо семантически складывать можно, как ты сам выше доказал.

context-sensitive languages

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

контекстно-независимые это context-free

все тьюринг-полные языки по определению не могут быть контекстно-независимыми

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

Тем что запятые идут в одном Cи стейтменте, а с typedef и функция в разных?

Нет.

можно рассматривать typedef и функцию как единую входную последовательность (нетерминал), который состоит из 2 нетерминалов typedef и void f() {..} и т.д. получаем то-же что и с запятыми.

Нельзя. Ты не сможешь в виде БНФ (БНФ и КС эквивалентны) записать такой набор правил грамматики Си, в котором a * b может быть распознано без знания контекста. Если хочешь, можешь попробовать.

A formal grammar is considered «context free» when its production rules can be applied regardless of the context of a nonterminal.

Пусть у тебя есть правило: statement -> expression | declaration;

При этом есть частные случаи expression и declaration, которые выглядят одинаково: a * b. Ты не сможешь выбрать, в какой нетерминал эту последовательность свернуть: в expression или в declaration.

С запятыми ситуация иная. x, y, z встречается только в нетерминалах, которые КС-автомат не спутает между собой, потому что в грамматике нет случая, когда между ними придётся делать выбор. Нет такого правила, которое выглядело бы как somenonterm -> argument_list | expression;

Когда автомат встречает последовательность x, y, z, он находится либо в состоянии root -> {какие-то еще нетерминалы} -> expression -> binary_operator, либо в состоянии root -> {какие-то еще нетерминалы} -> argument_list. Таким образом, никакой путаницы не возникает.

При выборе для a * b мы находимся в состоянии root -> {какие-то еще нетерминалы} -> statement, и нам нужно сделать выбор между expression и declaration. Выбор этот сделать невозможно.

Еще раз, мы говорим не о сферических грамматиках, а о конкретных грамматиках, задающих язык для некоторого вычислителя и т.о. любая последовательность терминалов - есть последовательность инструкций вычислителя, каждая из которых имеет для вычислителя смысл. Так что можно не разводить здесь демагогию, а просто говорить о том, что любой нетерминал после всех трансформаций получает некоторый смысл. Если смысл этих инструкций одинаковый (входная последовательность данных после вычисления преобразуется в одинаковый результат), значит преобразования одинаковы (эквивалентны). Зачем бл..ть писать тут целый этот параграф, вместо одного слова?

Советую начать отсюда: http://en.wikipedia.org/wiki/Context-free_grammar

Мы говорим о формальных грамматиках Хомского (внимательно смотрим на название треда; еще раз смотрим; думаем). Так что можно не разводить здесь демагогию, а просто прочитать определение формальной грамматики. А потом определение КС-грамматики. Можно прямо в википедии.

Это просто блядь болезнь какая-то: вместо того, чтобы пользоваться нормативной теорией и отвечать на тот вопрос, который обозначен в треде, люди придумывают какую-то свою теорию с похожими словами и потом с кем-нибудь спорят. Что ты доказываешь? Что терминал запятая имеет разное значение в разных местах программы? Так это очевидно. Какое это отношение имеет к Хомскому или к парсерам? Никакого.

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

заигнорь меня пожалуйста.

Стыдно стало штоле? Давай ты лучше забанишься. Или сделаешь вдоль.

Принципиально не пользуюсь игнором.

При выборе для a * b мы находимся в состоянии root -> {какие-то еще нетерминалы} -> statement, и нам нужно сделать выбор между expression и declaration. Выбор этот сделать невозможно

root -> typedef -> {какие-то еще нетерминалы} -> declaration

root -> {какие-то еще нетерминалы} -> expression -> binary_operator

Ну и в чем разница с запятыми-то?

Ты не сможешь в виде БНФ (БНФ и КС эквивалентны) записать такой набор правил грамматики Си, в котором a * b может быть распознано без знания контекста

А ты не сможешь записать такой набор правил для запятых.

root -> typedef -> {какие-то еще нетерминалы} -> declaration

1. У тебя нетерминал a * b будет лежать внутри нетерминала typedef?

2. Даже если и будет, что само по себе facepalm, тебе надо попоставить затайпдефленное a с тем a, которое в a * b. КС-автомат сопоставлять произвольные строки не умеет.

А ты не сможешь записать такой набор правил для запятых.

Не придуривайся.

1. У тебя нетерминал a * b будет лежать внутри нетерминала typedef?

А что если нетерминал записан не внутри скобочек он уже не является вложенным?

typedef int a { a*b; } // Гипотетический оператор с указанием области действия

vs

typedef int a; a*b;

Ну и в чем разница? В том, что он действует всегда до конца единицы трансляции? Лол.

тебе надо попоставить затайпдефленное a с тем a, которое в a * b. КС-автомат сопоставлять произвольные строки не умеет

Что тут с чем сопоставлять? Распарсили нетерминал, что а - тип. В контексте этого нетерминала распарсили а, значит это тип, значит это нетерминал - определение. Всё это работает на уровне соглашений, т.е. мы договариваемся, что у нас такой язык.

А теперь с запятыми, там всё тоже самое. Нельзя определить, что делать с 1,2,3 без знания контекста. Я конечно понимаю, что вызов функции foo(1,2,3) выглядит естественно, но кто собственно сказал, что 1,2,3 тут должно восприниматься как список параметров, а не как выражение? Так же как и в случае a*b тут просто договоренность, что в таком контексте - такой смысл (ок, такая трансформация нетерминала в терминалы).

Стыдно стало штоле? Давай ты лучше забанишься. Или сделаешь вдоль.

нет не стыдно.

нет не забанюсь

нет не сделаю

Начни с себя, советчик.

Ну и в чем разница с запятыми-то?

Мда... Попробую еще раз...

КС-автомат имеет стековую память. Состояние автомата - это состояние его стека + текущий терминал во входной последовательности.

Когда автомат встречает «запятую как разделитель» и «запятую как оператор», он заведомо имеет разные состояния на стеке.

Вот тебе упрощенная грамматика под это дело:

expression := comma_operand expression_tail
expression_tail := "," expression | e
comma_operand := word arguments
arguments :=  "(" argument_list ")" | e
argument_list := comma_operand argument_list_tail
argument_list_tail := "," argument_list | e

На входной последовательности x, y, z встретив запятую, автомат имеет на стеке expression -> expression_tail, а на входной последовательности f(x, y, z) — expression -> comma_operand -> arguments -> argument_list -> argument_list_tail.

В случае с a * b состояние стека одинаковое, нетерминал тоже одинаковый: выбор сделать нельзя. При анализе встретив a, автомат для принятия решения должен знать: перед ним имя типа или имя переменной. На КС-автомате такую логику закодировать невозможно.

Между прочим, я сейчас рассказываю элементарные вещи со второго, что ли, курса универа. Хочется спросить: вы в ВУЗЕ на соответствующей специальности учились вообще? И если учились, то за что вам оценки ставили?

А что если нетерминал записан не внутри скобочек он уже не является вложенным?

Не терминал не является вложенным, если он не вложенный. Сугубо в рамках БНФ, без всякой фантации про единицы трнасляции.

действует всегда до конца единицы трансляции

Это и есть контекст. В КС-анализе тебе надо только знать то, что СВЕРХУ. В КЗ-анализе тебе надо знать то, что ДО или ПОСЛЕ. Разницу между СВЕРХУ и РЯДОМ сам поймёшь?

Распарсили нетерминал, что а - тип. В контексте этого нетерминала распарсили а, значит это тип, значит это нетерминал - определение. Всё это работает на уровне соглашений, т.е. мы договариваемся, что у нас такой язык.

Блядь. Это и есть контекст. Твой гипотетический парсер встречает typedef int a, и запоминает, что терминал a является сущностью «тип». Я тебе уже битых полдня объясняю, что в КС-автомате именно ТАКУЮ логику закодировать невозможно. Потому он и называется контекстно-свободным. Он видит только свой стек и текущий терминал входной последовательности. Всё, больше у него ничего нет, никакого дополнительной информации.

А теперь с запятыми, там всё тоже самое. Нельзя определить, что делать с 1,2,3 без знания контекста.

Можно. Для распознавания 1,2,3 не надо хранить никакой вспомогательнйо информации, кроме той, что уже есть на стеке автомата.

но кто собственно сказал, что 1,2,3 тут должно восприниматься как список параметров, а не как выражение?

Грамматика сказала. Грамматика - это набор формальных правил для стекового автомата.

Народ, вам реально стыдно должно быть. Я лет в 19 всё это понимал, когда учился, и сейчас столь же ясно понимаю. Вы же вообще учились где-нибудь, нет? Если нет, то зачем вы лезете без знания матчасти, А если да, то просто стыдно должно быть.

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

Я лет в 19 всё это понимал, когда учился, и сейчас столь же ясно понимаю. Вы же вообще учились где-нибудь, нет?

Я в 19 лет тоже много чего понимал. Потом прошло.

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

И что же тут подразумевается под контекстно-свободностью языка?

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

А я что написал?

все тьюринг-полные языки по определению не могут быть контекстно-независимыми

А можно примеры реальных ЯП? Хаскель — контексто-зависим или нет?

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

Так что, разумеется, любой тьюринг-полный ЯП как целое является контекстно зависимым.

Но формализм его синтаксиса стараются делать контекстно свободным для облегчения чисто практических задач: разработки IDE, автоматического анализа исходников и т.п.

Например, контекстно свободные парсеры возможны для таких ЯП как TCL, CL, Pascal, Modula и т.п. Для С++ контекстно-свободный парсер невозможен.

что не одно и то же

А аноним не безнадёжен. Правда контекстно-независим и не понял, что отвечал я совершенно не ТСу.

Неоднозначные грамматики

у бабки на рынке спрошу

Лучше у классики - Hopcroft J.E., Motwani_R., Ullman J.D. Introduction to automata theory, languages, and computation 2001, лично тебе желательно с самого начала, но сама тема начинается на 205-й странице.

Твоей изворотливости даже Эмулек бы позавидовал.

Для С++ контекстно-свободный парсер невозможен

Да не принципиально: стандартом ограничить максимальную глубину рекурсивных шаблонов, A*B подправить.

таких ЯП как TCL, CL

Это не такой уж и плюс им. [Крайний пример] могу хоть регулярный язык сделать таким макаром: anychar+ , все что не является программой по с99 (для конкретики) - UB, остальное по текущей ревизии.

могу хоть регулярный язык сделать таким макаром: anychar+

Тут вопрос в практической применимости же. Скажем, для Модулы сделать практически-полезный парсер довольно просто (вопрос о практической пользе самой Модулы оставим в стороне), например, для использования в IDE. А для C++ уже значительно сложнее.

В случае с TCL и CL (и вообще с гомоиконностью) разговор о практической их пользе сведётся к срачу, выходящему за рамки формальных грамматик. Защищать любую из сторон в таком сраче я не горю желанием. :)

Скажем, для Модулы сделать практически-полезный парсер довольно просто

Против модулы ничего не имею, выделил цитату ровно.

Защищать любую из сторон в таком сраче я не горю желанием. :)

Наверное можно сказать, что «низкоуровневость» (анализ структуры дальше списков особо не идет) их грамматик - цена за подобную гомоиконность. А если просто говорить КС - может звучать предвзято.

И что же тут подразумевается под контекстно-свободностью языка?

определимость контекстно-свободной грамматикой, очевидно

А я что написал?

о, прости, глаза замылились. все верно.

Хаскель — контексто-зависим или нет?

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

некоторые^Wпочти все реально существующие тьюринг-полные языки программирования «описывают» контекстно-свободными грамматиками. фишка в том, что это описание не является полным - в контекстно-свободной грамматике невозможно запомнить, какой идентификатор был объявлен, а какой нет: это учитывается на более поздних стадиях компиляции

по сабжу:

«распознавание» всех возможных формально правильных предложений принципиально неосуществимо

фишка в том, что в тикле код - это строка, строка в кавычках (ну или фигурных скобках - однофигственно).

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

определимость контекстно-свободной грамматикой, очевидно

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

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

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

То есть язык SKI нельзя породить с помощью BNF (КС по определению)

<T> ::= 'S' | 'K' | 'I' | '(' <T> <T> ')'

или грамматики Хомского

G = ({S, K, I, (, )}, {T}, T, {T -> S, T -> K, T -> I, T -> (TT)})

(тоже КС), так, что на соответствующем множестве термов (множестве строк как подмножестве KleeneStar({S, K, I, (, )}) порождённом указанными грамматиками) задаётся редуцирование и отношение бета эквивалентности делающее этот язык Тьюринг-полным?

А для разбора деревьев из текста (или его инвалидации) в случае КС-грамматик достаточно МП-автомата, как известно (разрешимость).

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

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

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

а вот это просто не понял

грамматика должна являть _полным_ описанием языка

не должна, никто ее не заставляет.

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

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

Это утверждение ортогонально изначальному:

все тьюринг-полные языки по определению не могут быть контекстно-независимыми

И тоже вряд ли верно: почему бы КЗ грамматике не быть эквивалентной (в плане принимаемого языка) некой КС грамматике?

// ортогонально: в смысле причина и следствие не в том порядке

да, я не прав. каша в голове.

тот же brainfuck замечательный пример.

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

поправь, если ошибаюсь

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

приведи свое определение контекстно-свободного языка.

приведи свое определение контекстно-свободного языка.

А, если в плане _существования_ - то да, но один и тот же язык может описываться разными грамматиками. Все равно этот аргумент - немного не к месту.

ты то ли не то ответил, то ли не ту цитату вставил

[жж]я еще раз извиняюсь, если это я туплю, т.к. в настоящий момент под водкой, которая под пивом. или наоборот... с какой стороны посмотреть[/жж]

Как можно быть столь безграмотными долбоебами? понятие «контекстной зависимости» в словосочетании «контекстно-зависимая грамматика» говорит не о том, что смысл символа может зависеть от окружающих его символов (это происходит в ЛЮБОЙ нетривиальной грамматике, даже в регулярной, разбираемой регекспами, например, регексп «12» разбирает только «12», а значит «синтаксический смысл» «2» зависит от положения - идет ли эта «2» после «1»), а о том, что нетерминалы в левой части правил могут быть окружены другими (не)терминалы, то есть ПРОДУКЦИИ МОГУТ ЗАВИСЕТЬ ОТ КОНТЕКСТА. С другой стороны, грамматика является контекстно-свободной, если она не содержит таких правил (или ее можно привести к такому виду).

вот ты и не угадал, указатель+указатель, это НЕ выражение, а HEX.

Это НЕХ только лишь потому, что такого нетерминала, как «указатель» в с/с++ ВООБЩЕ НЕТ. Нету в построенном АСТ никаких указателей.

Твоей изворотливости даже Эмулек бы позавидовал.

Да ладно. Ты просто, видно, не видел, как Емулек в одном посте сперва заявил, что рациональные/действительные числа не образуют кольцо, а потом, поняв, что сморозил глупость, просто сказал, что НЕ БЫЛО ТАКОГО МАМОЙ КЛЯНУСЬ (при том что ему приводили цитату из поста, в которой это прямым текстом сказано). Вот это действительно изворотливость.

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

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

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

Это НЕХ только лишь потому, что такого нетерминала, как «указатель» в с/с++ ВООБЩЕ НЕТ. Нету в построенном АСТ никаких указателей.

а что народ столько времени спорил за A *B?