Здравствуйте, vdimas, Вы писали:

V>И не нужен. Большинство актуальных запросов формируются ТОЛЬКО динамически....

В моей практике большинство запросов все же можно статически скомпилировать. Сейчас они динамические благодаря тому, что все API доступа динамические (кроме LINQ). Другое дело, что совсем без динамических запросов тоже плохо, поэтому LINQ частенько тоже проблемен.

Здравствуйте, AndrewVK, Вы писали:

AVK>Не, ну это понятно. Неоднозначные грамматики с эвристиками (типа тернарного оператора в шарпе или угловых скобок в плюсах, ты это имел ввиду?) это уже точно кандидаты на рукопашное разруливание проблем.
Или TDOP'у. Он такие вещи ест, вообще не напрягаясь.
Вот, например тренарный оператор
cond is expr = expr : 300 '?'s expr ':'s expr;

Здравствуйте, WolfHound, Вы писали:

WH>Или TDOP'у. Он такие вещи ест, вообще не напрягаясь.

Какие такие? Бывают вещи, которые не описываются вообще грамматикой. Вместо этого есть текстовое описание, как поступать в той или иной конфликтной ситуации.

WH>Вот, например тренарный оператор
WH>cond is expr = expr : 300 '?'s expr ':'s expr;

Я точно не помню, но там проблемы не с самим оператором. а с его комбинацией с оператором ??.

Здравствуйте, WolfHound, Вы писали:

WH>>>Брееед! TDOP прост как пробка и ресурсы не ест.
V>>Это LALR или LL(1) ресурсы не ест.
WH>Ты хоть знаешь как TDOP работает

Сорри, я ваше новое увлечение TDOP подробно еще не смотрел, хватило ПЕГ когда-то. Но и без этого известно, что любая грамматика без неоднозначностей относительно выбранного способа разбора будет линейна, то бишь ее можно парсить за O(n), в чем был прикол отрывка? Как решаются неоднозначности, которые возникают из-за контекстно-зависимой сути исходной грамматики? Как TDOP разберет угловые скобки в С++ до ответа семантического анализатора — это типы или переменные в области видимости? Т.е. это шаблоны или последовательность операций больше/меньше? Неоднозначности грамматик приходится протаскивать в грамматику парсера, где вместо целевых выражений описывать такие промежуточные, требующие решения "потом". И эта техника общая, независимо от техники реализации парсера, бо все эти техники все-равно оперируют лишь в подклассах контекстно-свободных грамматик... Т.е. положа руку на сердце — подробности немного фиолетово.


V>>Дык, Пратт его показал в каком-то махровом 70-м году и никто ни кого не послал. Ведь Дракон — лишь одна из мн-ва работ на эту тему, но почему-то стала более популярной... Не насильно же...
WH>Насильно. Ибо в институтах только это направление и дают.

Этот учебник мы не учили, учили другие. Но да, подача материала примерно такая же. Просто для решений "в лоб" особо и учить нечего. Если ты учился на 2201 или 2202, то должен помнить, что алгоритму нисходящего разбора с потенциально бесконечным магазином было уделено менее половины одной лекции, бо там понимать нечего даже идиоту. А ведь на уровне этой "тупизны" работают такие "современные" алгоритмы, как Эрли и его модификации только лишь за счет того фокуса, что глубина любой потенциальной рекурсии не может быть глубже длины входной цепочки при параллельном пошаговом разборе. Ну просто космические технологии, да?

Чему действительно много учили на практиках — это строить автоматы для LL(k)/LR(k) и преобразовывать грамматики из одной в другую. Т.е. если разобраться — учили сугубо практическим вещам... ХЗ почему Влад считает рядом, что это далеко от практики. Это и есть современная практика, на которой написаны многие тонны парсеров.


V>>А теоретических работ по детерминированному парсингу недетерминированных грамматик хватало, от Ахо в т.ч.
WH>Работ по созданию распознавателей на основе языка для генерации.

Еще раз, Ахо серьезно занимался проблемами парсинга неоднозначных грамматик. Собсно, только они проблематику и составляют. Я не изучал его работы особо, но можно попытаться поискать. Возможно, вы пропустили что-то интересное, ХЗ.


WH>БНФ описывает ГЕНРАЦИЮ, а не распознавание.
WH>Тебе не скажется что сама постанвка задачи бредовая?

