qdw*_*ang 6 parsing context-free-grammar context-sensitive-grammar
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解析器,那么写起来并不难,是真的吗？
但是当我检查维基时,它说解析CSG,我们应该使用linear bounded automaton.
什么是linear bounded automaton？
ric*_*ici 10
上下文敏感语法是非确定性的.所以你不能假设减少会发生,只是因为RHS恰好在推导中的某个点可见.
LBA(线性有界自动机)也是非确定性的,因此它们不是真正的实用算法.(您可以使用回溯模拟一个,但是执行解析可能花费的时间没有方便的限制.)它们是CSG的接受者这一事实对于解析理论很有意义,但对于解析实践却并非如此.
与CFG一样,有不同类别的CSG.一些受限制的CSG子类更易于解析(例如,CFG是一个子类),但我不相信对实际应用的调查很多; 在实践中,CSG难以编写,并且没有明显类似的解析树可以从推导构造.
有关更多阅读,您可以从LBA上的维基百科条目开始,并继续关注其参考.祝好运.