從CFG

Question

我試圖生成從上下文無關文法的句子隨機生成時確定一組有效的下一個終端。在每個步驟中，根據與該問題無關的一些概率標準確定下一個要生成的非終端。我被卡住的地方是，如果給出一個語法和目前爲止產生的部分語句，我如何根據語法確定下一步可以生成的非終端的集合？

下面是BNF的示例語法和部分產生。

<expr> ::= <term> "+" <expr> | <term> 
<term> ::= <term> "*" <factor> | <factor> 
<factor> ::= "(" <expr> ")" | <const> 
<const> ::= "0" | "1" | "2" | "3" | "4" 

到目前爲止假設生成的序列：(1 +。在這種情況下，我們可以很容易地看到要生成的下一個令牌應該來自集合{"(", "0", "1", "2", "3", "4"}。

是否有一個算法，以確定這組給出的一般語法和局部產生，或在一定程度上使得該組可用在每一步產生的句子？

Answer 1

通常的方法來生成句子是開始與開始符號，然後反覆替代第一（或最後）非末端與它的製作中的一個，使用採樣準則不能完全此答案相關的。

如果語法是左到右解析的，你可以簡單地解析前綴，然後選擇其中一個非錯誤動作的存在終端之一。這要求解析表適用於任何從左到右的算法。如果算法是LALR（k），則需要注意減少導致最終錯誤的操作。爲了避免這種情況，如果您決定選擇減少操作，請勿提交相應的預覽符號。只有在你進行輪班時才做出承諾。 （但你不能忽視相當於減少行動向前看符號要麼，你需要保持整個集合，這樣就可以確保先行符號一致選擇。）