具体来说,我注意到正则表达式的语言本身并不是正则的。因此,我无法使用正则表达式来解析给定的正则表达式。我需要使用解析器,因为正则表达式本身的语言是上下文无关的。
有没有什么方法可以用可以使用正则表达式解析结果字符串的方式来表示正则表达式?
注意:我的问题不是关于是否存在与当前正则表达式语法相匹配的正则表达式,而是关于我们今天所知道的正则表达式是否存在“表示”(可能不像我们今天所知道的那样简洁)可以使用正则表达式进行解析。另外,请有人删除该重复项,因为它不是重复项。我问的是完全不同的事情。我已经知道当前的正则表达式语言不是正则的(这就是我开始提出原始问题的方式)。
根据“代表”的含义,答案是“是”或“否”:
如果你想要一种(同态)映射到通常的基本正则表达式语言的语言,答案是否定的,因为正则语言不能与非正则语言同构,而标准正则表达式语言是非正则的。这是因为语法需要匹配任意深度的左括号和右括号。
如果“代表”仅意味着指定正则语言的另一种方法,那么答案是肯定的,现在我可以想到至少三种方法来实现这一目标:
-
“最愚蠢”和最简单的方法是定义一些满射映射f : ℕ -> RegEx
从自然数到所有有效标准正则表达式的集合。您可以使用正则表达式定义自然数0|1[01]*
,以及由自然数(表示的字符串)表示的正则语言n
是由以下表示的常规语言f(n)
.
当然,自然数所附加的含义对于人类读者来说根本不明显,因此这种“正则表达式语言”将完全没有用处。
-
由于括号是简单正则表达式中唯一的非常规部分,因此最简单的人类可解释方法是扩展标准简单正则表达式语法以允许悬挂括号并定义悬挂括号的语义。
明显的选择是忽略不匹配的左括号并将不匹配的右括号解释为匹配正则表达式的开头。这本质上相当于根据需要在正则表达式的开头隐式插入尽可能多的左括号,并在正则表达式的末尾隐式插入尽可能多的右括号。此外,(*
必须被解释为空字符串的重复。如果我没有错过任何内容,这个定义应该将任何字符串变成具有指定含义的“正则表达式”,所以.*
定义了这个“正则表达式语言”。
该变体甚至具有与标准正则表达式相同的抽象语法。
-
另一种变体是指定使用常规语言直接识别语言的 NFA,例如:([a-z]+,([^,]|\\,|\\\\)+,[a-z]+\$?;)*
.
这个想法是[a-z]+
用作状态的标签,表达式是转换三元组的列表(s, c, t)
从源状态s
到目标状态t
消费性格c
, and a $
表示接受转换(参见下面的注释)。在c
, 反斜杠用于转义逗号或反斜杠 - 我假设您对标准正则表达式使用相同的字母表,但当然您可以将中间组件替换为任何其他正则语言的符号,表示您希望的任何字母表的字符。
提到的第一个源状态是(单个)初始状态。空表达式定义空语言。
上面,我写了“接受转换”,而不是“接受状态”,因为这会使上面的正则表达式变得更加复杂。您可以解释包含以下内容的三元组$
作为两个转换,即一个转换消耗c
from s
到一个新的、独特的状态,以及从该状态到t
。这应该允许任何 NFA 被表示,通过将每个到接受状态的转换替换为$
三元组,每次转换到非接受状态时都带有非$
triple.
需要注意的是,可能会使“是”部分看起来更直观:汇编语言是常规的,甚至是图灵完备的,因此如果无法使用常规语言指定“纯粹的”常规语言,那将是意外的。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)