Договорились, поздравляю. Форма БНФ без побочных эффектов, поэтому поддается аналитическим преобразованиям без нарушения св-в исходной грамматики. Почему так? Потому что является всего-навсего разновидностью записи уравнений редукций для случая контекстно-свободных грамматик, т.е. имеет отображение 1-в-1 на систему редукций после преобразования их к контекстно-свободному виду. А уравнениям редукций вообще до фени, что ими описывается: разбор, генерация, зависимые типы, задача для Пролога или азбука Морзе.

Похоже, вас сбил с толку обычай описывать сначала нетерминалы верхнего уровня в БНФ... но в системе без побочных эффектов, повторю, это абсолютно фиолетово — меняй местами правила как хочешь.

Сравнить теперь с ПЕГ, который не поддается аналитическим преобразованиям, имеет побочные эффекты, является условием задачи для классического динамического программирования, т.е. заведомо не для всех преобразований грамматики возможно доказать их корректность из-за той самой проблемы останова. Т.е. если ограничить ПЕГ только таким подмножеством правил, в которых преобразования доказуемо корректны — то я был еще не против... Иначе это заведомое UB, которое непонятно где может вылезти и у тебя не будет даже найти ответ в гугле при всем твоем желании, бо матаппарата для побочных эффектов не существует. Еще раз повторюсь, что TDOP подрбно не смотрел, но 5 лет назад вы с не меньшим жаром рассказывали про ПЕГ, чем спровоцировали бесполезную потерю времени на знакомство с этим разделом у многих, я уверен.



V>>И там же 100 раз говорилось, что у всех этих "приоритетных" грамматик, в отличие от однозначных,
WH>Это БНФ то одназначная?

Стоп, грамматика самой БНФ? Или описанная с помощью нее?
Однозначность — это св-ва формальной грамматики относительно выбранного способа разбора, независимо от способа ее записи. Предлагаю помедитировать над этой фразой, вместо попыток подмены понятий. А то у тебя выходит, что если на заборе мелком похабное слово нарисовали, то виноват мелок.


WH>Вот ПЕГ однозначный. TDOP тоже.

ПЕГ детерминированный, бо это просто алгоритм. Алгоритм задает грамматику, угу. Отношение м/у алгоритмом разбора и грамматикой 1:1, поэтому грамматика, заданная ПЕГом, не может быть неоднозначной, если разбирать ее этим же алгритмом... Это же сколько каши должно быть в голове, чтобы всерьез утверждать про однозначность ПЕГа и неоднозначность БНФ. Про ПЕГ-грамматику можно лишь сказать, что она контекстно-свободная, больше ничего. Поэтому если тебе удалось записать в ПЕГ некоторую неоднозначную в координатах контекстно-свободного разбора грамматику (например грамматику С++), то ты записал ее с ошибкой.


WH>А БНФ неоднозначная. Да еще и не для этой задачи придумана.

Выделенное больше не пиши никогда. Ну просто чтобы не было столь стыдно, за грамотных, казалось бы, коллег. БНФ получила популярность как "человеческая" запись редукций для случая контекстно-свободных грамматик. Можно сравнить с диаграммами Вирта, в терминах которых, например, описывает свои спецификации IBM. Это все одно и то же.


V>>трудно вывести св-ва грамматики.
WH>Да нахрен эти свойства не упали.
WH>Они нужны теоретикам, ибо без этого работа не будет считать научной.
WH>А практикам они не нужны.
WH>Практикам нужен работающий алгоритм.

Правильно, и когда алгоритм не работает, я могу отбросить хотя бы на часок лень ума и поискать решение через вникание в суть происходящего, благо теории хоть попой кушай. А в случае ПЕГа у нас есть только эксперименты, эвристика и сплошное TDD, которое не факт, что будет достаточно полным, если у меня всего одни мои руки. Не ты ли в соседних форумах поливаешь динамические языки? Но при этом предлагал ПЕГ на динамическом программировании вместо статически-спроектированного парсера, доказанно работающего по исходной грамматике? Разрыв шаблона-с...


V>>И практически невозможно доказать сохранение эквивалентности грамматики во время преобразований (например факторизации), бо упираемся в проблему останова и т.д.
WH>Чего?
WH>Нахрена TDOP'у факторизация?

Угу, а ПЕГу нахрена? (его имел в виду)


V>>Ну и самое главное, существующие ЯП позволяют решать синтаксические неоднозначности на семантическом уровне, что НАДЕЖНЕЕ, чем это:
V>>

