Регулярные выражения для non-strings

Question

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

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

Answer 1

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

Однако, если у Вас есть движок регулярных выражений, что позволяет лечить строку в качестве данных 8-Bit не-закодирован (иногда называемого BINARY, 8BIT или ASCII-8BIT), то можно использовать этот двигатель для разбора байт-ориентированных двоичного данные.

Ragel является компилятором конечного автомата, специально разработанным для синтаксического анализа двоичных протоколов. Вы записываете свой конечный автомат в высокоуровневом (regexp-like) DSL и Ragel затем компилирует это на ваш целевой язык - Ragel в настоящее время поддерживает C, C++, Objective-C, D, Java и Ruby.

Большинство функциональных языков программирования имеют мощные возможности для сопоставления образцов, испеченные прямо на самом языке. эти средства могут использоваться для сопоставления двоичных данных. Одним из примеров этого является поддержка Erlang для building and pattern matching binary data structures.

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

Answer 2

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

Answer 3

Вы можете использовать обычные генераторы парсера без контекста (такие как Yacc/Bison) для генерации регулярных парсеров языка, даже если «атомы» не являются символами. При подключении к функции сканера вы можете заставить грамматику разбирать «что угодно» независимо от того, является ли она строкой или нет.

Другое дело, что в области логики существуют «временные логики», такие как LTL и CTL, которые в основном являются подмножествами регулярных выражений для «событий». Логические формулы в LTL обычно переводятся в конечные автоматы.