Здравствуйте, VladD2, Вы писали:
A>>АФАИК оба умеют работать с SVN как с родным. HG точно (сам пользуюсь). VD>Т.е. я могу автоматом при пуле обновлять и связанные репозитории, например, с кодплекса?
Ну именно в таком сценарии я не использовал. Просто чтобы не ставить зоопарк клиентов подключаюсь к SVN через hg/TortoiseHG. Думаю как ты описал должно рабтать без проблем.
Здравствуйте, Ziaw, Вы писали:
Z>1. Как там сделать то, что я делаю чаще всего: глянуть то, что незакомичено. Z>2. Как ревертнуть файлы?
Из окошка коммита.
Один раз его открыл, а дальше только кнопочку обновить жмешь.
Z>3. Как сделать pull/update с одновременным merge рабочей копии?
В окошке pull нужно поставить галочку "Merge remote branch to current branch"
Галочку он запоминает.
Z>4. Это уже не к тулзам, это к гиту, никак не могу понять, на кой ляд там бранчей столько: master, origin/master, origin/HEAD?
Ну кабе master это твой локальный главный бранч.
origin/master это главный бранч репозитория с которого ты стянул код.
Кто такой origin/HEAD я не знаю. У меня его нет.
Вроде все логично.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Ну и что ты написал?
Следи за руками:
Парсим if.
Проверяем есть ли далее else
Если есть то откатываемся парсим if/else
Проще говоря выбираем ближний else.
Что полностью равнозначно стратегии побеждает длиннейший.
VD>Ты сам себе доказательства придумываешь и сам же в них веришь.
Пока что ты только тем и занимаешься что подтверждиешь мои выводы.
VD>А кто будет решать что попало, а что нет?
Я. Если кому-то не понравлюсь я, то он может завести свой репозиторий и мержить туда все что захочет.
VD>Да ломай сколько влезет. Только брэнч создай.
Вот я и создал бранч куда никто без моего разрешения не влезет.
VD>Пока что в твоем репозитории вообще никаких существенных изменений нет. Там один рефакторинг. И это за 4 месяца.
Я его только два дня назад создал. Смотри на даты ради разнообразия.
А начинать переделку нужно с выноса мусора.
VD>Тебе может 20. Мне или кому-то неделю убить. В прочем, на фоне других проблем это мелочь. Одно то что проект нельзя собрать в один клик уже, как ты выражаешься, бесит.
Проект парсера можно.
И это отдельный проект.
Никакого отношения к немерле не имеющий.
VD>Ну, то есть ты хочешь работать над этом проектом в гордом одиночестве и не хочешь чтобы им кто-то пользовался до релиза (который неизвестно будет ли вообще, ведь новые идеи могут появиться)?
Я не хочу чтобы в проекте появлялся непонятный код который не ясно что и как делает.
Я просто хочу порядок.
Я что так много хочу?
VD>Посмотрел. 1 открытый 0 закрытых.
А ты фильтр зактрытых отключи.
VD>Опять же у ИТ контрибьютеры по мелочи дописвают. Если же делать что-то большое, то без постоянных слияний остальные будут с тобой конфликтовать. И их жизнь привратится в постоянные обновления по твоей ветки и постоянные же разрешения конфлитов. Если работа ведется, то брэнчи самое то. Сливай по мере законченности и все будет ОК.
Форк это бренч. Просто чуть более изолированный.
VD>Иначе ты будешь писать один. Примерно как ИТ.
Да я и так один пишу.
Серьезные правки что вносили в парсер мне приходилось переделывать чуть менее чем полностью.
VD>Это конечно хорошо. Но боюсь через некоторое время будет не ясно что за репозиторий главный.
Вот только реальные проекты от этого почемуто не страдают.
VD>Не вижу кучи.
Ну как минимум на этом принципе живет ядро линуха.
Причем там иерархия репозиториев на верхушке которой сидит Линус.
VD>Ага. Именно для них и удобно. А для членов команды все же удобнее брэнчи и просто комиты, если делается мелкая фича. VD>Жить на идеях полного недоверия всем себе же дороже.
Ты так говоришь просто по тому что тебя испугал кривущий гуглокод и ты думаешь что форки это что-то страшное.
VD>По уму надо посмотреть как делают в командах того же Линукса. Там ведь есть и море контрибьюторов и центральная команда.
Вот только они живут по схеме что описал я, а не ты.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD> то мы имеем информацию о том для какого правила генерировался код и "по else" (т.е. при обломе правила) можем запомнить текущую позицию разбора в переменную ассоциированную с этим правилом. Но когда речь идет об оптимизированных правилах, код которых встраивается в код других правил и при этом еще и переставляется по много раз, определить что же за правило реально обломалось не выходит. Классический пример такого правила — это разбор ";" в грамматике C#. ...
А можно чуть поподробнее, не совсем понятно в чем проблема.
При инлайнинге ничего не теряется, а даже дублируется, размножается. Поэтому каждая ";" знает откуда она появилась — была с самого начала, или из какого правила оригинального варианта(до переделки) грамматики ее вставили. Эта информация статическая, часть парсера разбирающая input не должна ничего об этом знать. Когда правило обломилось, эта часть парсера возвращает для обломившегося правила ID его родительского правила, и индекс обломавшегося элемента. Потом другая часть парсера смотрит какое правило по индексу лежит и из какого правила исходного описания грамматики оно появилось.
В модифицированном варианте грамматики для каждого элемента внутри правила прописано откуда он появился.
Или я что-то не так понимаю?
Правда гитхаб более раскручен, подозреваю, что не зря. Но у меня к гиту предвзятое ощущение, он вводит лишние сложности на ровном месте. С другой стороны у IT ест опыт синхронизации репо на гитхабе и svn на google code.
Здравствуйте, Silver_S, Вы писали:
S_S>А можно чуть поподробнее, не совсем понятно в чем проблема. S_S>При инлайнинге ничего не теряется, а даже дублируется, размножается. Поэтому каждая ";" знает откуда она появилась — была с самого начала, или из какого правила оригинального варианта(до переделки) грамматики ее вставили. Эта информация статическая, часть парсера разбирающая input не должна ничего об этом знать. Когда правило обломилось, эта часть парсера возвращает для обломившегося правила ID его родительского правила, и индекс обломавшегося элемента. Потом другая часть парсера смотрит какое правило по индексу лежит и из какого правила исходного описания грамматики оно появилось. S_S> В модифицированном варианте грамматики для каждого элемента внутри правила прописано откуда он появился. S_S>Или я что-то не так понимаю?
Та посмотри в исходник, они строят ДКА как для лексера. Самиздат, короче. Но даже тут можно восстановить один уровень иерархии.
Почитал я сие "произведение". Впечатление тягостное, угу. Ни малейшего понятия о предмете. Я понимаю, что ты к программированию малость боком, и постоянно делаю на это скидку, но в упор не понимаю, откуда такое желание месить оппонентов с г-ном, размахивать лозунгами и стараться всех перекричать? Лучше бы аккуратно сходил по ссылкам, а подкрепившись, внимательней посмотрел бы на ваш собственный код. Потому как на сегодня ты не до конца понимаешь, как этот ваш код работает. И даже после неоднократных тыканий носом в очевидные вещи, так и не понял, какие преобразования кустов графов вы совершаете при вашем т.н. "инлайнинге".
Ты ошибся в каждом предложении в этом огромном посте. Пока мне не надоест, я на кое-что отвечу. Не на всё, извини, т.к. много повторений, флуда, ухода от темы и откровенной истерики.
VD>ДКА Вольфхаунд генерирует исключительно для оптимизации листовых правил (в твоем лексиконе называемых "терминалами") и исключительно когда в них нет рекурсии.
Ты ошибся. Не только листовых. Да, оно начинается с листовых, но может "свернуться" на несколько уровней вверх. Смотря как карты лягут.
И кстати, рекурсивность грамматики не означает, что она не регулярная. Регулярная грамматика — это такая КС грамматика, которая растет за счет терминалов либо только вправо, либо только влево, потому и называется регулярной, в отличие от растущей в любую сторону КС. Так что, рекурсия вполне допустима, но только одного вида. Кстати, этот момент тоже можно доработать в коде, тем более, что праворекурсивные регулярные правила имеют однозначное отображение на леворекурсивные. Да, оптимизатор заметно распухнет. Собственно, именно это и критиковалось в продемонстрированном коде — смешение диспетчеризации и несвязанных алгоритмов оптимизации. Каждый из которых по мере развития может усложняться, меняться, вы может захотите в месте диспетчеризации выбрать разные в зависимости от условной компиляции для сравнения, и т.д., в общем, тела этих алгоритмов вовсе необязательно было сливать в "общую кучу".
VD>Так что получается там конечный автомат.
Конечные автоматы разные бывают. Я не зря обращал твое внимание на отличие автомата для LL(1) и автомата для сканера или LR. Но еще вернемся.
VD>PEG при этом нарушается не сильно.
Изюминка PEG на этом конкретном "заинлайненом" узле испаряется. Не нужна. Регулярную грамматику могут разбирать любые парсеры, потому как эта грамматика находится на самом нижнем уровне иерархии грамматик. Тут разумно взять самый простой и самый эффективный алгоритм парсинга, способный восстановить исходную топологию "заинлайненного" куста правил.
VD>GLR не получается вовсе.
Ну и каша в голове... GLR — это не разновидность грамматики, это способ парсинга. А характеристики грамматики "даны сверху". Если по-существу, то GLR полностю покрывает класс КС-грамматик, поэтому про него можно сказать, что он "получается всегда", в отличие от LL(1), PEG и прочих алгоритмов, работающих на ограниченных подклассах КС-грамматик. Но не суть, просто твой способ изложения мыслей доставляет.
VD>Твой GLR даже не начинает работать там где у нас работают ДКА.
ДКА в чистом виде сами по себе не работают в парсинге. Они нужны для управления исполнительными устройствами, разбирающими входную цепочку. Потому что это самый эффективный в программной реализации способ управления. Саму ДКА обслуживает "внешний" по отношению к нему код, который его запускает, ловит выходные сигналы (т.е. ловит факт попадания в конечные состояния, если это автомат Мура), сбрасывает, возвращает лишние символы обратно во входной буфер (в жадном алгоритме, например), потом запускает снова, и т.д. и т.п. Обрати внимание, по одному и тому же ДКА может работать как жадный алгоритм лексера (всегда используемый для ЯП), так и обычный.
Конкретно ваш ДКА при инлайнинге строится как ДКА для управления лексером, только поэтому теряются промежуточные нетерминалы, т.е. вместо иерархии оных он принципиально способен дать лишь самый верхний "незаинлайненнный" нетерминал. Поэтому и предлагается, строить ДКА, но чуть другой, для управления другой схемой. По регулярной грамматике та, другая схема, работает с эффективностью сканера. Тормоза только на конфликтах, но у вас их не будет априори.
VD>Если инлайнинг совпадает с построением ДКА, то все становится еще сложнее, так как тут уже отследить что-то практически невозможно.
Эту задачу решили очень много десятилетий назад. Для заведомо регулярной грамматики покатит LR(0).
VD>С кем? С тобой? Ну, в общем-то с человеком говорящем о восходящем анализе при разборе PEG-грамматик действительно все ясно.
Уффф, зануда.
Заинлайнив целый куст с некоей иерархией и "склеив" несколько ДКА, ты теряешь исходную структуру графа. Напомню, что нисходящий разбор — это разбор, совпадающий с нисходящим обходом дерева правил (parser tree), т.е. движение от вершины с рекурсивным перебором узлов дерева вниз и откатами из неудачных попыток. Сам перебор нисходящих узлов происходит на нетерминалах, т.к. в нелистовых узлах этого дерева по-определению могут находиться только нетерминалы. Т.е. если у вас, после преобразования некоего куста исходного дерева, теряются нетерминалы и вместо дерева остается пространственный граф на терминалах (граф ДКА), то какой там может быть в ж-пу нисходящий разбор? В общем, мы теперь можем лишь поглощать терминалы и продуцировать из них нетерминалы. Чтобы восстановить кусок дерева обратно, нужно добавить лишь одну операцию из восходящего разбора, которая выполняется в состояниях, эквивалентным конечным в ДКА от лексера.
Сорри за ликбез, но если гора не идет к Магомету, надо что-то делать.
Итак, задача:
— в результате подстановок обнаруживается, что некий куст правил из parser tree представляет из себя регулярное подмножество (повторю: вы пока находите неполное подмножество, туда можно включать рекурсивные и взаимно-рекурсивные правила, растущие в одном направлении за счет терминалов. Облом опять смотреть тот код, но насколько я помню, сейчас включаются только растущие вправо).
— принимается решение всё это подмножество реализовать в "отдельном парсере" регулярной грамматики.
— найти решение восстановить иерархию исходного куста в процессе работы этого "отдельного парсера".
Ответ:
Упрощенный LR-анализ. По мере хождения по ДКА он восстановит исходный граф. Суть упрощения — в откидывании веток алгоритма, обыгрывающих конфликты свертка-свертка и сдвиг-свертка. Почему так? — парсер будет строиться по заведомо безконфликтной грамматике (она регулярная). Вот тут наши коллеги когда-то парой слов об похожем случае перекидывались: http://www.rsdn.ru/forum/alg/2855264.aspx
Я также набрел на похожесть в процессе реализации GLR, т.к. он реализуется как парсер по НКА (т.е. как семейство ДКА), и позволяет по той же самой причине каждый из этих парсеров по ДКА выполнять по упрощенной схеме.
Хотя, чтобы не забивать себе сразу голову — фиг с ней с упрощенной реализацией!!! Берите как пример любую реализацию, просто несколько веток алгоритма никогда не будут вызываться.
Справедливости ради, если бы сохранили направляющие символы, то можно было бы упорядочить разбор как нисходящий LL(*), но... он тут overdesign, усложнение процесса парсинга на ровном месте (хоть его легче построить), худшее из решений и т.д., ибо регулярная грамматика этого не требует.
VD>Ты поторопился предположить, что ты понимаешь то о чем говоришь. Более того ты тут все время упрекаешь Вольфхаунда в том, что он слишком резок в высказываниях и задевает других (что в общем-то не далеко от истины), но сам сейчас делаешь тоже самое.
Только в общении с тобой. Ибо ты мастер провокаций. Твой слог полон "изяществ", однако. Да, с общечеловеческих позиций это меня не оправдывает, понятное дело, ибо никогда не стоит уподобляться...но в нашем "междусобойчике" мне твой стиль почему-то развязывает руки...
VD>Ты мало того что по полной программе облажался и назвал белое черным, так еще имеешь наглость беспардонного хамить в стиле выше процитированного предложения.
А как ты вообще хотел вести технические споры? Тебе дают ссылки, обсуждают похожие случаи, делятся опытом. Но тебе в одно ухо влетает, в другое вылетает. Я не вижу желания понять собеседника. Мы уже 4-й пост не можем продраться сквозь уровень 0 — где тут восходящий, а где нисходящий разбор, что из себя представляет парсинг по графам КА, и какие разновидности этого парсинга бывают. Мы топчемся на месте. И ты периодически срываешься на ликбез такого же 0-го уровня, хотя никто не заказывал. Это откровенно ламерский, позорный уровень обсуждения, дискредитирующий всех в него вовлеченных. Я не вижу динамики, присущей нормальному техническому обсуждению. В каждой итерации, после очередного дележа информацией и взятия таймаута на обдумывание, собеседники должны возвращаться все более и более подкованными. По крайней мере, хотя бы освежить материал в памяти, бо голова не мусорный ящик, подробности могут забываться. Но фиг там, мы топчемся на месте, исключительно из-за тебя. И профанируем тем самым цели обсуждения. Хотя, с Вольфхаундом любезностями тоже не забываем обмениваться (неплохой у тебя "ученик" вышел), но там хоть какое-то поступательное движение. Он то сообщит что-то полезное из подробностей (хоть и на понтах), то отреагирует на информацию оппонента. Хотя бы в стиле "посмотрю" или "не интересует", т.е. хотя бы видно понимание. А ты уперся не пойми во что. Я прочитал пост дважды, так и не смог выделить, с чем именно ты споришь. Бо ровно 0 аргументов. Вся писанина отдает каким-то банальным раздражением студента, которому препод "плохо объясняет". Но я выдал вообще всю информацию, которую было можно выдать. Следующим шагом будет копирование сюда глав из книг по всему упомянутому, но я этого делать не буду.
VD>А ты не думай. Ты спрашивай. Тогда не будешь выглядеть полным ламером, как сейчас. Никаких "сверток" там нет. ДКА используется по прямому назначению, чтобы ускорять парсинг вот таких вот фрагментов:
Тю, блин. Чем интересен класс регулярных грамматик написано в первых строчках любого учебника по грамматикам. И я знаю, что никаких сверток у вас там нет. Я спрашиваю — почему у вас там нет сверток или других аналогичных действий? Вам не нужно исходное дерево грамматики? Из примерно десятка твоих постов вокруг этой темы выходит, что оно "нужно, но не всегда". Сорри, это очередной детский сад. Нельзя быть чуть-чуть беременным. Или алгоритм умеет восстанавливать исходный parser-tree, и ты пользуешься результатом "когда нужно", либо алгоритм не умеет, и ты не пользуешься этим никогда (как обстоят дела на сегодня).
V>>Тогда еще один намек: "сдвиг" в LR — это и есть собсно накопление цепочки терминалов, как делает ДКА сканер по мере движения по входному потоку.
VD>Эй, умник! Остынь. Нет никаких накоплений цепочек терминалов. Нет даже самих цепочек. Есть тупой рекурсивный спуск и много разных оптимизаций. ДКА используются только там где они способны обогнать перебор.
Ну и где мне взять эпитеты для описания глубины демонстрируемого невежества?
Нельзя изучать какую-то область "кусками". Если ты уже так давно увлекся темой парсеров, то эту область надо рыть сплошняком. Хотя бы для того, чтобы не изобретать велосипедов в различных сценариях, и понимать терминологию собеседника. "Нет накоплений цепочек терминалов" — это шедевр однако. Накопление — это необязательно "копирование/складирование". Почти всегда оно сводится к оперированию метками начала и конца текущей разбираемой цепочки в буфере, но этот целевой диапазон символов именно что накапливается по мере разбора.
VD>И это далеко не частый случай. Вот на приведенном выше фрагменте ДКА рулит.
ДКА вообще рулит, не только на этом примере. Максимальное избавление от рекурсивного обхода рулит само по себе, бо рекурсивный обход дорогой, даже который без откатов.
VD>При этом даже семантика PEG нарушается, так как начинает работать правило, что кто длиннее тот и прав. "строки" тупо разворачиваются в дерево if-ов и goto.\
Пффф... Правило "само по себе" не начинает работать. Ты лишь упомянул один из алгоритмов сканера по ДКА. Да, для ЯП используют именно самую длинную цепочку, поэтому там есть еще откат на последнее обнаруженное конечное состояние. А упомянутое тобой "дерево" switch/case/goto — вообще к теме отношения не имеет. Это всего-навсего один из способов эмуляции работы ДКА. Попроси Вольфхаунда, он тебе покажет еще минимум 3-4 способа. Все эти техники выполнения ДКА равноправны и ортогональны обсуждаемому.
VD>А вот для чего-то большего ДКА не применяются, ибо это не гибко и не дает реального ускорения.
"Реальное ускорение" дает оптимальный выбор техники парсинга, соответствующий св-вам обрабатываемых данных. Надо просто понимать, какой алгоримт куда лезет. GLR хорош для грамматик с малой неоднозначностью и особенно хорош, когда при такой грамматике сами данные имеют относительно большую длину, но малую глубину. Применять в таких случаях LL-техники — это нубство, хотя они хорошо работают на современных ЯП (временно). Твои выкрики, типа "GLR/LALR никому не нужны" от невежества. На GNU Bison за десятилетия сделаны просто миллионы парсеров и парсерочков в мире. И далеко не только под ЯП. Для парсера всяких кастомных конфигов GLR идеален. Для систем электронного документооборота — идеален. Для языков декларации, навроде IDL — идеален. Для парсинга нетривиальных логов — идеальнее не бывает. Для парсинга смешанных языков играмматик, например некий ЯП общего назначения с инлайными всявками из других грамматик, типа SQL, либо же такие "смеси" как AspectJ — идеален, и на его уровне справляются только алгоритма типа Эрли, но они хуже работают и требуют слишком много памяти, что еще 5-7 лет назад программисты не могли себе позволить. Повторю, все сильные и слабые места GLR многократно обжеваны. Надо понимать, где он катит, а где будут наихудшим вариантом. Поэтому замеры на грамматике C# — это одно, а на каком-нить электронном док-те или объемном конфиг-файле — совсем другое.
И вообще, быстродействие алгоримов парсерсинга измеряется в кол-ве посещений узлов внутренних структур на единицу длины входной цепочки + учитывается размер требуемой динамической памяти. Почему так? Потому что абсолютное быстродействие конкретных реализаций одного и того же алгоритма, в зависимости от степени их "вылизанности" и способа управления динамической памятью, может легко отличаться на порядок.
VD>Да пора. Разговаривать с невеждой возомнившей себя гением и правда бесполезно. Разбираться в вопросах реализации ты даже не собираешся, а любой разговор без этого просто бессмысленнен, так как ты рассуждаешь не о том, что есть, а о чем-то придуманном тобой. По сему нужно завязывать. Все равно никто вменяемый и не ангажированный этот сообщение уже не прочтет. А объяснять тебе что-либо бесполезно.
Ты же не объясняешь ничего.
"Там все перемешивается и информация о нетерминалах теряется". Это такое объяснение? Того, как у вас сейчас работает? Я видел. Дык, исправьте. В чем именно ты обнаружил невежество оппонента? Что предложил вам одно из решений? Если тебе не нравится конкретно мое решение — обоснуй. Разложи по полкам. Предложи альтернативы. Но для начала тебе таки придется разобраться в чем состоит мое решение (хотя оно не мое, разумеется, ему уже лет 50). А до тех пор твои злопыхания беспочвенны.
VD>Умник, блин. В листовых правилах (которые у тебя в лексерах торчат) лишний if может преговорить к чертям всю производительность. Это же не лишний if на грамматику, а лишний if почти на любую букву.
Очередная демонстрация невладения темой. В регулярных выражениях или расширенной БНФ (PEG как их разновидность) нетерминалы "крупногранулированы", т.е. конечные состояния ДКА идут далеко не на каждую входную букву. Ну и с той же целью полезно различать в системе правил целевые и промежуточные нетерминалы, чтобы парсер не давал калбеки по промежуточным, и вы могли делать полную подстановку промежуточных нетерминалов в процессе оптимизации системы правил. А не только вот ту эмпирическую по "весу" сложности.
VD>Надо же соображать, что для PEG-а терминалами являются отдельные символы (символы строки). Плюс втыкая этот if ты рушишь другие оптимизации. В 99% случаев всем плевать, что терминальные правила сливаются. Всем важнее скорость их разбора. Но из-за какого-то "одного if-а" это слияние будет невозможно! И в итоге мы получим тормозное говнище вроде GLR, Эрли или Пакрата.
Похоже, ты не понимаешь, на чем именно тормозят эти алгоритмы.
V>>Эх, "работники передового края"... Извини, но продолжаю склоняться к тому, что это первый ваш парсер в истории, который с "0-ля" (в отличии от твоего R#). И вы там делаете кое-какие преобразования грамматики, но не способны оказались понять, что же это за преобразования такие у вас получаются.
VD>Ну, уже достаточно выставил себя полным ламером и от того подобные слова не взывают у окружающих ничего кроме смеха.
Что-то мне подсказывает, что ты заблуждаешься насчет "окружающих". Ты так и не понял смысла PEG, который соотносится с Пакратом не больше, чем соотносится язык программирования и конкретный его компилятор. PEG — это лишь способ задания грамматики и соответствующий их класс. Это не есть ограничения на реализацию, тем более, что за счет отсечений по приоритетности обобщенный парсер PEG — модульный, не накладывающий ограничений на способ реализации каждого "модуля".
VD>Пойми разница между нами с тобой не большая. Мы просто не обсуждаем твою работу, так как не видели ее. Я подозреваю, что то что ты делаешь — это полное очковтирательство и лажа, так как серьезную работу могут делать только серьезные люди, а серьезные люди не несут такой пурги как ты и не высказываются так по хамски о чужом труде даже не разобравшись в деталях. Но утверждать я подобного не буду, так как косвенные улики не могут являются основанием для серьезных суждений. Всегда может быть что и полный трепач способен чего-то добиться.
Ну понятно, т.к. аргументов по предмету спора у нас не было и не ожидается, можно переходить к непосредственному плеванию г-ном. Поздравляю.
Ладно, и так несколько последних постов были лишние. Было бы тебе действительно интересно решить задачу, тебе хватило бы одного намека на возможное решение. И ты бы сказал коллеге спасибо за подсказку. А т.к. очевидная твоя задача — повыступать на форумах, то мы сталкиваемся с классической в IT проблемой останова. Пожалуй, я тут произведу простой abort.
Здравствуйте, VladD2, Вы писали:
VD>С кем? С тобой? Ну, в общем-то с человеком говорящем о восходящем анализе при разборе PEG-грамматик действительно все ясно.
Для тех, кто начнет читать с середины.
Предыстория. Из грамматики, заданной в стиле PEG выделяются "куски", являющиеся регулярными подмножествами исходной грамматики. Проблема начинается в процессе подставновки вместо некоторых нетерминалов их тел в процессе оптимизации и склейки этих подмножеств в одно более мощное. В результате теряются промежуточные нетерминалы, которые были заинлайнены.
Осталось заметить, что данные подмн-ва правил обрабатываются не как PEG, т.е. никакого перебора не происходит, другими словами, внутри этих выделенных "модулей" используется алгоритм, который не-PEG. Хотя, использование таких алгоритмов внутри PEG — неотъемлимая его часть. Надо проникнуться спецификой. Итак, там алгоритм лексического разбора по ДКА. Осталось проанализировать, что сие значит. Если представить себе parser tree лексера, то оно будет ровно уровня 1: на верху будет нетерминал S0, а внизу будут все остальные целевые нетерминалы — "черные ящики", не разбиваемые на составляющие, т.к. промежуточные состояния ДКА не интересуют. И тут два очевидных наблюдения: 1 — восстановить можно только один уровень вложенности исходного куста, 2 — отображая технику разбора на parser tree, мы наблюдаем восходящий обход, т.к. идет не перебор вариантов, а непосредственное продуцирование нетерминалов по входной цепочке. Учитывая глубину parser tree, любой удачно-разобранный нетерминал ведет к успешности разбора, что и происходит при лексическом анализе.
В момент предложения применить другой восходящий алгоритм парсинга по ДКА, который сможет восстановить всю иерархию parser tree выделенного куста, как у быка на красную тряпку идет реакция "о ужас, какой еще восходящий алгоритм, если PEG — нисходящий". Напомню, речь идет о реализации участка, который и так уже парсится не-PEG парсером, и который и так работает аналогично восходящему разбору.
Здравствуйте, vdimas, Вы писали:
V>Поэтому с подачей данных тоже бороться пришлось.
Достаточно обычного упреждающего чтения. Не вижу особой проблемы.
V>А "захардкожено" потому, что стоимость обработки результата заметно влияет на общую производительность, поэтому я избавлялся от виртуальных вызовов где только можно, т.е. интерфейс парсера вышел не абстрактным, а завязанным на конкретные прикладные типы — клиенты.
Виртуальные вызовы? OMG
V>Блин, сюда в день час потратишь, и то дофига. А это работа на несколько дней. Сначала надо узнать на чем-то несложном, будет ли смысл, после всех операций по убиранию хардкода.
За "несколько дней" можно написать парсер C вообще с нуля и полностью вручную.
PS В общем, очень хотелось бы посмотреть на реальный пример и его производительность в реальной задаче. Иначе это всё выглядит чистейшим пустозвонством.
Здравствуйте, Klatu, Вы писали:
K>Достаточно обычного упреждающего чтения. Не вижу особой проблемы.
Что тебе позволило считать, что проблемы "особые"? Речь лишь о том, что подход "в лоб" на стандартных файловых ср-вах не так хорош, т.е. становится заметен.
V>>А "захардкожено" потому, что стоимость обработки результата заметно влияет на общую производительность, поэтому я избавлялся от виртуальных вызовов где только можно, т.е. интерфейс парсера вышел не абстрактным, а завязанным на конкретные прикладные типы — клиенты.
K>Виртуальные вызовы? OMG
Ну дык, калбеки в прикладной код надо же как-то подавать. Полностью динамически строящийся парсер должен иметь некое универсальное АПИ. В любом случае, вызов виртуальных методов не так критичен, как выделение памяти из кучи, даже если это куча GC.
В этом плане в дотнете всё очень печально, особенно когда надо делить входной поток на строки, требуемые для прикладной обработки. GC начинает все тормозить. Для него несколько сотен тысяч выделений в секунду — многовато. Поэтому на дотнете не так просто замерить производительность парсера в чистом виде. Тест должен быть относительно короткий, хоть на коротких текстах большая погрешность.
Вот тут и понимаешь, как удобно все-таки в С++ сделан строковый шаблонный интерфейс, что можно сделать любую его специализацию, например для того, чтобы класс строки ссылался на данные из чужого буфера. Т.е., чтобы обойтись без копирований и лишних выделений/освобождений памяти.
V>>Блин, сюда в день час потратишь, и то дофига. А это работа на несколько дней. Сначала надо узнать на чем-то несложном, будет ли смысл, после всех операций по убиранию хардкода.
K>За "несколько дней" можно написать парсер C вообще с нуля и полностью вручную.
Разумеется. Особенно, если "несколько", это неделя минимум, а не пара дней. Но вряд ли можно за это время сделать парсер, работающий по произвольному описанию.
K>PS В общем, очень хотелось бы посмотреть на реальный пример и его производительность в реальной задаче. Иначе это всё выглядит чистейшим пустозвонством.
О, дурной пример заразителен.
Смотри, привыкнешь.
Какие именно цифры смутили?.. чтобы я знал, каковы ожидания. Ну и тут
стоит пройтись предварительно, начиная от слов "Реальное ускорение" дает оптимальный выбор техники парсинга,. Чтобы не уподобляться Владу. И не цепляться так за C/C#, если мне вдруг захочется потягаться на чем-то другом.
Здравствуйте, Klatu, Вы писали:
V>>Какие именно цифры смутили?.. чтобы я знал, каковы ожидания.
K>Просто ты много и с большим апломбом критикуешь остальных, а свой код показывать не желаешь.
Я уж подумал, что не понравилась сотня мег/сек на ДКА-лексере. Это проверить самому 20 мин.
K>Некрасиво выглядит.
Хм. Никто не просил тыкать нам в лицо некий код из открытого проекта, как доказательство собственной "крутости". Мне думается, что среди коллег сие не принято. По крайней мере, везде , где я работал. Вышел типичный epic fail. Да, не у всех в реальных проектах всегда код идеален, тем более, что идеальность кода далеко не на первом месте по приоритетам. Но мы его никому и не тыкаем.
Что касается моего кода, то в избранном полно всяческих сниппетов за разные годы (в "файлах" тоже). Давал коллегам как подсказки/решения.
Ну и пропагандируемую галиматью про размер кода в Немерле я тоже всерьез воспринимать не могу, извини. Понимаешь, иногда размер кода может быть еще на порядки меньше, а результат куда как заметнее: http://www.contextfreeart.org/gallery/view.php?id=2496 Потыкай там еще примеры и соотнеси размер кода с результатом, если любопытно. Чудес не бывает, вопрос в специализации. А способов достижения специализации тоже больше одного, это я к тому, что макросы — лишь один из вариантов. Причем, один из худших, как и все eDSL. Короче, вопрос размера кода не такой однозначный, чтобы обсуждать его на каких-то нелепых понтах, да еще попуская при этом коллег и преподавателей. Кто-то должен был сказать что-то в ответ на все эти наезды.
Здравствуйте, vdimas, Вы писали:
V>Хм. Никто не просил тыкать нам в лицо некий код из открытого проекта, как доказательство собственной "крутости". Мне думается, что среди коллег сие не принято. По крайней мере, везде , где я работал. Вышел типичный epic fail. Да, не у всех в реальных проектах всегда код идеален, тем более, что идеальность кода далеко не на первом месте по приоритетам. Но мы его никому и не тыкаем.
Ты не понял ничего.
Совсем.
Ни моих притензий к преподам.
Ни зачем я показал тот кусок кода.
Ни то что там происходит.
Ни то какие там действительно есть проблемы.
Причем по ходу обсуждения ты крутился как уж на сковородке. Несколько раз сменил тему. Сделал несколько просто эпичных заявлений...
Так что epic fail демонстрируешь здесь ты.
V>Ну и пропагандируемую галиматью про размер кода в Немерле я тоже всерьез воспринимать не могу, извини. Понимаешь, иногда размер кода может быть еще на порядки меньше, а результат куда как заметнее: http://www.contextfreeart.org/gallery/view.php?id=2496
Вот это дествительно галиматья.
Эта игрулька бесполезна чуть более чем полностью.
V>Причем, один из худших, как и все eDSL.
Ох лол. Эпичность данного фейла сложно переоценить.
Я на макросах этот твой contextfreeart могу повторить один в один.
Те код можно будет тупо копипастить.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Элементарно. Берем два правила. Пускаем их по очереди (или параллельно) и смотрим кто из них съел большее количество входной строки. Кто съел больше, тот и папа.
Блин, всё время упускаю из виду эту "модульность".
Понятно.
VD>Если у нас PEG и мы поставим правила так: Х / У, то У с огромной вероятностью (а иногда на 100%) никогда не сможет сопоставиться. Оно просто будет всегда затенено.
Ну, это первое, за что ругают ПЕГ. Но как я понял из "ихних" форумов, такую ситуацию несложно валидировать автоматически еще на этапе построения парсера и выдавать ошибку.
Проскакивало еще мнение, близкое к обсуждаемому: задавать все правила как ИЛИ (т.е. как равнозначный выбор), затем выделять общие части после приведения, сортировать вхождения ИЛИ таким образом, чтобы самые длинные (поглощающие) подправила шли первыми, и заменять потом ИЛИ на приоритетное ИЛИ в стиле ПЕГ. Итого, самое длинное правило попытается быть разобранным самым первым, т.е. будут достоверно сохранены св-ва исходной грамматики, хотя будет использоваться техники разбора ПЕГ.
Но самое длинное правило не означает самую длинную цепочку.
V>>Ведь по классике, это же не лексер, который разбивает входную цепочку символов. Парсер распознает поданную цепочку целиком или не распознает. А если у нас несколько вариантов удачного распознавания одной и той же цепочки (т.е. несколько вариантов AST), какой из них самый длинный?
VD>Классика тупо не работает как надо. Она только на словах работает. А люди много десятилетий пишут парсеры языков вручную.
Только те, кто может себе позволить такие ресурсы. А так пишут на яках, бизонах, кокорах и прочих, коих много.
V>>(немного оптимизировано дерево вывода в сравнении с Эрли, но не сильно спасает).
VD>Эрли требует создания кучи динамических данных. VD>Это не приминимый на практике алгоритм.
Применяют, с доработками. Не все грамматики укладываются в ограничения популярных техник парсинга.
VD>Наш же алгоритм может жить вообще без динамического заема памяти. На практике мы занимаем память для циклических правил, чтобы накапливать результаты разбора. Но это не сильно влияет на производительность, так как там применяются динамические массивы. Да и на фоне создания АСТ это не такие уж и большие затраты.
Динамическое создание AST вообще не позволяет замерить собственную производительность парсера. GC не может некоторое долгое время агрессивно выделять память, начинает заметно тормозить. У меня недавно дошли руки погонять 4-й дотнет на предмет ускорения GC. Не особо. Результаты таковы: на коротком тесте простейший токенайзер, переводящий цепочки символов в String (без всяких вычислений) упирается в GC на уровне 100 МБ/сек. А ведь машинка у меня довольно серьезная. Через 2 секунды первоначальный показатель падает вдвое, а еще через три секунды — втрое от первоначального, оставаясь потом на уровне ниже 28-29 МБ/сек. Простое создание затем узлов АСТ на бинарных узлах попускает всё на уровень 8-12 МБ/сек. И это при том, что вообще никаких вычислений не происходит и подготовленные данные гоняются по кругу в памяти. Кол-во сохраняемых промежуточных токенов — не более 300к. Итого, дотнет позволяет на моей машинке работать примитивному токенайзеру со скоростью 250-300 МБ/с (если реультат не переводить в String и прочие АСТ), но при задействовании GC скорость падает до 8-12 МБ/с.
Вот почему я пользую пулы объектов даже в дотнете. И когда я в ответ на 4 MB/c с некоей иронией спрашивал, что же вы там замеряете, я имел ввиду не C#, а вопрос стоял так: измеряете работу GC, или вам таки интересно было померить собственные алгоритмы? Похоже, что быстродействие собственных алгоритмов вы пока не мерили. Это тоже причина не доверять Вольфхаунду в его типичных резолюциях "это ни на что не влияет". Я делился только теми приемами, которые у меня реально влияли. Просто у вас они влияют в рамках погрешности измерений производительности GC.
И вот диллема: в моей задаче, связанной с документооборотом, токены были по нескольку десятков символов, поэтому показатели в MB/c были относительно неплохие (50-80MB/c). Если перейти на тест с токенами длиной 1-8 байт (на примере среднестатистического JSON), то мерить я уже буду исключительно работу GC. Пока еще думаю, что с этим всем делать, и не попробовать ли переписать на нейтив, хотя бы соревнований ради.
V>>К примеру, есть SRNGLR, он парсит SASL в 8-10 раз быстрее, чем просто SGLR (для которого SASL — хорошая демонстрация имеющихся проблем в GLR). По более "привычным" языкам: Питон, например, парсится в 3-5 раз быстрее. Тоже нехилый такой буст.
VD>Быстрее чем что? Это все общие слова. Есть хоть какие-то измерения?
Быстрее в колв-ах операций на единичный входной символ. Теперь понимаешь, почему так? Как ты говоришь "учОные"... они не такие уж дураки. Вылизывать реализацию по имеющейся асимптотике — это работа для нас, чернорабочих.
VD>И опять же SRNGLR ведь скорее всего расширяемость динамическую не поддерживает. Так?
Поддерживает исходный SGLR, этот уже нет. Кроме комбинаторных парсеров всерьез никто не поддерживает расширение. ПЕГ недалеко от последних ушел.
VD>Ты опять что-то гонишь. Вот я сделал поиск по SRNGLR и нашел вот это: VD>Из чего делаем вывод, что у них не только генерируется АСТ, но и генерируется только в одном из возможных форматов.
Во-первых, это уже другая тема. Во-вторых, Parser tree не сильно от AST отличается. Только тем, что Parser tree не содержит прикладных вещей, а исключительно описывает структуру правил. Но основное отличие тут в используемой динамической памяти. Если AST строят целиком по мере разбора и запоминают, то узлы ParserTree статичны, динамичен только путь к текущему правилу (вся "динамика" лежит обычно в массиве, длина которого равна мксимальной глубине дерева правил). Понятно, что для сохранения чего-то куда-то в файл надо сохранять именно целиком, но для прикладного кода, работающего в оперативном режиме — нет.
VD>Ты реально гонишь. Просто у самого подхода GLR есть трудности. На самом деле почти все языки что ими парсят являются однозначными. А GLR не умеет сразу создавать однозначных деревьев. У него есть тупиковые ветви, а есть неоднозначное ветвление. Вот им и приходится вводить самопальные промежуточные структуры. А на это ведь уходит и память и время.
Ну, некий коэф неоднозначности грамматики можно прикинуть по коэф неоднозначности переходов эквивалентного НКА. В моих случаях он был ~1.05. Промежуточных "самопальных" структур никаких. Есть пул ДКА (каждый — это value-type с двумя полями), есть граф ссылок на parser tree, почему граф — потому что разветвления на неоднозначностях. На однозначной грамматике выживает в конце одна ветка. В процессе разбора узлы тупиковых веток возвращаются в пул, что позволяет ограничить требования к динамической памяти для построения версионных цепочек вывода Parser Tree. А если известен характер данных и коэф неоднозначности — то практически исключить.
VD>У нас все просто. Строится всегда одно дерево. Если в результате отката его часть теряется, ну и фиг бы с ним. Все равно мы всегда создаем дерево сверху вниз и имеем оду его копию.
В GLR тоже самое.
VD>Дык Parser Tree и есть лишний объект. Это и есть АСТ причем специфичное для парсера.
Это как бы АСТ исходной грамматики парсера.
V>>А у вас одна и та же кодовая база для рассмотренного PEG-макроса и для динамического расширения будущего парсера Nemerle? Там же разная техника исполнения парсера должна быть, как мне видится.
VD>Я не понял что за кодовую базу ты имеешь в виду. PEG-макроса читают грамматику из атрибута, преобразует ее в дерево состоящее из варинтных типов (АСТ грамматики), а далее начинает с ним играться. В итоке генерируется код парсера. Примерно тоже самое будут делать новые макросы. Только АСТ грамматики они будут брать из другого места (из описания макросов).
VD>Так что код будет повтоно использоваться. Но не на 100%.
Мне показалось, что это "независимый" генератор парсеров по грамматике ПЕГ.
Ну попробуйте. Посмотреть будет любопытно. Если у Лиспа макросами перехватывался выход парсера, а у Форта — входной поток символов, то здесь нечто третье.
Здравствуйте, WolfHound, Вы писали:
WH>Ты не понял ничего. WH>Совсем. WH>Ни моих притензий к преподам. WH>Ни зачем я показал тот кусок кода. WH>Ни то что там происходит.
Что-то написали, но аналитическую модель кода вывести не в состоянии.
WH>Ни то какие там действительно есть проблемы.
Да помню я твои реплики в ответ на то, что вы выбираете регулярное подмножество не полностью, потому что оно типа в вашей реализации не особо-то и влияет. Ну так не делайте этого вообще. Всё-равно никогда не понимал такого подхода на "отъе#ись". Если решили реализовать какую-то задачу — её надо сделать полностью, или не делать вообще, если она ни на что не влияет. Да и заключение насчет "не влияет" — умозрительное. Вы же не пробовали. Некая система правил может быть на 90% регулярной, но твоя реализация этого никак не обнаружит и не позволит выяснить "степень влияния". Так и будет нисходящим перебором шпарить праворекурсивные правила.
WH>Несколько раз сменил тему.
Разве я задавал тему? Я лишь отвечаю на комменты. Иногда возвращаюсь к какой-то теме и разъясняю, если с первого раза непонятно. Лень конечно, но хз с чего ведусь на откровенное хамство.
V>>Ну и пропагандируемую галиматью про размер кода в Немерле я тоже всерьез воспринимать не могу, извини. Понимаешь, иногда размер кода может быть еще на порядки меньше, а результат куда как заметнее: http://www.contextfreeart.org/gallery/view.php?id=2496 WH>Вот это дествительно галиматья. WH>Эта игрулька бесполезна чуть более чем полностью.
Для Немерле?
Народ вовсю пользует для генерации битмапов. Но вопрос был не в прикладной области. Он вообще пох в этом обсуждении.
V>>Причем, один из худших, как и все eDSL. WH>Ох лол. Эпичность данного фейла сложно переоценить. WH>Я на макросах этот твой contextfreeart могу повторить один в один. WH>Те код можно будет тупо копипастить.
Ну клиника же. Варка в собственном соку... Не нужны для этой задачи никакие макросы внутри никакой IDE. Какой-нить прикладной спец в этом случае будет иметь возможность "наломать дров", что всегда и происходит. По ссылке в downloads лежит простейшее, заточенное под конкретную задачу IDE ("блокнот" + 3 кнопки). Там не автокомплит нужен, а мгновенный предпросмотр результата работы. Из опыта складов/бухгалтерий такая же точно история. Никогда не будут популярны склады-бухгалтерии на основе универсального языка и универсальной IDE.
Ты и Влад не понимаете сути подобных аргументов от коллег (а вам их накидали за эти годы просто тонны). Это не против Немерле аргументы, это аргменты против рекламируемого мнения, что универсальный тул заменит все остальные. Никто не отрицает, что у Немерле есть ниша. Даже многие согласны, что она может быть достаточно широка. Но вас же послушать — Немерле должен поглотить все остальные ниши. Вот на скидку и привел примеры, которые никогда не стали бы популярны, будь они завязаны на программирование в макросах на Немерле. И на вижуал-студию тоже, даже экспресс. Не веришь — попробуй пропихнуть тоже самое на Немерле. Удачи.
Здравствуйте, vdimas, Вы писали:
V>Я уж подумал, что не понравилась сотня мег/сек на ДКА-лексере. Это проверить самому 20 мин.
Для лексера это крайне посредственный результат. RE2 выдает порядка гига в секунду.
V>Что касается моего кода, то в избранном полно всяческих сниппетов за разные годы (в "файлах" тоже). Давал коллегам как подсказки/решения.
Меня интересует тема, которая обсуждается конкретно сейчас — парсеры. Ты вдребезги раскритиковал чужое решение, но показать свое упорно отказываешься
V>Кто-то должен был сказать что-то в ответ на все эти наезды.
Пока что ты не сказал ничего, кроме похвальбы и пустозвонства.
Здравствуйте, vdimas, Вы писали:
V>Только те, кто может себе позволить такие ресурсы. А так пишут на яках, бизонах, кокорах и прочих, коих много.
Так по чему люди тратят тонны ресурсов на ручной парсер?
А я скажу: По тому, что бизоны, коки итп УГ!
А те, кто их использует, работают с примитивными грамматиками при этом получают кривущее решение с жуткой диагностикой ошибок.
V>Это тоже причина не доверять Вольфхаунду в его типичных резолюциях "это ни на что не влияет". Я делился только теми приемами, которые у меня реально влияли. Просто у вас они влияют в рамках погрешности измерений производительности GC.
Клиника. У меня задача создать АСТ.
Если усложнение парсера приводит к ускорению в приделах погрешности измерения, то это усложнение идет в сад.
V>Во-первых, это уже другая тема. Во-вторых, Parser tree не сильно от AST отличается.
1)Отличается и сильно.
2)А зачем Parser tree вообще нужен? У меня его нет.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Так по чему люди тратят тонны ресурсов на ручной парсер? WH>А я скажу: По тому, что бизоны, коки итп УГ!
Ты же прекрасно знаешь в чем причина. Любая солидная контора всегда будет пытаться разработать компилятор ЯП с парсером по LL(1). Почему именно так, надеюсь известно? И почему не катят автогенерилки для LL(1) надеюсь тоже?
Опять же, это не значит, что ничего не автоматизируют при проектировании своего парсера. Системы, типа ASF+SDF, ANTLR и т.д. неимоверно популярны. Да и захардокить любой парсер по отлаженной грамматике — дело нехитрое. Просто далеко не все программисты владеют темой и не все сценарии требуют бороться за миллисекунды, вот и пользуются автогенерилками.
WH>Клиника. У меня задача создать АСТ. WH>Если усложнение парсера приводит к ускорению в приделах погрешности измерения, то это усложнение идет в сад.
Отсюда вывод — возиться с доработкой вашего парсера вообще нет смысла, пока вы упираетесь в GC. Но твои понты в тех постах, типа "ты ничего не угадал, это ни на что не влияют, нифига ты в парсерах не шаришь" таки показательны. Ты понятие не имел, что именно у вас влияет больше всего. Хотя я не раз пытался спросить, как и что именно вы замеряете — но ты не проникся ситуацией. К проблематике парсеростроения конкретно ваша причина не имеет никакого отношения. В общем, очередной epic fail.
WH>2)А зачем Parser tree вообще нужен? У меня его нет.
Он нужен там, где и даром не нужно AST. Т.е. фактически везде, кроме узкой области компиляторостроения под ЯВУ. Для сравнения, компиляторов ЯВУ в активной разработке вряд ли больше нескольких сотен по всему миру (ну или единиц тысяч), а только лишь среду ANTLR качают по 5тыщ экземпляров в месяц.
