解析上下文敏感语言

Question

我正在读Terence Parr的最终ANTLR参考文献,他说:

语义谓词是一种通过允许运行时信息驱动识别来识别上下文敏感语言结构的强大方法

但书中的例子非常简单.我需要知道的是:ANTLR可以解析上下文相关的规则,例如:

xAy - > xBy

如果ANTLR无法解析这些规则,是否还有另一种工具可以处理上下文敏感的语法？

Answer 1

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

特别是,人们可以在"减少动作"上使用语义谓词(我们这样做是为了我们的DMS软件再造工具包使用的GLR解析器,但我认为这个想法类似于ANTLR),以检查解析器到目前为止收集的任何数据,或者作为其他语义动作的临时副作用,或者在部分构建的解析树中.

对于我们基于DMS -基于DMS的Fortran前端,有一个上下文敏感的检查,以确保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的MetaS语法系统一段时间; 这听起来像是接近实际的尝试.