PEG vs RegExp
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.06.10 19:26
Оценка: 160 (22) +1 :))
Есть мнение, что новые научные теории побеждают только тогда, когда вымирают сторонники старых теорий. Удивительно, но с совершенно практическими вещами дело обстоит точно так же. Возьмем, например, такую распространенную вещь, как регулярные выражения. Они поддерживаются практически везде, библиотеки или фреймворки, поддерживающие регулярные выражения, написаны практически для всех языков программирования. При этом за последние два десятилетия регулярные выражения мало изменились. В частности, они как были, так и остались "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++) не приходится. Почему? Вернитесь к началу сообщения.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.