这种无上下文的语法是正则表达式吗？

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-closure,它代表你可以使用0或更多As 制作的所有单词.