3

我正在寻找一种方法来确定 BNF 语法中的特定规则是否可以转换为正则表达式。

（对于“正则表达式”（RE），我指的是简单的数学类型。我对只能通过使用反向引用、环视或其他高级功能来完成的 BNF 规则不感兴趣。）

我只对可能的情况感兴趣。

我知道这个问题通常是无法确定的，所以我基本上是在寻找技巧来做到这一点。半可决定的东西会很好。

我目前的方法是基于所有非递归规则（不引用自身且不包含引用自身的规则的规则）都可以轻松转换为 RE 的想法。所以“我所要做的”就是重写递归规则。简单的例子：

S = a | b S
  = b* a

T = a | T b T | T c T
  = a | T (b|c) T
  = a ( (b|c) a )*

但是，这种方法受限于我识别 BNF AST 中的模式和简单地说 AST 的能力。这是一种非常有限的方法，所以我正在寻找更好的方法。

这是解决方案必须能够处理的示例：

S = a | c | S (b S)* c | S d S | S e S ( e S )*

上述规则的语言是规则的。然而，展示这一点并不容易，而且需要时间。

证明草图：

S = a | c | S (b S)* c | S d S | S e S ( e S )*
  = a | c | S (b S)* c | S d S | S e S
  = a | c | S (b S)* c | S (d|e) S
  = a | c | S c | S b S (b S)* c | S (d|e) S

现在，让我们忽略S b S (b S)* c替代方案：

S' = a|c | S' c | S' (d|e) S' 
   = (a|c)c* ( (d|e) (a|c)c* )*

回到S b S (b S)* c替代方案：它基本上说如果输入包含 a b，那么在 之后的某个地方b，必须有 a (a|c)c。这在 RE 中很难表达，但在 NFA 中很容易做到。

构造 2 个 NFA x 和 y 使得x = S'和y = S' (b S')* c。每当我们处于 x 的最终状态时，转换b到 y 的初始状态。每当我们处于 y 的最终状态时，通过 epsilon 转换到 x 的所有最终状态。最终的 NFA 将同时具有 x 的初始状态和最终状态。最终 NFA 的 RE 为：(a|c) ( c | (d|e)(a|c) | b(a|c) ( (b|d|e)(a|c) )* c )*

4

0 回答 0