java - 算法:正则表达式字符交集

Question

我在 Java 中有两个正则表达式，我想知道第一个正则表达式(成功)匹配的字符串的最后一个字符是否可以与第二个正则表达式(成功)匹配的字符串的第一个字符相同.

这些表达式很复杂，不仅有字符限制，还有长度或形式的限制。

我正在调查 https://code.google.com/archive/p/xeger/但这只是一半。

(我正在解决一个问题，即在受这些正则表达式限制的两个连续字符串之间是否需要分隔符，或者解析器是否能够在没有分隔符的情况下区分它们)

例子:

Regex1 = <
Regex2 = [:a-zA-Z]([:a-zA-Z]|-|_|\.|[0-9])*
Regex3 = Regex2

[Regex1][Regex2] 不需要分隔符，因为解析器会解析字符串 <xml安全地分成 2 个 token (< 和 xml)。

[Regex2][Regex3] 共享很多字符，解析器在如何解析字符串 table 方面有多种可能性。 .

我知道正则表达式评估(自动机...)背后的理论，但是我想避免自己实现 DFA 生成。

Answer 1

我在 github 上有一个可以为您构建 DFA 的开源库:http://mtimmerm.github.io/dfalex/

请注意，您的问题似乎表述不正确。如果您想知道匹配两个正则表达式的字符串之间是否需要分隔符，您可能需要知道任何可以“扩展”第一个正则表达式的成功匹配的字符是否也可以开始第二个正则表达式的匹配。在 DFA 中，可以扩展匹配的字符是从接受状态转换出来的字符。

我应该补充一点，您不一定需要构建 DFA 来回答这些问题。第一个+最后一个字符，扩展字符，以及它是否匹配空字符串，这些问题可以通过对正则表达式 AST 进行简单的递归操作来回答。

例如(对 boolean 运算和集合运算使用 | 和 &):

令 NULLABLE(X) 为真当且仅当正则表达式匹配空字符串。然后:

NULLABLE(AB) = NULLABLE(A) & NULLABLE(B)
NULLABLE(A|B) = NULLABLE(A) | NULLABLE(B)
NULLABLE(A+) = NULLABLE(A)
NULLABLE(A?) = true

设 FIRST(X) 为可以启动正则表达式的字符集:

FIRST(AB) = NULLABLE(A) ? FIRST(A)|FIRST(B) : FIRST(A)
FIRST(A|B) = FIRST(A)|FIRST(B)
FIRST(A+) = FIRST(A?) = FIRST(A)

设 EXT(X) 为可以扩展正则表达式的字符集:

EXT(AB) = NULLABLE(B) ? EXT(A)|EXT(B) : EXT(B)
EXT(A|B) = EXT(A) | EXT(B)
EXT(A+) = EXT(A?) = EXT(A)|FIRST(A)