上下文無關語法的算法

Question

我試圖設計一個算法，它將一個CFG G和一個終端符號a作爲輸入，並且如果S（G的開始規則）可以生成一個開始的句子形式，與。即如果在（T U N）*中有一個串α使得S => *aα，否則它輸出否。例如，如果語法是S - > [S] | SS | ε，如果a =]，答案是否定的。我不在尋找代碼，我只是想了解我應該如何在僞代碼中處理這個主題。

Answer 1

有三種方式X可以派生一個字符串從a開始。

1. 有形式X -> a...
2. 的規則有形式X -> A...的規則和A派生開始a的字符串。
3. X -> B A...和B從ε和A...派生出一個字符串，從a開始的規則。

可以使用這些構建算法，着眼於該語法的開始與那些形式S -> ...的所有規則和適用任一檢查1，如果RHS與終端或兩個檢查2和3，如果它開始從非終端開始。每個檢查對應一個返回布爾值的（可能是遞歸的）函數。

一個有趣的細節是需要處理語法中的循環，例如，單條規則如A -> A a，還有A -> B...,B -> C...,C -> A...。如果你不小心，相互遞歸檢查將無限重現。我會讓你的。考慮深度優先搜索如何避免圖表中的下一個循環永久。

另一個細節是如何確定給定的非終端B是否派生ε。你應該能夠自己解決這個問題，但如果其他方法都失敗了，請查找「可空的非終端」。你會發現一個衆所周知的小算法。

如果任何檢查都是肯定的，則返回yes。否則規則的詳盡應用已經找不到辦法。返回no。

Answer 2

您可以只運行Earley parser的預測值，直到它停止預測，並查看它是否生成以相關終端開始的任何規則。

或者從下往上開始，將接受問題終端的所有非終結點標記爲第一個輸入，然後將接受已標記爲非終點的所有非終結點標記爲它們的第一個輸入，然後重複直到完成，並查看S在標記的非終結符中。