Компилятор регулярных выражений

Question

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

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

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

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

Тогда я хотел бы задать вопрос: существует ли такая вещь, как компилятор регулярных выражений? Или можно даже построить?

Можно было бы рассматривать регулярные выражения с метафорической точки зрения как язык ассемблера - здесь есть некоторые сходства. Может ли быть разработан компилятор, который мог бы превратить более естественный язык - более высокий язык - в регулярные выражения? Затем в моем коде я мог определить свои регулярные выражения, используя язык более высокого уровня в заголовочном файле, и ссылаться на них при необходимости, используя символическую ссылку. Я и другие могли бы ссылаться из моего кода на файл заголовка и легче оценивать то, чего я пытаюсь достичь с помощью моих регулярных выражений.

Я знаю, что это можно сделать с логической точки зрения, иначе компьютеры были бы невозможны, но если бы вы зашли так далеко, то не могли бы вы потратить время на его реализацию?

Answer 1

1) Perl разрешает использование регулярных выражений /x для включения комментариев и пробелов в само регулярное выражение. Это позволяет разбить сложное регулярное выражение на несколько строк, используя отступ для указания структуры блока.

2) Если вам не нравятся сами символы, напоминающие шум строки, нетрудно написать свои собственные функции, которые создают регулярные выражения. Например. в Perl:

sub at_start { '^'; }
sub at_end { '$'; }
sub any { "."; }
sub zero_or_more { "(?:$_[0])*"; }
sub one_or_more { "(?:$_[0])+"; }
sub optional { "(?:$_[0])?"; }
sub remember { "($_[0])"; }
sub one_of { "(?:" . join("|", @_) . ")"; }
sub in_charset { "[$_[0]]"; }       # I know it's broken for ']'...
sub not_in_charset { "[^$_[0]]"; }   # I know it's broken for ']'...

Тогда, например, регулярное выражение для соответствия строке в кавычках (/^"(?:[^\\"]|\\.)*"/) становится:

at_start .
'"' .
zero_or_more(
    one_of(
        not_in_charset('\\\\"'),    # Yuck, 2 levels of escaping required
        '\\\\' . any
    )
) .
'"'

Использование этой стратегии «функции построения строк» ​​позволяет выразить полезные строительные блоки в виде функций (например, приведенное выше регулярное выражение может быть сохранено в функции с именем quoted_string(), у вас могут быть другие функции для надежного сопоставления с любым числовым значением, например адрес электронной почты и т. д.).

Answer 2

Регулярные выражения (ну, «настоящие» регулярные выражения, ничего из того современного); это конечные автоматы. Поэтому вы создаете синтаксис, который описывает регулярные выражения в терминах состояний, ребер, входных и, возможно, выходных меток. fsmtools от AT & T поддерживают нечто подобное, но они далеки от инструмента, готового к повседневному использованию.

Язык в XFST , инструментарии конечного состояния Xerox, также более подробный.

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

Answer 3

А как насчет того, чтобы написать их с помощью Regex Buddy и вставить описание, которое оно генерирует как комментарий к вашему коду?

Answer 4

Я никогда не сталкивался с чем-то подобным. И я не думаю, что что-то подобное было бы полезно.

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

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

Answer 5

«Модель содержимого» XML-схемы является примером того, что вы хотите.

c(a|d)+r

может быть выражено как модель содержимого в XML-схеме как:

<sequence>
 <element name="c" type="xs:string"/>
 <choice minOccurs="1" maxOccurs="unbounded">
  <element name="a" type="xs:string"/>
  <element name="d" type="xs:string"/>     
 </choice>
 <element name="r" type="xs:string"/>
<sequence>

У Relax NG есть другой способ выразить ту же идею. Это не должен быть сам формат XML (Relax NG также имеет эквивалентный синтаксис не XML).

Читаемость регулярных выражений снижается благодаря необходимому экранированию, и такой формат, как приведенный выше, уменьшает необходимость в этом. Читаемость регулярного выражения также уменьшается, когда регулярное выражение становится сложным, потому что не существует систематического способа составления регулярных выражений большего размера из меньших (хотя вы можете объединять строки). Модульность обычно помогает. Но для меня более короткий синтаксис чрезвычайно удобен для чтения (я часто конвертирую модели содержимого XML-схемы в регулярные выражения, чтобы помочь мне с ними работать).

Answer 6

Существуют способы сделать RE в их обычной форме более читабельными (например, синтаксис perl /x) и несколько более выразительных языков для их выражения. См:

