我正在尝试设计一种算法，将CFG G和终端符号a作为输入，如果S（G的起始规则）可以生成以aie开头的句子形式（如果存在字符串α），则输出yes在（TUN）*中使S => *aα，否则输出否。例如，如果语法为S-> [S] | SS | ε，如果a =]，则答案为否。我不是在寻找代码，我只是在试图理解我应该如何使用伪代码来实现这一主题。
有三种方法X可以得出以开头的字符串a。
X -> a...X -> A...并A派生一个以开头的字符串a。X -> B A...并B派生ε和A...派生一个以开头的字符串a。您可以使用它们来构建一种算法，该算法从形式的语法规则开始S -> ...查看语法的所有规则，如果rhs以终结符开头，则应用check 1；如果非终结符开头，则应用check 2和3。每个检查都对应一个返回布尔值的（可能是递归的）函数。
一个有趣的细节是，处理周期在语法的需要，如单规则一样A -> A a，而且A -> B...，B -> C...，C -> A...。如果您不小心，则相互递归检查将无限重复。我会把它交给你。考虑一下深度优先搜索如何永远避免图形中的后续循环。
另一个细节是如何确定给定的非末端B是否派生ε。您应该可以自己解决这个问题，但是如果其他所有方法都失败了，请查找“可为空的非终结符”。您会发现一个著名的小算法。
如果任何检查为阳性，则返回“是”。找不到规则的其他详尽应用。退货编号
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句