V>>Так правило "кто длиннее тот и прав" разрешает чуть менее чем все конфликты.

WH>Тройной фейспалм.
WH>Ты даже не понимаешь, что эту же эвристику используют классические парсеры.
WH>Что? Не знал?

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


WH>А чем ты думаешь лексер занимается?

Думаю, что ты уже третий раз на моей памяти наступаешь на одну и ту же граблю. Не каждый лексер использует жадный алгоритм, и я тебе минимум дважды уже это говорил в разные годы. Это не эвристика никакая, а спецификация "лексемы" в сугубо некоторых языках. Для сравнения в классическом Бейсике или Фортране это вовсе не так, потому что спецификации на лексемы и их отношении с ключевыми словами чуть другие, чем в жабе, С++ или C#. Поэтому Фортран не имеет выделенного лексера, но все-равно парсится не хуже Паскаля.

Короче, про "эвристику в классических парсерах" ты врешь или сам не в курсе, поэтому изобретаешь тут. Неоднозначность возникает только из-за несоответствия техники разбора имеющимся правилам, больше не из-за чего. Например, если у нас выражение можно распарсить LR(k) распознавателем, где K может достигать длины цепочки, то используя LR(1) у нас будут возможные неоднозначности в процессе разбора. Если все варианты неоднозначностей "протянуть" до конца то, если грамматика однозначна в координатах всех контекстно-свободных грамматик и входная цепочка принадлежит грамматике, то обязательно останется только один вариант. Я только что доказал тебе теорему о том, что такая разновидность параллельного LR(1) разбора разбирает все существующие контекстно-свободные грамматики без ограничений. Или это скорее аксиома определения удачного разбора — ХЗ. Называется GLR. О св-вах GLR разбора написано достаточно... Так зачем платить больше?

Здравствуйте, AndrewVK, Вы писали:

AVK>Какие такие? Бывают вещи, которые не описываются вообще грамматикой. Вместо этого есть текстовое описание, как поступать в той или иной конфликтной ситуации.
Это смотря какой грамматикой.

WH>>Вот, например тренарный оператор
WH>>cond is expr = expr : 300 '?'s expr ':'s expr;
AVK>Я точно не помню, но там проблемы не с самим оператором. а с его комбинацией с оператором ??.
Какие именно?

Здравствуйте, WolfHound, Вы писали:

AVK>>Я точно не помню, но там проблемы не с самим оператором. а с его комбинацией с оператором ??.
WH>Какие именно?

Не помню, а искать лень. В стандарте шарпа описано.

Здравствуйте, AndrewVK, Вы писали:

AVK>В моей практике большинство запросов все же можно статически скомпилировать.

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


AVK>Другое дело, что совсем без динамических запросов тоже плохо, поэтому LINQ частенько тоже проблемен.

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

Здравствуйте, oldjackal, Вы писали:

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

Фурсенко аплодирует стоя...

Здравствуйте, vdimas, Вы писали:

AVK>>В моей практике большинство запросов все же можно статически скомпилировать.

V>Наверно, с точностью до параметров

У меня язык строго типизирован и типы параметров обязательны к декларированию. Я ж говорю — это проблема SQL, а не предметной области.

AVK>>Другое дело, что совсем без динамических запросов тоже плохо, поэтому LINQ частенько тоже проблемен.

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

Значит такая задача. У нас написание запросов пользователем не предполагается вообще.

Здравствуйте, Sinclair, Вы писали:


V>>Я не игнорирую, я вижу что ты успел забыть на какие твои вопросы я даю ответы. Ты сделал кое-какие утверждения относительно С? Я не согласился и объяснил — почему. Потому что изкаробки слишком много возможностей, даже без внешних библиотек — из-за CRT и адресной арифметики ф-ий.
S>Сосредоточьтесь. Я вам напомню — мы обсуждаем, годится ли "возможность использовать библиотеки" в качестве критерия DSL. Пока что выходит, что никак не годится.

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

V>>Мы недообсуждали Лого, чтобы делать такие выводы. Я еще не увидел твоего примера целиком. Покажи предположительный синтаксис вызова произвольных внешних ф-ий для "расширенного Лого", а затем я тебе дам небольшой список экспорта, например, NT.DLL, с помощью которого можно уронить любую, самую защищенную программную среду.
S>Непонятно, что вы называете "произвольными внешними функциями". Мы имеем стандартный логовский синтаксис вызова функций/процедур:
S>

