Есть мнение, что новые научные теории побеждают только тогда, когда вымирают сторонники старых теорий. Удивительно, но с совершенно практическими вещами дело обстоит точно так же. Возьмем, например, такую распространенную вещь, как регулярные выражения. Они поддерживаются практически везде, библиотеки или фреймворки, поддерживающие регулярные выражения, написаны практически для всех языков программирования. При этом за последние два десятилетия регулярные выражения мало изменились. В частности, они как были, так и остались "write only" – будучи единожды написанными, они практически не поддаются прочтению. Оно и понятно, не так ведь просто догадаться, что делает набор из палочек и скобочек типа ("(\\"|\\\\|[^"])*"|/\*.*\*/|//[^\r]*) (если вы не смогли догадаться, то это выделение комментариев в С-подобном языке). Характерно, что регулярные выражения являются довольно слабым средством разбора текста, так как позволяют разбирать только регулярные (нерекурсивные) грамматики. Например, с их помощью невозможно полноценно разобрать XML или HTML.
Каковы же причины того, что регулярные выражения до такой степени нечитаемы, но при этом так популярны? Основная причина нечитаемости – в них отсутствуют средства абстрагирования, и более того, выражения приходится записывать одной монолитной строкой. Естественно, в таких условиях более-менее сложный образец превращается в кашу. А популярны они, по всей видимости, потому, что являются классическим и стандартным встроенным DSL. Как уже говорилось, они доступны где угодно, причем не просто доступны – они находятся "в шаговой доступности". На вопрос "почему не работает мое регулярное выражение" довольно легко найти ответ на любом программистском форуме. Получается парадокс – нечитаемый язык с плохими возможностями отладки, но очень доступный, вызывает массу проблем, но при этом все равно массово используется. Почему же ежики плачут, колются, но продолжают кушать кактус? Возможно, причина в том, что регулярным выражениям просто нет альтернативы?
Альтернатива, конечно, есть. Любой программист, окончивший любой ВУЗ, проходил курс формальных грамматик и знает, что существуют такие вещи, как контекстно-свободные грамматики и утилиты-генераторы парсеров, использующие более мощный язык (обычно BNF или EBNF). Такие генераторы парсеров построены на весьма изученных современной наукой методах, быстры и значительно мощнее регулярных выражений. Но на практике их используют редко даже по прямому назначению – для генерирования парсеров полноценных языков программирования.
Почему же парсеры на основе BNF/EBNF не используются там, где сейчас используются регулярные выражения? Одна из причин – такие парсеры несколько более сложны. Они требуют отдельного выделения токенов, что фактически аналогично возможностям регулярных выражений, и уже только потом – описания самой грамматики. Но нам кажется, что это мелкая и уж точно не главная причина. Основных причин две. Первая – требование более высокой квалификации программиста, а вторая, и, возможно, главная – то, что такие парсеры трудно использовать как встроенные средства. Использование регулярных выражений из языка программирования обычно сводится либо к вызову функции, либо к использованию встроенной прямо в язык (как в Perl) поддержки. Если такой поддержки или функции нет, то время, затрачиваемое программистом на создание нужного ему окружение, равно (а чаще превышает) время, которое потребуется программисту для ручного разбора нужных данных. В этом случае начинают работать естественные факторы – лень и желание избежать объемной непродуктивной работы. Программисты просто выбирают обходные пути, либо вообще избавляясь от разбора текста, или делая его кое-как. В общем, таких парсеров нет, и встроить их в языки общего назначения тяжело.
Относительно недавно появилась работа некоего Брайена Форда (Bryan Ford), посвященная его алгоритму, названному "packrat parsing". Он вытащил на свет формализм, разработанный около 30 лет назад, и описывавший парсер, использующий алгоритм нисходящего спуска с откатами (Top-Down Parsing Language, TDPL). Этот формализм позволяет описывать практически любой язык с одним ограничением – у этого языка может быть только одно дерево разбора, то есть он не может быть неоднозначным. Под это описание подходит практически любой компьютерный язык (в отличие от человеческих, неоднозначных по природе). В те далекие времена было научно доказано, что этот метод разбора может привести к экспоненциальному росту времени разбора. Алгоритм packrat за счет мемоизации промежуточных результатов позволил добиться линейного времени разбора. Однако на практике и без данной оптимизации этот алгоритм показывает весьма высокую производительность, по крайней мере не меньшую, чем скорость многих библиотек регулярных выражений, например, в .NET. В качестве формализма для описания TDPL Форд использовал PEG. Так вот PEG очень близок к регулярным выражениям, но при этом имеет средства абстрагирования и позволяет описывать рекурсивные грамматики. Его можно использовать в точно так же как регулярные выражения (поместив парсер в функцию или встроив его поддержку в язык программирования общего назначения). Более того, первые ласточки его использования уже есть – создана библиотека LPEG, которая позиционируется как замена регулярных выражений для языка Lua. Однако надеяться на победоносное шествие PEG по господствующим языкам и фреймворкам (Java, .NET, C++) не приходится. Почему? Вернитесь к началу сообщения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Есть мнение, что новые научные теории побеждают только тогда, когда вымирают сторонники старых теорий. Удивительно, но с совершенно практическими вещами дело обстоит точно так же. Возьмем, например, такую распространенную вещь, как регулярные выражения. Они поддерживаются практически везде, библиотеки или фреймворки, поддерживающие регулярные выражения, написаны практически для всех языков программирования. При этом за последние два десятилетия регулярные выражения мало изменились. В частности, они как были, так и остались "write only" – будучи единожды написанными, они практически не поддаются прочтению. Оно и понятно, не так ведь просто догадаться, что делает набор из палочек и скобочек типа ("(\\"|\\\\|[^"])*"|/\*.*\*/|//[^\r]*) (если вы не смогли догадаться, то это выделение комментариев в С-подобном языке). Характерно, что регулярные выражения являются довольно слабым средством разбора текста, так как позволяют разбирать только регулярные (нерекурсивные) грамматики. Например, с их помощью невозможно полноценно разобрать XML или HTML. VD>Каковы же причины того, что регулярные выражения до такой степени нечитаемы, но при этом так популярны? Основная причина нечитаемости – в них отсутствуют средства абстрагирования, и более того, выражения приходится записывать одной монолитной строкой. Естественно, в таких условиях более-менее сложный образец превращается в кашу. А популярны они, по всей видимости, потому, что являются классическим и стандартным встроенным DSL. Как уже говорилось, они доступны где угодно, причем не просто доступны – они находятся "в шаговой доступности". На вопрос "почему не работает мое регулярное выражение" довольно легко найти ответ на любом программистском форуме. Получается парадокс – нечитаемый язык с плохими возможностями отладки, но очень доступный, вызывает массу проблем, но при этом все равно массово используется. Почему же ежики плачут, колются, но продолжают кушать кактус? Возможно, причина в том, что регулярным выражениям просто нет альтернативы? VD>Альтернатива, конечно, есть. Любой программист, окончивший любой ВУЗ, проходил курс формальных грамматик и знает, что существуют такие вещи, как контекстно-свободные грамматики и утилиты-генераторы парсеров, использующие более мощный язык (обычно BNF или EBNF). Такие генераторы парсеров построены на весьма изученных современной наукой методах, быстры и значительно мощнее регулярных выражений. Но на практике их используют редко даже по прямому назначению – для генерирования парсеров полноценных языков программирования. VD>Почему же парсеры на основе BNF/EBNF не используются там, где сейчас используются регулярные выражения? Одна из причин – такие парсеры несколько более сложны. Они требуют отдельного выделения токенов, что фактически аналогично возможностям регулярных выражений, и уже только потом – описания самой грамматики. Но нам кажется, что это мелкая и уж точно не главная причина. Основных причин две. Первая – требование более высокой квалификации программиста, а вторая, и, возможно, главная – то, что такие парсеры трудно использовать как встроенные средства. Использование регулярных выражений из языка программирования обычно сводится либо к вызову функции, либо к использованию встроенной прямо в язык (как в Perl) поддержки. Если такой поддержки или функции нет, то время, затрачиваемое программистом на создание нужного ему окружение, равно (а чаще превышает) время, которое потребуется программисту для ручного разбора нужных данных. В этом случае начинают работать естественные факторы – лень и желание избежать объемной непродуктивной работы. Программисты просто выбирают обходные пути, либо вообще избавляясь от разбора текста, или делая его кое-как. В общем, таких парсеров нет, и встроить их в языки общего назначения тяжело. VD>Относительно недавно появилась работа некоего Брайена Форда (Bryan Ford), посвященная его алгоритму, названному "packrat parsing". Он вытащил на свет формализм, разработанный около 30 лет назад, и описывавший парсер, использующий алгоритм нисходящего спуска с откатами (Top-Down Parsing Language, TDPL). Этот формализм позволяет описывать практически любой язык с одним ограничением – у этого языка может быть только одно дерево разбора, то есть он не может быть неоднозначным. Под это описание подходит практически любой компьютерный язык (в отличие от человеческих, неоднозначных по природе). В те далекие времена было научно доказано, что этот метод разбора может привести к экспоненциальному росту времени разбора. Алгоритм packrat за счет мемоизации промежуточных результатов позволил добиться линейного времени разбора. Однако на практике и без данной оптимизации этот алгоритм показывает весьма высокую производительность, по крайней мере не меньшую, чем скорость многих библиотек регулярных выражений, например, в .NET. В качестве формализма для описания TDPL Форд использовал PEG. Так вот PEG очень близок к регулярным выражениям, но при этом имеет средства абстрагирования и позволяет описывать рекурсивные грамматики. Его можно использовать в точно так же как регулярные выражения (поместив парсер в функцию или встроив его поддержку в язык программирования общего назначения). Более того, первые ласточки его использования уже есть – создана библиотека LPEG, которая позиционируется как замена регулярных выражений для языка Lua. Однако надеяться на победоносное шествие PEG по господствующим языкам и фреймворкам (Java, .NET, C++) не приходится. Почему? Вернитесь к началу сообщения.
статья классная... я даже не то что не находил альтернативы регулярных выражений, а даже не мог подумать что стоит поискать...
вперед на habrahabr
Здравствуйте, VladD2, Вы писали:
VD>Почему? Вернитесь к началу сообщения.
Все гораздо проще. Я, например, никогда не слышал про PEG. Думаю таких, как я, большинство. Благодаря форуму узнал и буду пробовать. И никакой интриги.
Считаете что PEG лучше Regexp, так сделайте и не оглядывайтесь на чужие мнения. Примерно так появились все передовые разработки.
Только кроме самой возможности в Nemerle, еще хотелось бы видеть реюзабельную библиотеку для .NET (иначе смысла нет) и какой-нить killer app, демонстрирующий фичу.
Она реализует парсер EBNF. Причем в компайлтайме. Несмотря на несколько покореженный синтаксис вполне удобна.
❝ Некоторые люди, во время решения одной проблемы думают: «Я знаю, я буду использовать регулярные выражения». Теперь у них две проблемы… ❞— Jamie Zawinski
А кому надо — пользуют нормальные парсеры.
Здравствуйте, olegkr, Вы писали:
VD>>Почему? Вернитесь к началу сообщения. O>Все гораздо проще. Я, например, никогда не слышал про PEG. Думаю таких, как я, большинство. Благодаря форуму узнал и буду пробовать. И никакой интриги.
Проблема в том что пробовать не чего (ну, если конечно ты не собираешся пересесть на Nemerle или Lua). И, что самое обидное, вряд ли появится в ближайшее время? Почему? Вернись к началу сообщения
Здравствуйте, gandjustas, Вы писали:
G>Только кроме самой возможности в Nemerle, еще хотелось бы видеть реюзабельную библиотеку для .NET (иначе смысла нет) и какой-нить killer app, демонстрирующий фичу.
Оно есть http://code.google.com/p/peg-sharp/
Насколько оно юзабельно — сейчас выясняю. Киллер фича — рекурсия и то, что PEG действительно можно читать.
Имхо, главная причина, мало кому нужно.
Предположим задачи среднестатистического программиста разбиты так.
99% — никак не связаных с каким либо разбором текста.
0.9% — текст, но либо что то простое что вполне укладывается в несложный регексп >Например, с их помощью невозможно полноценно разобрать XML или HTML.
либо для данного формата уже есть тонна библиотек для его разбора, кому нужно писать свой парсер html?
0.1% — да вот эти самые задачи для PEG, 0.09% который наверное можно решить существующими инструментами типа ANTLR.
Здравствуйте, gandjustas, Вы писали:
G>Красиво написано, но непонятно к чему.
Пользуясь случаем — спасибо за редактирование Михаилу Купаеву.
G>Считаете что PEG лучше Regexp, так сделайте и не оглядывайтесь на чужие мнения.
Сделал(и)
G>Только кроме самой возможности в Nemerle, еще хотелось бы видеть реюзабельную библиотеку для .NET (иначе смысла нет) и какой-нить killer app, демонстрирующий фичу.
"Реюзабельная библиотека в дотнете" требует совсем другого объема работы и при этом еще и не обеспечивает того же удобства и скорости как то что сделано в немерле на коленке. Но это уже другая история.
В общем, моя задача — обратить внимание на проблему других с тем, чтобы эти другие решили проблему для их любимых языков. Мы даже создали отличный прототип этого дела. Осталось передать эстафету .
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Насколько я понимаю она использует похожий алгоритм рекурсивного супска. Но думаю что без откатов.
Ну, а огромной проблемой этой библиотеки является средство реализации. Простенькие примеры выливаются в сотни мег занятоно места на диске.
M>❝ Некоторые люди, во время решения одной проблемы думают: «Я знаю, я буду использовать регулярные выражения». Теперь у них две проблемы… ❞— Jamie Zawinski
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, olegkr, Вы писали:
VD>>Проблема в том что пробовать не чего O>Есть peg sharp, его и пробую.
Поглядел... Это очередной внешний генератор (если я правильно понял). Особым минусом является semantic actions задаваемые в конце правил (после апострофа). Это вряд ли может конкурировать с регексами.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>"Реюзабельная библиотека в дотнете" требует совсем другого объема работы и при этом еще и не обеспечивает того же удобства и скорости как то что сделано в немерле на коленке. Но это уже другая история.
А тогда какой смысл? Пока не будет возможности написать что-то вроде Regex.Replace нету смысла обсуждать что лучше, не сопоставим уровень трудозатрат и получаемого эффекта.
VD>В общем, моя задача — обратить внимание на проблему других с тем, чтобы эти другие решили проблему для их любимых языков. Мы даже создали отличный прототип этого дела. Осталось передать эстафету .
имхо тут кроется наибольшая проблема немерелистов, вы не занимаетесь популяризацией nemerle.
Страуструп, Гослинг, Кей, ван Россум, Вирт, они все сами продвигали свои творения, а не ждали кому бы "передать эстафету".
Здравствуйте, dotneter, Вы писали:
D>Имхо, главная причина, мало кому нужно. D>Предположим задачи среднестатистического программиста разбиты так.
D>99% — никак не связаных с каким либо разбором текста.
D>0.9% ...
И как при этом регексы появились?
Может быть проблема в том, что проблема которая составляет 0.9% от основной задачи начинает занимать 20% времени всей разработки при решении ее без соответствующих средств?
А если так, то почему не использовать более мощные и удобные средства для того же самого?
>>Например, с их помощью невозможно полноценно разобрать XML или HTML. D>либо для данного формата уже есть тонна библиотек для его разбора, кому нужно писать свой парсер html?
Зайди на форум по дотнету погляди сколько людей пытается парсить ХМЛ/ХТМЛ с помощью регексов.
D>0.1% — да вот эти самые задачи для PEG, 0.09% который наверное можно решить существующими инструментами типа ANTLR.
Про ANTLR написано в тематическом сообщении.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, gandjustas, Вы писали:
G>А тогда какой смысл? Пока не будет возможности написать что-то вроде Regex.Replace нету смысла обсуждать что лучше, не сопоставим уровень трудозатрат и получаемого эффекта.
Чтобы "Regex.Replace()" сначала нужно написать "class Regex ...". Это уже сделано... для Regex...
Еще вопросы?
G>имхо тут кроется наибольшая проблема немерелистов, вы не занимаетесь популяризацией nemerle.
Мне казалось мы о PEG назговариваем. Но в общем-то с Немерлом те же проблемы. У всех есть унылое говно к которому все привыкли и тратить деньки и время на создание чего-то лучше (да что там на создание, на попробовать даже) никто не хочет. В прочем, это тоже другая история.
G>Страуструп, Гослинг, Кей, ван Россум, Вирт, они все сами продвигали свои творения, а не ждали кому бы "передать эстафету".
PEG не моя идея. Я ее увидел, воспользовался и рассказал окружающим. Не понимаю почему меня при этом в чем-то бвиняют.
И главное... не понимаю причем тут Немерле?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Поглядел... Это очередной внешний генератор (если я правильно понял). Особым минусом является semantic actions задаваемые в конце правил (после апострофа). Это вряд ли может конкурировать с регексами.
Есть такое. Без особой необходимости пользоваться не захочется.
Здравствуйте, VladD2, Вы писали:
VD>И как при этом регексы появились?
Администраторам юникс систем нужен был иструмен для работы с текстом, а потом худо бедно перекочивал в программирование взяв с собой проблеммы однострочности, понимаемости и сопровождения. VD>Может быть проблема в том, что проблема которая составляет 0.9% от основной задачи начинает занимать 20% времени всей разработки при решении ее без соответствующих средств?
Сомневаюсь.
VD>А если так, то почему не использовать более мощные и удобные средства для того же самого?
Мощность не дается бесплатна, ее нужно изучать а многие и регекспы не могут осилить.
VD>Зайди на форум по дотнету погляди сколько людей пытается парсить ХМЛ/ХТМЛ с помощью регексов.
Я думаю эти люди не справяться с пегом.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, gandjustas, Вы писали:
G>>А тогда какой смысл? Пока не будет возможности написать что-то вроде Regex.Replace нету смысла обсуждать что лучше, не сопоставим уровень трудозатрат и получаемого эффекта.
VD>Чтобы "Regex.Replace()" сначала нужно написать "class Regex ...". Это уже сделано... для Regex... VD>Еще вопросы?
Ага, кто будет писать?
G>>имхо тут кроется наибольшая проблема немерелистов, вы не занимаетесь популяризацией nemerle.
VD>Мне казалось мы о PEG назговариваем.
Пока реализация peg в более пригодном виде есть только в Nemerle (хотя есть парсер-комбинаторы в других языках).
G>>Страуструп, Гослинг, Кей, ван Россум, Вирт, они все сами продвигали свои творения, а не ждали кому бы "передать эстафету".
VD>PEG не моя идея. Я ее увидел, воспользовался и рассказал окружающим.
Все послушали, согласились и продолжили использовать regex, а потом выросло следующее поколение разработчиков, которое кроме regex ничего и не знает.
VD>Не понимаю почему меня при этом в чем-то бвиняют. И главное... не понимаю причем тут Немерле?
При том что единственный способ популяризировать идею — воплотить её в жизнь.
