解析上下文相关语言

Question

我正在阅读 Terence Parr 撰写的权威 ANTLR 引用文献，他在其中说道:

Semantic predicates are a powerful means of recognizing context-sensitive language structures by allowing runtime information to drive recognition

但是书中的例子非常简单。我需要知道的是:ANTLR可以解析context-sensitive规则如下:

xAy --> xBy

如果 ANTLR 无法解析这些规则，是否还有其他工具可以处理上下文相关语法？

Answer 1

ANTLR 仅解析 LL(*) 语法。它无法使用完整上下文相关语言的语法进行解析，例如您提供的示例。我认为 Parr 的意思是 ANTLR 可以解析需要某些(左)上下文约束的某些语言。

特别是，可以在“归约操作”上使用语义谓词(我们为 GLR 解析器执行此操作)我们的 DMS Software Reengineering Toolkit 使用但我认为 ANTLR 的想法是相似的)检查解析器到目前为止收集的任何数据，无论是作为其他语义操作的临时副作用，还是在部分构建的解析树中。

对于我们基于 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

解析器如何知道哪个 DO 语句与哪个 CONTINUE 语句搭配？(说每个 DO 与其最接近的 CONTINUE 匹配是行不通的，因为 FORTRAN 可以与多个 DO 头共享一个 CONTINUE 语句)。

我们在以下规则的约简中使用语义谓词“CheckMatchingNumbers”:

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

检查 DO 关键字后面的数字和 CONTINUE 关键字后面的数字是否匹配。如果语义谓词表示它们匹配，则此规则的缩减成功，并且我们已将 DO 头与正确的 CONTINUE 对齐。如果谓词失败，则不建议减少(并且该规则将从用于解析本地上下文的候选者中删除)；其他一些规则必须解析文本。

处理带有共享继续的 FORTRAN 嵌套的实际规则和语义谓词比这更复杂，但我认为这很重要。

您想要的是完整的上下文相关解析引擎。我知道人们已经构建了它们，但我不知道任何完整的实现，并且不期望它们很快。

我确实关注了Quinn Taylor Jackson's MetaS grammar system一阵子;这听起来像是一次接近实际的尝试。