Регулярные выражения для нестроковых

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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