这个上下文无关语法是正则表达式吗？

Question

我的语法定义如下：

A -> aA*b | empty_string

A 是正则表达式吗？我对如何解释 BNF 语法感到困惑。

Answer 1

不，这个问题实际上与正则表达式无关。上下文无关语法指定无法用正则表达式描述的语言。

这里，A 是一个非终结符；也就是说，它是一个必须通过产生式规则扩展的符号。鉴于您只有一个规则，它也是您的开始符号 - 此语法中的任何产生式都必须以 A 开头。

产生式规则是

(1)    A -> aA*b | 
(2)         empty_string

a 和 b 是终结符号 - 它们位于语言的字母表中，并且无法扩展。当左侧不再有非终结符时，就完成了。

因此，该语言指定的单词类似于平衡括号，只不过使用 a 和 b 而不是 ( 和 )。

例如，您可以生成 ab，如下所示：

A -> aA*b (using 1)
aAb -> ab (using 2)

同样，您可以生成 aabb:

A -> aA*b (1)
aAb -> aaA*bb (1)
aaAbb -> aabb (2)

甚至 aabbabb:

A -> aA*b
aA*b -> aabA*b:
aaba*b -> aababA*b:
aababA*b: -> aababb

明白了吗？星号可能有点令人困惑，因为您已经在正则表达式中看到过它，但实际上它在这里和那里做同样的事情。它称为 Kleene 闭包，它表示可以用 0 个或多个 A 组成的所有单词。

Answer 2

正则表达式生成正则语言，并且可以使用状态机进行解析。

BNF 语法是上下文无关语法，它生成上下文无关语言，并且可以使用下推自动机（堆栈机）进行解析。

上下文无关语法可以做常规语法可以做的所有事情，甚至更多。

Answer 3

A 似乎是 BNF 语法规则。我不太确定为什么你会将此与正则表达式混淆。您是否因为其中有*而感到困惑？所有带有 * 的东西都不是正则表达式。