解析上下文敏感的语言

Question

我被特伦斯·帕尔，他说读权威ANTLR参考：

语义谓词是识别上下文敏感 语言结构的有力 手段使 运行信息来推动 承认

但书中的例子很简单。我需要知道的是：可以ANTLR解析context-sensitive规则，如：

XAY - > XBY

如果ANTLR不能解析这些规则，是有另一种工具，与上下文相关的语法交易？

Answer 1

ANTLR只解析LL（*）的文法。它无法使用语法解析完整的上下文敏感语言，例如您提供的示例。我认为Parr的意思是ANTLR可以解析一些需要一些（左）上下文约束的语言。

特别是，人们可以使用“减排行动”的语义谓词（我们这样做对我们DMS Software Reengineering Toolkit但这个想法是对ANTLR类似，我认为使用GLR分析器 ）检查到目前为止解析器收集的任何数据，或者作为其他语义行为的临时副作用，或者是部分构建的分析树。

对于我们的基于DMS的DMS-based Fortran front end，有一个上下文相关的检查来确保DO循环正确排列。试想一下：

DO 20, I= ... 
    DO 10, J = ... 
     ... 
20 CONTINUE 
10 CONTINUE 

但从解析器的角度来看，词法流是这样的：

DO <number> , <variable> = ... 
    DO <number> , <variable> = ... 
     ... 
<number> CONTINUE 
<number> CONTINUE 

如何解析器后来才知道里面做陈述与哪个CONTINUE语句？ （说每个DO与其最接近的CONTINUE匹配将不起作用，因为FORTRAN可以通过 与多个DO头共享一个CONTINUE语句）。

我们使用语义谓词“CheckMatchingNumbers”关于以下规则的减少：

block = 'DO' <number> rest_of_do_head newline 
     block_of_statements 
     <number> 'CONTINUE' newline ; CheckMatchingNumbers 

检查该做关键字后的数字，而数字之后的CONTINUE关键字匹配。如果语义谓词表示它们匹配，则此规则的减少会成功，并且我们已将DO头与正确的CONTINUE对齐。如果谓词失败，则不会提出约简（并且将此规则从候选解析本地上下文中删除）;其他一些规则必须解析文本。

处理FORTRAN嵌套与共享继续的实际规则和语义谓词比这更复杂，但我认为这说明了一点。

你想要的是完整的上下文相关的解析引擎。我知道人们已经建立了它们，但我不知道有什么完整的实现，也不希望它们速度很快。

我确实按照Quinn Taylor Jackson's MetaS grammar system一段时间;这听起来像是一个实际尝试接近。