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

Question

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？

Answer 1

上下文相关语法是非确定性的。所以你不能假设会发生减少，只是因为 RHS 恰好在推导中的某个点可见。

LBA（线性有界自动机）也是非确定性的，因此它们并不是真正实用的算法。（你可以用回溯来模拟一个，但是对于执行解析可能花费的时间量没有方便的限制。）它们是 CSG 的接受器这一事实对于解析理论来说很有趣，但对于解析实践来说并不是真的。

与 CFG 一样，CSG 也有不同的类。 CSG 的一些受限子类更容易解析（例如，CFG 是一个子类），但我认为对实际用途的调查不多；实际上，CSG 很难编写，并且没有明显的可以从推导构造的解析树的模拟。

如需更多阅读，您可以从 wikipedia entry on LBAs 开始，然后继续阅读其参考资料。祝你好运。

Answer 2

Nearley parser generator is able to parse some simple context-sensitive patterns using postprocessors.

可以编写匹配 to be or not to be 或 to do or not to do 的上下文相关规则，但不匹配 to be or not to do:

# "_" is whitespace, "word" is a single word
example_rule -> "to" _ word _ "or" _ "not" _ "to" _ word {%
    function(d,l, reject) {
        if (d[2] !== d[10]) {
            return reject;
        } else {
            return {d.join(" ")};
        }
    }
%}

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

how to parse Context-sensitive grammar?

parsing

context-free-grammar

context-sensitive-grammar