S>FORWARD 100
S>LEFT 90
S>

S>Плюс мы имеем стандартный синтаксис объявления функций и процедур:
S>

S>TO CHAIR  REPEAT 4 [FD 100 RT 90]  FD 200  END
S>

S>Плюс мы имеем команду IMPORT, которая втягивает лого-библиотеку, делая видимыми все функции и процедуры, определённые в них.
S>Никакого синтаксиса для загрузки NT.DLL нет.

Вот, ЧТД. Тогда речь не идет о произвольных библиотеках.

S>То есть вы не считаете C++ языком общего назначения? Очень странно.

Я не считаю таковым JS и не согласен приравнивать его к C++. JS ничем не лучше Logo в своей ограниченности, идущей изкаробки. Поэтому на JS можно делать свои DSL, которые заведомо будут specific.

Здравствуйте, vdimas, Вы писали:

V>Сорри, я ваше новое увлечение TDOP подробно еще не смотрел, хватило ПЕГ когда-то.
Это не увлечение. Это один из множества разобранных по косточкам алгоритмов.

V>Но и без этого известно, что любая грамматика без неоднозначностей относительно выбранного способа разбора будет линейна, то бишь ее можно парсить за O(n), в чем был прикол отрывка? Как решаются неоднозначности, которые возникают из-за контекстно-зависимой сути исходной грамматики? Как TDOP разберет угловые скобки в С++ до ответа семантического анализатора — это типы или переменные в области видимости?
Это для драконщины проблема.
А для ДСЛей заточенных на практическое использование нет.
Интегрировать парсер с таблицей символов дело тривиальное.

V>Т.е. это шаблоны или последовательность операций больше/меньше? Неоднозначности грамматик приходится протаскивать в грамматику парсера, где вместо целевых выражений описывать такие промежуточные, требующие решения "потом". И эта техника общая, независимо от техники реализации парсера, бо все эти техники все-равно оперируют лишь в подклассах контекстно-свободных грамматик... Т.е. положа руку на сердце — подробности немного фиолетово.
Очередной фейспалм.
Например мой парсер (даже без интеграции с таблицей символов) захватывает некоторое подмножество контекстно зависимых грамматик.

Ты так веришь в драконщину что ничего другого просто не хочешь видеть.

V>Этот учебник мы не учили, учили другие. Но да, подача материала примерно такая же.
Так я не про конкретную книгу, а про направление.
Просто книга дракона это бренд.
Поэтому все направление и называю драконщиной.

V>А ведь на уровне этой "тупизны" работают такие "современные" алгоритмы, как Эрли
Это просто песец, какой тормоз.
Его просто нельзя использовать для практической работы.

V>Чему действительно много учили на практиках — это строить автоматы для LL(k)/LR(k) и преобразовывать грамматики из одной в другую. Т.е. если разобраться — учили сугубо практическим вещам... ХЗ почему Влад считает рядом, что это далеко от практики. Это и есть современная практика, на которой написаны многие тонны парсеров.
Это плохая практика.
И я тебе по секрету скажу парсеры действительно больших проектов написаны руками. Без всего этого матана.
Вы там со своей драконщиной совсем от реальности оторвались.

V>Сравнить теперь с ПЕГ, который не поддается аналитическим преобразованиям, имеет побочные эффекты, является условием задачи для классического динамического программирования, т.е. заведомо не для всех преобразований грамматики возможно доказать их корректность из-за той самой проблемы останова. Т.е. если ограничить ПЕГ только таким подмножеством правил, в которых преобразования доказуемо корректны — то я был еще не против... Иначе это заведомое UB, которое непонятно где может вылезти и у тебя не будет даже найти ответ в гугле при всем твоем желании, бо матаппарата для побочных эффектов не существует. Еще раз повторюсь, что TDOP подрбно не смотрел, но 5 лет назад вы с не меньшим жаром рассказывали про ПЕГ, чем спровоцировали бесполезную потерю времени на знакомство с этим разделом у многих, я уверен.
Просто песец. Нахрена мне грамматику трансформировать, если она без трансформаций работает?
Просто работает.

