grammar - BNF 语法匹配

Question

我的老师给了我两个 bnf 语法：

A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'

和四个与之匹配的字符串：

• dffd
• dddefddfe
• 德夫
• 专用的

我想出了其中两个，但其他两个让我难过。我不希望任何人告诉我答案，但如果有人能给我一些关于我哪里出错的提示，我将不胜感激。

Answer 1

这是一种无上下文语法，因此您应该寻找绘制解析树。然后，您可以查看哪个非终结符导致哪个产生的字符串。这些语法相当简单，因此绘制解析树应该很容易手工完成。

Answer 2

嗯……

通过归纳，所有匹配必须有奇数个字符。所以这4个字符串中的任何一个都不会被击中......

---

等一下。我刚刚注意到第一条规则中的“Y”。我们知道那是什么吗？它可能会立即打破我的论点......

Answer 3

我的建议是在编写任何代码之前为自己绘制一个有限自动机或状态图。先用铅笔和纸手工完成。