将令牌优先于另一个令牌

Question

我试图了解LEXERS，我想知道如何优先考虑一个令牌而不是另一个令牌。我使用了一个真正的问题作为参考。

我制作了两个令牌，一个代表TEXT，另一个代表列表。它们共享一个字符，这意味着列表也可以作为文本读取。

有没有办法给我想要的令牌某种优先权？

我看了很多，但我没有发现任何关于这个主题的内容。我尝试将列表的定义放在文本上面，但它似乎没有改变任何东西。

TOKEN: {
    <#DIGIT: ["0"-"9"]>
    <#LETTER: ["a"-"z", "A"-"Z"]>
    <#SYMBOLS: ["@" , "."]>
    <#WORD: (<LETTER>|<DIGIT>|<SYMBOLS>)+>
} 


TOKEN: {
     ...
     <LI:  ((<DIGIT>)+)(".")>
     <TEXT:  <WORD>+ >
     ...
 }

如果我使用输入此作为LEXER的输入，

1.this is a list

我希望能回来

LI as 1.
TEXT as this is a list

但我得到的实际输出是

TEXT is 1.this is a list

谢谢

Answer 1

实际上Javacc使用两个规则来决定优先级，

规则1：在声明令牌时按顺序发生的优先级。

规则2：可能的基于优先级的最长匹配。

规则2总是优先于规则1.也就是说，JavaCC总是匹配输入的最长匹配前缀;然后，如果有多个令牌匹配最长匹配，则它使用规则1来确定要生成哪个令牌。

在您的情况下，您期望应用规则1但JavaCC使用规则2，最长的匹配;结果。

此外TEXT不能匹配this is a list，因为它包含空间字符，这是TEXT的定义所不允许的。

令牌部分仅用于进行词法分析。因此，使用生产规则进行语法分析。

Answer 2

问题是“有没有办法给予某种优先权，我想让它[匹配]？”

有几种方法。

---

第一种方式就是这样

• 列出令牌规则，以便优先级最高的那个首先出现。

但这只适用于两个规则匹配相同长度的字符串时。

在你的情况下，你希望“1.this”匹配为<LI>，然后是<TEXT>。但是文本规则将匹配6个字符，而<LI>规则将仅匹配2.因此，正如FAQ和@ sarath的答案中所解释的那样，<TEXT>规则将获胜。

---

第二种方式。

• 使用词法状态禁用您不想获胜的规则。

此方法不适合您的问题，因为您需要同时激活这两个规则。

---

第三种方式。

• 重写规则，以便在应用较高优先级规则时，较低优先级的规则不能应用于较长的字符串。

在你的情况下，你希望“1234.this”不匹配为<TEXT>，以便<LI>规则可以适用。我们将重写<TEXT>规则，使其不适用于任何这些字符串

"1234.this"
"1234.thi"
"1234.th"
"1234.t"
"1234."

（实际上，我们可以允许最后一个字符串，然后对规则进行排序，以便<LI>排在第一位。但我发现排除最后一个字符串也更容易。）

新令牌将被称为<TEXT1>以避免混淆。所以我们对<TEXT1>的规则将匹配任何字符串

• 匹配<TEXT>和那
• 不匹配<LI>和那
• 没有与<LI>匹配的前缀。

如果JavaCC为这种情况提供了一个很好的语法，那就太好了，但事实并非如此。我们必须找到正则表达式。

我喜欢在这种情况下派生正则表达式的方式是从正则表达式有限状态识别器（REFR）开始，然后从中派生正则表达式。 REFR的定义在幻灯片组1.2 here中，将REFR转换为正则表达式的算法也是如此。

TEXT1的第一个REFR如下。

    0s ---P|S|L---> 1f
    0s ---D-------> 2f
    1f --P|S|L|D--> 1f
    2f --D--------> 2f
    2f --S|L------> 1f

L表示字母，D表示数字。 P表示期间。 S表示除句点以外的任何符号，即“at”符号。有3种状态：0s，1f和2f。最终（即接受）州的名称中有“f”。起始状态名称中包含“s”。

希望机器的正确性是显而易见的。特别要注意的是，在输入D或DD或DDD等之后，机器可以处于的状态集是{2f};并且，如果机器处于状态2f并且P是下一个字符，则机器没有要进入的状态，因此该字符串被拒绝。因此，任何匹配LI或具有与LI匹配的前缀的字符串都将被拒绝。

第一步是将接受状态的数量减少到1，并确保没有来自接受状态的传出转换。 （我们还希望确保没有到启动状态的传入转换，但情况已经如此。）新机器是

    0s ---P|S|L---> 1
    0s ---D-------> 2
    1  --P|S|L|D--> 1
    1  --epsilon--> 3f
    2  --D--------> 2
    2  --S|L-----> 1
    2  --epsilon--> 3f

接下来消除状态2。

    0s ---P|S|L----> 1
    0s --D+(S|L)---> 1
    0s ---D+-------> 3f
    1  --P|S|L|D---> 1
    1  --epsilon---> 3f

将两个过渡从0到1组合在一起

    0s ---P|S|L|D+(S|L)----> 1
    0s ---D+---------------> 3f
    1  ---P|S|L|D----------> 1
    1  ---epsilon----------> 3f

消除状态1。

    0s ---(P|S|L|D+(S|L)) (P|S|L|D)*---> 3f
    0s ---D+---------------------------> 3f

结合转换得到

     (P|S|L|D+(S|L)) (P|S|L|D)*  | D+
0s--------------------------------------> 3f

最后，我们看看RE，看看它确实有意义，并寻找任何简化。

对我来说似乎是对的，我看不出任何简化它的方法。

我们完成了。