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

S>Для DSL придётся изобретать формат и структуру документации самостоятельно, что и является шоу-стоппером.
На грамматику можно повесить теже самые Doc Comments.
С семантикой сложнее. Но для сложной либы тоже одними Doc Comments не отделаешься.

S>Вот это — убедительный пример. Хотелось бы подробностей.
Это был стековй (хотя наверное надо было делать регистровый ибо локальное хранилище считай регстры всеравно было), load/store (созранение/загрузка одни команды обработка другие), XML-based (ибо он изначально создавался под генерацию кода демонами) язычек в котором описывалось какие данные из распределенного хранилища поднять, что и как с ними сделать и куда их сохранить.
Все это с поддержкой транзакций, фаиловера и тому подобным.
Также данные могли приходить вместе со скриптом. Тогда они помещались в "локальное хранилище".

Изначально начальство хотело певесить прикладную логику на меня. Но когда я понял что буду узким местом в трех проектах (и на горизонте еще маячили...) я сделал интерпритируемый ДСЛ.
Интерпритируемость ни на что не влияла ибо каждая из команд могла выполняться до нескольких секунд.
Соответственно ко мне приходили всего несколько раз когда нужно было добавить еще команд, а не каждый день когда у них там что-то менялось.
Им тоже было хорошо ибо ко мне и без них очередь была не слабая, а так они могли сами пару строк в своем коде поправить. Да и поэксперементировать на тестовом кластере можно было без проблем.

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

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

N>>Дай Nemerle хотя бы под JVM, и мы начнём его рассматривать. А лучше — под LLVM или native. А на сейчас — его не существует для тех, кто хочет выйти за пределы десктопа.
WH>Во первых не стоит списывать со счетов виндовые серверы. Они очень не плохо работают.

Для моих задач это даже не под микроскопом, этого просто нет.

WH>Во вторых моно никто не отменял.

Моно — УГ.

WH>Ну и у Н2 со временем будут сменные бекенды.

"Не кажи гоп..."
Когда они будут и начнут работать, тогда и начнём смотреть. Не раньше.

Здравствуйте, WolfHound, Вы писали:
WH>На грамматику можно повесить теже самые Doc Comments.
Это место мне непонятно. Можно пример?

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

WH>>На грамматику можно повесить теже самые Doc Comments.
S>Это место мне непонятно. Можно пример?
Берем например парсер C#
http://code.google.com/p/nemerle/source/browse/nemerle/trunk/snippets/csharp-parser/CSharpParser/Parser.n
И пишем Doc Comments на каждое правило.
Типа так:

            /// <summary>
            /// Any character
            /// </summary>
      any                     = ['\u0000'..'\uFFFF'];

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

