如何解析上下文敏感的語法？

Question

CSG與CFG類似，但縮減符號是多個。

那麼，我可以使用CFG解析器來解析CSG，將生產減少到多個終端或非終端嗎？

像

1. S → a bc 
2. S → a S B c 
3. c B → W B 
4. W B → W X 
5. W X → B X 
6. B X → B c 
7. b B → b b 

當我們遇到W X，可我們只是減少W X到W B？

當我們遇見W B時，我們可以減少W B爲c B？

因此，如果CSG解析器是基於CFG解析器，它不難寫，它是真的嗎？

但是當我檢查wiki時，它說解析CSG，我們應該使用linear bounded automaton。

什麼是linear bounded automaton？

Answer 1

上下文敏感文法是非確定性。所以你不能認爲減少會發生，僅僅是因爲RHS恰好在推導的某個點上是可見的。

LBA（線性有界自動機）也是非確定性的，所以它們並不是真正的實用算法。 （你可以使用回溯來模擬，但是執行解析可能需要的時間沒有方便的限制。）他們是CSG接受者的事實對解析理論很有意義，但對於解析練習來說並不真實。

正如CFG一樣，CSG有不同的類別。 CSG的一些受限制的子類更容易解析（例如，CFG是一個子類），但我不相信對實際應用有太多調查;在實踐中，CSG很難寫，並且沒有明顯的類似於可以從推導構建的分析樹。

欲瞭解更多信息，您可以從wikipedia entry on LBAs開始，然後繼續查看其參考文獻。祝你好運。