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

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开始，然后继续查看其参考文献。祝你好运。