2

具体来说,我注意到正则表达式本身的语言不是正则的。所以,我不能使用正则表达式来解析给定的正则表达式。我需要使用解析器,因为正则表达式本身的语言是上下文无关的。

有什么方法可以表示正则表达式,从而可以使用正则表达式解析结果字符串?

注意:我的问题不在于是否存在匹配当前正则表达式语法的正则表达式,而是是否存在我们今天所知道的正则表达式的“表示”(可能不像我们今天所知道的那样简洁)可以使用正则表达式解析。另外,请有人删除 dup,因为它不是 dup。我问的是完全不同的东西。我已经知道当前的正则表达式语言不规则(这就是我最初提出问题的方式)。

4

2 回答 2

1

根据“代表”的含义,答案是“是”或“否”:

如果你想要一种(同态)1:1 映射到通常的基本正则表达式语言的语言,答案是否定的,因为正则语言不能同构到非常规语言,而标准正则表达式语言是非常规的. 这是因为语法需要匹配任意深度的左括号和右括号。

如果“represent”只意味着另一种指定正则语言的方法,答案是肯定的,现在我至少可以想到三种方法来实现这一点:

  1. “最愚蠢”和最简单的方法是定义一些f : ℕ -> RegEx从自然数到所有有效标准正则表达式集的满射映射。您可以使用正则表达式来定义自然数0|1[01]*,而由自然数(表示该自然数的字符串)表示的n正则语言是由 表示的正则语言f(n)

    当然,自然数所赋予的含义对人类读者来说根本不明显,因此这种“正则表达式语言”将毫无用处。

  2. 由于括号是简单正则表达式中唯一的非正则部分,最简单的人类可解释的方法是扩展标准的简单正则表达式语法以允许悬空括号并为悬空括号定义语义。

    显而易见的选择是忽略不匹配的左括号并将不匹配的右括号解释为匹配正则表达式的开头。这基本上相当于在正则表达式的开头隐式插入尽可能多的左括号,并在正则表达式的末尾插入尽可能多的右括号。此外,(*必须将其解释为空字符串的重复。如果我没有遗漏任何内容,这个定义应该将任何字符串变成具有指定含义的“正则表达式”,因此.*定义了这个“正则表达式语言”。

    此变体甚至具有与标准正则表达式相同的抽象语法。

  3. 另一种变体是指定使用常规语言直接识别语言的 NFA,例如:([a-z]+,([^,]|\\,|\\\\)+,[a-z]+\$?;)*.

    这个想法是[a-z]+用作状态的标签,表达式是(s, c, t)从源状态s到目标状态t消费字符的转换三元组列表c,以及$指示接受转换(参见下面的注释)。在c中,反斜杠用于转义逗号或反斜杠 - 我假设您对标准正则表达式使用相同的字母表,但当然您可以将中间部分替换为任何其他正则语言的符号,表示您希望的任何字母表的字符。提到的第一个源状态是(单个)初始状态。空表达式定义空语言。

    上面,我写的是“接受转换”,而不是“接受状态”,因为这会使上面的正则表达式更复杂一些。您可以将包含 a 的三元组解释$为两个转换,即一个转换消耗cfroms到一个新的唯一状态,以及一个从该状态到 的 ε-转换t。这应该允许任何 NFA 被表示,通过用三元组替换到接受状态的$每个转换,用非$三元组替换到非接受状态的每个转换。

一个可能使“是”部分看起来更直观的注释:汇编语言是常规的,而且它们甚至是图灵完备的,因此如果无法使用常规语言指定“纯粹的”常规语言,那将是出乎意料的。

于 2020-06-25T12:28:06.167 回答
0

答案可能是否定的。

正如您所指出的,所有可能的正则表达式的集合本身不是正则集。任何TRUE正则表达式(不是那些扩展的)都可以转换为有限自动机 (FA)。如果正则表达式可以用一种可以自己解析的形式来表示,那么FA也可以用正则表达式来解析。

但据我所知,这是不可能的。RE本身可以简化为三个基本操作(根据龙书):

  1. 串联:例如ab
  2. 交替:例如a|b
  3. kleen 闭合:例如a*

kleen 闭包可以匹配无限个字符,但它不知道要匹配多少个字符。试想这样的情况:你想匹配 3 个连续a的 s。那么对应的正则表达式就是/aaa/。但是如果你想要匹配 4、5、6... as 怎么办?只有一个 RE 的解析器无法知道as 的确切数量。因此它无法为任意表达式提供正确的匹配。但是,RE 解析器必须匹配无限不同形式的 RE。根据您的表达,正则表达式无法匹配所有可能性。

嗯,RE 解析器的唯一区别是它不需要分词器。(可能这就是词法分析中使用 RE 的原因)RE 中的每个字符都是一个令牌(不包括那些转义字符)。但是要解析 RE,无论转换什么,都必须面对 NFA/DFA/TREE……所有 RE 本身无法解析的等效结构。

于 2013-10-23T07:17:05.987 回答