M>Нет такой проблемы, а есть теорема о том, что каждый НКА может быть преобразован в ДКА, допускающий тот же язык. ДКА разбирает любую строку за время O(n), где n -- длина этой строки. В этом и состоит сермяжный смысл задания шаблонов с помощью регулярных выражений. Есть теорема Клини, которая гласит: классы автматных и регулярных языков совпадают. Это, в частности, означает, что для каждого регуляного выражения можно построить ДКА, допускающий в точности тот же язык, что опсиан регулярным выражением. Проблема с перловыми регулярками в том, что они расширили синтаксис языка регулярных выражений для ссылки на группы, выделенные в начале. Это ведет к неоднозначностям и необходимости откатов (если выбран поиск в глубину). Последнее, в свою очередь, ведет к тому, что невозможно построить ДКА для такого выражения. Вынужденно работать с НКА на этапе компиляции и пытаться строить ДКА методом ленивого вычисления подмножеств -- не есть хорошо. Поэтому такие компании, как Google и Яндекс недавно выпустили свои версии поисковых движков на основе регулярных выражений (https://github.com/dprokoptsev/pire и http://code.google.com/p/re2/).

Вот так пользуясь вполне вменяемыми научными теориями и реальными ссылками можно сделать в корне не верные выводы.

M>При построении поисковых автоматов главная проблема состоит в выделении групп (того, что в круглых скобках), при таком выделении возникают неоднозначности, которые можно разрешить, например, установив по умолчанию жадный поиск.

Факт в том, что регулярки на основе ДКА очень ограничены в применении (неудобны). А те что имеют много фич как один используют худшие варианты бэктрэкинда, а значит НКА.

M>Кроме того, могут быть проблемы с построением из ПОИСКОВОГО НКА с обратными ссылками соответствующего ДКА. Состояний в некоторых случаях может набраться сотни тысяч, автомат раздувается. Хотя это проблема не метода, а ресурсов.

Это проблема тех кто пытается использовать такие решения.

M>Принципиальное отличие регулярок от PEG -- это возможность построения оптимального линейного поискового движка.

Это бред. Как было замечено выше. 90% регулярок не используют ДКА по куче соображений. Те что используют дико ограничены в возможностях и далеко не такие шустрые как ты тут пыташеся описать.

Дело в том, что важны не только теории, но и проблемы реализации этих теорий на базе конкретного железа, конкретных ЯП и конкретных компиляторов.

M>Грамматики PEG, насколько я понимаю, иногда даже в рамки КС-языков не укладываются, поэтмоу сравнивать их с регулярками все равно, что сравнивать теплое с мягким.

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

Собственно WolfHound это и проделал (с нашей помощью). В итоге мы получили решение которое не уступает в скорости ни лучшим ДКА-ным движкам регексов, ни лучшим генераторам парсеров. А имеющиеся на дотнете реализации регулярок он рвет настолько жестого, что их даже стыдно с ним сравнивать.

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

А теперь о главном

Сейчас WolfHound тратит время на совершенно бессмысленные споры с тобой и окружающими. А тем временем развитие мега-крутого движка парсинга на основе PEG-а (сделанного WolfHound-ом) стоит на месте!

Он уже где-то пол года обещает сделать наш движок расширяемым динамически. Ты хорошо рассылшал? Ага. Движок который рвет все статические движки еще к тому же может (и будет) расширяться динамически!

Так вот давайте как все вместе перестанем спорить и попросим нашего уважаемого WolfHound перестать заниматься херней (спорить с теоретиками) и таки сделает то что нам нужно по зарез!

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

J>Ну тогда твой движок перестанет быть пегом и станет регэкспом, не?

Нет. Бэки не нужны просто потому, что есть именованные правила и предикаты. Это в сто раз круче.

J>Вон, даже гугл отказался в RE2 от попыток сделать быстрые регэкспы с бэкреференсами — они их там просто запретили.

Они ограничивают функционал, чтобы влезть в рамки ДКА. Вот только наша реализация ПЕГ-а скорее всего порвет эти RE2 без этих ограничений. Ну, если и не порвет, то будет давать очень близкие результаты.

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

J>посмотрим, как быстро он сможет парсить бэкреференсы с квантификаторами.

А с какой целью они тебе нужны? Покажи правило которое без них ты не можешь разобрать.

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

J>Ты тогда тоже разберись, что такое регэкспы и как там работает ".*", и тебе тоже все станет ясно.
J>В ПЕГе в принципе нет понятия "последовательность любых символов с откатом" (т.е. оно есть, но не имеет смысла, так как такое правило просто съест всю строчку до конца), поэтому мне придется написать грамматику для этой последовательности, чтоб она не съела больше, чем нужно — очевидный оверкилл для большинства случаев, когда тебе нужно что-нть по-быстрому найти.

Это по по незнанию лепишь. На самом деле есть и понятие, и применять его очень даже можно. Вот как, например, выглядит правило разбора сишного комментария:

delimitedComment          = "/*" (!"*/" any)* "*/";

any — это и есть твоя точка. Просто то что делается на "умности" "*" в регексах в ПЕГе делается на предиткатах.
И что характерно, на практике это намного удобнее. Ведь ".*" в регексах найдет последнее хождение того что идет за ним, а это как раз обычно никому не нужно.

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

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

H>>Пакрат обычно не реализуется вообще — он дико медленный

K>Интересно, почему так получается?

На саомо деле это не совсем так. Во-первых есть куча поделок использующих чистых Пакрат. Но они тормозные. Скорость линейно низкая .

Кроме того есть реализация Rats! которая исходит из тотальной мемоизации и вводит кучу оптимизаций уменьщающих негативное влияние этой самой мемоизации на "константу" времени. В итоге они сделали вполне себе применимый на практике генератор парсеров который практически гарантирует линейное время.

Однако же все же еще лучше отказаться от гарантий линейного времени, но при этом улучшить "константу" для наболее часто используемых случаев.

Именно так и было сделано в ПегГраммаре о котором говорит веольфхаунд. Он начал с чистого Пакрата, но в итоге получился совсем другой алгоритм.

Секрет в том, что 99% грамматик компьютерных языков это "почти LL(1) граммитики". Но вот это почти делает создание парсеров для них на чем-то вроде LL(k) или LARL(1) мучительным до безобразия.

Большая часть реальных парсеров по прежнему пишется вручную методом рекурсивного списка. Это позволяет сделать в основном простой парсер и разрулить сложные места врукопашную.

Так вот ПегГраммар делает тоже самое. Он оптимизирует эти самые 99% так как только может. Для разбора регулярной части используется ДКА (причем не табличный, а генерированный). Для нивилирования откатов используется частичная мемоизация. Ну, и сам он написан так чтобы не тратить такты зря. Первое что было предложено — это использовать в качестве позиции и информации об успехе парсинга одну переменную типа int. Почему-то большинство тех кто реализует ПЕГ до этого не додумываются. Далее была сделана отимизация правил (переписывание) и инлайнинг. Потом ДКА и мемоизация. В купе это дало очень приличную скорость. Многие в ручную написанным парсером такую обеспечить не могут.

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

ВВ>Почему? Идея пакрата, как я понимаю, это "мемоизируем все". Т.е. по идее это не должно бы приводить к "дико медленный". К тому же автор декларировал линейное время парсинга, откуда бы взяться тормозам?

Линейное и быстрое не синонимы . Линейное время он гарантирует. Но формула у его линейности такая:

O(C)
C = N * P * P_size

Где "C" — это константа потребления памяти.
N — это количество символов в разбираемой строке.
P — количество правил в грамматике.
P_size — средний размер структур данных занимаемых под представление состояния мемоизации.
В итоге C для сложных грамматик и больших файлов получается весьма большим. И то что скорость линейная — это не радует, так как на каждый шаг требуется слишком много времени.

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

ВВ>А если мемоизировать не все, то будет быстрее линейнего что ли?

Для большей части входных строк — да.

ВВ>Мне интересно:
ВВ>- Пакрат реально дает O(n) или это только в теории, а на практике это не O(n)? Если да, то почему так происходит.
ВВ>- Если излишняя мемоизация вредна, но по каким критерием определяется, что мемоизировать, а что нет?

Ответ таков. Ты не понимаешь что такое линейное время.

Представь себе, что мы имеем линейный алгоримт. Это быстро или медленно?
Правильный ответ — ни то и ни другое.

Скажем если мы имеем линеный алгоритм парсинга который на распознование каждого символа тратит 0.01 секунды, то на разбор уже килобайта информации у него уйдет секунда! А на мегабайт 10.

В то же время не линеный алгоритм может показывать экспоненциальный рост времени разбора, то только в очень экзатических случаях. Зато в 99% реальных случаев он может показывать очень высокую скорость, так как в среднем на один символ будет тратить не 0.01 секунды, а 0.0000001.

Так вот линейный алгоримт это когда у него на каждый символ всегда 0.01 или 0.00001. А не линейный, это когда иногда 0.00001, а иногда 0.01.

Так что линейность хороша только в теории. На практике важна не линейность, а практическая применимость. Вот Пакрат линейный, но практически не применимый. А наш алгоритм не линейный, но очень быстрый на практике.

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

DG>из-за того, что промежуточные результаты парсинга запоминаются, а из свойств packrat-а следует, что применение конкретного правила к конкретной позиции — всегда выдает один и тот же результат (в независимости от предыдущих вызовов),
DG>то выполнение не может быть хуже, чем: длина текста * кол-во правил

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

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

WH>>>>Это просто пример того что из людей получаются хреновые компиляторы.
J>>>Идиотский пример, потому что нет постановки задачи.
WH>>Тем не менее ты запутался в 4х символах...
J>Ну и что к реальной жизни это не имеет отношения.

Реальная жизнь таковая, что лично я не раз запутывался в регексах размером с пол предложения что я сейчас написал.
Может я конечно дебил. Тогда это все объясняет.

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

WH>>А ты пробовал?
O>Зачем мне это нужно? У меня есть выбор
O>1) Написать пару строк на дотнете, заюзав стандартный фреймворк
O>2) Поставить немерле, добавить новый проект в солюшн, изучить синтаксис, потрахаться, поругаться с менеджером, провести неделю в митингах с подчиненными индусами

