Здравствуйте, vdimas, Вы писали: V>Я тебе дал вполне конкретное представление о том, что есть IDL, не наговаривай на конкретно CORBA или COM. V>В этом месте тебе должно быть уже понятно отличие Google protobuf или Microsoft bond от фреймворков подобного рода.
Та же википедия (и огромное количество других ресурсов) называет язык protobuf IDL. Официальная документация — нет, но к примеру Apache Thrift (полный аналог protobuf) в документации называет свой язык IDL. Дальнейший спор о терминах мне неинтересен. V>Потому что в первом случае ты сам работаешь напрямую с транспортным слоем, а во втором тебе транспортный слой, считай, не видим
То, что ты называешь транспортным слоем, в моем случае, считай, не видимо. Пользователь работает с сервисами через функции, возврат значений (если есть) и проброска исключений — под капотом. V>Не надо путать фреймворки сугубо для бинарной сериализации и фреймворки для удалённых вызовов методов объектов.
И protobuf, и Thrift, и мой фреймворк поддерживают описание сервисов и RPC. V>Почему именно он — он лучший на сегодня из всех. V>Хотя, даже сам ASN.1 весьма удобен
Я не разделяю твою точку зрения об удобстве языка ASN.1, так как использовал и ASN.1 и альтернативы. V>Например, в этом языке есть ЯВНАЯ поддержка optional-семантики. V>А еще в языке есть параметрические типы. ))
Это есть и в моем языке. _>>При этом кодогенерация вообще никак не контролируется, системы метаданных как например в protobuf у него нет. V>Вот тебе с метаинформацией для C#:
Скрытый текст
V>
V>[ASN1Sequence ( Name = "TestSequence", IsSet = false )]
V>public class TestSequence
V>{
V> private long field1_ ;
V> [ASN1Element ( Name = "field1", IsOptional = false , HasTag = false , HasDefaultValue = false ) ]
V> public long Field1 {
V> get { return field1_; }
V> set { field1_ = value; }
V> }
V>...
V>
Речь шла о метаданных в DSL, определяющих генерируемый код, а не о метаданных в генерируемом коде. Зачем мне C# атрибуты, когда я могу сгенерировать все что захочу? V>А не путаете ли вы, батенька, транспортный слой с прикладным? V>Или у тебя там всё вперемешку?
Я объяснял, что в IDL/DSL/whatever определяю модель дизайн-данных, и почему мне это необходимо. V>Блин, во всех этих сетевых делах ничего изобретать не надо — всё уже изобретено до нас. Например, любые обращения к серверу БД — это точно такое же обращение к сетевому внешнему сервису. И точно так же существует некий слой DAL, дальше которого сугубо транспортные типы данных не пролезают.
1) У меня на это нет ни процессорного времени, ни возможности делать лишние аллокации. Мне нужен максимальный FPS.
2) Маппинг транспортных типов на модельные все равно пришлось бы генерировать. Так зачем это надо? Обычно у меня минимум типов, которые используются исключительно как транспортные — в этом нет необходимости, так как сервисные функции принимают и возвращают произвольное количество аргументов. Редкое исключение — дельта-рекорды, о которых я писал.
3) Игры не похожи на бизнес-приложения. Не все практики одинаково полезны для них. V>Потому что ты уткнулся в архитектуру без DAL.
Я никуда не уткнулся, потому что я не использую ASN.1. V>Я тебе предлагал на основе BLToolkit сделать автоматический маппинг с транспортного слоя на прикладной.
1) На большинстве таргет-платформ запрещен JIT. Подозреваю, что для BLToolkit это будет проблемой.
2) Все, чем мне может помочь BLToolkit, я могу сгенерировать. Мне кажется, ты недооцениваешь простоту использования расширяемого кодогенератора, возможно, у тебя никогда не было подходящего инструмента.
3) Я еще тогда объяснил, почему конкретно в случае дельта-рекордов обновление ручное. Потому что: первое — при обновлении коллекций настолько много вариантов, что вручную написать проще, чем определять атрибутами (неважно, в коде C# или DSL). Второе — не всегда есть явное соответствие полей апдейта и сущности.
4) Проблемы, которую ты предлагаешь решать, не существует. V>А еще потому, что ASN.1 предлагает тебе trade-off изкаробки: можно выбирать из целой градации профилей кодирования, от самых эффективных по размеру пакета до самых эффективных по затрачиваемым ресурсам проца. И тебе несложно будет переключать эти профили. Например, если у какого-то клиента плохой пинг, то серверу стоит ужать трафик в сторону такого клиента в НЕСКОЛЬКО РАЗ. А если хороший, то стоит тратить на такого клиента меньше тиков процессора.
Для игр это совершенно бессмысленно. Плохой пинг не станет лучше, если вместо 40 байт послать 20. V>А еще в ошибках, т.е. тупо в багах. Был я как-то на одном проекте, так только в коде бинарной кастомной сериализации отловил порядка десятка ошибок. Причем, ошибки удачно максировались тем, что периодически шла не только дельта, но и абсолютные значения, угу. Поэтому ошибки в дельтах приводили лишь к "кратковременному вранью", которое списывали на притормаживание. )) А не было никакого притормаживания, были баги.
За 8 лет использования конкретно этого IDL у нас был только один баг, связанный со сгенерированным кодом сериализации (я не считаю баги, в которых сгенерированный код не компилировался — эти ловятся элементарно, хотя и тоже редкость), и он был быстро выявлен и пофикшен. Так что мой опыт вкорне отличается от твоего, а своему я доверяю больше. V>Ты, таки, взял бы в руки ANTLR. Это мощнейшая визуальная система разработки и отладки грамматик.
Я брал. Спасибо, не надо. А в наше время я возьму Нитру. Но я не хочу и не буду об этом спорить. V>В ANTLR ты можешь вести быструю разработку языка, вводить новые конструкции в него и достоверно на каждом шаге знать — получается ли у тебя язык однозначным на любых входных цепочках или уже нет. В случае PEG ты об этом не узнаешь до тех пор, пока тебе на входе не встретится такая цепочка. И вот ты создашь в JIRA тикет, вынужден будешь открыть исходник своего парсера и начать медитировать.
PEG использовал часто. Таких проблем не встречал. _>>а удобная интерполяция строк как в Nemerle это musthave для кодогенерации. V>Да это вообще для кодогенерации пофиг. Экономия 1% усилий.
Я не согласен. Это очень большое подспорье. Код нашего кодогенератора (кроме таргет-назависимого ядра) состоит из интерполяции строк процентов на 80, если не больше.
Здравствуйте, vdimas, Вы писали:
WH>>Но похоже ничего кроме трёпа от него так и не будет. Видимо показывать просто нечего. V>Показываю.
Опять исключительно трёп. Код где?
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
V>>>enum ClanUpdate { NoUpdate, EnterClan, ExitClan };
V>>>union ClanEvent switch (ClanUpdate) {
V>>> case NoUpdate: ;
V>>> case EnterClan: int ClanId;
V>>> case ExitClan: ;
V>>>};
V>>>
N>Ну если ты этому человеку опишешь это (в Erlang стиле) как {ok, ClanId:integer()} | no_update | exited — будет совершенно очевидно.
Если так ставить вопрос, то да. И я в общем-то осознаю, что с первого взгляда решение с вложенным Optional кажется неудачным. Попробую объяснить мотивацию в деталях, так как в реальной системе важны тонкости.
(Отредактировано:
До меня запоздало дошло, что если заменить T | undefined на {ok, T} | undefined, то в аргументации ничего не изменится, поэтому следующий абзац можно пропустить, а дальше подставлять любой из вариантов по вкусу)
Например, как у вас принято обозначать опциональные поля в Эрланге — T | undefined, или {ok, T} | undefined, или что-то еще. В OTP на эту тему зоопарк, но в собственном фрэеймворке и проектах логично выбрать что-то одно. Мы выбрали T | undefined, это хорошо подходит, если часто использовать рекорды (а мы их любим, т.к. любим intellisense и статические проверки) и проплисты. Ну и синтаксического шума меньше. Еще одна причина — {ok, T} удобно работает именно с PM, чтобы свалиться по месту, но на практике именно в нашем случае мы редко хотим свалиться с badmatch, т.к. отсутствие опционального поля в нашем случае это чаще всего throw — ошибка валидации или рассинхрона, в отличие от error — признака бага, и мы их по-разному обрабатываем и смешивать не хотим. Если же использовать case, то там и без разницы, с тэгом или без.
Итак, T | undefined. Значит, где-то есть функция clan(state()) -> clan_id() | undefined, а значит есть и парная функция для записи этого значения — set_clan(state(), clan_id() | undefined) -> state(). И вот это то место, где удобно уведомлять подписчиков.
Итак, в реализации set_clan мы должны вызвать код уведомления подписчиков. Он может выглядеть так:
set_clan(State, Clan) ->
... = unit_update:set(State, clan, Clan)
или так:
set_clan(State, Clan) ->
... = unit_update:set(State, clan, case Clan of undefined -> exited; _ -> Clan end).
или другие варианты с PM — это не так важно.
Это все: другого релевантного кода мы руками не пишем (да даже и здесь часто будет parse_transform, а перечисленные функции сгенерированы, но если сгенерировать первый вариант тривиально, то второй — нет). Напрямую с вложенным Optional мы в серверном коде не сталкиваемся. Нутрянка unit_update (сгенерированного) использует map, и отсутствие поля в мапе трактует как no_update (или None верхнего уровня) — но пользователю это и не важно.
Важно еще и то, что этот код будет совершенно идентичный и для required полей.
И объяснить новому человеку принципы обновления полей элементарно — для любого неколлекционного T просто добавь T? в update-рекорд — и все.
И получается так, что на первый взгляд вы с vdimas правы, а если смотреть на конкретный реальный сценарий использования, то Optional оказывается удобнее.
Я не жду, что ты обязательно согласишься, но надеюсь что хоть причины подобного решения мне удалось объяснить.
N>А вот заворот в несколько слоёв Optional<> хуже и тем, что после второго уровня шарики забегают за ролики, и тем, что туда не вложить никакую дополнительную информацию.
Опять же, если говорить в общем, без конкретики, то я согласен.
N>Не хочу тут рассуждать о формате IDL, всё это вторично, а то, что описал тут — важнее. IMHO.
Потому что у нас разные приоритеты. Для меня более важен код, который я чаще читаю, пишу, модифицирую и разделяю с коллегами, а в данном случае это именно код IDL. Поэтому я вынужден принимать в штыки необходимость написания нескольких строк для обновления одного поля.
Да, теоретически возможен более компактный синтаксис IDL для tagged unions (сейчас мы его не поддерживаем), и если бы использование optional в данном случае приводило к проблемам, я бы думал в эту сторону. А так — нет.
V>Что означает, что у F(T) несомненно ДРУГОЕ представление в памяти, т.е. памяти может потребоваться больше.
V>Например, в ФП языках некий Т был value-тип (ну вот так компилятор решил), а после заворачивания F(T) всегда получаем ссылочный тип. Итого, храним лишнюю ссылку вместо значения.
Ерунду полнейшую говоришь. Опшон без пооблем может быть как сылочным, так и нет. Я в библиотеку немерла специально добавил вэлью–опшон, чтобы обекты в хипе не создавать.
В Окамле не рекурсивные юнионы являются вэлью–типом и содержат доп поле для различия подтипов.
Ну и, естественно, вспоминаем классический VB–шный Variant, который был валью–типом описанным на С с применением тег–поля и сишных юнионов.
V>Только какие проблемы повторить тоже самое с ссылочными (nullable) типами в том же дотнете или C++?
Ты путаешь абстракцию типа и реализацию. Нулевая ссылка конечно же может интерпретироваться программистом как отсутствие значения, но система типов языка о такой интерпретации ничего не знает, а стало быть не может уберечь от ошибок. Тот же Котлин, хотя и использует нулевую ссылку каксэ отсутствующее значение, интерпретирует, например, string и string? как разные типы. Это позволяет компилятору контролировать ошибки связанные с null–ами.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Обещано было "со сравнимой с лексером скоростью на большинстве цепочек".
А что значит "сравнимой"? Я вот бьюсь об заклад, что GLR всегда будет медленне. Согласен?
V>Это как бэ, сама суть LR-разбора на цепочках без отката (программа не содержит ошибок, например), потому что обычный лексер — это LR(0).
И простой LR–автомат будет существенно медленнее ДКА. А GLR привносит еже оверхэд.
Ты не путаешь линейную скорость и физическое быстродействие.
V>Я тебе это уже писал, просто ты в этом вопросе плаваешь.
Я видимо тоже плаваю. По сему тоже посмотрелбы на GLR не сливающий ДКА.
V>Т.е., как работает автоматный лексер по "жадному" алгоритму ты интуитивно понимаешь, ОК, но как этот алгоритм соотносится с LR(k) — понятия не имеешь.
Мне кажется вы о разном говорите. Ты об алгоритмической сложности, которая у обоих вариантов в вырожденном случае должна быть O(n). А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>И зачем ждать, когда уже всё есть?
Мы за тебя т:стыдно должны писать?
V>Парсеры в промышленных компиляторах С++ — все поголовно GLR
Еще одно спорное заявление. Парсеры, почти навер-яка, тупо рукопашные рекурсивного спуска. Им скорость нужна, GLR тормоза еще те на неоднозначных грамматиках.
Короч/, ссцлку в студию плиз.
V>или модифицированный LALR.
Это ты совсем все попутал. Там ДВА своих алгоритма. К GLR у вообще не имеющие отношения хотябы потому что они леворекурсивные.
V>Никакие существующие в природе парсеры не работают быстрее.
Ты несешь чушь.
V>Собсно, из-за необходимости на каждый CPP-файл перемалывать многие мегабайты H-файлов, парсинг в С++-компиляторах вылизан по самое небалуй. Если ты предложишь нечто кардинально быстрее работающее (хотя бы на 30%-50%) — можешь смело номинироваться на "Нобелевку по Информатике" (премию Тьюринга).
1. С++ спакойно парсится супер–ьыстрым парсером рекурсивного спуска с контекстом в виде таблицы имен.
2. Для скорения компиляции хэадоров применяется кэширование.
3. Применение GLR для парсинга C++ не лучшая идея, так как это медленно (грамматика то не однозначная и большая константа).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали: DM>>что-то я перестал понимать твои слова практически. WH>Главное то что он сам не понимает о чём он говорит.
Задолбал, реально. ))
Главное то, что ты сам не понимаешь, когда уже отрываешься от реальности и начинаешь спорить не с живыми людьми, а с голосами в голове.
WH>В своё время он не смог даже понять формулу альфабленда двух пикселей с альфой и пытался мне доказать, что артефакты на отмасштабированном изображении не от неправильной работы с альфаканалом, а из-за использованного фильтра. Даже не смотря на то что рядом лежало изображение, отмасштабированное тем же фильтром, но с правильной работой с альфаканалом.
Мде? ))
А разве это не ты там несколько постов сам с собой спорил, не в состоянии как Брат Нибеэнимэда связать двух слов и объяснить коллегам, чего ты там сам с собой так до смерти воюешь-то?
Твои формулы изначально никто не смотрел, бо тема была вааще никому не интересна. Ты её зачем-то прилепил в рамках совсем другого спора, на котором и было сосредоточено внимание. Оба примера картинок — и правильный и неправильный — были исключительно твои. Т.е. ты сам себя там "разбил" в кровавой битве с самим собой. Когда ты мне надоел оскорблениями и наездами (по совершено не интересующей меня теме, заметь, отвлекающей от основной темы обсуждения), я вернулся, вникнул в твои т.н. формулы, поржался над тобой и покинул тему.
Коллеги, в двух словах, о чем шла речь.
Предлагаю улыбнуться вместе. ))
Предположим, что у нас есть изображение из двух частей: слева пусть будет сплошной желтый цвет полностью непрозрачный, а справа ну пусть будет сплошной синий цвет, но полностью прозрачный. И никаких градиентов м/у по строго вертикальной границе (для простоты понимания).
Теперь, если наложить такое изображение на белый цвет, то слева будет сплошной желтый, а справа будет сплошной белый, т.к. полностью прозрачного синего будет не видно. ОК.
Если теперь отмасштабировать изображение на некратные размеры по некоей формуле, по которой цвета смежных пикселей смешиваются отдельно, а альфаканалы отдельно и опять наложить такое изображение на белый цвет, то м/у желтой областью и белой будет зеленая полупрозрачная полоса, которой в исходном изображении не было.
И вот такую простейшую мысль WH не мог озвучить несколько постов, шипел, пускал пену, и обвинял окружающих во всех смертных грехах.
Собсно, я еще тогда сказал ему, что у него ба-а-альшая проблема с формулировками. А это первый признак полнейшей каши в голове.
WH>Точно такая же история была с многими другими темами.
Да, точно такая же.
Ты не в состоянии связать двух слов.
Сверху этого полнейшая неадекватность.
WH>Например, он долго с умным видом говорил, что знает, как сломать современную криптографию.
Брехня. Я говорил как сломать вполне конкретную систему, в разработке которой участвовал.
Отвечать мне аргументами из разряда "да ты знаешь сколько миллиардов лет этот алгоритм надо ломать???" — это строить из себя дурачка, как по мне.
Я сразу же сказал в чем там слабость — в распространении ключей.
Современные системы шифрования ломаются через слабость инфраструктуры, ес-но.
WH>Когда его наконец загнали в угол и заставили выдать секрет он выдал что-то типа "Злоумышленник может подменить публичный ключ сервера, зашитый в приложение."
Какой в опу "угол"?
Из моего предложения обсудить ситуацию ты устроил очередное побоище с оскорблениями. Ты ж неадекватен, не видишь себя со стороны.
Я просто ушел на время из топика. Потом однажды вернулся и описал, что там не так в той системе.
WH>После вопроса: "Если злоумышленник может изменить программу, то что ему помешает зашить в эту программу вообще любой вредоносный код?" тихо слился из темы.
Проблема в том, что про "публичный ключ сервера, зашитый в приложение" тебе сказал голос в голове.
Система распределённая, ключи могут добавляться динамически. В этом месте я и усмотрел слабость и хотел обсудить, в том числе хотел услышать предложения по инфраструктуре. Но благодаря неадекватному тебе, обсуждение не состоялось.
Спасибо большое, как грится, удружил...
WH>Но самое плохо в том, что для людей, которые не понимают о чём идёт разговор он звучит весьма убедительно что приводит к распространению заблуждений.
Каких именно "заблуждений", о чём ты шепчешь? ))
Чтобы показать чьи-то заблуждения ты сначала должен научиться сформулировать свою мысль, а потом уже сформулировать ошибки в рассуждении коллег. Но ты НИКОГДА этого не умел и никогда не научишься.
У тебя просто отсутствует нужная часть в мышлении, которая отвечает за связанность мыслей.
WH>Короче крайне вредный персонаж.
Я просто неучей на чистую воду вывожу. ))
Как в том эпическом споре насчет БНФ.
Причем, в отличие от, прекрасно формулирую свои мысли. Было бы тебе что внятно ответить в том споре — ты бы внятно ответил. Вместо этого ничего полезнее чем "это фсё фигня, этот матан придуман для дебилов" (С) от тебя так и не прозвучало.
Как бы ты не перекручивал, но у тебя постоянно идут рассуждения дилетанта и я это регулярно насчет тебя показываю.
Чем очень тебе "вредю", вестимо.
Ну уж извини, кто на что учился. ))
Здравствуйте, VladD2, Вы писали: V>>Например, в ФП языках некий Т был value-тип (ну вот так компилятор решил), а после заворачивания F(T) всегда получаем ссылочный тип. Итого, храним лишнюю ссылку вместо значения. VD>Ерунду полнейшую говоришь. Опшон без пооблем может быть как сылочным, так и нет.
Т.е. если в Nemerle опишу некий свой variant MyOptional, это будет value-тип?
VD>Я в библиотеку немерла специально добавил вэлью–опшон, чтобы обекты в хипе не создавать.
"Специально"?
Я правильно понимаю, что средствами языка, т.е. через variant, его нельзя было описать как value-тип?
Я-то уже 100 лет на Немерле не смотрел, но если я понимаю правильно, то ты лишь удружил через ЧТД.
VD>В Окамле не рекурсивные юнионы являются вэлью–типом и содержат доп поле для различия подтипов.
А как ты отличаешь value-тип от ссылочного?
Т.е. вопрос в следующем: а как эти значения этих типов передаются в кач-ве аргументов функций — по ссылке или по-значению?
Надеюсь, суть вопроса понятна?
Ниже подробней распишу в чем тут тонкость.
VD>Ну и, естественно, вспоминаем классический VB–шный Variant, который был валью–типом описанным на С с применением тег–поля и сишных юнионов.
1. Было сказано "в ФП языках".
2. Variant не описан средствами VB, а "дан сверху", т.е. является встроенным для него.
Я тебе больше скажу. Генератор CORBA IDL или COM IDL генерит размеченные объединения как value-типы для С++.
Одно плохо — CORBA это тоже не про ФП-языки.
В общем, в двух словах. Не столько для тебя, сколько для читателей.
Основная фишка тут в том, что реализация объединения через условный value-тип будет занимать в памяти такой же размер, какой нужен для представления самого большого из вариантов + дискриминатор. К тому же, данные за дискриминатором в любом случае выравниваются, т.е. под дискриминатор изволь выделить машинное слово к этому самому большому размеру.
А когда варианты представлены в виде ссылочных типов, то под каждый из них можно выделить ровно столько памяти, сколько необходимо для представления конкретного варианта.
А самое главное, в отличие от C#, "ссылочный тип" не означает размещение в куче. "Ссылочный тип" означает передачу этого типа по ссылке. Поэтому, оптимизатор запросто может выделить под конкретное значение алгебраика место на стеке и передать затем его в ф-ию по ссылке, если "увидит", что ф-ия лишь читает это значение, но нигде не запоминает ссылку на него.
Вот как раз для OCaml-а это вполне может работать, т.к. компилятор обычно знает, какой тип он будет "заворачивать" в алгебраик, т.е. нет смысла выделять больше памяти, чем требуется для представления конкретного из вариантов.
V>>Только какие проблемы повторить тоже самое с ссылочными (nullable) типами в том же дотнете или C++? VD>Ты путаешь абстракцию типа и реализацию. Нулевая ссылка конечно же может интерпретироваться программистом как отсутствие значения, но система типов языка о такой интерпретации ничего не знает, а стало быть не может уберечь от ошибок.
Верно.
VD>Тот же Котлин, хотя и использует нулевую ссылку каксэ отсутствующее значение, интерпретирует, например, string и string? как разные типы. Это позволяет компилятору контролировать ошибки связанные с null–ами.
А тут не верно.
Озвученное тобой говорит о том, что система типов Котлина НЕ контроллирует значение ссылочного типа, поэтому просто добавила ДРУГОЙ тип для non-nullable-ссылок.
То, что в синтаксисе языка наоборот — т.е. как бэ nullable-тип видится как "другой" — это ж просто трюк такой, верно?
А так-то похожий трюк с введением ДРУГОГО типа я тоже в С++ тоже периодически делаю.
Вот из рабочего проекта (надеюсь не наругают бо это примитивщина):
void foo(NotNull<SomeRefType> arg) {...}
// можно и через typedef NotNull<SomeRefType> SomeRefTypePtr;
// - тут на вкус и цвет, явные аннотации тоже неплохи, бо читабельность! ))
И в теле ф-ий ничего проверять не надо.
Т.е. один раз сконструировал экземпляр non-nullable из nullable, т.е. всего один раз произошла проверка, а затем гарантии распространяются далее без проверок. Обрати внимание на explicit-конструкторы — помогает в том самом распространении гарантий, потому что implicit получился только конструктор копирования.
Здравствуйте, VladD2, Вы писали:
V>>Обещано было "со сравнимой с лексером скоростью на большинстве цепочек". VD>А что значит "сравнимой"? Я вот бьюсь об заклад, что GLR всегда будет медленне. Согласен?
Сравнимой — это когда не в разы, а на единицы или десяток-другой процентов.
Цифры разницы на своих данных я давал.
Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
Потому что трафик символов разный, ес-но.
VD>А GLR привносит еже оверхэд.
Только на неоднозначностях.
Почитай внимательно вот это: https://ru.wikipedia.org/wiki/LR(0)
Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
В этом случае содержимое "стека" — это цепочка-значение разобранной лексемы.
Теперь представь, что неоднозначностей не возникло на конкретных данных.
Разница по сравнению с алгоритмом лексера будет в операциях замены некоей цепочки символов в потоке на другой один.
Частота таких событий в общем потоке исходных терминалов мала.
Заметь так же, что если у нас в системе будет отдельный лексер (так часто делают), то первый уровень такой замены делает сам лексер — отображает входную последовательность терминальных символов на последовательность нетерминальных ("сворачивает" входные цепочки с т.з. LR(0)-алгоритма) — вот тебе отдельный шаг LR(0)-автомата-лексера. Выходные нетерминалы лексера можно считать входными терминалами для вышестоящего "слоя" и т.д.
Вот точно так же происходит в LR(0). Легко заметить, что трафик каждого вышестоящего "слоя" получается намного ниже, чем из предыдущего. Это я к тому, что даже "глубокие" выражения вносят несущественный в среднем оверхед, т.к. чем глубже некое выражение, тем меньше трафик нетерминала, его описывающего.
А теперь делаем фокус: при возникновении неоднозначности создаем клон(ы) текущего разбора, т.е. у нас будет уже как бы два (или более) LR(0) парсеров, работающих в параллель над однимим и теми же входными символами. Вот тебе GLR. Вот тебе вся теория. Это даже проще чем ПЕГ, ИМХО.
В практической реализации все клоны используют общую предыдущую часть разбора, т.е. возможно эффективное представление клонов в памяти.
А еще на практике средняя "ширина" разбора для языков программирования очень мала и приближается к 1-му — более 90% входных цепочек нетерминалов для парсера на практике однозначны.
V>>Т.е., как работает автоматный лексер по "жадному" алгоритму ты интуитивно понимаешь, ОК, но как этот алгоритм соотносится с LR(k) — понятия не имеешь. VD>Мне кажется вы о разном говорите. Ты об алгоритмической сложности, которая у обоих вариантов в вырожденном случае должна быть O(n).
Именно так насчет сложности:
Алгоритм GLR в худшем случае имеет такую же сложность, как алгоритм Кока — Янгера — Касами и алгоритм Эрли — O(n³). Однако, у GLR-алгоритма имеется два преимущества:
* Время, необходимое для выполнения алгоритма, пропорционально степени недетерминированности исходной грамматики — при полностью детерминированной грамматике GLR-алгоритм работает за O(n). (Для Earley- и CYK-алгоритмов это не так, хотя оригинальный алгоритм Earley может быть модифицирован для получения такого же преимущества).
* Алгоритм GLR «оперативный» (it is on-line) — считывая каждый символ из входного буфера, он производит как можно больше работы по анализу доступной по прочтению данной входной последовательности.
Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
Игнорить это и приписывать мне что, мол, GLR лучше всех всегда и везде — нагло передёргивать, но WH занят именно этим. ))
И то, что он требует — тоже именно оно, чтобы иметь возможность найти сценарий, где GLR будет хуже некоей другой альтернативы, например, где какой-нить ПЕГ отработает вообще без откатов. Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
VD>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
Вот так "обыгрываются" вложенности.
Чем глубже рекурсия, тем меньше трафик на верхних её уровнях.
Представь, что ты провел декомпозицию грамматики более одного раза.
Сначала выделил отдельный лексер и у тебя осталась часть грамматики (повторюсь, так делают часто).
Но из оставшейся части ты опять выделил лексер (регулярную часть) и т.д.
Вручную выделять не надо, ес-но, потому что алгоритм построения таблицы их сам выделяет и трюк работает через замену цепочек на нетерминалы во входном потоке.
Вот тут, собсно, и состоит принципиальное отличие от нисходящего разбора, что нисходящий разбор "не знает", какое-же именно выражение идёт следом (зачастую возможна куча альтернатив), а восходящий почти всегда "знает", ведь он "свернул" уже все низлежащие цепочки до известных нетерминалов.
VD>Еще одно спорное заявление. Парсеры, почти навер-яка, тупо рукопашные рекурсивного спуска.
Они гибридные. Потому что в любом современном языке можно различить непересекающиеся или слабо пересекающиеся мн-во правил из общей грамматики языка. Например, ты можешь писать некие выражения языка только в телах методов и ф-ий, т.е. нет смысла их ожидать при объявлении типов, если в текущем контексте ожидаются только объявление членов типа. Встретил объявление метода, пошло следом описание его тела — это уже другой контекст, который можно парсить по совсем другой грамматике. Вот так иногда работают т.н. "гибридные парсеры" — по смешанному LL/LR алгоритму в разных контекстах.
Строго говоря, ЛЮБОЙ современный LL(k) парсер с отдельным автоматным лексером — это гибридный LL/LR парсер.
Однако (продолжу), для неоднозначных мест в языках навроде С++ используют тот самый "поиск в ширину", потому что ничего лучше пока не придумали.
Это оно и есть.
V>>или модифицированный LALR. VD>Это ты совсем все попутал. Там ДВА своих алгоритма. К GLR у вообще не имеющие отношения хотябы потому что они леворекурсивные.
Здравствуйте, meadow_meal, Вы писали:
_>И объяснить новому человеку принципы обновления полей элементарно — для любого неколлекционного T просто добавь T? в update-рекорд — и все.
А почему бы не сделать обновление автоматизированным (типа как делают ORM), где прикладной код писать в колбэках навроде onClanChanged?
Тогда новым коллегам вообще не придется возиться с транспортным слоем или возиться по-минимуму.
Еще идея.
Если уж у вас собственный DSL и собственный маппинг (кодогенерация) на типы, то можно ввести такую штуку
(условный синтаксис):
type ClanId = Optional<int> where NotSet = 0;
type Coord = Optional<uint> where NotSet = ~0; // 0xFFFFFFFF
Надеюсь, смысл понятен.
Для C# генерить примерно такой маппинг:
struct ClanId {
public int Value;
public bool HasValue { get { return Value != 0; }}
}
struct Coord {
public int Value;
public bool HasValue { get { return Value != ~0; }}
}
void Update(ClanId clanId) {
if(clanId.HasValue) ...
}
Тогда размер структуры в памяти будет минимален и уже имеющийся код можно будет оставить без изменений.
Здравствуйте, vdimas, Вы писали:
VD>>Ерунду полнейшую говоришь. Опшон без пооблем может быть как сылочным, так и нет.
V>Т.е. если в Nemerle опишу некий свой variant MyOptional, это будет value-тип?
Value-option не обязан быть вариантом. В немерле он сделан просто структурой.
В Немерле варианты сделаны на базе классов, но это одна из возможных реализаций.
V>Я правильно понимаю, что средствами языка, т.е. через variant, его нельзя было описать как value-тип?
У языка как бы средств больше чем одно. option ни разу не обязан быть ваниантом.
V>Я-то уже 100 лет на Немерле не смотрел, но если я понимаю правильно, то ты лишь удружил через ЧТД.
Ты себе что-то на придумывал и пытаешься это обосновать любыми путями.
V>А как ты отличаешь value-тип от ссылочного?
Как кота от кошки. Смотрю value-тип — говорю — "value-тип".
V>Т.е. вопрос в следующем: а как эти значения этих типов передаются в кач-ве аргументов функций — по ссылке или по-значению?
Не имеет значения. Передать вэлью-значение по ссылке не особо проблематично. Это детали реализации.
V>Надеюсь, суть вопроса понятна?
Понятна. Пытаешься придумать обосновании явно неверному утверждению.
V>1. Было сказано "в ФП языках".
Язык не имеет значения.
V>2. Variant не описан средствами VB, а "дан сверху", т.е. является встроенным для него.
Опять же не имеет значения.
V>Я тебе больше скажу. Генератор CORBA IDL или COM IDL генерит размеченные объединения как value-типы для С++. V>Одно плохо — CORBA это тоже не про ФП-языки.
Ты себе придумал какой-то странный ценз "ФП-языки". Он только тебе интересен.
V>В общем, в двух словах. Не столько для тебя, сколько для читателей.
Ну, да. Как всем же ясно что ты прав и они хотят у гуру поучиться.
V>Основная фишка тут в том, что реализация объединения через условный value-тип будет занимать в памяти такой же размер, какой нужен для представления самого большого из вариантов + дискриминатор.
Ой-йо-йо. Великое горе! А любой объект в дотнете занимает 24 байта (под x64). И стало быть перерасход 1-2 интов не такая уж проблема. А там еще локальность памяти подтягивается, затраты на занятие памяти в куче и в друг оказывается, что потеря этих байтов просто фигня по сравнению с выигрышем.
Вот так и с ValueOption оказывается, что потеря 1-4 байта (занимаемого bool-ом в зависимости от выравнивания) — это ни что по сравнению с затратами на ссылочные типы.
VD>>Тот же Котлин, хотя и использует нулевую ссылку каксэ отсутствующее значение, интерпретирует, например, string и string? как разные типы. Это позволяет компилятору контролировать ошибки связанные с null–ами.
V>А тут не верно.
Только по-твоему.
V>Озвученное тобой говорит о том, что система типов Котлина НЕ контроллирует значение ссылочного типа, поэтому просто добавила ДРУГОЙ тип для non-nullable-ссылок.
Не говори ерунды. Система типов нигде значения не контролирует, так как значения сущность времени исполнения. Зато она контролирует отсутствие ошибок с этими значениями.
V>То, что в синтаксисе языка наоборот — т.е. как бэ nullable-тип видится как "другой" — это ж просто трюк такой, верно?
Какие на фиг трюки? Это система типов языка. Для этого языка это разные, хотя и связанные типы. Учись мыслить абстрактно. Система типов языка может отличаться от системы типов базовой платформы.
V>А так-то похожий трюк с введением ДРУГОГО типа я тоже в С++ тоже периодически делаю.
Да это где угодно можно. Вопрос лишь в удобстве использовании и загрузки компилятора ненужной работой.
В том же Колине кроме разведения типов еще есть ряд фич упрощающих жизнь с этим. Иначе эта была бы адова боль, а не работа.
Так у них можно проверить в if-е значение на null и компилятор сам подменит тип внутри true-секции этого if-f. Оберткой это не сделаешь. Или можно? Далее для null-абл значений есть лифтинг. Например, написав optionX?.Foo мы получим значение Foo поднятое в null-абл тип. И это можно проделывать сколько угодно долго. А потом можно просто проверить результат один раз или использовать оператор замены null-значений. Еще они проводят анализ библиотек Явы и вычисляют функции точно не возвращающие нулабл-типы. Всего этого на обертках не добьешся. В итоге получается разный класс решений. У тебя это примочка вызывающая боль при использовании, а у них стройная система.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Сравнимой — это когда не в разы, а на единицы или десяток-другой процентов. V>Цифры разницы на своих данных я давал.
Я не знаю, что ты там за цифры давал. Но на свете нет ни одного GLR-а пригодного для промышленного использования. У них и с производительностью проблемы, и с восстановлением после ошибок. Они только для научных эксперементов и детских поделок годятся.
Если я ошибаюсь, дай ссылок.
V>Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
Слушай читать твои фантазии у меня никакого желания нет. Рассуждения настолько не серьезные, что надо начинать разжевывать тебе все детали, чтобы что-то объяснит. Но учитывая, что ты слушать то не намерен — это совсем уж бесполезное время препровождение.
Само наличие лексера сокращает число этих самых тактов на порядки. Парсеру приходится работать не с миллионами символов, а с тысячами или даже сотнями. Число неоднозначностей падает с тысяч, до единиц или даже нуля.
Но сам лексер работает просто на порядки быстрее. "Отлексить" с помощью качественного компилированного кода основанного на ДКА даже десятимегабайтный файл — это денницы миллисекунд. А вот парсинг того же самого — это совсем другой расклад.
V>Потому что трафик символов разный, ес-но.
Ты говоришь полную чушь! Трафик ничто по сравнению с вычислительными затратами. Даже сложност грамматики резко менят расклад. Например, грамматика препроцессора шарпа отрабатывает так быстро, что ее можно даже не брать в расчет при парсинге.
А главное, что GLR (ну, если это реально GLR, а не что нибудь) являются безлексерными и разбирают отдельные символы далекими от эффективности алгоритмами.
VD>>А GLR привносит еже оверхэд.
V>Только на неоднозначностях.
Хрен там. У них и константа во много раз выше. Не может быть обобщенный алгоритм столь же эффективным, как специализированный. Вот ДКА ты хрен когда догонишь. Хот ты лопни.
Плюс ты похоже не понимаешь принципов работы GLR-ов. Они сворачивают продункции в обратную сторону, так что промежуточные свортки им надо как-то хранить. Они обязательно оперируют структурой лесов. Все это не бесплатно.
V>Почитай внимательно вот это: V>https://ru.wikipedia.org/wiki/LR(0)
Спасибо. Читай это сам. И за одно запомни LR(0) это совсем не GLR. LR(0) не распарсит даже C#.
V>Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
Языком в основном. На практике код там будет долек от того, что можно сгенерировать для ДКА. А попытка жрать символы ЛР-ом приведет к неоднозначностям на ровном месте. GLR, конечно, их разрулит, но обойдется тебе это не дешево.
V>В этом случае содержимое "стека" — это цепочка-значение разобранной лексемы.
Языком. Языком.
V>Теперь представь, ...
Не хочу. Мне время дорого. Приведи тесты GLR vs лексер и за одно дай ссылки те самые С++-парсеры, которые используют GLR для разбора С++. Потом поговорим. А до тех пор не убивай мое время, плиз.
V>Именно так насчет сложности: V>
V>Алгоритм GLR в худшем случае имеет такую же сложность, как алгоритм Кока — Янгера — Касами и алгоритм Эрли — O(n³). Однако, у GLR-алгоритма имеется два преимущества:
V>* Время, необходимое для выполнения алгоритма, пропорционально степени недетерминированности исходной грамматики — при полностью детерминированной грамматике GLR-алгоритм работает за O(n). (Для Earley- и CYK-алгоритмов это не так, хотя оригинальный алгоритм Earley может быть модифицирован для получения такого же преимущества).
V>* Алгоритм GLR «оперативный» (it is on-line) — считывая каждый символ из входного буфера, он производит как можно больше работы по анализу доступной по прочтению данной входной последовательности.
Блин, клинический детский сад! Открой для себя понятие константы. Тогда узнаешь, что линейное != быстрое. Если ты на разбор символа в потоке тратишь секунду, то твой алгоритм линейный, но он никому не нужный, так как даже на 100 символов ты потратишь неприемлемо много времени. Вот именно это и происходит со всеми G.
И еще задумайся на фиг нужен GLR, если грамматика полностью детерминирована?
Вот мы используем модифицированный Эрли для качественного восстановления после ошибок. При этом числ неоднозначностей растет просто лавинообразно. Но по другому нельзя, так как только обобщенный алгоритм может найти все пути.
V>Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
Нет таких сценариев на практике. GLR используется исключительно в научных целях. Я просто ржал читая научные статьи где на полном серьезе говорилось об восстановлении после ошибок за 10 секунд. Успехов всем кто готов ждать отклика редактора по 10 секунд.
V>И то, что он требует — тоже именно оно, чтобы иметь возможность найти сценарий, где GLR будет хуже некоей другой альтернативы, например, где какой-нить ПЕГ отработает вообще без откатов.
Блин. Это просто песня!
Запомни на будущее.
1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
V>Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
Пипец ты берд несешь! Прямо хоть в юмор выноси тему. Но, боюсь, там большинство не поймет. Весь смысл Пакрата в том, что он безоткатный, т.е. гарантирует линейное время. Вот константа у него опять же достаточно высокая. Но все же ниже чем у GRL. У нас сейчас файлы в редакторе перепарсиваются на каждый чих и производительности хватает. Хуже с восстановлением. Но и с ним в большинстве случаев все не плохо работает.
VD>>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
Пипец! Эта песня хороша, начинай сначала. Не я на тебя время тратить не буду.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH> В С++ не парсер тормозит. Даже если бы он был в 10 раз медленней на времени компиляции это бы сказалось не сильно.
Тут ты не прав. Парсер там тоже имеет значение. Особенно без кэширования и разных прекомпайлед-хэадеров.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Просто, никакое поделие ни на каком на дотнете не построит сегодня AST с нужной скоростью. В дотнете банально оператор new не умеет с такой скоростью работать, какая там требуется. Мои самописные страничные и пул-аллокаторы умудряются работать в несколько раз быстрее дотнетного new. А на освобождение многих многих миллионов объектов вообще зачастую ни такта не тратится — на то они и региональные аллокаторы.
V>Ну и пробег по памяти, поиск в мапах и хеш-таблицах — тут тоже дотнет сливает серьезно.
V>Это я уже молчу о банальной беготне табличного парсера или лексера по его таблице состояний. Самый вылизанный дотнетный код бегает по таблице состояний почти в 2 раза медленнее. Это как?
Горазд ты трепаться. Вот смотри. Я тебе сейчас приведу сразу 8 критических к производительности задач написанных на дотнетных языках и яве:
1. ReSharper.
2. IDEA и ее языковые плагины.
3. NetBeans.
4. Eclipse.
5. Компилятор Шарпа.
6. Компилятор Явы.
7. CodeRush.
8. Nitra и наш движок IDE.
Назови хотя бы 3-4 аналога написанного на С++ и объясни почему движки IDE и компиляторы теперь пишут на управляемых языках? Может они не так уж и медленны?
Может как раз AST на GC строится быстрее?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
WH>> В С++ не парсер тормозит. Даже если бы он был в 10 раз медленней на времени компиляции это бы сказалось не сильно. VD>Тут ты не прав. Парсер там тоже имеет значение. Особенно без кэширования и разных прекомпайлед-хэадеров.
По сравнению с шаблонами фигня.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, vdimas, Вы писали:
V>Задолбал, реально. ))
А уж как ты задолбал всяким бредом типа зависимых типов в С++.
V>Главное то, что ты сам не понимаешь, когда уже отрываешься от реальности и начинаешь спорить не с живыми людьми, а с голосами в голове.
ЗТ в С++ это точно голоса.
V>А разве это не ты там несколько постов сам с собой спорил, не в состоянии как Брат Нибеэнимэда связать двух слов и объяснить коллегам, чего ты там сам с собой так до смерти воюешь-то?
Я сразу сказал в чём проблема. Но ты начал разговаривать с голосами в голове про фильтры.
V>Твои формулы изначально никто не смотрел, бо тема была вааще никому не интересна.
А зачем ты начал учить меня использовать фильтры если тема интересной не была?
V>Да, точно такая же. V>Ты не в состоянии связать двух слов. V>Сверху этого полнейшая неадекватность.
Со мной не все соглашаются, но что характерно не понимаешь меня только ты. Может в тебе проблема?
V>Я сразу же сказал в чем там слабость — в распространении ключей. V>Современные системы шифрования ломаются через слабость инфраструктуры, ес-но.
А к чему твой взлом то свёлся? Правильно к подмене в программе ключа которым подписывали остальные ключи.
V>Проблема в том, что про "публичный ключ сервера, зашитый в приложение" тебе сказал голос в голове.
Вот не ври. В конце концов было выяснено что в программе зашит ключ.
После чего ты из темы слился.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, vdimas, Вы писали:
V>Подсказка №1: GRL/LALR существуют во всех компиляторах языков, где требуется перемалывать БОЛЬШИЕ объемы исходников.
Задрал. Назови имена этих компиляторов и дай ссылки на пруфы.
V>Подсказка №2: дотнет и немерле — это НЕБОЛЬШИЕ объемы исходников, скорее микроскопические.
Что такое "объемы исходников дотнет"?
V>И вот даже в этом обсуждении — сходу наговорил глупостей, но окружающим непременно раздаешь "бред", "ты бредишь" и т.д. V>Ничего не меняется... ))
Ну, назвать бред бредом — это вполне нормально. Ты несешь действительно феерические перлы. Причем безапелляционно и упорно отказываешься приводить доказательства.
WH>>Но в реальной реальности, а не твоём воображении у GLR огромная константа
V>Нет никакой константы.
Кончай повторять один и тот же набор слов. Возьми и докажи свои слова на практике. Сделай тесты и дай ссылки на мифические компиляторы со встроенным GLR (что бы это не означало).
С одной отсылкой ты уже облажался. ANTLR никакого отношения к LR не имеет, не смотря на наличие букв в зназвании. Это LL-пасрер генератор. Если быть точнее он использует Adaptive LL(*) который в базе использует более производительный но не обобщенный (сюрприз!) алгоритм и переходит на обобщенный в случае, если основной алгоритм не српавляется.
V>Ты знаешь как работает табличный лексер?
V>"Константа" там может быть только от кривых рук,
Константа есть везде. Вопрос лишь в ее величине.
V>При том, что программист с твоим опытом мог бы потратить пару дней и проверить самому, не?
Table 3. Speed (characters/second), Parse time (seconds) , Filter time (seconds), Total
time (seconds) and Speedup (%) of SGLR (S) and SRNGLR (SRN). k = 103.
Фастерх-фигастре парсер работает со скоростью 175k в секунду!!! То есть, если это чудо использовать как движок для IDE, то при редактировании мегабайтного файла это чудо будет втыкать по 6 секунд на каждое нажатие!
А для Питона, смешно сказать, и одного К в секунду не смогли спарсить.
О каком на фиг парсинге моря инклюдов ты вел речь?
Оцени весь маштаб своих заблуждений! И не повторяй эту чушь в новь.
В отличии от этого чуда в перьях мы парсим сравнимые грамматики со скорость несколько метров в секунду. И на С++-грамматике у нас не будет провала производительности, как у GLR-ов.
V>Тем более, что я давал конкретные координаты сценариев, когда GLR рвет всех и вся как тузик грелку: V>
V>входные цепочки большой длины, но низкой "глубины" вложенности.
Кому интересны какие-то синтетические данные?
V>Любой алгоритм с откатами/мемоизациями просто не работает на таких данных.
Ой как интересно. И что же мешает мемоизации работать на таких данных? И почему для лексического разбора надо вообще выбирать что-то отличное от ДКА?
V>Вернее, работает, но это ж-па полная.
Так работает или нет? Ты уж определись. От этого зависит то бредишь ли ты полностью или просто заблуждавшийся в оценках.
V>Смотри. V>Пусть даже для некоторой цепочки GLR протягивает одновременно/параллельно пару цепочек разбора по таким данным, т.е. работает на каком-то участке чуть медленней единичного лексера, но (!!!) зато потом не надо будет откатываться на мегабайты символов назад. Никакая мемоизация и никакой откат в этих условиях банально не живут.
Ты вообще не понимаешь о чем говоришь.
1. Для разбора регулярных грамматик (из которых и состоят лексемы всех без исключения языков) вообще не нужны алгоритмы сложнее ДКА. Ну, за исключением редко встречающихся случаев вроде рекурсивных комментариев или строк.
2. Парсер с мемоизацией вообще (ни при каких условиях, никогда) не откатывается.
Так что это ты нихрена не понимаешь в обсуждаемых аглгоритмах. Иди и выучи наконец то матчасть.
Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения[1]. Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов. Другой пример — фибоначчиевы кучи, несмотря на асимптотическую эффективность, с практической точки зрения программная сложность реализации и большие значения констант в формулах времени работы делают их менее привлекательными, чем обычные бинарные деревья[1].
«Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка nC, а при другом — порядка n+n!/C, где C — постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй — нет, хотя, например, при С=10(1010) дело обстоит как раз наоборот[2].
А. А. Зыков»
V>Если на каком-то из участков появляется конкурирующая нить разбора, то это НЕ означает падения скорости разбора вдвое. Почему? Потому что GLR-парсер, который работает с нетерминалами, получаемыми от лексера
А какой смысл в GLR с отдельным лексером? Им половину языков не разберешь. Лексемы то могут быть уникальны для разных правил. Оно и то же место может быть разобрано разными лексемами. Правильные GLR-ы безлексерные, как и наш нитровский.
Ты же сам утверждал, что производительность GLR-ов сравнима с лексерами. Зачем нужны отдельные лексеры? Чтобы сократить класс грамматик?
Ну, и падение все равно будет, так как лексер выполняет самые дяжелые рассчеты. Основное время уходит на все эти шифт-редьюсы и на построение леса резултата разбора. Он там в общем случае является графом.
V> (в твоём генераторе, кста, автоматный лексер тоже строится отдельно), парсер потребляет намного меньше тиков процессора, чем лексер. Потому что трафик выходных нетерминалов от лексера в несколько раз ниже трафика входных терминалов.
Ты несешь околесицу. Лексер в нашем парсере встроен в правила. Генерируется он вместе с правилами. Но это не важно. Важно, что твои утверждения, что про трафик и про "парсер потребляет намного меньше тиков" не соответсвтуют действительности от слова вообще! Лексический анализ для мегабайтного файла занимает несколько миллисекунд. Понимаешь ты это? МИЛЛИСЕКУНД! Он на время разбора практически не влияет. Узким местом в нем является скорость чтения памяти (или диска).
Паркинг же занимает существенно больше времени. Даже линейный Пакрат на мегабайтный файл потратит сотни миллисекунд. А уж этот квадратичный GLR и вовсе может всраться по полной. И для нас не нужно специально адаптировать грамматику, а для GLR нужно стараться не допускать неоднозначностей. Они ведь могут возникать и от не очень аккуратного написания грамматик. А а грамматика без неоднозначностей читается уже куда как хуже. Да и усилий на ее переписывание нужно потратить не мало.
V>И, по моим исследованиям, "широкие" параллельные цепочки возникают редко.
Не проводил ты никаких исследований. Понятно же что ты просто трепишься. Иначе бы ты такой чуши про GLR-ы не нес.
V>Вернее, там такая зависимость — чем больше "параллельности", тем короче этот участок.
Ты даже не представляешь что дает одна только параллельность. Там из-за ветвления начинают появляться миллионы альтернатив. GLR их схлопывает в лес. За счет этого ему удается не уйти в астрал. Но все это требует не хилых вычислений. Плюс еще после того как этот лес будет построен его еще нужно отфильтровать выкинув тупиковые пути. У нас же можно сразу по внутреннему представлению осуществлять обход. По сути у нас тоже нечто похожее на лес, точнее граф. Но этот граф может быть обойден без фильтрации. Например, по нему мы сразу можем подсветить литералы и сгенерировать информацию для фолдинга (оутлайнинга) кода. АСТ строится по нему же. По сути можно вообще жить без АСТ, так как внутренее представление он и есть. Но это пока мы не потянули.
V>В языках программирования аналогично — неоднозначные места обычно очень "коротки".
Ну, вот любуйся на результат. Сравни время для С++ (175k), Явы (467k) и Питона (0.9К).
Плюс ты не понимаешь, что даже для языка для которого можно написать однозначную грамматику легко можно написать и неоднозначную.
V>А что касается константности — то это вопрос управления ресурсами.
V>В GLR необходимо уметь оперативно порождать конкурирующие ветки разбора корнем от текущей и так же оперативно убивать отмершие, т.е. текущей может стать одна из новых конкурирующих.
Разберись, что такое лес деревьев и как он используется GLR.
V>Тут даже представление нетерминалов, получаемых от лексера, и то важно. )) V>Я только на этом представлении умудрился скорость чисто парсинга поднять примерно вдвое. Т.е., включение парсера сверху лексера давало, скажем +20% ко времени работы "чистого лексера" (без парсера), а после вылизывания представления нетерминалов — всего 10% от чистого лексера. (Т.е. подключили к лексеру полноценный парсер, скорость потребления потока упала на 20% и 10% соответственно).
Ты что разбирал? Операцию сложения?
V>И так по каждому моменту этой "константы" — оно допиливается почти до скорости работы чистого лексера.
Т.е. даже шифт-редюсь у тебя бесплатные?
А построение дерева и его фильтрация видимо даже ускаряют разбор?
V>Далее. V>Так же утверждалось, что он есть ВСЕ контекстно-свободные грамматики. V>Т.е. пусть у нас даже будет сильно неоднозначная грамматика, данная сверху. V>Однозначно её распарсить можно лишь GLR (или любым другим параллельным алгоритмом, не боящимся рекурсий, типа Эрли).
Ляжет он на на этом, а не распарсит. n3 дождаться на сотне килобайт входных данных не выйдет.
V>К тому же, GLR — это алгоритм разбора, а не способ описания грамматики.
А кто кроме тебя их путает то? Это ты все откаты в ПЕГ-е пытаешься усмотреть.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, fddima, Вы писали:
F> Именно поэтому ни один нормальный фронтэнд не использует *L*. При этом местами могут применяться всякие выверты и оптимизации основанные на автоматах.
Согласен со всем, кроме вот этого про L, если под одной из звездочек не подразумевается G.
На ANTLR есть ряд фронтэндов. Да даже РеШарпервый парсер — это модифицированный парсер созданный старым ANTLR-ом. Ну, и наша Нитра показывает не плохие результаты:
В том числе и парсер. Можешь использовать его отдельно как компонент.
F>Это язык сам в себе.
Любой генератор парсеров имеет свой язык. Странно к этому претензии предъявлять.
F>Спасибо, но это не то что нужно.
Кому нужно? Зачем нужно? Может у тебя просто неверное понимание? Или банальный NIH?
F> (Хотя мне очень нравится инструмент). Проблема тока что авторы почему-то решили что бутстрап нужен только им — поэтому и имеют что имеют.
Ничего не понял. Причем тут бутсрап? И что значит "нужен только им"? Мы кому-то что-то запрещаем?
F> Насчет ваших споров с WH — это вообще ниочем. Господин WH выложит нормальный пейпер в пдф с выкладками — тогда и будет о чем говорить вообще. А так — видно что он в курсе — и все. Проблема что другие не в курсах. F> Для ANTLR4 с их ALL(*) выкладка в пдф вот есть.
Можно ссылку на то о чем идет речь?
F> А так — хваставство у обоих. Правда у WH — есть на что ссылаться. У тебя нет. Впрочем мне пофигу — я не рефери а тема интересна.
Ну, Нитру то можно загрузить и попробовать. Можно даже готовый язык загрузить и попробовать.
Здравствуйте, VladD2, Вы писали:
VD>Запомни на будущее. VD>1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
Пакрат это один из алгоритмов разбора ПЕГ. Можно и тупым рекурсивным спуском без мемоизации. На некоторых грамматиках оно будет даже быстрее. Но на других улетит в экспоненту.
Например это
В то же время нитра пакрат с возможностью переключится на Эрли, но не ПЕГ. Ибо приоритетного выбора там нет.
VD>2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
Ты не прав. Пакрат работает с откатами, но без повторного разбора.
Те если правило разбирается с того же места, то оно будет взято из мемоизации.
Но если во время разбора правила произошёл облом, то будет именно откат и попытка парсить другое правило.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, fddima, Вы писали:
F> Вопрос ровно в одном — дать коду стэк разбора. Если их предложить штук 100 — то ясен фиг будет порногоафия. Прошу учесть, что это не про нитру.
Нет никаких 100 стеков. Во всех обобщенных (или вроде того) парсерах вместо стека — граф в котором 100 вариантов сжаты в эдакие ромбы.
Основная проблема при этом грамотно протйтись по такому графу и создать логичную информацию об ошибках. Я этот код раза 3 переписывал, но вроде как сейчас он более менее не плохо работает. Конечно при условии, что восстановление прошло качественно. Если оно не угадало, то и сообщенния будут дрянь. Но такое редко бывает.
F> Т.е. ты считаешь что нисходящие (аля top-dow и recirsive-descent но тут я вообще подход имею ввилу — т.е более общем смысле) лучше?
Нисходящие падают на реальной ошибке. Т.е. когда парсер упал, то уже точно известно, что именно здесь ошибка. Бывают, правда, хитрые случаи, но они редки. А вот со свертывающими парсерами все плохо. Они падают во многих местах одновремнно и не ясно какое из них реальная ошибка. Если сделать восстановление, то найти наверно не сложно будет. Можно просто пройти по графу и найти самые первые восстановленные ветки.
F> видишь ли — люди не идиоты
Это спорный вопрос.
F>- они выбираюи самые трудоемкие способы но которые стабильные через десятилетия.
Я уже устал смотреть на совершенно необоснованный выбор людей. Для людей важнее не факты или рассуждения, а какие-то далекие от логики вещи вроде пира, того как сделали другие, какая фирма за этим стоит и т.п.
Что же касается использования рекурсивного спуска, то тут как раз все ясно. Большая часть ЯП им парсится или вообще без проблем, или небольшим объемом хаков. При этом можно получить наивысшую скорость и гибкость. Но процесс трудоемок, а код быстро превращается в говнокод. Плюс такие парсеры обычно являются бесполезными в IDE и т.п.
F> Однако, и у тебя и у меня возникает вопрос — неужели нельзя бы было сгенерить? Я уверен что можно. Вопрос чем — нитрой? А зачем? (нитрачисто бля примера, но я ещё раз повторю — на практике "до зачем" — другие нитровые вопросы стоят). не показатель, увы.
Вот в том то все и дело. Люди тупо делаю глупости которым нет объяснений. И это не лечится. Каждый ищет свои пути. Каждый пилит сам от забора и до обеда.
F> Насчет бутстрапа — мне кажется что любой вменяемый ЯП захочется бутстрапиться. С нитрой *пока* что это не выглядит возможным.
Смысл в бутстрапе в том, чтобы упростить разработку языка. Если ты делаешь ее на специализированном средстве, то бутсрапинг довольно глуп, если ты, конечно, не создаешь свой инструмент для разработке языков. Например, глупо заменять сгенерированный парсен на рукописный (если первый удовлетворяет запросам). Но любой язык содержит не только ДСЛ-и, но и кучу кода, которые ДСЛ-и не перекрывают. Вот для их можно спокойно переписывать на собственном языке.
F> Вместе с тем... вот сами прикиньте что такое язык котопый не умеет сам себя. Вот вы предлагаете делать именно такие.
Ну, как рыз мы то будем делать на Нитре новый Немерл, а потом бутсрапить Нитру на нем. Так что тут все ОК.
А, например, AMMY вообще невозможно забутстрапить, так как это специализированный язык.
F> Так и с нитрой — инструмент на сегодняшнмй — аховый. Я уже спрашивал... Влад очень подробно объяснил. Но, на сейчас: по факту — или ты живешь с рантаймом да ещё под дот нетом или бери любой другой инструмент (удовлетворяющий задаче).
Ну, так проблема с платформой то решается. Присоединяйтесь и помогите ее решить.
F> Ты пойми правильно — мои выпады о стратегии развития и они реальны. Даже если счтаешь что не так — то... да хер что ты изменишь. Огранияения вашей платфоры ж и так понятны. Но я и говорю.- что как же ж так. Какого хера что- бы это спортировать — нужно спортировать целый немерл?
Ну, не целый, а сабсэт используемый в Нитре. Ну, и Нитра она в том числе для этого и затевалась. По сути Нитра — это ДСЛ-и написанные на Немерле, чтобы создать новый Немерл, который будет ближе к идеалу. А уж дальше у него будет такая гибкость, что ты себе сможешь запилить хоть С++, хоть Дельфи.
F> Но ими можно доказать людям что впша придумка не фикция. Это раз. Во-вторых — профессору пришлось потратить 20 лет на эту статью.
Можно на нее ссылочку? О чем речь?
F>WH — ты вот недавно предложил человпку парсер в другом форуме — всё супер. Но... если бы ты дал ссылки на внешние ичточникм — было бы хорошо. Но ещё лучше — если бы ты описал все свои чаяния и/или нитра алгорттм в любой доступной тебе форме.Если профессор сука потратил 20 лет на сраный кеш правил и назвал это ALL — неужели ты не можешь что-то подобное совеошить? Тем более кау я слышал нитра там ошибки генерирует красивые.
Поддерживаю!
F> Имхо просто не все могут задачу осознать. Но короче — мое сугубое имхо — или ЯП с помощью нитры смогут сами себя компилировать (без ВМ разумееися). Либо...
Как ты себе это видишь? Выбросить специализированные языки решающие кучу проблем и переписать на ЯП общего назначения воспроизведя всю сложность?
Пиши прикладной код на своем языке. Его в любом случае будет море.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Нельзя. До сих пор все генераторы парсеров создавались для того чтобы статью в журнал написать. И к реальной работе пригодны небыли.
Вечно у тебя крайности. В реальности тот же АНТЛР — это волне себе качественный продукт. У нас над ним есть только преимущество в расширяемости и в том, что Нитра это не только парсер, а решение предоставляющее и мезанизмы типизации, бэкэнда и т.п.
WH>По крайней мере я до сих пор не слышал ни об оlном генераторе парсеров который создавался бы как инструмент для создания промышленных решений не уступающих рукописным парсерам. http://www.antlr.org/about.html
ANTLR is a powerful parser generator that you can use to read, process, execute, or translate structured text or binary files. It’s widely used in academia and industry to build all sorts of languages, tools, and frameworks. Twitter search uses ANTLR for query parsing, with over 2 billion queries a day. The languages for Hive and Pig, the data warehouse and analysis systems for Hadoop, both use ANTLR. Lex Machina uses ANTLR for information extraction from legal texts. Oracle uses ANTLR within SQL Developer IDE and their migration tools. NetBeans IDE parses C++ with ANTLR. The HQL language in the Hibernate object-relational mapping framework is built with ANTLR.
Aside from these big-name, high-profile projects, you can build all sorts of useful tools like configuration file readers, legacy code converters, wiki markup renderers, and JSON parsers. I’ve built little tools for object-relational database mappings, describing 3D visualizations, injecting profiling code into Java source code, and have even done a simple DNA pattern matching example for a lecture.
WH>>>Разница в том, что автор ANTLR4 профессор. Ему нужны статьи, а мне от них ни жарко, ни холодно. F>> Но ими можно доказать людям что впша придумка не фикция. WH>Нельзя.
Доказать может и нельзя, но вот доверия это бы добавило. Тем более, что скрывать нам особо нечего. Все наши алгоритмы — это компиляция из имеющихя. Разве что с восстановлением получилось что-то уже совсем уникальное. Но и оно из готовых блоков вроде Эрли.
WH>Алгоритм нитры это промышленное, а не академическое решение. И как следствие это не красивый алгоритм, а жуткий монстр. Примерно, как IntroSort (сборная солянка из нескольких сортировок) только намного сложнее.
Да ладно! Когда ты будешь описывать тебе не придется показывать этот код. Почитай статьи того же профеесора создавшего АНТЛР. Там ведь кода нет почти. Разве что псевдокод.
WH>Я устану его описывать.
Описать общие идеи было бы не плохо все же. Тут я с fddima согласен.
WH>Тем более что у меня есть желание неслабо его переделать.
Что-то оно уж больно долго зреет. Да и переделывать там надо не алгоритмы, а дорабатывать их чтобы контестную информацию можно было таскать. У нас сейчас главная проблема — невозможность котнекстнозависимых вещей вроде отступных грамматик парсить. У того же АНТЛР, в виду наличия лексера, с этим проблем нет. Так что мы ему в этом уступаем.
Та же фигня с инткрементальным парсингом. У Розлина он есть. А у нас нет. Файл на пару метров уже может и тормозить.
WH>Нужно только с духом собраться.
Вот чтобы его написать я пару реализаций в помойку пустил. И первые как раз с парсером возились, а не с АСТ-мо.
Сейчас уже гляжу и подробностей не помню. Помню только, что от души потрахался.
Вот если бы описал вовремя, то сейчас можно было бы впомнить. А теперь только код читать. Та же фигня и с алгоритмами парсинга будет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
