language-design - 如何将语言的上下文无关部分与上下文相关部分分开？

Question

我在 comp.theory 列表中读到了这篇精彩的文章：

海报指出，大多数编程语言都定义了一个上下文无关的核心，然后在解析树上运行额外的算法来过滤掉语言中非法的结构：

这将语言的上下文无关部分与上下文相关部分分开——这通常被认为是良好的实践（一种用于语言设计的模块化“编程”学科）。

您能否提供一个“Hello World”示例来说明这种技术？也就是说，提供一种简单的上下文敏感语言，识别上下文无关核心，然后勾勒出如何使用上下文无关核心解析输入，然后过滤掉解析树中的非法结构。

你能给我推荐任何讨论这种技术的文章或书籍吗？

score 1 · Accepted Answer

最简单的非上下文无关语言之一是单词类型为 a ⁿ b ⁿ c ⁿ（a、b 和 c 重复相同次数，即 abc、aabbcc、aaabbbccc、.. ..)。

您可以使用上下文无关语言 {a ⁿ b ⁿ c ^m } 的语法对其进行解析，其中 c 的数量不受限制。一旦有了解析树，就可以使用单独的算法检查 c 的重复次数是否等于 a 和 b 的重复次数。

score 0 · Accepted Answer

通常进行过滤也是为了消除语言的过度近似。我们为编程语言编写模棱两可但清晰的上下文无关文法，然后使用 tree walkers 或其他机制来删除不需要的派生。

一个参考：

另一方面，您也可以考虑将处理抽象语法树的类型检查器作为这样的过滤器。类型检查器拒绝解析器基于非本地（上下文）信息生成的树。例如：

1 + "1"

被语法接受，因为：

E ::= Int | String | E "+" E;

但是类型检查器说整数和字符串之间的加法不起作用，并拒绝该语言中的句子。类型检查器通过在解析和识别加法符号后遍历树来完成此操作，然后可能在表中查找操作数的有效组合，如果组合无效，它就会开始抱怨。我想这通常是编译器的工作方式。见 Aho 等人。龙书。如果您抽象地谈论它，听起来会更有趣:-)

2 回答 2