V>Однозначность — это св-ва формальной грамматики относительно выбранного способа разбора, независимо от способа ее записи. Предлагаю помедитировать над этой фразой, вместо попыток подмены понятий. А то у тебя выходит, что если на заборе мелком похабное слово нарисовали, то виноват мелок.
Да ты хоть какой алгоритм разбора возьми, БНФ в общем случае неоднозначна.
Те одну строку можно сгенерировать разными способами.

V>Это же сколько каши должно быть в голове, чтобы всерьез утверждать про однозначность ПЕГа и неоднозначность БНФ.
Эта грамматика неоднозначна всегда.

A = a
B = a
C = A | B

Ничиная с нетерминала C эта грамматика порождает только одну строку "a".
Но может сделать это двумя способами.
C -> A -> a
C -> B -> a
И никакой алгоритм разбора тут не поможет
Так что каша в голове у тебя.

V>Про ПЕГ-грамматику можно лишь сказать, что она контекстно-свободная, больше ничего.
ПЕГ может разбирать некоторые КЗ правила.

V> Поэтому если тебе удалось записать в ПЕГ некоторую неоднозначную в координатах контекстно-свободного разбора грамматику (например грамматику С++), то ты записал ее с ошибкой.
Для начала тебе всё же нужно изучить, что же такое ПЕГ.
Ибо ты этого не понимаешь.

V>>>И практически невозможно доказать сохранение эквивалентности грамматики во время преобразований (например факторизации), бо упираемся в проблему останова и т.д.
WH>>Чего?
WH>>Нахрена TDOP'у факторизация?
V>Угу, а ПЕГу нахрена? (его имел в виду)
ПЕГу тоже не нужна. Небольшим допиливанием напильником его можно научить разбирать левую рекурсию.

А TDOP вообще искаропки её поддерживает. А еще приоритеты с ассоциативность.

Я с тебя фигею. В парсерах ничего не понимаешь. Почему альфаканал в картинках не такой как остальные не знаешь. А учить лезешь.

Здравствуйте, AndrewVK, Вы писали:

AVK>Не помню, а искать лень. В стандарте шарпа описано.
Скачал. Не вижу.
Влад говорил что ? : в сочетании с самим собой весьма проблемный. Мой алгоритм распарсил не поперхнувшись.

Здравствуйте, Sinclair, Вы писали:


S>Прикольно. То есть все Expression Trees процессятся статически, во время компиляции?

Именно. А код построения дерева каждого выражения в итоге линейный, без циклов и обхода. Так работает boost::lambda. Характерно, что и само AST зачастую не строится.

Т.е. как таковой интерпретации на этом месте нет — одна статика. Любую динамику в C++, типа рефлекшена дотнета, надо проектировать и реализовывать явно, а это затратно- описывать акцессоры на все мемб.


S>Как-то мне это кажется подозрительным. В какой-то момент всё равно произойдёт потеря информации о конкретном типе, т.е. рано или поздно всё свернётся в некий Predicate*.

Ну... когда-то в компиляторах С++ (не в стандарте!) было ограничение на 256 вложенных шаблонов. Недавно я экспериментировал в MSVC от 2010-й — нет таких ограничений. Сколько памяти хватит, столь глубоким может быть такое статическое AST.


V>>Не факт что в задаче персистить от запуска к запуску надо... Я же говорю — уже пошло слишком много деталей на одного меня.
S>Как правило, неперсистить неинтересно. За один запуск не получается получить так много данных, чтобы запросы по ним имело смысл делать в декларативном виде.

В финансовой области — запросто. Как раз в памяти хранится БД на эффективном мультииндексе. Ну разве что никакой динамической оптимизации запросов — это я фантазировал как бы оно могло быть и какие технологии из уже имеющихся могли бы сэкономить трудоемкость. В реальности статически подобрана структура/граф/индексы под конкретный характер данных конкретной биржи. Важный момент еще в том, что кол-во и характер операций не является заведомо неизвестным (это зачем нужен динамический оптимизатор запросов). Т.е. все структуры данных тюнятся под заведомо-известные алгоритмы их обработки, коих очень счетное кол-во.


S>Тут я могу ошибаться, т.к. вроде бы на дотнете народ рапортовал об эффективности индексов в памяти супротив банального сканирования на объёмах от 16 элементов и выше.

Похоже на результаты моих эксперименты на плюсах, только от вдвое/четверо большего числа элементов. Сканирование в нейтиве дешевле, видать.
Но только если ключ целочисленный, т.е. если лишнее сравнение дешевле косвенной навигации. У меня стандартный двоичный поиск на самописном "плоском" map на 32 элемента немного слил поиску по целочисленному ключу перебором для серий случайных данных. Там же если не сортировать, то операции вставки/удаления совсем дешевые выходят.


