1

查看Chomsky 语法层次结构，我发现对于类型 2 语法（上下文无关语法），存在非常好的工具来帮助创建软件以将这些从文本读取到内存中可用的数据结构中。根据我的经验， Antlr4是执行此操作的工具之一。

最近我遇到了 Markdown，它原来是一种上下文相关的语法（即 Chomsky 类型 1），因此不存在Antlr4的语法定义。见这里和这里。

所以我想知道；

  • 是否有工具可以帮助创建上下文相关语法的解析器？
  • 如果没有，这样的事情甚至可能吗？
4

2 回答 2

3

大多数（如果不是全部）现实世界的编程语言都是上下文相关的。一个典型的解析器接受一些构造，这些构造后来会因为违反某些规则或约束而被拒绝，和/或依赖某种上下文相关的预处理来生成可解析的令牌流。像C预处理器这样的宏语言显然属于后一类，但在更可控的范围内，插入INDENT和DEDENT标记的 Python 扫描器也是如此。第一个示例包括在使用之前声明变量或函数调用具有与原型中的参数相同数量的参数的常见要求。静态类型分析也属于这一类。

因此，所有实用的解析器都在一定程度上偏离了形式语言理论教科书中所展示的理想化模型。像 bison 和 antlr 这样的实用解析器生成器提供了可定制的钩子，允许这些偏差的特殊实现。

简而言之，解析器生成器对于“技术上”上下文敏感的语言很有用（我使用引号是因为上下文敏感是一个二进制属性；要么是，要么不是）。

避免特殊的黑客攻击会很好，但这个问题似乎很棘手。由于上下文相关语言可以对图灵机进行建模，因此确定性解析必须能够解决停机问题。另一方面，对于上下文敏感语言集合的某些子集，有确定性的解析算法，但它们似乎并没有提供实际语言中存在的所有上下文敏感性。我们仍然缺乏在太强大而无法解析和太弱而无法替换黑客之间的最佳平衡点。

这仍然是一个肥沃的研究领域，也许你会有一些贡献。但是，如果您正在寻找现成的东西，我担心您会失望。

于 2018-06-20T02:38:09.023 回答
1

我真的遇到过一个。Quinn Taylor Jackson 的meta-S似乎符合 OP 的要求。这篇维基百科文章讨论了它和许多类似的系统，但 meta-S 似乎比那里讨论的大多数其他系统更实用：https ://en.wikipedia.org/wiki/Adaptive_grammar#cite_note-Jackson2006-3

在 quora，我分析了这在实践中如何对抗 GLR 解析器： https ://www.quora.com/What-is-the-most-powerful-parser-algorithm

于 2018-06-20T07:52:41.527 回答