考虑以下 BNF 文法（BNF、递归和推导）

Question

考虑以下 BNF 语法：

<S> ::= a <S> c <B> | <A> | b
<A> ::= c <A> | c
<B> ::= d | <A>

好的，然后我得到了各种字符串，其中一个是：

aabccd

如果字符串可以从BNF文法推导出来，那我应该提供推导。

所以我从一个非终端开始（根据我的理解）：

<S> ::= a <S> c <B> -> a a <S> c <B> c <B> -> a a b c <B> c <B> ->
a a b c <A> c <B> -> a a b c c c <B> ->  a b c c c d

这是正确的吗？因此不能导出？因为我有三个C？还是我做错了。 BNF 总计 n00b。

编辑：好的，从更 "free" 的角度来看。 valid/legal 将字符串中的 terminal/token 与非终结符 一起转换为 "c"，换言之 "c <A>" 简单地转换为 "c"？鉴于 "c A" 是 "A"？因此允许我将它们转换为简单的 "c"。这将允许我获取请求的字符串：

<S> ::= a <S> c <B> -> a a <S> c <B> c <B> -> a a b c <B> c <B> ->
a a b c <A> c <B> -> a a b c c <B> ->  a a b c c d

有效吗？

编辑：我不知道如何显示小于号和大于号，尝试使用美元符号，但我想它在这里不起作用。

Answer 1

因为你的文法是context-free，你可以把它转换成Chomsky Normal Form (CNF) and apply the CYK (Cooke-Young-Kasemi)算法来检查这个词是否是L(G)的一部分，有一个guess-free，确定性的方法.

Answer 2

您的第一个推导是正确的，'aabccd' 没有使用此语法进行解析。您需要第三个 'c' 才能成为 parse-able - 因此可以解析 'aabcccd'，但不能解析 'aabccd'.

祝你好运。