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

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)

甚至aababb:

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

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