O>Кто в здравом уме выберет пункт 2?

Тот кто решает действительно сложные задачи и хочет решать их проще (умнее).
Но те кто выбирает индусов явно не из этого круга. Им Немерл все равно что самолет обезьяне.

WH>>Это генератор C# из ПЕГа?
O>Это обычный регексп, которого хватает на все сто. Объясни мне причины по которым я должен перейти не пег? Скорость парсинга и рекурсия меня не интересуют.

Причин нет. Каковы задачи таковы и инструменты. Если задачи примитивные, значит и тупых инструментов (да и тупых исполнителей) хватит.

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

Z>Обычно генератор подразумевает свой язык. Как инструмент они ничем не отличаются от nemerle. Хоть ANTLR, хоть Coco/R, у тебя в проекте появится код на их языке. И тебе придется что-то устанавливать, чтобы получить IDE для разработки. В чем отличия-то?

А это феномен, кстати! Люди не боятся кривых сложных языков которые не конкурируют с их любимым языком общего назначения. Но как огня боятся языка который может заменить им их любимый язык.

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

Z>Ну не такая уж она и существенная, надо лишь сделать аналогичный макрос принимающий грамматику в виде строки, превращающий ее в аст и вызывающий старый макрос. Вообще это надо бы сделать, хотя бы для использования пегпарсера в виде библиотеки и компиляции грамматик в рантайме. Может займусь через некоторое время.