S>Да меня количество бинарного кода не очень колышет. SQL Server под свои внутренние структуры отжирает всё равно на порядки больше. Беспокоит в основном количество того кода, который придётся колбасить прикладному программисту. DML у нас изобилует лишними скобками и подчерками (и это мы ещё намеренно завинтили гайки насчёт произвольных выражений, т.к. у нас в качестве аргументов between() могут быть либо мемберы, либо константы).

Ну... В реальности так делают только джидаи. Я не джидай, поэтому boost::lambda не пользую в коммерческих проектах. Обычно оформляю полезный код в виде привычных свободных ф-ий или ф-ий мемберов, а не лямбд, а потом просто делаю карринг через boost::bind. Такая техника на сегодня наиболее популярна. Во-первых декомпозиция, повторное использование + тестирование, начиная с совсем мелких кирпичиков-ф-ий. Во вторых, в обычную ф-ию можно брекпоинт поставить, в случае чего. Ну и карринг тоже неплохое подспорье, экономящее массу рукописного кода. Дальнейший переход на чистые лямбды экономит уже только на синтаксисе объявления ф-ий, что уже не столь принципиально.

Здравствуйте, AndrewVK, Вы писали:


AVK>У меня язык строго типизирован и типы параметров обязательны к декларированию. Я ж говорю — это проблема SQL, а не предметной области.

Ага, тогда я не правильно понял "компиляцию запроса", я думал, что это есть процедура получения готового SQL.

Интересно, а как запрос "ембедится" в исходник? Свой препроцессор C#? Или рядом в другом файле лежит?


AVK>>>Другое дело, что совсем без динамических запросов тоже плохо, поэтому LINQ частенько тоже проблемен.

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

AVK>Значит такая задача. У нас написание запросов пользователем не предполагается вообще.

Ну это да, и это наверно уже обсуждается второй десяток лет... Когда-то кости Парусу в курилках перемыли некисло... Таки не удержусь. У нас ходило мнение в бытность 1С 6-ки, что она, невзирая на свою убогость и тормоза, стала популярной именно из-за того, что в ней сделали более-менее человеческую кастомизацию клиентом. Хотя реальную кастомизацию все-равно не сами клиенты делают, а всякие "партнеры", но шаговая доступность для этого и вообще сам сценарий: пришел представитель "партнера" к клиенту и прямо на месте что-то подкрутил — такой сценарий очень даже юзер-френдли.

Здравствуйте, Sinclair, Вы писали:

V>>>>Ничего такого здесь не подразумевалось. Речь шла про SQL как про DSL который можно сунуть везде и это прокатит.
S>>>Впервые об этом слышу. Кто вам сказал такую глупость? DSL, по определению, нельзя "сунуть везде".
V>> на название топика посмотрите.
S>Посмотрел. Дальше что? Подсказка: "языки общего назначения" и "DSL" — это не синонимы, а антонимы.
Ну т.е. что ЯОН имеют смысл при работе с бд вы согласны?

Здравствуйте, WolfHound, Вы писали:

V>>Но и без этого известно, что любая грамматика без неоднозначностей относительно выбранного способа разбора будет линейна, то бишь ее можно парсить за O(n), в чем был прикол отрывка? Как решаются неоднозначности, которые возникают из-за контекстно-зависимой сути исходной грамматики? Как TDOP разберет угловые скобки в С++ до ответа семантического анализатора — это типы или переменные в области видимости?
WH>Это для драконщины проблема.
WH>А для ДСЛей заточенных на практическое использование нет.
WH>Интегрировать парсер с таблицей символов дело тривиальное.

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


V>>Т.е. это шаблоны или последовательность операций больше/меньше? Неоднозначности грамматик приходится протаскивать в грамматику парсера, где вместо целевых выражений описывать такие промежуточные, требующие решения "потом". И эта техника общая, независимо от техники реализации парсера, бо все эти техники все-равно оперируют лишь в подклассах контекстно-свободных грамматик... Т.е. положа руку на сердце — подробности немного фиолетово.

WH>Очередной фейспалм.
WH>Например мой парсер (даже без интеграции с таблицей символов) захватывает некоторое подмножество контекстно зависимых грамматик.

