Здравствуйте, WolfHound, Вы писали:
VD>>Да я их и искать не собираюсь. Оно работает и этого достаточно. WH>В том то и дело что оно только вид делает что работает.
Ты как всегда преувеличиваешь. Он не просто работает, а разбирает реальные исходники. Хардкейс несколько проектов скомпилировал им.
VD>>Если надо мы можем сделать их автоматизированный поиск. WH>Не сможем.
Выявлять то полное перекрытие? Почему же? Сможем. Возможно не во всех случаях, но во многих сможем.
VD>>Для разруливания неоднозначностей. Мне не всегда нужно "самый длинный". WH>Например?
Простейший пример разрешение неоднозначности с if/else и if (без else). В одном случае надо выбирать ближний else, в другом — нет.
VD>>А зачем мне его форкать? Ну, вот скажем найдется очередной баг в парсере грамматик. Или захочу я его переписать по человечески без использования ручного разбора (на старой версии Пега). И что мне форкать проект? WH>А в чем проблема?
Их масса. Первая — нет прав на комит. Я могу разве что-ли локальный клон сделать.
Вторая — разные репозитории. Если мне требуется за одно поправить компилятор, то нужно делать два комита. Это же создает проблему вынимания исходинков и сборки в один клик.
Следующая проблема — дополнительное обучение.
VD>>В гите для этого есть брэнчи. Там тупо можно вести параллельные ветки и потом сливать их. WH>Ну так и форки без проблем можно сливать.
Видимо ты неверную терминологию используешь. Вилка (fork) это, как я понимаю, полное дублирование проекта. Искользуется когда кто-то хочет создать свое ответвление. А когда речь идет о совместной работе, то делают ветку (как я понимаю это у них называется брэнч). А для этого нужны права на репозиторий.
VD>>Можно конечно патчи слать и ждать пока ты их применишь и закомитешь, но это неудобно. WH>На гитхабе есть такая кнопочка "Pull Request" называется.
Я в курсе. Только это не очень удобно для реальной работы.
WH>Жмешь ее и мне приходит сообщение о том, что ты что-то сделал. WH>А я уже буду думать слить то, что ты сделал или нет.
Многие просто не будут начинать что-то делать, если их работу будут выбрасывать.
WH>>>Да и гугл код с меркури похоже толком работать не умеет. VD>>С чего ты это взял? WH>Так вроде там была куча проблем с клонированием репозиториев из-за чего все в одну кучу переползли.
Там была одна проблема — недоведенный до ума клиент. Сейчас его подтянули.
А та проблема о которой ты говоришь исходила из того что Ziaw неверно истолковал предназначение личных клонов которые поддерживает гуглькод. Как и в Гите в Меркури для совместной работы используются брэнчи и патчи. Клоном тоже можно пользоваться, но это будет просто клон репозитория. А клоны на гуглакоде — это просто частные копии в которых нельзя дать права другим.
VD>>Тогда нужно было уж переводить на меркури или гит (хотя эта идея мне не нравится) весь Н1. WH>Думаю что таки нужно это сделать. WH>SVN совсем достал.
Ну, достал или нет это отдельный вопрос. Разведение анархии это не оправдывает. От локальных удобств может пострадать все дело.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
V>>Ну вот ты и подставился. Перечитай еще раз замечания Влада и потом моё. Только на этот раз не по диагонали. WH>Это не я подставился, а ты в очередной раз нихрена не понял.
Гм...
Одна из проблем заключается в том, что для оптимизации правила надо инлайнить. Но для обработки ошибок это плохо (информация о правилах теряется).
Это оно в вашей реализации теряется, потому что Wolfhound не сохраняет к каждому оптимизированному правилу (т.е. к каждому вхождению элементов choice/sequence) всю цепочку подстановки исходных.
Я НЕ смотрел как у вас организована диагностика ошибок. Сам я делал таблицы соответствий наборов конфликтующих нетерминалов и текстов сообщений об ошибках. Эта фишка, кстати, плохо обобщается, потому как просто выдать все возможные положительные варианты на данном символе/лексеме — это не сильно помогает. Надо человеческий текст писать. А чтобы эта таблица соответствий работала, мне нужно на каждое состояние протянуть исходный нетерминал через все инлайн-подстановки. Итого, у меня их на каждом состоянии НКА получается обычно больше одного. И вот на "самые типичные" комбинации из них, эмпирически составляется таблица, где ключом является набор нетерминалов из всех "положительных" направлений возможного разбора (случай одного направления тоже туда вписывается).
Почему я вообще тут упомянул GLR? — потому как тоже восходящий разбор, похожая специфика, т.е. вся диагностика строится вокруг набора "положительных" вариантов продолжения парсинга из точки, в которой по текущему терминалу нет перехода. Когда вариантов продолжения больше одного, и это сочетание не выделено в таблице сообщений, я просто давал "Invalid syntax in position X,Y". Вот эти наиболее "популярные" invalid syntax и покрывал эмпирически вменяемыми сообщениями.
WH>Ну что за бред то? Как минимизированный может работать медленней?
Мы же имеем одинаковое число переходов для любых разбираемых лексем в обоих случаях. Но! За счет схлопывания (collapse) так же состояний, не являющимися конечными (в модели Мура), эти промежуточные состояния могут иметь больше ветвлений. Вот он, момент истины. Итого, по технологии кодогенеренного switch/case на каждом шаге у нас больше мощность перебора для вычисления следующего состояния в случае минимизированного автомата, хоть и меньше кода. Но переходов столько же. Но больше проверок на каждом шаге...
И я заранее оговаривался, что если делать в табличном виде, то практически идентично по скорости работают, совсем чуть-чуть минимизированный может оказаться быстрее лишь из-за размеров таблицы в памяти и всяких эффектов кешей.
Если на этот раз все-равно не согласен и не захочешь попробовать... то давай этот пункт тупо свернем. Уже по 10-му кругу одно и тоже во всех ветках...
WH>А как ты собрался минимизировать входной алфавит мне вообще не ясно. WH>Алфавит тут юникодные символы. Куда ты их минимизировать собрался то?
А я вообще не понимаю, как парсить по юникоду без минимизации алфавита?
Суть минимизации по алфавиту такова (на пальцах): берем символы, скажем '0'-'9', по всем ним идут идентичные переходы, т.е. все дуги в графе переходов по этому набору полностью параллельны. Заменяем через таблицу подстановки терминалы T0..T9 на один терминал T'. Затем, при работе, вместо десяти ветвлений из каждого состояния получаем одно. Либо, вместо проверки диапазона (2 сравнения) имеем одно сравнение. Латинские символы и прочие "общеюникодные" схлопываются еще лучше. "Наивный" алгоритм такого разбиения исходного алфавита на эквивалентные множества прост как три копейки, возможно, что существуют "продвинутые", я не интересовался. Хотя, ты можешь покумекать. Даю затравку — наивный алгоритм минимизации алфавита идентичен наивному алгоритму (Мура) минимизации по состояниям с точностью до разворота таблицы переходов. Я имею ввиду, что минимизация состояний — это минимизация по столбцам, а минимизация алфавита — это минимизация по строкам. И там и там суть алгоритма в разбиении исходного мн-ва на классы эквивалентности. Наивный алгоритм делает это за счет попарного перебора. Возможно, за счет этой изоморфности в сути алгоритмов, получится приспособить тот оптимальный алгоритм минимизации по столбцам (по твоей ссылке) к минимизации по строкам. Но сие не принципиально.
Продолжаем.
В итоге, у меня никогда не получалось подстановочных терминалов T' более 255 штук (3-4 десятка в среднем), т.е. это уже кодирование в байт, т.е. таблица преобразований из юникода ровно в 64к байт. Правда, я там делал две таблицы преобразования — одну до кода 127 (как самую частую), другую — общую до 64к. На эффектах линий кешей еще кое-какие копейки в итоге выжимаются на ACII-ориентированном потоке, но не принципиальные.
Кроме того, коды T' надо отсортировать по частоте использования в дугах. Чем чаще используется, тем меньший код надо присвоить. Тоже кое-какие копейки прироста дает.
Далее, когда требовался safe и всё происходило динамически (т.е. без кодогенерации, по табличному варианту), после преобразования алфавита есть возможность поступать крайне цинично (в случае лексера): для каждого состояния находится максимальный код терминала T' в исходящей дуге, и просто выделяется массив длиной T'+1 для переходов. Потом, во время работы ДКА, я выбираю следующее состояние БЕЗ проверки на выход за границы массива. Среда и так проверяет, а если мимо и я поймал эксепшен — то там скорость уже не особо нужна, ведь затык лексера — это откат на начало неудачной лексемы, сдвиг (иногда ручной) и новый разбор. Сортировка по частоте делает средний размер таких массивов в единицы элементов. В случае null в таблице переходов так же цинично ничего не проверяю, просто ловлю эксепшен. Итого 2 сэкономленных if тоже кое-какие копейки дают. В общем, по мелочам в 2 раза и больше от начальной эффективность набегала.
WH>2)Нахрена мне неоднозначные грамматики? Я делаю парсер для разбора языков программирования. А они однозначны.
GLR на однозначных еще лучше работает. А парсеры не только для ЯП используют.
И вообще, низкоуровневую "механику" как раз лучше профилировать на несложных грамматиках, где откатов будет меньше всего (или не будет вообще). А уж сами откаты после профилирования механики оптимизировать независимо. Это я насчет того, что в случае парсера по грамматике C# там много чего сидит и друг на друга влияет. Для конечного сравнительного тестирования оно может и хорошо, но для профилирования — наихудший вариант.
Здравствуйте, VladD2, Вы писали:
VD>Я вот перечитал и не понял в чем он подставился.
В пальцах веером. Очередная попытка кого-то принизить не разобрамшись. Я ему ответил максимально подробно, хоть это и стоило мне некоторого времени. Скорее, для читателей, ибо личный спор с удивительной повторяемостью заканчивается в манере "дурак"/"сам дурак"..
VD>Пробелема в том, что надо понять какое из правил обломалось при зазборе. Вычислить список правил которые могут идти после него не сложно и по исходной грамматике. Но вот отловить то правило что обломалось можно только если правило не заинлайнено.
Ну я там чуть подробней ответил, чем ты сейчас объясняешь. Просто я исхожу из того, что вы знаете, о чем речь, а вы не исходите из того же о собеседнике. Поверь, не вы придумали восходящий разбор. Да, проблема диагности в восходящем разборе — это классическая головная боль парсерописателей.
VD>У нас при обломе правила его индекс пишется в специальную переменную.
В общем случае происходит "облом" сразу нескольких возможных правил. Я же продолжаю спраишивать: в чем проблема протянуть подстановочные нетерминалы вплоть даже до узла генерируемого ДКА? Да, их там целый список получится в случае нескольких подстановок. И что?
VD>Но если правило заинлайнено и слито с другими, то понять что обломалось именно оно невозможно, так как прямой код правило уже не порождает.
А разве вариант, когда у нас идет выбор (choice) не та же проблема мн-ва обломанных вариантов? У меня хранилось в итоге в узлах/состояниях автомата (список списков правил-родителей). Потеряться ничего не могло. Сами целевые нетерминалы — статические данные. Сослаться на них откуда угодно несложно.
VD>Молодец. Только ни все как один дикие тормоза.
Исключительно от грамматики и данных зависит. В одном из применений мне парсеры с откатами не подходили вообще. Представь, несколькомегабайтный документ имеет неоднозначность, которая ресолвится лишь на последних его символах, угу. Так вот, он парсится себе GLR-парсером, который протягивает два варианта разбора сквозь весь документ, и на последних символах один из них отбрасывает. Это стоимость двух паралельных ДКА. Теоретически. А фактически — выборка по одной и той же таблице, один и тот же входной поток в кеше, и т.д., а на всё это тратится грубо 90% работы ДКА, и 10% — собственно переход. Т.е. там каждый параллельный вариант грубо требует +10% затрат. А если же использовать откат на начало — то это чистое удвоение. А если откатов больше — вообще хана.
VD>Последнее заявление гнусный п...ж. Пока что нет ни одного GLR-а дающего приемлемую скорость разбора. Они все как один тормоза.
Тормозом может быть конкретная реализация.
VD>Плюс еще сообщения об ошибках формируют ужасные (как все LR-ы).
Проблематика сообщений об ошибках у вас такая же.
VD>Ну, нам GLR никак не поможет. Нам нужна динамическая расширяемость. А GLR-ы все как одни на ДКА. Что с динамикой не вяжется.
На НКА, вообще-то. И эти НКА, по природе своей легко расширяемы.
VD>Плюс они лексерные. А это тоже приговор расширяемости.
Ну ты в курсе, что вы с Wolfhound в таких случаях говорите? http://en.wikipedia.org/wiki/ASF%2BSDF_Meta_Environment
Еще смотреть DParser или абревиатуру SGLR (scannerless GLR).
V>>Единственная динамически выделяемая память была уже за пределами парсера — это непосредственное построение электронного док-та. Т.е., заметь, на каком уже уровне идет борьба за эффективность.
VD>Заметь уровень высокий, а выхлоп нулевой.
Заметь, парсер парсит со скоростью лексера.
VD>А ты думаешь мы лаптем щи хлебаем? Ты создай парсер C# 4 и попробуй с нами потягаться. Уверен на 99% что все GLR-ы сольют и позорно.
Для начала было бы неплохо на чем-нить попроще.
V>>Как сказал, упирался уже непосредственно в эффективность символьного буфера (эти тормозные массивы дотнета!!!), в избавление от лишних копирований, в использовании файлового АПИ ОС напрямую для зачитки в unmanaged буффер и в лексере этого unsafe тоже хватало уже, бо уже играет рояль. Понятное дело, что на 4MB/c лезть в эту оптимизацию смысла нет вообще, это еще не тот порядок цифр.
VD>Когда ты обеспечишь 4 метра на грамматике C# 4, тогда мы с тобой что-то обсудим. А пока я склонен считать тебя трепачем. Без обид.
Сколько времени заняла разработка у вас этой грамматики до текущего варианта? И где гарантии, что она не содержит ошибок? И вообще, смысл предлагать тягаться на эксперименте, стоимостью в несколько рабочих дней оппонента? Чтобы заранее получить отказ? Надо брать что-то более реальное. А потом смотреть, есть ли смысл тягаться дальше.
VD>Блин! Да нет там никокого АСТ в тот момент что нужно. Нееет! Там код сгенерированный. И в нем ссылку не положишь.
Мде. А как ты думаешь, сколько здесь может быть вариантов, разрулить ситуацию? 5/10/20? Что-то вы за свою конкретику реализации уцепились, не оторвать. Я же не спорю, что в некий ваш текущий внутренний АПИ не положишь. Ну не предусмотрели пока, ну и что? Будете с диагностикой бодаться — предусмотрите. Либо выкинете нафиг в мусорку всю затею, делов-то.
Здравствуйте, alvas, Вы писали:
A>Я так понял что ты планируешь у PegParser'a только внутренности менять, a снаружи он останется таким же. A>Я прав или стоит волноваться?
По идее, если убрать оператор приоритета, а оставить только оператор равнозначного выбора, то "снаружи" очень даже неплохой интерфейс выходит для задания модульной грамматики. А что там внутри — какая фиг разница. Народ и комбинаторы GLL делает, и SGLR и всё в этом духе.
В текущем виде с приоритетами PEG смущает меня этим:
PEG advocates use the fact that PEGs can never be ambiguous as a selling point. I think it's harmful, because it means that you never know where the ambiguity actually is. In a PEG, if you write:
a: b / c;
... you don't know if there could be situations where "b" and "c" could both match. Imagine that b is "if/then/else" and c is "if/then" (the classic case of ambiguity). With PEGs you are explicitly resolving this ambiguity to say that else's always bound to the most recent "if", but you don't realize you've done this because you PEG tool will never warn you that an ambiguity ever existed! Remember that this ambiguity is a user-facing issue that needs to exist in the documentation for your language ("else's always bind to the most recent if"), but with PEGs you're flying blind about where these user-facing ambiguities actually lie.
With a PEG, you never know if changing "a: b / c" to "a: c / b" changes your language or not.
Т.е. по его входной грамматике нельзя узнать св-ва этой грамматики. Из-за проблемы останова. На разных данных разные св-ва.
Вот интересное что-то нарыл. http://www.reverberate.org/gazelle/
Автор периодически хорошо припечатывает PEG за его "расхлябанность", и обещает избавление от всех проблем за такое же или лучшее время.
Здравствуйте, vdimas, Вы писали:
V>И то был польщен, что для целого класса грамматик умудрился оптимизировать оригинальный (тоже достаточно "наивный") алгоритм до случая, когда операци "свертка" не нужна, что тоже дает приличный буст быстродействия. До сих пор руки не доходят качественно прошерстить интернет на этот счет — есть ли публикации на эту тему, или все-таки опубликовать под своим именем. Несколько раз искал — пока этой разновидности не видел...
Trace based parsing extends a parsing scheme that is known since Ken Thompsons work [1] of the late 60s about parsing regular expressions using nondeterministic finite atutomata (NFAs). It is used in Trail to parse languages using general context free grammars in EBNF format.
А почему свертка иногда не нужна, гы:
For LL(1) grammars trace based parsing collapses to NFA driven LL(1) parsing with O(n) complexity on the length of the input token stream.
Прикол в том, что на этих участках при разборе НКА превращается в ДКА. Еще прикол в том, что парсятся любые грамматики, но агрессивная оптимизация EBNF.
V>Ооо, это отдельная тема. Я экспериментировал где-то в 2004-м с не LL(1)-грамматиками и автоматным разбором для них. Так вот, если сейчас для классического LL(1)-парсера отдельно выделяет лексер и отдельно парсер, и всего этих звеньев два (нетерминалы предыдущего звена являются терминалами следующего), то этих звеньев можно больше. Например, 3 звена (лексер->LL(1)->LL(1)) справлялись с "отрывком" синтаксиса C# 1.0, который не разбирался классическим лексер->LL(1) без перехвата сигналов и коррекции состояния (т.е. не разбирался без костылей).
Этот гаденыш украл у меня всё! По миру пустил:
For non left factored grammar rules Trail modifies LL(1) parsing by carefully embedding NFA transition tables into each other. This step is called NFA expansion.
Наверняка RSDN через google translate читает, упырь.
Здравствуйте, WolfHound, Вы писали:
WH>Это тема про лень... и на реальных грамматиках ты охренеешь делать факторизацию просто по тому что она не делается.
VD>>>В гите для этого есть брэнчи. Там тупо можно вести параллельные ветки и потом сливать их. WH>>Ну так и форки без проблем можно сливать.
VD>Видимо ты неверную терминологию используешь. Вилка (fork) это, как я понимаю, полное дублирование проекта. Искользуется когда кто-то хочет создать свое ответвление. А когда речь идет о совместной работе, то делают ветку (как я понимаю это у них называется брэнч). А для этого нужны права на репозиторий.
Да, форк — это будлирование проекта. В этом — весь цимес распределенных VCS. Когд аты делаешь git clone (грубо говоря аналог svn checkout), То ты получаешь полную самостоятельную копию проекта. При чем ты ее можешь колбасить, как хочешь, а потом просто заливать изменения через pull requrests в основной/главный. Причем твоя копия может спокойно выместить главную, если в ней развитие быстрее идет
Pull requests позволяют контролировать, что, кто и когда именно вливает изменения в проект.
Бранчи там тоже есть, и работают сверхмегашустро (как и все остальное в git'е (и mercurial'е тоже)) по сравнению с svn. По бранчингу в git'е самая лучшая статья вот: http://nvie.com/posts/a-successful-git-branching-model/ Там же коротенько и про pull, push и т.п.
Здравствуйте, tmp4857, Вы писали:
VD>>Он уже был выше.
T>Не вижу
И кто виноват? Я тебе раз пять уже давал ссылку на грамматику C# 4. Это реальная, не тривиальная грамматика. Причем без особых сложностей. Думаю, что уже на ней ты получишь ощутимые проблемы.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Mamut, Вы писали:
M>Да, форк — это будлирование проекта. В этом — весь цимес распределенных VCS. Когд аты делаешь git clone (грубо говоря аналог svn checkout), То ты получаешь полную самостоятельную копию проекта. При чем ты ее можешь колбасить, как хочешь, а потом просто заливать изменения через pull requrests в основной/главный. Причем твоя копия может спокойно выместить главную, если в ней развитие быстрее идет
Я в курсе приципов работы git, так пользовался Меркури, а у них все примерно одинаково.
Но чтобы делать push все равно нужно иметь права на репозиторий. Или это будут два совершенно разных проекта. Потому когда люди работают над одним проектом, то используют бранчи. Или просто комитят по очереди и сливают изменения. Чем чаще сливаются изменения, тем проще их сливать в будущем.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
VD>>Я вот перечитал и не понял в чем он подставился. V>В пальцах веером. Очередная попытка кого-то принизить не разобрамшись.
В вопросе обнаружения ошибок ты явно не шаришь. Тут нужно понимать не общие приципы, и тем более GLR, а то какой код генерируется нашим генератором.
V>Я ему ответил максимально подробно, хоть это и стоило мне некоторого времени. Скорее, для читателей, ибо личный спор с удивительной повторяемостью заканчивается в манере "дурак"/"сам дурак"..
Твой ответ только доказал, что ты отвечаешь не шарая в вопросе.
VD>>Пробелема в том, что надо понять какое из правил обломалось при зазборе. Вычислить список правил которые могут идти после него не сложно и по исходной грамматике. Но вот отловить то правило что обломалось можно только если правило не заинлайнено.
V>Ну я там чуть подробней ответил, чем ты сейчас объясняешь. Просто я исхожу из того, что вы знаете, о чем речь, а вы не исходите из того же о собеседнике. Поверь, не вы придумали восходящий разбор. Да, проблема диагности в восходящем разборе — это классическая головная боль парсерописателей.
Ты исходишь из своих домыслов. Вот и сейчас ты несешь какой-то бред про восходящий разбор в то время как даже ребенку очевидно, что PEG парсится нисходящим (top-down) разбором. Соответственно проблем "диагностики в восходящем разборе" у нас нет. У нас есть проблема выявления правила которое обломалось в момент когда текущий индекс имел максимальное значение. Если не делать инлайнинг, то этой проблемы нет. Но если делать, то некоторые "терминальные" правила сливаются и перемешиваются, что мешает диагностики. Кроме того код сохраняющий эту самую позицию облома тоже кое что стоит. И пихать его в "терминальные" правила дороговато, так как они занимаются "числодроблением".
Я не понимаю почему ты в десятый раз несешь какую-то пургу на основании своих домыслов. Попробуй просто понять, что у нас другие алгоритмы и другие подходы, а соответственно и другие проблемы.
VD>>У нас при обломе правила его индекс пишется в специальную переменную.
V>В общем случае происходит "облом" сразу нескольких возможных правил.
Ну, ты еще мне расскажи как у нас что работает. Парсинг мы не параллелим. Так что одного за раз.
V>Я же продолжаю спраишивать: в чем проблема протянуть подстановочные нетерминалы вплоть даже до узла генерируемого ДКА? Да, их там целый список получится в случае нескольких подстановок. И что?
Уважаемый! Проблема в том, что ты пытаешься в наших алгоритмах видеть свои!
В момент когда работает парсер никаких нетерминалов нет. Есть рекурсивные функции производящие нисходящий разбор. Так вот когда речь идет о код генерируемом для правил идущих не на самых листовых ветках грамматики (напомню, что у нас нет лексера и его правила как бы смешаны с основными, а стало быть именно они являются листовыми), то мы имеем информацию о том для какого правила генерировался код и "по else" (т.е. при обломе правила) можем запомнить текущую позицию разбора в переменную ассоциированную с этим правилом. Но когда речь идет об оптимизированных правилах, код которых встраивается в код других правил и при этом еще и переставляется по много раз, определить что же за правило реально обломалось не выходит. Классический пример такого правила — это разбор ";" в грамматике C#. Правило слишком мелкое, не имеет обработчика и тупо инлайнится в другие. Приходится в парсере вставлять никому не нужный обработчик чтобы правило не инлайнилось и получалось четкое сообщение об ошибке. Но это негативно влияет на производительность.
В принципе можно было бы тупо забить на инлайнинг и генерить одинаковый код для любого правила. Но это привело бы к генерации моря лишних проверок и присвоений в "терминальных" правилах. Ведь надо не забывать, что у нас код "лексера" размазан по всему парсеру. И даже простейшие проверки литералов будут запоминать информацию об обломе. А это уже плохо не только с точки зрения производительности, но и с точки зрения осмысленности сообщений об ошибках. Ведь мало толку от информации, что в точке облома ожидался юникодная буква или число (при разборе идентификатора, например).
VD>>Но если правило заинлайнено и слито с другими, то понять что обломалось именно оно невозможно, так как прямой код правило уже не порождает.
V>А разве вариант, когда у нас идет выбор (choice) не та же проблема мн-ва обломанных вариантов?
Нет там никакой проблемы. Читай выше. С приоритетным выбором как раз все ОК. В конце ставится один else в котором и запоминается позиция облома. Только она почти наверняка не интересна.
V>У меня хранилось в итоге в узлах/состояниях автомата (список списков правил-родителей). Потеряться ничего не могло. Сами целевые нетерминалы — статические данные. Сослаться на них откуда угодно несложно.
Блин. Ну, нет там никаких узлов. Нету! Там код. Код запоминания позиции облома встраивается только в правила которые имеют обработчики (семантические действия).
VD>>Молодец. Только ни все как один дикие тормоза.
V>Исключительно от грамматики и данных зависит.
Конечно, конечно. Но ни одного шустрого пока свету не предявлено. Наверно их скрывают в закромах противопригарных решений .
V>В одном из применений мне парсеры с откатами не подходили вообще. Представь, несколькомегабайтный документ имеет неоднозначность, которая ресолвится лишь на последних его символах, угу.
Ага. Если не знаешь про мемоизацию, то можно кормить себя и такими сказками.
V>Так вот, он парсится себе GLR-парсером, который протягивает два варианта разбора сквозь весь документ, и на последних символах один из них отбрасывает. Это стоимость двух паралельных ДКА.
Не малая стоимость, в общем-то. В прочем, теоретических рассуждений можно построить много. Ты тут уже не раз хвалил свой парсер. Давай проведем простой эксперемент. Воссоздай парсер шарпаа который на выход выдаст АСТ. Сделаем тест в котором сравним полученное АСТ (чтобы видеть, что никто не врет) и сравним скорость разбора.
V>Теоретически. А фактически — выборка по одной и той же таблице, один и тот же входной поток в кеше, и т.д., а на всё это тратится грубо 90% работы ДКА, и 10% — собственно переход. Т.е. там каждый параллельный вариант грубо требует +10% затрат.
Вот это и есть — теоретически. А практически — тормоза .
V>А если же использовать откат на начало — то это чистое удвоение. А если откатов больше — вообще хана.
Этот вывод тоже от теоретизирования. На практике похожие грамматики имеющие разницу где-то в хвосте обычно состоят из общих подправил. А результат их разбора кэшируется. Так что когда пойдет повторный разбор, то его не будет, а результаты будут взяты из кэша.
VD>>Последнее заявление гнусный п...ж. Пока что нет ни одного GLR-а дающего приемлемую скорость разбора. Они все как один тормоза.
V>Тормозом может быть конкретная реализация.
Твоя достаточно крута? Ну, так докажи нам всем свою правоту. Предъяви парсер реального языка чтобы мы могли оценить его быстродействия.
VD>>Плюс еще сообщения об ошибках формируют ужасные (как все LR-ы).
V>Проблематика сообщений об ошибках у вас такая же.
У нас ее нет. У нас низходящий парсер мало отличающийся от рукописного. И сообщения получаются очень даже внятные. Плюс естественная стратегия восстановления после обнаружения ошибки. Наши проблемы в деталях оптимизации. И они не глобальны.
VD>>Ну, нам GLR никак не поможет. Нам нужна динамическая расширяемость. А GLR-ы все как одни на ДКА. Что с динамикой не вяжется.
V>На НКА, вообще-то. И эти НКА, по природе своей легко расширяемы.
Любой КА плохо расширяем. Даже то что у тебя отдельный лексер — это уже усложнение расширяемости.
Вот тебе задачка из реальной жизни. Есть язык — Nemerle. Он парсит входной поток и если обнаруживает открытие пространства имен, то импортирует новые правила (описанные в виде макросов). Ну, и что на ходу будешь перестраивать свои НКА? А что если экспонента получится?
А НКА — это еще и приговор производительности. И я тогда вообще не понимаю о каких таблицах ты там говоришь, если у тебя НКА.
Весь кайф PEG-а заключается в том, что он идеологически очень хорошо расширяется. Каждое правило по сути отдельный парсер. Для динамического расширения нам всего лишь надо сделать правило приоритетного выбора массивом и тупо дергать подправила из него.
VD>>Плюс они лексерные. А это тоже приговор расширяемости.
V>Ну ты в курсе, что вы с Wolfhound в таких случаях говорите?
Я в курсе всего этого. Все делится на два класса. Плохо расширяемые реализации и тормозные. SGLR — это не просто тормоза, а дикие тормоза.
Назови хотя бы одну реализацию GLR которая может расширяться динамически. Нет таких? А почему?
V>>>Единственная динамически выделяемая память была уже за пределами парсера — это непосредственное построение электронного док-та. Т.е., заметь, на каком уже уровне идет борьба за эффективность.
VD>>Заметь уровень высокий, а выхлоп нулевой.
V>Заметь, парсер парсит со скоростью лексера.
Докажи это. Тогда поговорим. В прочем, это чушь даже с точки зрения теории. Парсер рекурсивных грамматик не может работать со скорость парсера нерекурсивных.
VD>>А ты думаешь мы лаптем щи хлебаем? Ты создай парсер C# 4 и попробуй с нами потягаться. Уверен на 99% что все GLR-ы сольют и позорно.
V>Для начала было бы неплохо на чем-нить попроще.
По проще тебе же не выгодно будет. Да и неинтересно это. Реальные применения — это же языки программирования. Именно для них писать парсеры вручную тяжело. И именно при их создании получаются весьма неприятные эффекты в грамматиках (просто потому, что сложность велика и разложить все по полочкам создатель грамматики не может).
В прочем, можешь для начала тот же Джейсон повторить.
V>Сколько времени заняла разработка у вас этой грамматики до текущего варианта?
Неделю времени неподготовленного человека.
V>И где гарантии, что она не содержит ошибок?
Прогоны на массе реального кода. Это конечно не 100%-я гарантия, но все же.
Потом нет проблем сравнить полученное АСТ. Этот код мы напишем. От тебя потребуется только сгенерировать это АСТ. Можно тупо взять наше АСТ. Тогда вообще тесты будут 1 в 1.
V>И вообще, смысл предлагать тягаться на эксперименте, стоимостью в несколько рабочих дней оппонента? Чтобы заранее получить отказ? Надо брать что-то более реальное. А потом смотреть, есть ли смысл тягаться дальше.
Нет смысла тягаться на синтетике. Такие тесты ничего не покажут. Мы сделали парсер C# в основном с целью отладки технологий PegGrammar.
Если ты считаешь свой генератор парсеров коммерческим продуктом высокого качества, то тебе самому будет не лишним иметь хороший демонстрационный пример этого самого качества. Плюс ты сможешь не на словах, а на деле доказать применимость GLR, что будет несомненно интересно в научных кругах.
VD>>Блин! Да нет там никокого АСТ в тот момент что нужно. Нееет! Там код сгенерированный. И в нем ссылку не положишь.
V>Мде. А как ты думаешь, сколько здесь может быть вариантов, разрулить ситуацию? 5/10/20? Что-то вы за свою конкретику реализации уцепились, не оторвать.
Потому что на интересует только она.
V>Я же не спорю, что в некий ваш текущий внутренний АПИ не положишь. Ну не предусмотрели пока, ну и что? Будете с диагностикой бодаться — предусмотрите. Либо выкинете нафиг в мусорку всю затею, делов-то.
Ты лезешь учить других не разобравшись в их задачах. Мы, несомненно, поборем эту проблему. Но для того чтобы при этом не получить других (например, проблем производительности) нужно делать это с умом.
Твои же некомпетентные советы только раздражают (или веселят). Мы же те советуем тебе как оптимизировать или развивать твой GLR-парсер? Это потому что мы не знаем деталей и не хотим кидаться пустыми словами. Вот и ты попробуй так же.
А то ты говоришь о том, что Вольфхаунд гнет пальцы, а сам со стороны выглядишь не лучше.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>И кто виноват? Я тебе раз пять уже давал ссылку на грамматику C# 4. Это реальная, не тривиальная грамматика. Причем без особых сложностей. Думаю, что уже на ней ты получишь ощутимые проблемы.
Ты явно забыл, о чем шла речь
VD>>А вообще, достаточно одного правила экспоненциального. Поищи, в этом форуме было обсуждение по этому поводу. T>Ну это чистая патология. Надо еще очень постараться, чтобы этого добиться. VD>Этого элементарно добьется первый же не очень искушенный в грамматиках и парсерах пользователь. Ну, или искушенный когда начнет создавать сложный парсер. T>Дай какой-нибудь реальный пример
Здравствуйте, VladD2, Вы писали:
VD>Ты как всегда преувеличиваешь. Он не просто работает, а разбирает реальные исходники. Хардкейс несколько проектов скомпилировал им.
То что на реальных исходниках не проявился соответствующий баг ни о чем не говорит.
Тесты не являются доказательством работоспособности.
VD>Простейший пример разрешение неоднозначности с if/else и if (без else). В одном случае надо выбирать ближний else, в другом — нет. Если ты поставишь if до if/else то if/else у тебя никогда не сматчиться.
Учи правила ПЕГ.
Это кстати еще одно доказательство того что приоритетный выбор ты не понимаешь.
Он вообще крайне не интуитивный.
VD>Их масса. Первая — нет прав на комит. Я могу разве что-ли локальный клон сделать.
И правильно. Нехрен лить в основной репозиторий что попало.
VD>Вторая — разные репозитории. Если мне требуется за одно поправить компилятор, то нужно делать два комита. Это же создает проблему вынимания исходинков и сборки в один клик.
А меня это бесит.
Втянули прототип парсера в сборку и теперь блин не поломай
Даже локально поломать нельзя, ибо компилятор обновлять не получается.
VD>Следующая проблема — дополнительное обучение. минут за 10-20 разобрался с тем, что к чему.
VD>Видимо ты неверную терминологию используешь. Вилка (fork) это, как я понимаю, полное дублирование проекта.
И замечательно.
VD>Искользуется когда кто-то хочет создать свое ответвление. А когда речь идет о совместной работе, то делают ветку (как я понимаю это у них называется брэнч). А для этого нужны права на репозиторий.
Это ты нихрена не понял.
Это представление у тебя сложилось по тому что гуглокод толком не умеет работать с клонами.
Правильный метод это именно работа в своем клоне.
А дальше pull request https://github.com/IgorTkachev/bltoolkit/pulls
Посмотри сколько ИТ уже закрыл...
Если тебе так хочется работать толпой, то можно и толпой.
Добавляешь в свой репозиторий collaborators и все.
Причем в форк (в отличии от гуглокода) тоже можно добавить.
VD>Я в курсе. Только это не очень удобно для реальной работы.
Как видишь кучу народа с этим прекрасно работает.
Более того это очень удобно для "одноразовых" коммитеров.
Они ни кого не спрашивая делают свой форк.
Потом правят что хотят.
А потом в пару кликов отправляют запрос на интеграцию в основной код.
VD>Многие просто не будут начинать что-то делать, если их работу будут выбрасывать.
Если это правки по делу, то никто ничего выбрасывать не будет.
Если правка по делу, но кривая то будут высказаны пожелания по исправлению. И после исправления правка будет принята.
А если там мусор то извините.
VD>А та проблема о которой ты говоришь исходила из того что Ziaw неверно истолковал предназначение личных клонов которые поддерживает гуглькод.
Нет. Это ты не понял.
См выше.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Я в курсе приципов работы git, так пользовался Меркури, а у них все примерно одинаково. VD>Но чтобы делать push все равно нужно иметь права на репозиторий. Или это будут два совершенно разных проекта. Потому когда люди работают над одним проектом, то используют бранчи. Или просто комитят по очереди и сливают изменения. Чем чаще сливаются изменения, тем проще их сливать в будущем.
Бранч и форк в DVCS по сути одно и то же, и там и там делаются разные ветки разработки и там и там их потом можно слить. На гитхабе есть штатные механизмы сделать пулреквест в проект из форка. Хозяин проекта пулит к себе в репо изменения из пулреквеста.
Здравствуйте, vdimas, Вы писали:
V>Почему я вообще тут упомянул GLR? — потому как тоже восходящий разбор, похожая специфика, т.е.
Ой звездец. ПЕГ это нисходящей анализ.
V>Если на этот раз все-равно не согласен и не захочешь попробовать... то давай этот пункт тупо свернем. Уже по 10-му кругу одно и тоже во всех ветках...
Так я попробовал. Разницы не заметил.
V>Суть минимизации по алфавиту такова (на пальцах): берем символы, скажем '0'-'9', по всем ним идут идентичные переходы, т.е. все дуги в графе переходов по этому набору полностью параллельны. Заменяем через таблицу подстановки терминалы T0..T9 на один терминал T'. Затем, при работе, вместо десяти ветвлений из каждого состояния получаем одно. Либо, вместо проверки диапазона (2 сравнения) имеем одно сравнение.
А превращение T0..T9 в T' у нас бесплатно и делается святым духом?
V>В итоге, у меня никогда не получалось подстановочных терминалов T' более 255 штук (3-4 десятка в среднем), т.е. это уже кодирование в байт, т.е. таблица преобразований из юникода ровно в 64к байт. Правда, я там делал две таблицы преобразования — одну до кода 127 (как самую частую), другую — общую до 64к. На эффектах линий кешей еще кое-какие копейки в итоге выжимаются на ACII-ориентированном потоке, но не принципиальные.
Ты главное не забывай про одно маленькое, но противное функциональное требование к моему алгоритму: Динамическое изменение грамматики.
V>GLR на однозначных еще лучше работает. А парсеры не только для ЯП используют.
Нут вот пусть они что-то другое и используют.
Я делаю разбор для ЯП.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>>>Я вот перечитал и не понял в чем он подставился. V>>В пальцах веером. Очередная попытка кого-то принизить не разобрамшись.
VD>В вопросе обнаружения ошибок ты явно не шаришь. Тут нужно понимать не общие приципы, и тем более GLR, а то какой код генерируется нашим генератором.
А что первично? Яйцо или курица? Не, ну представсьте, что у вас не добровольное товарищество, а работаете за деньги, и вам поставили такую задачу. Вы бы решение подгоняли под задачу или задачу под имеющееся решение, как ты пытаешься делать?
VD>Ты исходишь из своих домыслов. Вот и сейчас ты несешь какой-то бред про восходящий разбор в то время как даже ребенку очевидно, что PEG парсится нисходящим (top-down) разбором.
Ох, ну ты и красавец. А что происходит, когда вы правила инлайните, не судьба была сообразить? Ну просто на бумаге распиши, что произойдет, если по некоему правилу полностью всё заинлайнить (чтобы легче было увидеть). А потом построй кусок ДКА по этому правилу, а потом сравни с построением НКА/ДКА GLR, и посмотри, наконец, почему же там не теряется информация о нетерминалах, хотя всё "заинлайнено" по самое нихочу, т.е. непосредственно до НКА/ДКА.
VD>Соответственно проблем "диагностики в восходящем разборе" у нас нет.
Да все ясно, можно сворачивать. Я поторопился предположить, что вы понимаете проблематику. Думал, оно же очевидно, и стоит только намекнуть на такую вещь как "свертка". Тогда еще один намек: "сдвиг" в LR — это и есть собсно накопление цепочки терминалов, как делает ДКА сканер по мере движения по входному потоку.
VD>У нас есть проблема выявления правила которое обломалось в момент когда текущий индекс имел максимальное значение. Если не делать инлайнинг, то этой проблемы нет. Но если делать, то некоторые "терминальные" правила сливаются и перемешиваются, что мешает диагностики.
Боже, Влад, ну детский сад. Завязывай. Понятное дело, что если сливать все цепочки правил до уровня "плинтуса", т.е. ДКА (как у вас), то исходные правила теряются, если ничего специально не предпринимать. Ты всерьез считаешь, что мы тут уже 10-й раз это обсуждаем и собеседник не может в это воткнуть? Ну и как с вами дальше общаться? Бесконечно отсылать к первому посту в ветке?
VD>Кроме того код сохраняющий эту самую позицию облома тоже кое что стоит. И пихать его в "терминальные" правила дороговато, так как они занимаются "числодроблением".
Тут речь идет об одном if, для отделения "конечного" состояния (состояния на границе корректно разобранной цепочки терминалов/нетерминалов) от промежуточного. Обычный же лексер тоже на каждом шаге проверяет — является ли состояние конечным? Иначе бы парсил бесконечно.
VD>Я не понимаю почему ты в десятый раз несешь какую-то пургу на основании своих домыслов. Попробуй просто понять, что у нас другие алгоритмы и другие подходы, а соответственно и другие проблемы.
Эх, "работники передового края"... Извини, но продолжаю склоняться к тому, что это первый ваш парсер в истории, который с "0-ля" (в отличии от твоего R#). И вы там делаете кое-какие преобразования грамматики, но не способны оказались понять, что же это за преобразования такие у вас получаются.
Все ясно, можно взять паузу, потом вернемся, коль желание будет. Хотя уверен, теперь справитесь и так, бо теперь даже мне понятно, что именно тебе было не понятно.
VD>Уважаемый! Проблема в том, что ты пытаешься в наших алгоритмах видеть свои!
Логично. Только не свои, а общеизвестные. Достучаться вот не могу.
VD>но и с точки зрения осмысленности сообщений об ошибках. Ведь мало толку от информации, что в точке облома ожидался юникодная буква или число (при разборе идентификатора, например).
Иногда доастаточно. Но ты абсолютно прав, что ориентироваться тут можно только на "положительные" возможные ветки от места ошибки. И очеловечивать тут можно через разъяснение "типовых" ошибок как-нить через в ручную подготовленные таблицы соответствий типовых ситуаций. Только для этого надо вернуться к самому началу, и протянуть информацию о нетерминалах.
Я себе вообще плохо представляю автоматизацию генерации сообщений об ошибках при парсинге по ДКА/НКА. Все, что у нас есть — это возможные положительные ветки. Для примера, у нас же грамматики ЯП не полные парсятся, бо они КЗ по своей природе, а парсим мы КС-подмножество. Т.е. мы парсим синтаксис, а сообщение об ошибке должно опираться на семантику. Отсюда пляски с кастомизацией сообщений об ошибках — обязательная часть балета.
V>>У меня хранилось в итоге в узлах/состояниях автомата (список списков правил-родителей). Потеряться ничего не могло. Сами целевые нетерминалы — статические данные. Сослаться на них откуда угодно несложно.
VD>Блин. Ну, нет там никаких узлов. Нету! Там код.
Это понятно. Непонятно, почему нельзя нагенерить статических данных, описывающих таги нетерминалов, и ссылаться на них из кода? Можно завести некий контекст парсинга, где по каждому псевдо-конечному состоянию (по "свертке" или ее аналогу, когда вы ее наконец сделаете) можно выставлять текущий контекст. Дополнительная стоимость — одно присвоение ссылки на статические данные раз в несколько символов исходного потока.
VD>Конечно, конечно. Но ни одного шустрого пока свету не предявлено. Наверно их скрывают в закромах противопригарных решений .
Дык, не пользовался бы народ. Или все дураки? Реально, техника откатов во многих сценариях наихудшая. А ее лечение, мемоизация, с таким требованиями к памяти как в Пакрате — не катит для длинных входных цепочек, по нескольку мег. Там нужны т.н. "оперативные" парсеры, которые однократно проходят по цепочке данных произвольной длины.
V>>В одном из применений мне парсеры с откатами не подходили вообще. Представь, несколькомегабайтный документ имеет неоднозначность, которая ресолвится лишь на последних его символах, угу.
VD>Ага. Если не знаешь про мемоизацию, то можно кормить себя и такими сказками.
Влад, ну как не знать с такой рекламой от тебя?
Ты мне память прикинь хотя бы для цепочки в 1 мег. А потом представь, что это серверное приложение, и оно многие десятки запросов одновременно обслуживает. Ну и плюс, мы и так для данной грамматики имеем O(n) по быстродействию, нафига тратить лишнюю память?
И потом, ты не правильно понял. Не правила в конце различаются, а цепочки. Правила асболютно разные, уникальные, т.е. твоей мемоизацией можно подтереться. Полностью деление всего потока на нетерминалы переиначивается в зависимости от участка, ближе к концу. В GLR общие части правил, которые можно мемоизировать, просто сливаются в один вариант на данном участке, и эта общая часть протягивается одним экземпляром ДКА. Потрать 5 мин хотя бы на Вики: http://ru.wikipedia.org/wiki/GLR-%D0%BF%D0%B0%D1%80%D1%81%D0%B5%D1%80
VD>Не малая стоимость, в общем-то. В прочем, теоретических рассуждений можно построить много. Ты тут уже не раз хвалил свой парсер. Давай проведем простой эксперемент. Воссоздай парсер шарпаа который на выход выдаст АСТ. Сделаем тест в котором сравним полученное АСТ (чтобы видеть, что никто не врет) и сравним скорость разбора.
Нет, мы сделаем что-то попроще для начала. Моя реализация не является генератором парсеров общего назначения, а была заточена под специфику, которую описал. Можно было бы взять какой-нить другой GLR, например DParser, но это будет непонятно, что мы меряем, бо от реализации много чего зависит, не только от алгоритмов.
V>>Теоретически. А фактически — выборка по одной и той же таблице, один и тот же входной поток в кеше, и т.д., а на всё это тратится грубо 90% работы ДКА, и 10% — собственно переход. Т.е. там каждый параллельный вариант грубо требует +10% затрат.
VD>Вот это и есть — теоретически. А практически — тормоза .
Да нет, по замерам два паралельных ДКА, работающих по одной и той же цепочке, не сильно добавляют в сравнении с одним ДКА. Т.к. основная работа не по состояниям ходить, а данные подавать. К тому же, у меня идет преобразование алфавита (рядом описал), и оно однократное (общее) для всех параллельных ДКА.
V>>А если же использовать откат на начало — то это чистое удвоение. А если откатов больше — вообще хана.
VD>Этот вывод тоже от теоретизирования. На практике похожие грамматики имеющие разницу где-то в хвосте обычно состоят из общих подправил. А результат их разбора кэшируется. Так что когда пойдет повторный разбор, то его не будет, а результаты будут взяты из кэша.
Коэффициент размера памяти для кеширования от длины цепочки какой?
VD>Любой КА плохо расширяем. Даже то что у тебя отдельный лексер — это уже усложнение расширяемости.
Есть безлексерные и именно они расширяемые. НКА расширяемы таки без малейших проблем, на то они и НКА. Не зря его строят по регулярным выражениям, например, бо там кажде новое распаршенное выражение именно что расширяет "накопленный" на каждый текущий момент НКА.
VD>Вот тебе задачка из реальной жизни. Есть язык — Nemerle. Он парсит входной поток и если обнаруживает открытие пространства имен, то импортирует новые правила (описанные в виде макросов). Ну, и что на ходу будешь перестраивать свои НКА? А что если экспонента получится?
НКА не перестраиваются, а достраиваются. И та же версионность, что в AB-дереве, вполне организуема. НКА — это же модульность. Каждый отдельный переход может вести в свой модуль.
VD>А НКА — это еще и приговор производительности. И я тогда вообще не понимаю о каких таблицах ты там говоришь, если у тебя НКА.
Дык, НКА тоже имеют табличную технику реализации. Там всей разницы, что по каждому нетерминалу у нас может быть не одно следующее состояние, а более одного. Т.е. происходит fork. При этом, что характерно, обычно идет "динамическое" равновесие. Новые ветки создаются, старые отмирают. На 99% участков в реальных данных вообще идет одна ветка, т.е. эти участки пробегаются как ДКА. Тормоза в рассматриваемых мною GLR исключительно были в постоянном динамическом выделении/освобождении памяти для каждого узла дерева разбора. Даже, если оно на GC. Я лишь только за счет стека переиспользуемых объектов ускорил начальный вариант более чем в два раза для дотнета. Там же смешные затраты на каждый шаг (переход по каждому из ДКА, их обычно 1-3 идет в параллель, по крайней мере в моих сценариях), и вся механика вокруг единичного шага начинает влиять на общую производительность.
VD>Весь кайф PEG-а заключается в том, что он идеологически очень хорошо расширяется. Каждое правило по сути отдельный парсер. Для динамического расширения нам всего лишь надо сделать правило приоритетного выбора массивом и тупо дергать подправила из него.
Ну? А массив переходов в НКА должен быть не расширяем, что ли? Я уже говорил, что мне не нравится в ПЕГ. Невозможно по правилам, содержащим приоритетность, вывести св-в грамматики.
Ну и опять же, я вас не призывал сменить технику своего парсера, а обратил на вполне конкретный маленький такой сценарий инлайна. И сказал, на что он похож. И как с этим борются.
V>>Для начала было бы неплохо на чем-нить попроще.
VD>По проще тебе же не выгодно будет.
Мне выгода нужна по как можно меньшим временным затратам на наши игры. Это же все интереса ради, более не для чего. В конкретном применения я взял максимально подходящую технику. Сейчас всего лишь любопытно пройтись по более-менее общим задачам.
VD>Да и неинтересно это. Реальные применения — это же языки программирования. VD>Именно для них писать парсеры вручную тяжело. И именно при их создании получаются весьма неприятные эффекты в грамматиках (просто потому, что сложность велика и разложить все по полочкам создатель грамматики не может).
Дык, я от того и привел GLR, что ему пох какая грамматика. И не обязательно воспроизводить всю грамматику для тестов, что за максимализм? Можно взять конкретный небольшой кусок, который не приводится, скажем в LL(1), и гонять на нем.
VD>В прочем, можешь для начала тот же Джейсон повторить.
Я тоже уже подумал, в выходные покумекаю, как его прикрутить.
V>>Сколько времени заняла разработка у вас этой грамматики до текущего варианта?
VD>Неделю времени неподготовленного человека.
Вот, дофига, если честно. Больше, чем пока могу себе позволить. Мне же ее перелопачивать для своего парсера придется, бо там по минимуму и со спецификой.
V>>И вообще, смысл предлагать тягаться на эксперименте, стоимостью в несколько рабочих дней оппонента? Чтобы заранее получить отказ? Надо брать что-то более реальное. А потом смотреть, есть ли смысл тягаться дальше.
VD>Нет смысла тягаться на синтетике. Такие тесты ничего не покажут. Мы сделали парсер C# в основном с целью отладки технологий PegGrammar.
VD>Если ты считаешь свой генератор парсеров коммерческим продуктом высокого качества, то тебе самому будет не лишним иметь хороший демонстрационный пример этого самого качества.
Заказной. Качество понравилось. С задачей ускорения разбора и линковки EDI док-тов справился. В среднем прирост был в 3-10 раз от их "самописного" варианта. Правда, как всегда без NDA не обошлось.
VD>Плюс ты сможешь не на словах, а на деле доказать применимость GLR, что будет несомненно интересно в научных кругах.
Да он обжеван тысячекратно. Где он плох, а где хорошо — известно и так. Любые его обсуждения начинаются с примерно таких слов "на большинстве грамматик он имеет быстродействие O(n)". Но засада в том, что на худшем случае у него быстродейтсвие, как у Эрли. В общем, ничего нового тут не откроешь. Он специфичный и ОЧЕНЬ хорош для одних сценариев и крайне плох для других. Бесплатного сыра не бывает.
VD>Твои же некомпетентные советы только раздражают (или веселят). Мы же те советуем тебе как оптимизировать или развивать твой GLR-парсер?
Чего там развивать? Две недели на разработку, две недели на профайлинг, и проект закрыт.
VD>А то ты говоришь о том, что Вольфхаунд гнет пальцы, а сам со стороны выглядишь не лучше.
Ну, в отличие от, я не делаю мину непонятной сакральности исследователя неведомого. И даю ссылки на открытые вещи. А то, что меня порой раздражает ваше непонимание, да еще усугубляемое тем, что это непонимание имеет природу снисходительного отношения к техническим предложениям оппонентов — это ожидаемо. То, что среди коллег требует одной итерации, здесь жуется по 10-му кругу. Лишь потому, что у тебя и твоего напарника все окружающие априори ламеры. Конечно, начинает доставлять.
Здравствуйте, Ziaw, Вы писали:
Z>Бранч и форк в DVCS по сути одно и то же, и там и там делаются разные ветки разработки и там и там их потом можно слить. На гитхабе есть штатные механизмы сделать пулреквест в проект из форка. Хозяин проекта пулит к себе в репо изменения из пулреквеста.
Ну, вот это гимор. Совместной разработки при этом уже не будет. Не уж то вы не понимаете, что чем дольше не делается слияние, тем сложнее это слияние сделать потом.
Такой подход может и оправдан когда когда кто-то обкатывает новые идеи. Или когда кто-то со стороны хочет помочь проекту и при этом этому кому-то доверия мало. При этом этот подход заменяет брэнчи в SVN. Но для реальной работы нескольких человек над одним проектом он не пригоден.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
V>>Почему я вообще тут упомянул GLR? — потому как тоже восходящий разбор, похожая специфика, т.е. WH>Ой звездец. ПЕГ это нисходящей анализ.
V>>Суть минимизации по алфавиту такова (на пальцах): берем символы, скажем '0'-'9', по всем ним идут идентичные переходы, т.е. все дуги в графе переходов по этому набору полностью параллельны. Заменяем через таблицу подстановки терминалы T0..T9 на один терминал T'. Затем, при работе, вместо десяти ветвлений из каждого состояния получаем одно. Либо, вместо проверки диапазона (2 сравнения) имеем одно сравнение. WH>А превращение T0..T9 в T' у нас бесплатно и делается святым духом?
Как делается — уже описал. Тебя стоимость табличной конвертации интересует (с указанными подробностями)? Мой комп превращает T в T' со скоростью гиг в секунду (936 MB, если быть точным). Проверь на своем компе, интереса ради. И сравни с порядком быстродействия всего остального.
V>>В итоге, у меня никогда не получалось подстановочных терминалов T' более 255 штук (3-4 десятка в среднем), т.е. это уже кодирование в байт, т.е. таблица преобразований из юникода ровно в 64к байт. Правда, я там делал две таблицы преобразования — одну до кода 127 (как самую частую), другую — общую до 64к. На эффектах линий кешей еще кое-какие копейки в итоге выжимаются на ACII-ориентированном потоке, но не принципиальные. WH>Ты главное не забывай про одно маленькое, но противное функциональное требование к моему алгоритму: Динамическое изменение грамматики.
Я так понял, что конкретный макрос генерит готовый парсер (модуль). Дык, модуль он и в Африке модуль, внутри может быть реализован как угодно. Т.е. иметь свой алфавит T'. И что-то мне подсказывает, что в случае модульности он будет вообще малюсеньким в каждом отдельном парсере.
WH>Нут вот пусть они что-то другое и используют. WH>Я делаю разбор для ЯП.
Ну ок, я вообще-то привел GLR лишь из-за ваших проблем с инлайновостью.
Здравствуйте, vdimas, Вы писали:
V>Ну, в отличие от, я не делаю мину непонятной сакральности исследователя неведомого. И даю ссылки на открытые вещи. А то, что меня порой раздражает ваше непонимание, да еще усугубляемое тем, что это непонимание имеет природу снисходительного отношения к техническим предложениям оппонентов — это ожидаемо. То, что среди коллег требует одной итерации, здесь жуется по 10-му кругу. Лишь потому, что у тебя и твоего напарника все окружающие априори ламеры. Конечно, начинает доставлять.
Я вообще не вижу смысла во всем этом бодании по переписке.
Ты можешь показать свой код на примере?
Несколько раз искал — пока этой разновидности не видел...
.
.
минут за 10-20 разобрался с тем, что к чему.