Тогда уж можно просто внешинй ДСЛ залудить. Но все равно бояться будут.

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

VD>Тот кто решает действительно сложные задачи и хочет решать их проще.
Что ты считаешь проще?
На текущем уровне работа с nemerle ведет к большим трудозатратам, чем на C#\VB для типовых задач.
Это как всегда связано документацией и инструментами.

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

S>Чтобы PEG заменил регекспы, нужно, чтобы он стал
S>а) очень-очень распространён. Чтобы можно было за $28 купить или за $7.99 скачать книгу O'Reilly про него, где всё обсосано до мелочей. Чтобы библиотеки с его поддержкой (совместимые по способу использования!!!) были широко доступны на всех основных языках разработки.
S>б) применим для мелких масштабов. Чтобы можно было применять его для проверки, поиска и замены коротких цепочек.
S>в) применим для непрограммистов. Чтобы "грамматику" или что там у него вместо строки регекспа можно было скормить в мою программу через несложный UI (или конфиг-файл), не привлекая IDE c code completion и билд-машину.

+1 По этому следующие 10 лет мы (пользователи немрла) будем пользоваться плодами прогресса, а вы каменным молотком. Ну, если конечно не хотите присоединиться к нам.

Мы вот сейчас начали проект Nemerle 2. В нем макросы будут с использованием PEG-а сделаны.

Не хочешь присоединиться?

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

N>Дай Nemerle хотя бы под JVM, и мы начнём его рассматривать. А лучше — под LLVM или native. А на сейчас — его не существует для тех, кто хочет выйти за пределы десктопа.

Уверен, что появись указанные бэкэнды у тебя найдутся новые отговорки.

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

S>>>Много факторов дополнительных есть — в том числе и наличие инструментария по построению DSL.
WH>>Немерле весьма не плох. Второй вообще конфеткой будет.
S>Было бы здорово.

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