Здравствуйте, VladD2, Вы писали:
V>>recursice descent в этом смысле — это декомпозиция грамматики на несколько НЕЗАВИСИМЫХ областей. VD>Слушай, не нельзя такой бред нести на публике. "recursice descent" — это алгоритм.
Точно, нельзя.
"recursice descent" — это класс алгоритмов, а не просто алгоритм.
Например, ПЕГ входит в этот класс.
"Комбинаторные парсеры" входят в этот класс.
А так же алгоритмы *LL(*)-разбора.
VD>Лексер работает по регулярной грамматике, которая тупо переписывается в ДКА. Никаких рекурсий в лексере нет! Там тупое чтение по автомату.
Одно плохо — грамматика в лексере строго праворекурсивная или строго леворекурсивная. ))
Заканчивай, кароч, ты не туда пошёл.
Я давал ссылку на LR(0), там можно было бы, чуть включив внимание, увидеть точный алгоритм автоматного лексера, если построить LR(0) для леворекурсивных правил в отсутствии праворекурсивных — ну т.е. по леволинейной регулярной грамматике.
V>>Простой пример: нет смысла парсить вычисления формул в синтаксисе объявлении класса или заголовков методов в C#. А вот внутри тел методов — есть, но зато внутри тел методов нельзя объявлять другие классы, поэтому эта часть грамматики внутри тел методов НЕ нужна. Вот тебе и декомпозиция. VD>Как этой банальностью можно оправдать заявление о том, что "recursice descent" — это не алгоритм, а способ декомпозиции?
Это не надо оправдывать, это объективная реальность.
Парсеры могут вызывать друг друга рекурсивно — в этом суть алгоритма рекурсивного спуска.
Вызываемые парсеры могут работать по разным грамматикам — в этом суть декомпозиции грамматик.
Еще вызываемые парсеры могут быть построены по разным алгоритмам — в этом суть гибридных парсеров, т.е. запросто возможен одновременно нисходящий разбор ("клей верхнего уровня") и восходящий на некоторых ветках.
Что, блин, тут сложного-то?
VD>И вообще зачем парсеру какая-то декомпозиия, когда правила явно ссылаются друг на друга?
Потому что кол-во состояний "единственного табличного автомата" растёт, грубо, в геометрической прогрессии от размера грамматики.
Суть трюка в том, что из грамматики популярных ЯП можно выделить несколько слабо пересекающихся наборов правил, применимых в разных т.н. "контекстах".
VD>Если правило не сослалось на другое, то оно его и не использует.
Верно. Но когда будешь строить единую таблицу пусть для LL(1) некоей большой грамматики, то размер таблицы может оказаться неприлично большим.
Поэтому, можно сделать "каркас" с ручным спуском и вызывать отдельные LL(1) парсеры для разных контекстов.
VD>"recursice descent" — это просто самый быстрый
Заведомо зависит от грамматики и разбираемых данных, потому что с откатами.
VD>и простой для ручной реализации алгоритм парсинга
Конечно простой для ручной реализации, ведь используется просто рекурсивный вызов ф/ий, т.е. стек разбора получается "сам собой".
Разница м/у нисходящим и восходящим разбором — она как м/у обычным и асинхронным кодом, где в последнем случае надо описывать реакцию автомата на события. Неудобно, верно?
Вон, в языки даже вводят конструкции (async/await) для поддержки написания такого событийного кода как бэ в виде "обычного".
Кстате, это ж идея для попробовать описать LR-парсинг на async/await!
Вдруг будет так же удобно? ))
VD>Проблес с ним масса.
Но и бенефиты есть.
LR-парсеры являются "оперативными". В некоторых сценариях это может оказаться решающим.
VD>Но кода ты пишешь парсер руками — это самый логичный выбор.
Здравствуйте, VladD2, Вы писали:
V>>Не надо меня перевирать: VD>Помилуй! Никто и не собирался перевирать. Вот твои исходные утверждения: VD>
VD>Например, в ФП языках некий Т был value-тип (ну вот так компилятор решил), а после заворачивания F(T) всегда получаем ссылочный тип. Итого, храним лишнюю ссылку вместо значения.
VD>Я тебе показал используемый на практике ValueOption в функциональном языке, что полностью опровергает твои утверждения.
Самое смешное тут то, что про ОСaml тебе несколько лет назад говорил именно я, предлагая возможность описывать variant value SomeVariant и даже давал пример мапинга такого описания на потенциальный генерируемый код.
В общем, OCaml — это не чистый ФП. Это гибридный язык, с мутабельностью, ООП и даже unsafe в шаговой доступности, как и Nemerle — тоже гибридный язык.
В общем, я одно время подробно изучал как унутре работают языки из семейства Standard ML и Хаскель — варианты представлены обычными ссылочными типами, над которыми трудится GC.
Ну и, справедливости ради, у тебя не F(T) из исходного утверждения:
По такой формуле: F(T) = T + 1. Здесь + это сумма типов.
Записи — это произведения, суммы — алгебраики.
К тому же, ты малость потерял контекст. Следующее в той же ветке моё сообщение: http://www.rsdn.org/forum/philosophy/6705449.1
более подробно раскрывает мою мысль: можно использовать ссылочные типы как nullable, а для non-nullable ввести ДРУГОЙ тип.
И там же далее по ветке толкается та идея, что для боксированного представления Some и None последний можно представить просто через null. Именно для обоснования такой идеи я напомнил, что в ФП-языках алгебраики почти всегда ссылочные.
В общем, ты вырвал утверждение из контекста.
Оно было не само по себе, а в кач-ве аргумента для описанного решения.
Здравствуйте, WolfHound, Вы писали:
V>>РАЗУМЕЕТСЯ, с произвольно большими диапазонами значений такая реализация ЗТ не справится ни в Хаскеле, ни на шаблонах С++. V>>Но это и так очевидно, не? WH>Очевидно, что это профанация, а не ЗТ.
Ну, хаскелисты утверждают, что такими св-вами обладают лишь языки с ЗТ.
Пирс даёт такой же трюк, описанный в Вики.
Решение условно предполагает, что фантомный тип n будет использоваться для моделирования целочисленного параметра вектора на основе аксиом Пеано
...
В 2012 году было построено[83] расширение языка Haskell, реализующее более развитую систему родо́в и делающее вышеприведённый код корректным кодом на Хаскеле.
V>>Заметь, как я расписал проблему словами для совсем уж нулевой подготовки, т.е. даже школьник-старшеклассник поймет с первого раза. WH>Нет. Ты начал бредить про фильтры.
Да и в чем проблема, если по какой-то конкретной теме кто-то что-то знает (или помнит на ДАННЫЙ момент) с меньшей подробностью?
Если тема интересна — пошел почитал и вот на завтра уже подробности освежил.
Проблема бывает наоборот — когда кто-то отказывается узнавать, как в том споре насчет возможностей трансформации уравнений БНФ и почему описание грамматики в виде ПЕГ этого достоверно не позволяет. Собсно, сам такой декларируемый отказ для целей обсуждения представляет непреодолимую проблему.
V>>Ес-но, первым делом было предположить ошибку в фильтре, тем более обсуждали их. WH>До тебя их не обсуждали.
А что обсуждали?
Без поиска ссылки на то обсуждение можно тупо спекулировать, бо это было лет 10 назад, наверно.
Я точно помню, что обсуждение изначально было не про альфаканалы, т.е. это был твой оффтоп.
_>>Ну вообще то полно IDE и на C++ (тот же QtCreator, VD>Раз! Два то будет?
Да их можно долго перечислять. Я назвал только те, с которыми предпочитал работать сам. А так пожалуйста: KDevelop (по слухам анализатор работает даже лучше голой VS), Code::Blocks (весьма популярна в мире МК), Codelite, Anjuta и т.д. и т.п. )))
_>>да и VS по сути тоже, хотя сейчас уже не целиком, но я пользовался как раз полностью нативной), VD>Ты живешь в плену своих домыслов и фантазий. В реальности VS была нативной только во времена VS 6, но это совсем другой продукт. А VS.NET (первая версия современной студии) уже содержала некоторый объем управляемоего кода.
Некоторый объём там был только ради работы с .net'ом. А так, какие-то реальные изменения в самой IDE там появились вроде только с 2010-ой (кажется переписали интерфейс на wpf). Я сам постоянно пользовался VS по 2005-ую версию. А потом уже ушёл из-за того, что уж слишком убогая она была (естественно речь про применение для C++) в сравнение с конкурентами. Хотя ставил потом бесплатные версии включая 2010-ую, чтобы убедиться, что никакого прорыва нет и всё по прежнему печально. Кстати, оно и до сих пор так. Тут вот коллега на этом форуме совсем недавно показывал дикий скрин с неадекватной реакцией VS на простейшую ошибку. )))
_>>причём они в отличие от указанных Java IDE не имеет слабого, но раздражающего торможения VD>Да? Значит тебя удовлетворят скорость дотнета .
Я пользовался нативной VS и после неё было несколько не комфортно работать с Eclipse и Netbeans. Поэтому переход с последних на QtCreator был прямо как откровение. )
VD>Кстати, многие считают, что IDEA работает быстрее студии. Так что твое утверждение тоже спорно.
IDEA не пользовался, не знаю. Она же для Java в основном, а не для C++. )
_>>А уж если говорить про компиляторы, то вообще смешно — если предложить gcc работать с такими объёмами как в .net, то он будет компилировать молнией. VD>Вылезать из своих иллюзий. Объемы исходников на Шарпе и Явы существенно больше С++-ных. И обрабатываются они за секунды. Так, например, на парсинг 123 мегабайтов исходников библиотек Java парсятся компилятором явы за 4 секунды.
Смешно. ) Ну вот зачем ты пишешь подобную ерунду, хотя прекрасно разбираешься в данном вопросе и знаешь как обстоят дела в реальности. Ты же прекрасно знаешь как работают заголовочные файлы C++, что там даже проект из одного файла в несколько строчек вынуждает парсить половину WindowsSDK (под сотню мегов) + солидный кусок какого-нибудь Boost'а (сотня мегов, но использует обычно не несколько процентов) или вообще жирного монстра типа Qt (полсотни мегов). Причём весь этот процесс повторяется для каждого мелкого исходного файла в проекте. Компиляторы Java и C# давно бы загнулись при таких условиях работы с каждым мелким исходником. )))
VD>Понятие "тормоза менеджед-языков" очень расплывчатое. Эти тормоза они относительные. Относительно идеального кода на С++ такой же идеальный код на Шарпе или Яве будет медленнее. Но это не значит, что кода на GC-языках неприемлемо медленный. Он весьма быстрый. Его хватает для реалтайм-парсинга тех же исходников и для их редактирования в редакторе кода.
А я кстати и не говорил, что GC языки для этого совсем не подходят. ) Я всего лишь отреагировал на твои сомнительные аргументы (типа а где нативные IDE, компиляторы и т.п.). А так я в принципе согласен. Т.е. конечно на C++ было бы быстрее, но если скорости хватает, то зачем напрягаться? )
VD>Зато использование GC-язков позволяет писать более сложный код.
_>>Хотя бы потому, что рантайм языков с GC пишется на языках без GC. ))) А вот обратное уже не верно — в языке с обязательным GC обычно нет возможности нормального использования других механизмов. VD>А какая тут связь с АСТ? Ты предлагаешь написать на С++ аналог GC чтобы соревноваться с GC. Это совершенно правильный подход, но это все требует не малого объема кода и ручного контроля. А в GC-языке мы получаем все тоже самое, но из коробки без единой строчки кода.
Смотри, для большинства задач встроенные средства C++ работы с памятью эффективнее чем GC. Но есть узкая категория задач (скажем где требуется большое число быстродействующих расшаренных ссылок), где GC будет эффективнее. Соответственно мы просто берём соответствующую библиотечку на C++ и получаем полностью аналогичное языкам с GC решение. Никаких проблем, причём все конструкции подхватят это. А вот в случае языков с GC так не получится, потому что даже если мы организуем в таком языке вызов нативного malloc, то всё равно у нас не получится проинтерпретировать его результат скажем как объект.
Вообще, я бы хотел чтобы ты запомнил мою позицию (раз уж мы не в первый раз общаемся на эту тему и подозреваю что будем ещё, возможно даже вне форума): я совершенно не против самой концепции GC или же его наличия в языке. Я против его обязательности.
Да, ну и что касается AST. Я лично созданием компиляторов никогда не занимался, так что я не в курсе какие подходы там оптимальнее всего (если бы стал интересоваться этим вопросом, то в первую очередь глянул бы скажем исходники clang'а). Эффективнее там GC или просто пулы или же достаточно классических подходов C++, не знаю. Но в любом случае я могу элементарно реализовать любой из них в своём приложение. Это и есть ключевой нюанс.
VD>Вот прикинь куча GC — это и есть пул. Только в этом пуле все ссылки контролируются и можно производить дефрагментацию.
Нет, пул — это то, что убивается целиком в нужный момент, а не чистится периодически (с сопровождающими этот процесс классическими "stop the world"). Кстати, для компилятора (с его режимом работы) особой разницы наверное нет. А вот в других местах это вполне принципиальная разница.
VD>А вот если ничего не делать и написать код на С++ в лоб, то получится даже медленее чем на Яве.
Не уверен. Надо смотреть какую модель памяти используют в gcc/clang (я как-то доверяю их профессионализму в данном вопросе)... )
VD>Читай эту страничку, если она тебе душу греет. Но все же ответь на мой вопрос. Почему IDE перестали писать на С++, а имеющиеся переводят на GC-языки? VD>Вот возьми ту же VS. Ей недавно исполнилось 20 лет. Первые её версии были целиком на С++. В версии VS.NET от 2002 года там появились первые куски написанные на C#. По началу их было не много. Но время шло и на сегодня уже большая часть VS написана на C#. VD>Зачем MS переводит VS на C#, если это так плохо, а С++ — это так круто? Почему они переписали на C# компилятор того же C#? Почему даже проектную модель для С++ (в Студии) переписали на GC-языках?
Ну так в случае MS всё очевидно — у них же с давних пор была такая политика, даже OS надеялись переписать на C#. Кстати, сейчас у них вроде новая мода пошла, на JS... И даже IDE соответствующая уже появилась. )))
VD>Почему все новые IDE или плагины пишутся на GC-языках? VD>Где новые IDE на С++?
Новые IDE сейчас пишутся скорее на JS или Python. )))
VD>Вот ты смог назвать только QtCreator. Я его в глаза не видел, но уверен, что его функциональность не сравнима с РеШарпером или КодРашем. А скорость она должна быть достаточной. Вот ты сам того не знаю похвалил IDE в которой большая часть критичного к скорости кода написана на C#.
Не знаю, это уже скорее дело вкуса. Но я вот перепробовал многие IDE и реальной самой удобной из всех стала QtCreator. И я встречал такое мнение не один раз (в том числе и на этом форуме). Она, что называется, сделана для людей. )))
VD>Ответ на эти вопросы просты, но не удовлетворят тебя: VD>1. Потому что разрабатывать на GC-язках проще. VD>2. Потому что скорости предоставляемой GC-языками хватает для решаемых задач.
Так а я вообще то согласен с обоими данными тезисами (ну естественно круг решаемых задач у языков с GC поуже чем у остальных). )
Здравствуйте, vdimas, Вы писали:
V>Ну, хаскелисты утверждают, что такими св-вами обладают лишь языки с ЗТ.
В 2012 году было построено[83] расширение языка Haskell, реализующее более развитую систему родо?в и делающее вышеприведённый код корректным кодом на Хаскеле. Решение состоит в том, что все типы (за определёнными ограничениями) автоматически «продвигаются» (англ. promote) на уровень выше, формируя одноимённые рода?, которые можно использовать явным образом. С этой точки зрения, запись Vec :: * -> Nat -> * не является зависимой — она означает лишь, что второй параметр вектора должен принадлежать к именованному роду Nat, а в данном случае единственным элементом этого рода является одноимённый тип.
Ты даже один абзац текста понять не можешь. Да ещё и фигурно его порезал. И после этого ещё имеешь наглость обвинять меня в нечистоплотности.
Они значения превращают в типы, а тип превращают в род (тип типов).
То же самое делает компилятор С++ для целых чисел.
Короче теорию типов ты не знаешь от слова совсем.
V>Проблема бывает наоборот — когда кто-то отказывается узнавать, как в том споре насчет возможностей трансформации уравнений БНФ и почему описание грамматики в виде ПЕГ этого достоверно не позволяет. Собсно, сам такой декларируемый отказ для целей обсуждения представляет непреодолимую проблему.
Ох. Переписывание грамматик тупо не нужно если алгоритм может её разбирать как есть. Это всё что я говорил тогда и повторю сейчас.
V>Я точно помню, что обсуждение изначально было не про альфаканалы, т.е. это был твой оффтоп.
Нет. Это вы с гапертоном офтопить начали.
Разговор был про генерацию кода. Я показал пример генерации кода для преобразования цветов между различными цветовыми пространствами.
И понеслось...
Гапертон начал учить меня преобразовывать RGB <-> sRGB (нелинейное преобразование) при помощи матриц.
Ты начал утверждать, что каналы независимы после того как я тебе показал, что бывает, когда работать с каналами независимо ты начал петь про фильтры.
В общем тогда вы оба неслабо обделались.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Довольно глупо работать на уровне АПИ ОС. К тому же есть другие методы описания этих самых АПИ.
Конечно кроссплатформенные библиотечные обёртки вокруг системного API — это верный подход. Только вот эти библиотеки тоже кто-то должен писать и соответственно у их авторов должен быть механизм для вызова системного API (без него же реально никак). Причём этот механизм не должен ни ухудшать производительность, ни ограничивать функциональность.
VD>Я вот только вчера использовал 4 функции из WinAPI.
Посмотрел на код ниже — это конечно же дикий ужас... Но если такое пишется один раз (для данной ОС), то в принципе не так уж страшно. При условии что там не вносятся дополнительные накладные расходы (а вот это уже не про .net).
VD>Самого C API — да. Описания в виде сишных хэадеров — нет.
Ну вот в .net можно увидеть например подготовленный набор функций (вроде как обёртки) для работы с отображаемыми в память файлами. Ты видел какая там ересь и насколько это дико неудобно в сравнение с использованием даже голого winapi? )
VD>С++-ные же типы и хеадеры вообще не нужны в современном языке. Они слишком частны и мало применимы в других языках.
Только вот почему-то практически для каждого серьёзного языка построен биндинг для Qt (а это огромный объём написанных руками обёрток). )))
Здравствуйте, WolfHound, Вы писали:
WH>Ты только что утверждал, что так делать нельзя.
Независимо от моих утверждений у коллеги будет использована именно такая схема, к тому же есть уже тонны кода, завязанные на такую схему.
В итоге, я мог предложить лишь ужать структуру в памяти, сохраняя исходную семантику и публичное АПИ, чтобы не пришлось сильно переписывать зависимый код.
Здравствуйте, WolfHound, Вы писали:
WH>Исключительно во время восстановления. Там Эрли улетает в O(N^2) при этом порождая экспоненциально большой лес деревьев разбора. Как чинить в принципе ясно. Но пока не чинил.
Эрли, вообще-то O(n3) в худшем случае. А при восстановлении этот худший случай мы сами и организуем.
Ты, кстати, разобрался с тем, что в АНТЛР 4 сделано? Там очень похожая на Эрли ситема применяется, а от тормозов спасает то, что он там прямо в онлайн строит НКА и переводит его в ДКА. И за счет этого ДКА отбрасывает большинство альертнатив. За счет этого же у него и восстановление после ошибок упрощается.
Как я понимаю идея строить ДКА-предсказатель в чем-то схожа с идеей делать левую факторизацию для текущих альтернатив. Получается один путь (для однозначной грамматики), который можно пройти очень быстро просто потому он один. Ну, и для восстановления — это просто песня. Вместо перебора 100500 вариантов можно перебирать только те где есть возможность восстановления.
WH>Основной парсер строго линейный на всех поддерживаемых грамматиках.
Линейный не значит одинаково быстрый. Всегда есть зависимость от размера грамматики/числа подправил/числа альтернатив. И наш парсер не исключение. Например, JSON у нас быстрее разбирается чем C# (кстати, в АНТЛР-е все наоборот, почему-то).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ты, кстати, разобрался с тем, что в АНТЛР 4 сделано? Там очень похожая на Эрли ситема применяется, а от тормозов спасает то, что он там прямо в онлайн строит НКА и переводит его в ДКА. И за счет этого ДКА отбрасывает большинство альертнатив. За счет этого же у него и восстановление после ошибок упрощается.
Там в отличии от LL(k) парсеров предсказание ветвления строится динамически.
Делается это всё исключительно из-за того, что нельзя в общем случае построить предсказатель перехода статически. А во время исполнения у нас всегда конечное множество префиксов из которого всегда можно сделать ДКА.
Ничего общего с Эрли оно не имеет. Ибо Эрли вообще не использует предсказание, а тупо парсит все альтернативы одновременно.
VD>Как я понимаю идея строить ДКА-предсказатель в чем-то схожа с идеей делать левую факторизацию для текущих альтернатив. Получается один путь (для однозначной грамматики), который можно пройти очень быстро просто потому он один. Ну, и для восстановления — это просто песня. Вместо перебора 100500 вариантов можно перебирать только те где есть возможность восстановления.
Главная проблема с восстановлением — это понять какой текст нужно выкинуть и какой терминал придумать. Как тут поможет предсказатель ветвления не понимаю.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
V>>Ну, хаскелисты утверждают, что такими св-вами обладают лишь языки с ЗТ. WH>
WH>В 2012 году было построено[83] расширение языка Haskell, реализующее более развитую систему родо?в и делающее вышеприведённый код корректным кодом на Хаскеле. Решение состоит в том, что все типы (за определёнными ограничениями) автоматически «продвигаются» (англ. promote) на уровень выше, формируя одноимённые рода?, которые можно использовать явным образом. С этой точки зрения, запись Vec :: * -> Nat -> * не является зависимой — она означает лишь, что второй параметр вектора должен принадлежать к именованному роду Nat, а в данном случае единственным элементом этого рода является одноимённый тип.
WH>Ты даже один абзац текста понять не можешь. Да ещё и фигурно его порезал. И после этого ещё имеешь наглость обвинять меня в нечистоплотности.
Мде...
Пока что очевидно только то, что ты так и не понял работу этого трюка. ))
Ну конечно, в системе типов Хаскеля зависимых типов нет.
Но зато в Хаскеле есть зависимость типов от типов.
На этой зависимости с помощью арифметики Пеано и такой-то матери представляются натуральные числа.
Вот D.Mon тоже (зачем-то) упомянул этот трюк:
F(F(F(T))) = T + 3
В частности, если T = 1, то F(F(T)) = 1 + 1 + 1 = 3, т.е. тип с тремя разными возможными значениями. Так из Option можно натуральные числа делать.
С помощью этого трюка они на Хаскеле решают именно такие задачи, которые можно решать только на языках с ЗТ:
Но обычно такой выразительностью обладают лишь системы с зависимыми типами, реализованные в таких языках, как Agda, Coq и др.
Например, на стандартном ML такое не выразить.
Вот как раз самый простой пример — длину вектора проверять НЕ надо, бо она зашита в тип.
Т.е. тип вектора зависит от его длины, но в рантайме работает один и тот же код, независимо от длины вектора.
WH>Они значения превращают в типы, а тип превращают в род (тип типов).
Сама программа строится так, что по мере добавления элементов в вектор его тип меняется.
WH>То же самое делает компилятор С++ для целых чисел.
Компилятор С++ для рантайма должен будет сгенерить код для каждого инстанса типа из шаблона.
Однако, когда компилятор встречает неограниченную генерацию для рантайма из шаблонного кода, он ругается и отказывается работать.
В случае Хаскеля ограничение на "длину" типа будет зависеть только от входных данных в рантайме.
В случае аналогичного трюка для вычислений времени компиляции на шаблонах С++ — от неких поданных и закодированных в кач-ве параметра шаблона эдаких "внешних" (по отношению к шаблону) данных.
WH>Короче теорию типов ты не знаешь от слова совсем.
Уже ломашься как девочка. ))
В стандартном ML система типов на лямбда кубе — это термы, зависимые от типов и типы, зависимые от типов.
Так вот. Допиливание системы типов Хаскеля позволило организовывать типы в счётные м-но внутри эдаких "родов".
И "пересчитывать" их. Вот так: раз, два, три, четыре...
Кароч, я так думаю, что ты хотя бы приблизительно понял о чем речь, а если напряжешься хотя бы минут на 15 поймёшь окончательно.
Ну или комедию ломаешь, бо стыдно. Потому что я тебе все это пытался было показать еще хрен его знает сколько лет назад, но ты настолько был от всей этой темы далёк... там у тебя в понимании было настолько всё печально, что сие было совершенно бесперспективно...
Считай, вот только сейчас у тебя появились первые слабые проблески насчёт того, о чем шла речь. ))
V>>Я точно помню, что обсуждение изначально было не про альфаканалы, т.е. это был твой оффтоп. WH>Нет. Это вы с гапертоном офтопить начали. WH>Разговор был про генерацию кода. Я показал пример генерации кода для преобразования цветов между различными цветовыми пространствами. WH>И понеслось...
Так тем более пофик на альфу, если кодогенерация.
WH>Гапертон начал учить меня преобразовывать RGB <-> sRGB (нелинейное преобразование) при помощи матриц. WH>Ты начал утверждать, что каналы независимы после того как я тебе показал, что бывает, когда работать с каналами независимо ты начал петь про фильтры.
Так ты нашел тот топик или нет?
WH>В общем тогда вы оба неслабо обделались.
Обделался тот, кто включил неадеквата, ес-но.
Это всё было вовсе не рокет саенс, а скорее ровно наоборот.
Сформулировал бы ты свой аргумент членораздельно — сходу получил бы от меня плюсик.
Перидически я тебя плюсую, если заметил...
Здравствуйте, vdimas, Вы писали:
V>Мде... V>Пока что очевидно только то, что ты так и не понял работу этого трюка. ))
Ох.
Это я показал тебе этот трюк. До этого ты не понимал, что числа в шаблонах С++ это не числа, а типы.
Даже по твоей ссылке написано, что "не является зависимой". Я это даже выделил.
Но ты продолжаешь это твердить.
V>Ну конечно, в системе типов Хаскеля зависимых типов нет. V>Но зато в Хаскеле есть зависимость типов от типов. V>На этой зависимости с помощью арифметики Пеано и такой-то матери представляются натуральные числа.
Ох. Зависимый тип — это такой тип, который зависит от значений времени исполнения.
V>Вот D.Mon тоже (зачем-то) упомянул этот трюк: V>
V>F(F(F(T))) = T + 3
V>В частности, если T = 1, то F(F(T)) = 1 + 1 + 1 = 3, т.е. тип с тремя разными возможными значениями. Так из Option можно натуральные числа делать.
Да ты вообще не понял, что тут написано. К данному разговору это вообще отношения не имеет.
V>С помощью этого трюка они на Хаскеле решают именно такие задачи, которые можно решать только на языках с ЗТ: V>
V>Но обычно такой выразительностью обладают лишь системы с зависимыми типами, реализованные в таких языках, как Agda, Coq и др.
V>Например, на стандартном ML такое не выразить.
Ты даже не понял к чему эта фраза. А она вот к этому:
Решение условно предполагает, что фантомный тип n будет использоваться для моделирования целочисленного параметра вектора на основе аксиом Пеано — то есть будут строиться только такие выражения, как Succ Zero, Succ Succ Zero, Succ Succ Succ Zero и т. д. Однако, хотя определения записаны на языке типов, сами по себе они сформулированы бестиповым образом. Это видно по сигнатуре Vec :: * -> * -> *, означающей, что конкретные типы, передаваемые в качестве параметров, принадлежат роду *, а значит, могут быть любым конкретным типом. Иначе говоря, здесь не запрещаются бессмысленные ти?повые выражения вроде Succ Bool или Vec Zero Int.[83]
Всё что делает это расширение это запрещает писать Succ Bool, Vec Zero Int и подобные бессмысленные типы. Всё.
V>Вот как раз самый простой пример — длину вектора проверять НЕ надо, бо она зашита в тип. V>Т.е. тип вектора зависит от его длины, но в рантайме работает один и тот же код, независимо от длины вектора.
Ох. Ну попробуй прочитать длину вектора из консоли. И создай вектор этой длинны.
Ты не сможешь. Ибо данное расширение не добавляет в язык зависимые типы.
WH>>Они значения превращают в типы, а тип превращают в род (тип типов). V>Сама программа строится так, что по мере добавления элементов в вектор его тип меняется.
Но она всё равно не зависит от значений времени исполнения.
Ты можешь зять вектор длинны N и получить вектор длинны N + 1. Но только при условии, что N известно на этапе компиляции.
WH>>То же самое делает компилятор С++ для целых чисел. V>Компилятор С++ для рантайма должен будет сгенерить код для каждого инстанса типа из шаблона. V>Однако, когда компилятор встречает неограниченную генерацию для рантайма из шаблонного кода, он ругается и отказывается работать.
Так и у хаскеля тоже количество вариантов ограничено статически.
V>В случае Хаскеля ограничение на "длину" типа будет зависеть только от входных данных в рантайме.
Бред полный. Покажи мне код на хаскеле который это делает.
Вот код на Dafny я показать могу. А на хаскеле ты это не сделаешь.
Ибо нет там зависимых типов.
V>В стандартном ML система типов на лямбда кубе — это термы, зависимые от типов и типы, зависимые от типов.
А зависимые типы — это типы которые зависят от термов.
Все остальные типы зависимыми не являются. Просто по определению. А что ты там себе нафантазировал никому не интересно.
method SelectionSortRange(a : array<int>, begin : int, end : int)
requires 0 <= begin <= end <= a.Length;
Вот это код на Dafny.
Множество значений, которое может принимать begin зависит от значения end и размера массива.
Множество значений, которое может принимать end зависит от значения begin и размера массива.
Именно зависимость от значений времени исполнения делает типы begin и end зависимыми.
Синтаксически зависимость прописана не в типе, а рядом просто по тому что так нагляднее и понятнее человеку.
V>Так вот. Допиливание системы типов Хаскеля позволило организовывать типы в счётные м-но внутри эдаких "родов". V>И "пересчитывать" их. Вот так: раз, два, три, четыре...
Отношение между родом и типом такое же как между типом и термом.
Тип — это именованное множество термов.
Род — это именованное множество типов.
Сорт — это именованное множество родов.
И так далее до бесконечности.
V>Кароч, я так думаю, что ты хотя бы приблизительно понял о чем речь, а если напряжешься хотя бы минут на 15 поймёшь окончательно.
Я всё точно понял и уже давно. А ты так до сих пор ничего и не понял.
WH>>Нет. Это вы с гапертоном офтопить начали. WH>>Разговор был про генерацию кода. Я показал пример генерации кода для преобразования цветов между различными цветовыми пространствами. WH>>И понеслось... V>Так тем более пофик на альфу, если кодогенерация.
Так зачем вы с гапертоном начали меня учить? Причем тому что не имеет отношения к реальности?
V>Обделался тот, кто включил неадеквата, ес-но.
То есть вы с гапертоном.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, vdimas, Вы писали:
V>Ну и какие проблемы, делаем так: V>[cs]
... V>ClanInfo GetClanInfo(int clan_id) {}
V>class PlayerInfo { V> ClanId clanId; V> ... V>}
... V>У вас на прямо сейчас примерно так же и выглядит. Потому что публичный интерфейс у struct ClanId и struct Optional<int> идентичный (я ориентировался на Nullabl<int>, бо вашего Optional в глаза не видел, но не суть).
Моя проблема по-прежнему в том, что опциональность ClanId в данном коде никак не отражена. Optional<int> или int? кричат об опциональности, а от ClanId подвоха не ждешь.
V>Для простых int это экономия вдвое. V>И для игр экономия памяти и эффективная её разметка — это первое дело. V>Просто у вас объектов в играх, похоже, немного или активность объектов низкая, поэтому вы не паритесь.
Для ядра это верно, ну а для игровой логики... Даже в стратегиях суммарное количество юнитов редко превышает несколько тысяч, ну и несколько опциональных полей дадут оверхед в десятки килобайт, что при футпринте в гигабайты есть экономия на спичках.
V>Утилитный код по ссылке можно организовать в виде методов-расширений для INullable<T>.
К сожалению, нельзя. Extension методы для generic интерфейсов c AOT-компиляцией нормально не работают.
Остальное возражений не вызывает, да и тема себя, кажется, исчерпала. Спасибо за беседу и поводы для размышлений.
Здравствуйте, vdimas, Вы писали:
V>Точно, нельзя. V>"recursice descent" — это класс алгоритмов, а не просто алгоритм.
Пипец у тебя каша в голове. Ознакомься, плиз, с общепринятой терминологией. Метод рекурсивного спуска
алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.
recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the productions of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.
PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.
V>"Комбинаторные парсеры" входят в этот класс.
Ты очередной раз говоришь ерунду.
Рекурсивный спуск, Пакрат, LR(k), LALR(k), GLR, GLL, TDOP (Top Down Operator Precedence) — это алгритмы.
Комбинаторные парсеры могут использовать разные алгоритмы. Так в них можно использовать рекурсивный спуск, Пакрат, TDOP или даже их смесь. По сути нитровский парсер — это смесь всех этих алгоритмов обладающая расширяемостью кобминаторных парсеров.
V>А так же алгоритмы *LL(*)-разбора.
LL — это действительно класс грамматик задающий класс грамматик которые можно разобрать нисходящим парсером (делающим левое порождение, Leftmost derivation). Что означает "*" спереди я не знаю. В скобках у LL(k) задается глубина заглядывания вперед. "*" в этом случае означает "неограниченный". LL(*) описывает однозначные контекстно-свободные грамматики не имеющие левой рекурсии.
Соответственно LR(k) описывает классы грамматик разбираемые восходящим анализом (делающим правый вывод).
При этом LR(k) и LL(m) эквивалентны (т.е. их можно преобразовать один в другой, возможно с изменением глубины заглядывания).
PEG же описывает более широкий класс грамматик включающий часть контекстно-зависимых грамматик.
К алогритмам все это имеет опосредованное отношение. Так и LL- и LR-грамматики могут разбираться автоматными парсерами. Хотя обычно LL-грамматики разбираются алгоритмами основанными на рекурсивном спуске.
Ну, а класс грамматик тут сильно зависит от того делают ли парсеры попытки анализа разных альтернатив. Те что делают называются недетерминированными и обобщенными. Те что — нет, называются детерминированными. Естесвенно, что первые разбирают более широкий класс грамматик и допускают более вольную запись грамматики.
До сих пор не понимаю зачем мне нужно работать Камитаном Очевидность, ведь все это написано в Википедии и любом учебнике.
Но раз ты намешал все в кашу, приходится писать банальности.
Так что запомни раз и на всегда "recursive descent" — это тип парсера. LL(1) — это класс грамматики которую им можно разобрать при односильмвольном заглядывании вперед и без откатов. С точки зрения класса грамматики LL(1) эквивалентен LALR(1) и SLR(1), если в LL(1) нет пустых правил.
Так что с помощью рекурсивного списка можно парсить и грамматики LR(k), и даже полное множество контекстно свободных грамматик (вопрос только в том, что при этом легко уйти в экспоненту). Ну, а делая контекстные проверки и передавая параметры можно парсить и контекстно-зависимые правила. Например, банальная передача параметром префикс позволит парсить аналогичны суффикс, что является контекстно-зависимой операцией.
VD>>Лексер работает по регулярной грамматике, которая тупо переписывается в ДКА. Никаких рекурсий в лексере нет! Там тупое чтение по автомату.
V>Одно плохо — грамматика в лексере строго праворекурсивная или строго леворекурсивная. ))
Грамматика там регулярная. Грубо говоря рекурсия ограничивается циклами. Потому для них и можно организовать крайне эффективный парсинг. Они тупо переписываются в ДКА без всяких стеков и внешних хранилищ. Эффективнее кода сгенерированного по ДКА не может быть ничего. Потому Вольфхаунд и смеется над твоими заявлениями о том, что GLR может быть столь же эффективен как и лексер.
V>Заканчивай, кароч, ты не туда пошёл.
Ты оспариваешь прописные истины. Пока ты не перестанешь это делать разговаривать с тобой не о чем.
V>Я давал ссылку на LR(0), там можно было бы, чуть включив внимание, увидеть точный алгоритм автоматного лексера, если построить LR(0) для леворекурсивных правил в отсутствии праворекурсивных — ну т.е. по леволинейной регулярной грамматике.
Ты говоришь глупости. Глупости неимоверные.
1. Если речь идет о парсерах а не классах грамматик, то для реализации LR(k) требуется автоматный парсер с магазинной памятью. Он уже по определению не может быть такой же эффективный как автоматный парсер для регулярного языка.
2. GLR не эквивалентен LR(k), так как LR(k) описывает детерминированные парсеры, а GLR не детерминированные. GLR требует, кроме магазинной памяти для каждого подпереться, хранить еще лес стеков/состояний подпарсеров. Даже будучи супероптимизировнным он будет не столь эффективне чем просто LR(k).
Твои рассуждения из серии "там и там канечные автоматы, значит они будут работать с одинаковой скоростью" — полезнейшее дилетантство. Не могут они работать эквивалентно по определен. Алгоритмы разные. Им надо учитывать разные нюансы. Даже на идеальной грамматике они будут показывать разное время. А грамматика реального языка вряд ли будет идеальной, так что особенности алгоритмов проявятся как бы ты этого не хотел. Ну, и имея идельную LR(k)-грамматику попросту не нужен GLR, а имея регулярную грамматику не нужен и LR(0).
V>>>Простой пример: нет смысла парсить вычисления формул в синтаксисе объявлении класса или заголовков методов в C#. А вот внутри тел методов — есть, но зато внутри тел методов нельзя объявлять другие классы, поэтому эта часть грамматики внутри тел методов НЕ нужна. Вот тебе и декомпозиция. VD>>Как этой банальностью можно оправдать заявление о том, что "recursive descent" — это не алгоритм, а способ декомпозиции?
V>Это не надо оправдывать, это объективная реальность.
Это бред. Просто бред. "recursive descent" — это алгоритм, чтобы ты не говорил. Тот кто заявляет бортное просто невежда.
А декомпозиция может быть произведена в любом виде парсеров, грамматик и алгоритмов. Я видел и модульные GLR. Никаких проблем с декомпозицией там нет.
Этой проблемы вообще не существует. Ты что-то там придумал.
V>Парсеры могут вызывать друг друга рекурсивно — в этом суть алгоритма рекурсивного спуска.
Гениально, о великий КО. Причем тут декомпозиция и как факт рекурсивного вызова устраняет тот факт, что "recursive descent" — это алгоритм?
Ну, что ты упрямится? Я же тебе прямые ссылки на определения даю. И в гугле тебя вроде не забанили.
V>Вызываемые парсеры могут работать по разным грамматикам — в этом суть декомпозиции грамматик.
Ты бредишь. В рекурсивном спуске "вызываемый парсер" и определяет правило грамматики.
Возможно ты пытаешься сказать, что функцию можно подменять в рантайме или в во время компиляции. Но ничто не мешает это делать и в других алгоритмах.
V>Еще вызываемые парсеры могут быть построены по разным алгоритмам — в этом суть гибридных парсеров, т.е. запросто возможен одновременно нисходящий разбор ("клей верхнего уровня") и восходящий на некоторых ветках.
Могут. Но recursive descent это конкретный алгоритм. Ты же скорее говоришь о том, что можно создавать парсеры из комбинаторов каждый из которых использует разные алгоритмы.
Мы в Нитре так и делаем. У нас для парсинга выражений используется TDOP (Top Down Operator Precedence) придуманный Pratt-ом. А базовая часть — это Пакрат. Вот Пакрат основан на рекурсивном спуске, но с откатами.
V>Что, блин, тут сложного-то?
Не знаю, но ты почему-то плаваешь в терминологии и занимаешься выдумками.
Путаешь алгоритм и классы грамматик. Восходящие алгоритмы так же комбинируются. Их можно комбинировать и с нисходящими. И алгоритмов много. Одни используют другие, и т.е.
VD>>И вообще зачем парсеру какая-то декомпозиия, когда правила явно ссылаются друг на друга?
V>Потому что кол-во состояний "единственного табличного автомата" растёт, грубо, в геометрической прогрессии от размера грамматики.
Ты перемешал все в кучу. У тебя каша в голове. Для декомпозиции грамматик вообще не важно какие там алгоритмы используются для парсинга. Декомпозицию проводят на базе формализмов. Вынес правила в отдельный модуль — вот тебе и декомпозиция.
Автоматы тоже можно комбинировать.
V>Суть трюка в том, что из грамматики популярных ЯП можно выделить несколько слабо пересекающихся наборов правил, применимых в разных т.н. "контекстах".
Это можно сделать для любого типа парсеров и любых алгоритмов! Это от них вообще не на зависит.
Или ты говоришь о динамическом подключении правил?
V>Верно. Но когда будешь строить единую таблицу пусть для LL(1) некоей большой грамматики, то размер таблицы может оказаться неприлично большим.
Да по фигу. У парсера вообще может не быть таблиц. И никто не мешает строить отдельные таблицы для несвязанных правил.
Я даже не хочу обсуждать детали реализации автоматных парсеров. Это к делу отношения не имеет. И уж с recursive descent — это никак не связано.
V>Поэтому, можно сделать "каркас" с ручным спуском и вызывать отдельные LL(1) парсеры для разных контекстов.
Набор бессмысленных слов. Весть твой "каркас" будет точно таким же LL(1)-парсером, а каждый твой LL(1)-парсер будет рекурсивным парсером.
VD>>"recursice descent" — это просто самый быстрый
V>Заведомо зависит от грамматики и разбираемых данных, потому что с откатами.
"recursive descent" — это конкретный алгоритм. Откатов он не предусматривает. С откатами это уже будет другой алгоритм. Для разбора LL(1)-грамматик достаточно recursive descent-парсера без откатов.
Если тебе надо разбирать более широкий класс грамматик, то ты можешь использовать LL(k), LL(*), ALL(*) (из АНТЛР 4) или Пакрат. Первые подразумевают ДКА предсказания. Пакрат использует мемоизацию. ALL(*) — это гибрид LL(*) с динамическим построением предсказания и элементами GLL для хранения разных путей обхода.
Собственно любой компьютерный язык парсится рукописным recursive descent-парсером при условии, что грамматика имеет праворекурсивную форму и для нее проведена левая факторизация. Именно так пишутся рукописные парсеры. Быстрее этого способа не существует. Все остальные извращения нужны для того, чтобы парсить неоднозначные грамматики и однозначные не факторизованные грамматики записанные в свободной форме.
V>Разница м/у нисходящим и восходящим разбором — она как м/у обычным и асинхронным кодом, где в последнем случае надо описывать реакцию автомата на события. Неудобно, верно?
Не то слово. Но автоматные пареры руками не пишут.
V>Кстате, это ж идея для попробовать описать LR-парсинг на async/await!
Глупая идея, так как там основная проблема не реакция на событие, а организация таблицы перехода и ее интерпретация.
V>LR-парсеры являются "оперативными". В некоторых сценариях это может оказаться решающим.
Что ты понимаешь под "оперативными". Чую очередную вольную интерпретацию терминологии.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Кстате, я бы, таки, был не против услышать подробности происходящего для случая Plus(None, None).
Для приведенной функции будет MatchFailurException. Эта функция чисто демонстративная. Там даже ошибки в написании типов есть . При компиляции такой функции будет выдано предупреждение:
warning : matching is not exhaustive, example unmatched value: (None, None)
Для варианта с ValueOption предупреждение будет:
warning : matching is not exhaustive, example unmatched value: (HasValue = (false, false))
Если добавить недостоющее вхождение:
def Plus(x : ValueOption[int], y : ValueOption[int])
{
| (VSome(x), VNone) => x
| (VNone, VSome(y)) => y
| (VSome(x), VSome(y)) => x + y
| (VNone, VNone) => -1
}
WriteLine(Plus(VNone(), VNone()));
Сработает оно и будет выведено "-1".
Все как с обычными вариантами.
Кстати, в Немерле тоже самое можно и на классах реализовать. В Немерле паттерн-матчинг одинаково хорошо работает как с вариантами, так и с любыми другими типами. Разве что синтаксис по пушистее может оказаться. Но он может быть упрощен как показано выше.
Кстати, я тут пока с тобой общался немного подумал и допилил напильником макро-оператор ??. Теперь он поддерживает не конкретные типы, а в том числе любой тип реализующий идиому HasValue/Value. Так что оператор ?? теперь можно использовать для ValueOption:
Здравствуйте, meadow_meal, Вы писали:
_>Моя проблема по-прежнему в том, что опциональность ClanId в данном коде никак не отражена. Optional<int> или int? кричат об опциональности, а от ClanId подвоха не ждешь.
Ну, можно обобщить:
interface IVoidable {
IsVoid { get; }
}
struct Voidable<T> where T : IVoidable<T> {
T Value { get { if(HasValue) return _value; /*else*/throw ... }
set { _value = value;} }
bool HasValue { get { return !_value.IsVoid; }
}
// автогенерённоеstruct ClanId : IVoidable<ClanId> {
int _value;
public ClanId(int v) { _value = v; }
public bool IsVoid { return _value == 0; }
public int ToInt32() { return _value; }
public static ClanId VoidValue { get { return ClanId(0); } }
}
...
// используемstruct PlayerPDU {
// достаточно кричаще? ))public Voidable<ClanId> clanId;
...
}
Итого, ClanId — самодостаточный примитивный тип. Реализован как бокс над int для реализации нужного интерфейса.
_>Для ядра это верно, ну а для игровой логики... Даже в стратегиях суммарное количество юнитов редко превышает несколько тысяч, ну и несколько опциональных полей дадут оверхед в десятки килобайт,
А как ты считал? По одному Optional на юнит?
А в сцене могут помимо юнитов дохрена других объектов с nullable-полями?
ИМХО, их может быть десятки тысяч в кадре в современной игре.
_>что при футпринте в гигабайты есть экономия на спичках.
А что в игре занимает гигабайты? (интересуюсь)
В основном графические ресурсы?
V>>Утилитный код по ссылке можно организовать в виде методов-расширений для INullable<T>. _>К сожалению, нельзя. Extension методы для generic интерфейсов c AOT-компиляцией нормально не работают.
Здравствуйте, WolfHound, Вы писали:
WH>Теперь если у нас есть обобщённый код который работает с хештаблицей и в него передадут Hashtable<int, Option<string>> то без этой фичи код не будет знать есть элемент или в таблице лежит None. WH>Из-за этого алгоритм может сломаться.
всё так, но только подобную семантику нужно выражать явно, а для этого просто нужен тип, который явно хранит информацию об ошибке, а-ля предлагаемого для C++ std::expected, и в случае ошибки строить логику вокруг именно инстанса ошибки, а не вокруг нагруженного лишними смыслами optional
Здравствуйте, VladD2, Вы писали:
VD>алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.
Это самое общее описание, которое подходит под целый класс алгоритмов.
"Комбинаторные парсеры" подходят под это определение?
А генерируемые ANTLR анализаторы для LL(k) грамматик подходят под это определение?
Например, LL(k)-парсер может работать по интерпретируемой таблице, т.е. обслуживать выделенную сущность-стек самостоятельно, но может работать и без таблицы, т.е. "напрямую", используя естественный стек взаимных вызовов ф-ий. Говорят, так эффективней. ANTLR генерит именно такой вариант для LL(k).
Аналогия: можно сделать лексер, интерпретирующий таблицу переходов ДКА, но можно обойтись и без таблицы переходов в явном виде, "зашив" сами эти переходы прямо в код через goto.
Что здесь "алгоритм", а что "способ реализации"?
Следуя твоей логике, "трюк перехода по goto" — это и есть "алгоритм".
А по моей логике, алгоритмом является эмуляция эквивалентного ДКА и ходьба по его состояниям.
VD>ПЕГ — это вообще не алгоритм: VD>PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.
ОК, принимается.
Вы тут рассматривали вполне конкретный алгоритм Packrat всвязи с ПЕГ, замени на Packrat в моём посте и ву а ля — в исходном виде алгоритм Packrat представлен как вызывающие друг друга процедуры парсинга.
V>>"Комбинаторные парсеры" входят в этот класс. VD>Ты очередной раз говоришь ерунду.
Я очередной раз не люблю слабовольных, которые не в состоянии собой владеть.
VD>Рекурсивный спуск, Пакрат, LR(k), LALR(k), GLR, GLL, TDOP (Top Down Operator Precedence) — это алгритмы.
А чего ж LL(k) забыл? )))
Еще раз, медленно.
Рекурсивный спуск — это СПОСОБ реализации некоего алгоритма нисходящего разбора.
В простейшем случае это простая интерпретация БНФ, т.е. привет бесконечная левая рекурсия.
Поэтому, такие алгоритмы разбора как Пакрат или LL(k)-анализатор — это вовсе не простая интерпретация БНФ, там кое-что предварительно делается с грамматикой, а потом и во время разбора кое-что дополнительно происходит. Но оба алгоритма могут быть и часто реализуются именно методом рекурсивного спуска.
VD>Комбинаторные парсеры могут использовать разные алгоритмы.
Именно так!
Одно "но": парсер самого верхнего уровня — это комбинация парсеров нижнего уровня.
комбинатор последовательного соединения. Принимает на вход два парсера, возвращает парсер, который ведёт себя как последовательный запуск парсеров на строчке
комбинатор альтернативного соединения. Принимает на вход два парсера, возвращает парсер, который ведёт себя как "или то или это".
+ парсер терминала (в т.ч. пустого).
Через эти комбинаторы можно выражать правила из БНФ.
Комбинаторные парсеры пришли им мира ФЯ, т.е. речь всегда идёт о комбинации ф-ий, т.е. сами комбинаторы — тоже ф-ии.
В "чистом виде" достаточно описанных 4-х сущностей, чтобы распарсить грамматику класса LL (после факторизации, без левых циклов).
Но в чистом виде мало кто делает, добавляют "черных ящиков", которые лучше справляются с некоторыми цепочками терминалов/нетерминалов.
Итого, на самом верхнем уровне комбинаторного парсера у нас в любом случае получается нисходящий разбор методом рекурсивного спуска, пока мы "бродим" по комбинаторам. А как только заходим в конкретный парсер-"черный ящик", то внутри него может быть произвольный алгоритм.
Именно так устроены гибридные парсеры, которые используют как нисходящий, так и восходящий разбор.
Все еще не?
V>>А так же алгоритмы *LL(*)-разбора. VD>LL — это действительно класс грамматик задающий класс грамматик которые можно разобрать нисходящим парсером (делающим левое порождение, Leftmost derivation). Что означает "*" спереди я не знаю.
Есть подклассы грамматик, например SLL(1).
VD>Соответственно LR(k) описывает классы грамматик разбираемые восходящим анализом (делающим правый вывод).
Ну и?
VD>При этом LR(k) и LL(m) эквивалентны (т.е. их можно преобразовать один в другой, возможно с изменением глубины заглядывания).
Ес-но, грамматики могут быть эквивалентны (помнишь спор насчет того — а зачем вообще БНФ нужна? я как раз говорил для чего — для возможностей транформации грамматики с сохранением эквивалентности).
Но алгоритмы-то разные.
Нисходящий разбор поочередно "пробует" доступные из текущего состояния варианты (если есть варианты), а восходящий разбор выплёвывает "наверх" уже готовый нетерминал, точно так же, как аналогичный нетерминал выплёвывает "наверх" лексер. Один в один.
VD>PEG же описывает более широкий класс грамматик включающий часть контекстно-зависимых грамматик.
ОК, PEG — это эдакий способ борьбы с неоднозначностью. В предыдущем сообщении я имел ввиду нисходящий алгоритм парсера под эту грамматику.
VD>К алогритмам все это имеет опосредованное отношение.
А что ты называешь "алгоритмом"-то?
Переходы по goto, интерпретацию таблиц автомата? ))
VD>Так и LL- и LR-грамматики могут разбираться автоматными парсерами.
Различные алгоритмы разбора автоматными парсерами LL и LR отличаются кардинально. Общее у них только слово "автоматными". Ну и еще слово "таблица", если автомат представлен в виде таблицы. Но содержимое таблиц (семантика ячеек) для LL и LR анализаторов будет резко отличаться.
VD>Хотя обычно LL-грамматики разбираются алгоритмами основанными на рекурсивном спуске.
Во-о-о-от! ЧТД.
Именно что речь идёт о целом классе алгоритмов, даже в случае семейства LL.
Например LL(k) — анализатор имеет вполне себе конкретный алгоритм для конкретного класса грамматик.
Уже писал выше — этот анализатор может работать по таблице, а может быть реализован методом рекурсивного спуска.
VD>До сих пор не понимаю зачем мне нужно работать Камитаном Очевидность, ведь все это написано в Википедии и любом учебнике.
Да потому что в Вики надо уметь заглядывать так, как заглядывают в запрещённую литературу работники отдела цензуры. Потому что если психика не подготовлена, если всё принимать за чистую монету, то можно начать называть "алгоритмом" лишь незначительную подробность реализации целого класса алгоритмов.
VD>Но раз ты намешал все в кашу, приходится писать банальности.
Ну вот прямо отсюда вернись на предыдущий пост и еще раз, не торопясь, прочти написанное.
Потому что пока мест ты потребляешь моё терпение в стиле:
— ты куда, в баню?
— да нет же, я в баню!
UPD
Добавлю (для уменьшения пинг-понга).
В общем, терминологические споры по-определению бессмысленные и беспощадные.
Я рассматриваю "рекурсивный спуск" сугубо как один из способов реализации огромного класса нисходящих алгоритмов парсинга.
Двигаться дальше уже можно?
. При компиляции такой функции будет выдано предупреждение:
