parsing - 如何解析上下文相关的语法？

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 开始并继续遵循其引用资料。祝你好运。