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

Question

我有一个语法定义如下：

A -> aA*b | empty_string

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

Answer 1

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

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

生产规则是

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

a和b是终端符号 - 它们在语言的字母表中，不能扩展。当左侧不再有非终结符时，您就完成了。

所以这种语言指定了类似于平衡括号的单词，除了用aandb而不是(and )。

例如，您可以生成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 或更多As 组成的所有单词。

Answer 2

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

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

上下文无关语法可以做常规语法可以做的一切，甚至更多。

Answer 3

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