CSG与CFG相似,但reduce符号为多个。
因此,我可以只使用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
?
上下文相关文法是不确定的。因此,您不能仅仅因为RHS在派生的某个时刻是可见的而不能假设会减少。
LBAs(线性有界自动机)也是不确定的,因此它们并不是真正的实用算法。 (您可以通过回溯来模拟一个,但是执行解析可能要花费的时间没有方便的限制。)对于解析理论而言,它们是CSG的接受者这一事实很有趣,但对于解析实践而言却并非如此。
就像CFG一样,有不同类别的CSG。 CSG的某些受限制的子类更易于解析(例如,CFG是一个子类),但我不相信有太多关于实际用途的调查;在实践中,CSG很难编写,并且没有可以通过推导构造的解析树的明显类似物。]
有关更多信息,您可以从wikipedia entry on LBAs开始,然后继续遵循其参考文献。祝你好运。
Nearley解析器生成器能够使用postprocessors解析一些简单的上下文相关模式。