非字符串的正则表达式

Question

我想知道是否存在不是字符串的顺序数据的正则表达式。

我知道正则表达式本质上归结为DFA，但我更关心指定这些DFA的高级语言。

Answer 1

正则表达式理论中绝对没有任何东西阻止它们被应用于除了字符串以外的其他东西。只是大多数正则表达式引擎实现不允许这样做。

但是，如果有一个正则表达式引擎，允许你治疗字符串作为未编码的8位数据（有时称为BINARY，8BIT或ASCII-8BIT），则可以使用该发动机解析面向字节的二进制数据。

Ragel是专门为解析二进制协议而设计的状态机编译器。你用一个高级（类似于regexp的）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中的逻辑公式通常被转换为有限状态自动机。