Какое "некоторое"?

WH>Ты так веришь в драконщину что ничего другого просто не хочешь видеть.

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


V>>А ведь на уровне этой "тупизны" работают такие "современные" алгоритмы, как Эрли
WH>Это просто песец, какой тормоз.
WH>Его просто нельзя использовать для практической работы.

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



V>>Чему действительно много учили на практиках — это строить автоматы для LL(k)/LR(k) и преобразовывать грамматики из одной в другую. Т.е. если разобраться — учили сугубо практическим вещам... ХЗ почему Влад считает рядом, что это далеко от практики. Это и есть современная практика, на которой написаны многие тонны парсеров.
WH>Это плохая практика.
WH>И я тебе по секрету скажу парсеры действительно больших проектов написаны руками. Без всего этого матана.

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


WH>Вы там со своей драконщиной совсем от реальности оторвались.

Ручная писанина не означает отсутствия бумажной стадии. Если LARL(1) или LL(k) кодить ручками, то без бумажной стадии вообще никак. Никакие руки не помогут. А это одни из самых популярных техник. И да, зайди на любой проект по генерации грамматик и посмотри, как часто их используют. Боюсь, твои сведения о ручной писанине парсеров неточны.



WH>Просто песец. Нахрена мне грамматику трансформировать, если она без трансформаций работает?
WH>Просто работает.

Ну мало ли — развиваем постепенно. Сейчас работает, а добавили потом правил — и уже работает не так, как надо. Для известных подклассов грамматик есть известные приемы избавления от рекурсий или неоднозначностей, есть т.н. операции "приведения грамматик" — по очищению их от мусора. Это как рефакторинг в процессе развития, т.е. дело нормальное. Но, если для классики после всех преобразований я спокоен за свою грамматику как слон, т.к. мне гарантировано сохранение исходной семантики, то для случае ПЕГ — ес-но нет.



V>>Однозначность — это св-ва формальной грамматики относительно выбранного способа разбора, независимо от способа ее записи. Предлагаю помедитировать над этой фразой, вместо попыток подмены понятий. А то у тебя выходит, что если на заборе мелком похабное слово нарисовали, то виноват мелок.
WH>Да ты хоть какой алгоритм разбора возьми, БНФ в общем случае неоднозначна.
WH>Те одну строку можно сгенерировать разными способами.

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

Я мог бы предположить чего похлеще, что ты имел ввиду подстроку, которая НЕ разбирается к начальному символу грамматики, хотя разбирается сразу к нескольким вариантам других нетерминалов, не имеющих правила S->N... но это совсем уже в профнепригодности подозревать... Хотя, твой пример ниже доставляет.


V>>Это же сколько каши должно быть в голове, чтобы всерьез утверждать про однозначность ПЕГа и неоднозначность БНФ.
WH>Эта грамматика неоднозначна всегда.
WH>

WH>A = a
WH>B = a
WH>C = A | B
WH>

WH>Ничиная с нетерминала C эта грамматика порождает только одну строку "a".
WH>Но может сделать это двумя способами.
WH>C -> A -> a
WH>C -> B -> a
WH>И никакой алгоритм разбора тут не поможет
WH>Так что каша в голове у тебя.

Нехило подставился, спасибо.

Если ты описал эту грамматику в КС-форме, то я её сразу отношу к регулярным (у которых нет рекурсии в правилах или все рекурсии одного вида), т.е. ты описал исходный недетерминированный автомат регулярной грамматики. Согласно твоего же определения A и B неразличимы. Т.е. в этой регулярной грамматике даже конфликтов нет и она эквивалентна после минимизации такой: S->a.

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

Полегчало?


V>>Про ПЕГ-грамматику можно лишь сказать, что она контекстно-свободная, больше ничего.
WH>ПЕГ может разбирать некоторые КЗ правила.

Без правого контекста в левой части правил? К сожалению, этого недостаточно, т.к. сам "контекст" может быть перехвачен удачно-примененным правилом из подмножества контекстно-свободных, разобрав полный терминал, т.е. закончив цикл разбора. А КЗ-грамматике нужен заход на продолжение разбора с накопленными предыдущими терминалами в ЛЕВОЙ части правила. Т.е. нужен другой верхний алгоритм верхнего уровня, нежели нисходящий для КС-грамматик. Последнее ключевое. Опыты по разбору КЗ-грамматик говорят, что нисходящий их разбор бессмыслен, т.к. редукция правил желательна уже по готовым нетерминалам.



