某種類型的語法分析，但沒有暴力

我有「轉變」 /「語法」不管你可以稱之爲形式的列表：某種類型的語法分析，但沒有暴力

L - >→| LL | N

這意味着L（字母）可以轉換爲1個字母或2個字母或一個N（數字）

我給出了一個轉換列表和一個數字序列，並執行了一個INITIAL動作，並且必須生成生成給定數字序列的最小移動列表。

For example: 

I have the transformations 
A->BC 
B->D 
B->ED 
C->F 
C->FB 
D->2 
D->3 
E->0 
E->1 
F->4 

The sequence: 2 4 0 3 
The initial move performed: A 

So the minimum list would be: 

1.(A, BC) [BC](initial move) 
2.(B, D) [DC] 
3.(D, 2) [2C] 
4.(C, FB) [2FB] 
5.(F, 4) [24B] 
6.(B, ED) [24ED] 
7.(E, 0) [240D] 
8.(D, 3) [2403]

有例如沒有循環A-> AB或A-> B，B-> A等蠻力是因爲變換的輸入的選擇是大〜1000，併產生所述序列是〜30。

經過在互聯網上的廣泛搜索後，我發現了CYK算法，但在我的例子中使用它後，結果是序列2403不在語法中（這是錯誤的）。

我真的不明白我應該怎麼做我想多天來解決這個問題。歡迎任何幫助。謝謝。

來源

2016-11-10 oren revenge

這看起來並不像解析。這更像是從起始位置生成一個序列。 –

爲什麼不解析？看起來他有一個語法，並且想要擴展語法規則（他似乎在稱這些「動作」）以匹配一個序列。 –

@oren：只是說「它不起作用」對我們沒有幫助，因此對你沒有幫助。所以說服我們你正確地在這個語法上實現了CYK。否則，你可能只是有一個錯誤。 –

在申請CYK之前，語法必須在Chomsky normal form之前，這意味着您需要eliminate the unit rules。

換句話說，規則B->D必須轉換爲兩個規則：B->2和B->3。同樣，規則C->F必須轉換爲C->4。

一旦你對語法進行了這些調整，它將以喬姆斯基的正常形式進行調整，所以CYK將起作用。當然，在顯示解析器結果時，只要您調用其中一個轉換後的規則，就需要生成兩行輸出。例如，調用B->2應顯示爲B->D，然後是D->2。

來源

2016-11-10 21:06:08 user3386109

感謝您的幫助，現在我明白了爲什麼它沒有工作。所以沒有其他算法，而不是cyk，我可以使用？ –

@orenrevenge與軟件中的一切一樣，解決問題的方法有很多。也就是說，這個問題似乎特別適合CYK。 – user3386109

消除單位規則的一般算法是什麼？這個問題對於「編程入門」課程來說太難了...... –

某種類型的語法分析，但沒有暴力

回答

相關問題