7

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？

4

2 回答 2

11

上下文相关语法是非确定性的。因此，您不能仅仅因为 RHS 在推导中的某个时刻恰好可见，就假设会发生减少。

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

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

如需更多阅读，您可以从LBA 的 wikipedia 条目开始，然后按照其引用继续。祝你好运。

于 2015-04-07T03:34:38.400 回答
2

Nearley解析器生成器能够使用后处理器解析一些简单的上下文相关模式。

to be or not to be可以编写与or匹配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(" ")};
        }
    }
%}
于 2019-11-10T18:20:00.390 回答