BNF语法匹配

Question

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

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

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

• dffd
• dddefddfe
• 德夫
• 德德

我已经弄清楚了其中两个，但另外两个让我难住了。我不想让任何人告诉我答案，但如果有人能给我一些关于我哪里出错的提示，我将不胜感激。

Answer 1

嗯...

通过归纳，所有匹配项都必须具有奇数个字符。所以这 4 个字符串都不能被命中......

---

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

Answer 2

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

Answer 3

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