非字符串的正則表達式

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中的邏輯公式通常被轉換爲有限狀態自動機。