BNF文法匹配

Question

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

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

和四个字符串来匹配它们：

• dffd
• dddefddfe
• dedf
• deded

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

Answer 1

嗯..。

通过归纳法，所有匹配必须有一个奇数字符。所以这四个字符串都不可能成功.

哦，等等。我刚注意到第一条规则中的“Y”。我们知道那是什么吗？这可能会让我的论点破裂.

Answer 2

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

Answer 3

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