parsing - 是否有可能有一个语法，其中 "keyword"也可以被视为 "non-keyword"？

Question

我在 ANTLRWorks 1.4 中有以下语法。我正在考虑在文本冒险游戏创建器中实现解析器的想法，其中用户将为他的游戏指定各种允许的命令。

grammar test;

parse       :   cmd EOF;


cmd         :   putSyn1 gameObject inSyn1 gameObject;

putSyn1     :   Put | Place | Drop ;

inSyn1      :   In | Into | Within;


gameObject  :   det obj;

det         :   The | A | An | ;

obj          :  Word obj | Word;


Space       :       (' ' | '\t' | '\r' | '\n'){$channel=HIDDEN;};
Put         :   'put';
Place       :   'place';
Drop        :   'drop';
In          :   'in';
Into        :   'into';
Within      :   'within';
The         :   'the';
A           :   'a';
An          :   'an';

Word        :   ('a'..'z' | 'A'..'Z')+;

我只是感受到其中涉及的各种微妙之处(就像我所做的 here )。

这一次，使用 ANTLR，我想知道是否可以解析输入，例如:

put wood in fire place

也就是说，“木头”和“火场”就是上面的游戏对象。然而，“地方”也是“放置”的同义词。所以这同样有效:

place wood in fire place

当尝试解析最后一个“place”标记时，ANTLR 给出了 NoViableAltException。我想将“fire place”识别为游戏对象。

那么这种事情在 ANTLR 中可能实现吗？语法上可以吗？

另一方面，我正在开发一个手动实现，它使用一种奇怪的自定义数据结构，其中包含 NFA、字典等内容。但我还需要更多的时间，必须牺牲一些脑细胞来设计所需的搜索和插入算法。

但如果这在 ANTLR 中可行，我就可以使用生成的 C# 文件，是吗？

Answer 1

当然。 PL/1 因没有任何保留字而闻名，例如，您可以在不需要关键字的任何地方使用关键字(例如 IF)作为变量名:

 IF  IF = 1  THEN  ELSE=3;  ELSE END=4;

构建一个执行此操作的解析器更加困难。您不能在词法分析器中“简单地”执行此操作，因为它不知道标识符可能是关键字的上下文，也可能不是关键字。

有几种出路。当找到类似实体的标识符时:

1) 让词法分析器询问解析器，“你现在想要一个关键字吗？”。在这种情况下，请生成一个关键字。让解析器在这里合作可能很困难。解析器也可能不知道，因为它必须查看更多输入才能做出决定。考虑 Fortran 著名的格式声明:

     FORMAT ( A1, I2, ... ) X

当您看到“FORMAT”一词时，您无法判断它是关键字还是标识符；你必须向前扫描任意远的距离来检查 X。如果 X 不是语句结尾，则 FORMAT 字是数组标识符的名称；如果 X 是语句结束，则它是 FORMAT 关键字和语句。

2) 发出关键字(如果标识符匹配)和标识符，并让解析器尝试两者。大多数解析器不能很好地处理这个问题，但是 GLR parsers如果设计合理的话，可以沉着地处理这个问题。通过引入解析器的前瞻功能，可以轻松处理格式问题。 (ANTLR 不是 GLR。我们的 DMS Software Reengineering Toolkit 正是这样一个 GLR 解析器，并且我们经常使用这个技巧)。

3)将所有类似标识符的东西放入哈希表中。使用递归下降解析器(ANTLR 就是其中之一)；当解析器需要一个关键字时，它只需检查它所获得的标识符以验证它是它需要的关键字。如果它不需要关键字，它只需使用标识符作为标识符。我不知道如何使用 ANTLR 来实现这个技巧，因为我不使用它。这不能很好地处理“没有前瞻就无法决定”的情况。