我在comp.theory列表上看到了这篇很棒的文章:
http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html海报指出，大多数编程语言都定义了一个与上下文无关的核心，然后在解析树上运行额外的算法，以过滤掉语言中非法的结构:
这将语言的上下文无关部分从上下文敏感的部分——这通常被认为是很好的实践(一种用于语言设计的模块化"编程"学科)。
你能提供一个"Hello World"的例子来说明这个技术吗?也就是说，提供一种简单的上下文敏感语言，确定上下文无关的核心，然后概述如何使用上下文无关的核心解析输入，然后过滤掉解析树中的非法结构。
你能给我推荐一些讨论这种技术的文章或书籍吗?
不是上下文无关的最简单的语言之一是单词的类型为anbncn (a、b和c重复相同的次数，即abc、aabbcc、aaabbbccc，…)。
您可以使用上下文无关语言{anbncm}的语法来解析它，其中c的数量不受限制。一旦有了解析树，就可以使用单独的算法检查c的重复次数是否等于a和b的重复次数。
一般来说，过滤也是为了消除语言的过度近似。我们为编程语言编写模糊但与上下文无关的语法，然后使用树漫步器或其他机制删除不需要的派生。
一个参考:
- 使用过滤器消除上下文无关语法的歧义(1994)，http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9812
另一方面，您也可以将处理抽象语法树的类型检查器视为过滤器。类型检查器拒绝解析器根据非本地(上下文)信息生成的树。例如:
1 + "1"
被语法接受，因为:
E ::= Int | String | E "+" E;
，但是类型检查器说整数和字符串之间的加法不起作用，并从语言中拒绝该句子。类型检查器通过在解析和识别添加符号后遍历树来完成此操作，然后可能在表中查找操作数的有效组合，如果组合无效，则开始报错。我猜这就是编译器的典型工作方式。看阿霍等人的龙书。抽象地说会更有意思:-)