BNF语法匹配
我的老师给了我两个 bnf 语法：
A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'
以及四个与之匹配的字符串：
- dffd
- dddefddfe
- dedf
- deded
我已经弄清楚了其中两个，但另外两个让我难住了。 我不想让任何人告诉我答案，但如果有人能给我一些关于我哪里出错的提示，我将不胜感激。
My teacher has given me two bnf grammars:
A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'
and four strings to match with them:
- dffd
- dddefddfe
- dedf
- deded
I've figured out two of them, but the other two have me stumped. I don't want anyone to tell me the answers, but if someone could give me some hints as to where I'm going wrong it would be much appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是一个上下文无关语法，因此您应该绘制一个解析树。 然后您可以看到哪个非终结符导致哪个生成的字符串。 这些语法相当简单，因此手动绘制解析树应该相当容易。
This is a Context-Free grammar, so you should be looking to draw a parse tree. You can then see which non-terminal symbol leads to which yielded string. These grammars are fairly simple, so drawing a parse tree should be fairly easy to do by hand.
嗯...
根据归纳，所有匹配项都必须有奇数个字符。 所以这 4 个字符串都不能被命中……
哦等等。 我刚刚注意到第一条规则中的“Y”。 我们知道那是什么吗？ 它可能会彻底打破我的论点......
Hmmm...
By induction, all matches must have an odd number of characters. So neither of the 4 character strings can be a hit...
Oh wait. I just noticed the 'Y' in the first rule. Do we know what that is? It could break my argument right open...
我的建议是在编写任何代码之前为自己绘制有限自动机或状态图。 首先用铅笔和纸手工完成。
My advice would be to draw a finite automata or state diagram for yourself before you write any code. Do it out by hand with a pencil and paper first.