V>> Поэтому если тебе удалось записать в ПЕГ некоторую неоднозначную в координатах контекстно-свободного разбора грамматику (например грамматику С++), то ты записал ее с ошибкой.
WH>Для начала тебе всё же нужно изучить, что же такое ПЕГ.
WH>Ибо ты этого не понимаешь.

Т.е. ты таки изобрел способ парсинга КЗ-грамматик?


V>>>>И практически невозможно доказать сохранение эквивалентности грамматики во время преобразований (например факторизации), бо упираемся в проблему останова и т.д.
WH>>>Чего?
WH>>>Нахрена TDOP'у факторизация?
V>>Угу, а ПЕГу нахрена? (его имел в виду)
WH>ПЕГу тоже не нужна. Небольшим допиливанием напильником его можно научить разбирать левую рекурсию.

WH>А TDOP вообще искаропки её поддерживает. А еще приоритеты с ассоциативность.

WH>Я с тебя фигею. В парсерах ничего не понимаешь.

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

Или вот твои перлы, каждый и которых комментировать устанет рука:

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

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


WH>Почему альфаканал в картинках не такой как остальные не знаешь. А учить лезешь.

Дык, вижу невладение базовыми вещами, сорри. Я не понимаю выражение "альфа канал не такой как остальные". А "остальные" какие? Что за тайна великая раскрыть выбранный способ передискретизации/ресэмплинга изображений? И почему полный игнор вопросов относительно округления цветовой глубины при переходе м/у цветовыми пространствами? А что насчет цветового масштабирования в TV-диапазон для YUV и обратно?

Но это лучше в том же топике продолжить, чтобы не путаться. Мне действительно интересно, бо цветами и изображениями занимался прилично. Потом покажу пару способов в RGB и YUV, а ты попробуешь на них пояснить, где же там "альфа не такая как остальные". Особенно если альфа в телестудиях идет как ключевой канал для управления YUV и передискретизируется в точности так же, как монохромный Y by design. И особенно интересно место DSL в описании адаптивного гребенчатого цветного фильтра или обязательного derainbow filter при преобразовании RGB->YUV. Ты же вроде говорил о быстродействии?

Очепятка, тут везде имелись ввиду нетерминалы:

V>Без правого контекста в левой части правил? К сожалению, этого недостаточно, т.к. сам "контекст" может быть перехвачен удачно-примененным правилом из подмножества контекстно-свободных, разобрав полный терминал, т.е. закончив цикл разбора...

Здравствуйте, vdimas, Вы писали:

Песец. Полный. Даже комментировать тот феерический бред, что ты тут понаписал, не хочу.
Всё равно без толку.

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

Аааааааааа!!!!!!!!!!!!!! Жжжжжжжжееееееесть.

Здравствуйте, Vain, Вы писали:
V>Ну т.е. что ЯОН имеют смысл при работе с бд вы согласны?
С реляционными БД — нет. Пока что я не вижу никаких аргументов в пользу этого утверждения.

Здравствуйте, vdimas, Вы писали:

V>Я-то уже давно. Я говорил про произвольные библиотеки, это ключевое. Если же можно подлючать только ограниченные библиотеки, с тем же уровнем ограничений, что и сам DSL, то ес-но никаких изменений границ этого specific не происходит.
Ок. Хорошо. Ну, то есть для платформы Windows нам достаточно иметь аналоги LoadLibrary и GetProcAddress.

S>>То есть вы не считаете C++ языком общего назначения? Очень странно.

V>Я не считаю таковым JS и не согласен приравнивать его к C++. JS ничем не лучше Logo в своей ограниченности, идущей изкаробки. Поэтому на JS можно делать свои DSL, которые заведомо будут specific.
И всё же в самом С++ нет никаких LoadLibrary и GetProcAddress. Если уж на то пошло, то единственный язык, который вашему критерию не-DSLности удовлетворяет — это C#, в котором можно напрямую размечать импорты.
Всякие прагмы в С++ — это всего лишь хинты линкеру, которые компилятор встраивает в тело .obj — файла.
Если хочется иметь DSL, основанный на C или C++, то можно все эти прагмы проигнорировать или выдать ошибки при линковке. Точно так же, как попытка сделать произвольный CreateObject в JS будет зарезана хостом при желании хозяина хоста.