上下文无关文法的算法

Question

我正在尝试设计一种算法，将 CFG G 和终结符 a 作为输入，如果 S(G 的起始规则)可以生成以 a 开头的句子形式，则输出 yes。即，如果 (T U N)* 中有一个字符串 α 使得 S =>* aα ，否则它输出 no。例如，如果文法是 S -> [S] |党卫军 | ε，如果 a = ]，答案是否定的。我不是在寻找代码，我只是想了解我应该如何在伪代码中处理这个主题。

Answer 1

X 可以通过三种方式导出以a 开头的字符串。

1. 有一个形式为 X -> a...
的规则
2. 有一个 X -> A... 形式的规则，A 导出一个以 a 开头的字符串。
3. 有一个 X -> B A... 形式的规则，B 导出 ε 和 A... 导出一个以 a 开头的字符串。

您可以使用这些来构建一个算法，该算法查看以 S -> ... 形式开始的所有语法规则，如果 rhs 以 a 开头，则应用检查 1如果它以非终端开头，则终端或两者都检查 2 和 3。每个检查都对应一个返回 bool 值的(可能是递归的)函数。

一个有趣的细节是需要处理语法中的循环，例如单个规则，例如 A -> A a，还有 A -> B...、B -> C...、C -> A...。如果您不小心，相互递归检查将无限重复。我会让你的。想一想深度优先搜索如何避免永远跟随图中的循环。

另一个细节是如何确定给定的非终结符 B 是否派生 ε。您应该能够自己解决这个问题，但如果一切都失败了，请查找“可空非终端”。你会发现一个众所周知的小算法。

如果任何检查结果为正，则返回 yes。否则规则的详尽应用是没有办法的。返回编号。