• https://stackoverflow.com/questions/263072/why-are-regular-expressions-such-a-complicated-cryptic-mess
• Почему люди защищают синтаксис регулярных выражений?

Однако отмечу, что многим старым рукам они не нравятся.

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

Answer 7

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

Answer 8

Возможно, некоторые инструменты JavaScript могут помочь:

• Визуализируйте RegEx , что довольно удивительно, он также на GitHub
• Оцените RegEx несколькими способами
• Regex Evaluator с некоторой подсветкой синтаксиса
• Быстрый оценщик RegEx с некоторыми полезными регулярными выражениями

К сожалению, я не нашел ни одного готового к использованию инструмента JS "наведи и щелкни", чтобы легко создавать и манипулировать RegEx. Сила RegEx (PCRE, Posix, Python) в том, что они

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

Так что изобретать колесо, возможно, не лучший выбор, и Регулярные выражения уже скомпилированы для ускорения процесса. Если вы ищете что-то более сложное, есть LEX и YACC (и их преемники), но в большинстве случаев обе вещи преувеличивают по сравнению с простым способом применения RegEx.

Следующее может быть полезно для других, но это не Linux, поэтому я не смог его протестировать:

• .NET и VS regex tools

Если вы найдете другие хорошие ссылки, возможно, добавьте в качестве комментария. Я знаю, что это немного ТАКОЕ злоупотребление, чтобы запросить это, но это невероятно полезно. Спасибо.

Answer 9

Я вижу множество ответов, пытающихся решить проблему, но, думаю, у меня есть для вас ответ.

Я полагаю, что весь синтаксис регулярных выражений пришел с конца 70-х годов. (Жаль, что я не могу найти какую-то историю по этому вопросу) Я взял книгу 1979 года об автоматах букв, и вся книга заполнена математическими доказательствами нахождения шаблонов в тексте. Когда я вернусь домой, я получу название и обновлю его здесь.

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

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

Так что, что касается компилятора, я сомневаюсь, что такой может быть. Как отметил dmckee, «я отмечаю, однако, что многим старым рукам они не нравятся». У вас есть карикатуры и комедии, изображающие сложные математические уравнения на досках. Это шутка, чтобы показать, насколько сложен тот или иной предмет, но на самом деле любой, кто имеет опыт, может понять его, если ему дадут подтекст и немного обучения. Регекс не сложно. Как только вы изучите основы, все сводится к тому конкретному парсеру, который вы используете. Как некоторые дети говорят мне, что они не хотят изучать C / C ++, потому что это сложнее, чем Javascript, даже если он имеет такой же синтаксис. Его восприятие, а не сложность.

Как только вы выучите регулярные выражения, это двигатели, которые вызывают у вас проблемы. Visual Studio использует скобки вместо скобок для группировки. Простая библиотека регулярных выражений SLRE , которую я использую, имеет простое подмножество против PCRE с более полным синтаксисом. На этом этапе мы начинаем говорить о более новом языке, а не об инструменте для сопоставления текста.

Кроме того, большинство программистов используют одну короткую строку для своих совпадений с регулярным выражением, а не создают полное совпадение с регулярным выражением, потому что они просто хотят проанализировать некоторые случайные данные. Сопоставление с регулярным выражением - это такой инструмент, как Bison, yacc или ANTLR. Парсер, созданный вручную, всегда будет лучше, так что, по сути, вы можете скомпилировать свое собственное регулярное выражение, так зачем тратить время на 2 страницы кода для соответствия регулярному выражению, когда простой цикл while и быстрее?

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

В качестве примечания рассмотрим исходный код Lua между Lua 3.0 и 3.2.2. Они превращаются из парсера бизонов в ручной. Вы понимаете, насколько больше у них свободы, чем при использовании инструмента для анализа текста, особенно в последних выпусках функций. Конечно, это также усложняет код для обновления. Это был выбор между чистотой файлов * .y и надежностью сборки вручную.

Answer 10

Если вы читаете Книгу Дракона для компиляторов, она предлагает вам использовать регулярные выражения для анализа и анализа вашего языка более высокого уровня. Таким образом, регулярные выражения кажутся чем-то более низким уровнем. Я очень часто использую их в своих ежедневных рабочих задачах для разработки внешнего интерфейса / бэкэнда, и да, я нашел некоторые из них немного загадочными. Тем не менее, это не делает регулярное выражение неправильным, вы всегда можете написать новый язык, если он вам не нравится, учитывая, что 1) у вас есть время 2) вы готовы приложить необходимые усилия 3) сила внутри Вы:)