JavaCC 可以根据上下文区分令牌吗？

Question

基本要求是使用关键字作为标识符，所以我想将令牌与其上下文区分开来。（例如，class 是关键字，但我们允许使用名为 class 的变量）。

在java，这是可以做到的，但是太难了，here我就是这样做的

TOKEN :
{
    <I_CAL:     "CAL">  : DO_CAL
    | <I_CALL:  "CALL">
    | <I_CMP:   "CMP">
    | <I_EXIT:  "EXIT">
    | <I_IN:    "IN">
    | <I_JMP:   "JMP">
    | <I_JPC:   "JPC">  : NEED_CMP_OP
    | <I_LD:    "LD">   : NEED_DATA_TYPE
    | <I_NOP:   "NOP">
    | <I_OUT:   "OUT">
    | <I_POP:   "POP">
    | <I_PUSH:  "PUSH">
    | <I_RET:   "RET">
    | <I_DATA:  "DATA"> : DO_DATA
    | <I_BLOCK:  ".BLOCK">
}

// T prefix for Token
TOKEN :
{
    <T_REGISTER : "R0" | "R1" | "R2" | "R3" | "RP" | "RF" |"RS" | "RB">
// We need below TOKEN in special context, other wise they are just IDENTIFIER
//    | <DATA_TYPE: "DWORD" | "WORD" | "BYTE" | "FLOAT" | "INT">
//    | <PSEUDO_DATA_TYPE: "CHAR" >
//    | <CAL_OP: "ADD" | "SUB" | "MUL" | "DIV" | "MOD">
//    | <CMP_OP: "Z" | "B" | "BE" | "A" | "AE" | "NZ">
    | <T_LABEL: <IDENTIFIER> ([" "])* <COLON>>
}

// Now we need a CMP OP
<NEED_CMP_OP> TOKEN:
{
    <CMP_OP: "Z" | "B" | "BE" | "A" | "AE" | "NZ"> : DEFAULT
}
// Now we need a DATA TYPE
<NEED_DATA_TYPE,DO_CAL> TOKEN:
{
    // EXTENSION Add char to data type
    <DATA_TYPE: "DWORD" | "WORD" | "BYTE" | "FLOAT" | "INT" | "CHAR"> {
        if(curLexState == DO_CAL){
            SwitchTo(NEED_CAL_OP);
        }else{
            SwitchTo(DEFAULT);
        }
    }
}
// We need a CAL OP
<NEED_CAL_OP> TOKEN:
{
    <CAL_OP: "ADD" | "SUB" | "MUL" | "DIV" | "MOD"> : DEFAULT
}
// Aslo need to skip the empty
<NEED_DATA_TYPE,NEED_CAL_OP,NEED_CMP_OP,DO_CAL,DO_DATA> SKIP:
{
    " "
|   "\t"
|   "\r"
|   "\f"
}

来源是here，我可以通过curLexState来区分token和context。

这是可行的，但是做起来很麻烦，需要添加很多额外的状态，并维护很多states.Is有什么简单的方法可以实现这个？

Answer 1

如果将词法分析器和解析器合并成一个面向字符的解析器，那么在上下文中区分关键字就相对容易了，因为解析器就是为了保留上下文。您可以在字符标记上运行 JavaCC 来实现这种效果，但由于其他原因，它的 LL 性质可能会导致无法编写实用的语法。

如果将词法分析器和解析器分开，这并不容易。

你要求词法分析器知道什么时候是标识符或关键字，它只能通过了解找到 Id/keyword 的上下文来做到这一点。

理想情况下，词法分析器会简单地向解析器询问其状态，这将标识做出选择的上下文。这很难组织；大多数解析器并非旨在轻松揭示其状态或以易于解释的形式来提取所需的上下文信号。 JavaCC 显然不是这样组织的。

您的另一个显而易见的选择是将不同的上下文建模为词法分析器中的状态，词法状态之间的转换对应于有趣上下文之间的转换。根据上下文，这可能容易也可能不容易。如果你能做到，你必须在你的词法分析器中对状态和转换进行编码，并使它们保持最新。当你可以做到这一点时 "easily"，这不是一个糟糕的解决方案。根据具体情况，这可能很难或不可能。

出于 OP 目的（显然是汇编程序的解析器），上下文通常由源代码行中的位置决定。通过观察空白，可以定性地将汇编程序输入分为标签、操作码、操作数、注释上下文：换行符将上下文设置为标签，标签模式中的空白将上下文设置为操作码，操作码中的空白设置操作数上下文，操作数上下文中的空白设置注释语境。通过这些状态转换，可以为每个上下文编写不同的 sublexer，从而在每个子上下文中具有不同的关键字。

这个技巧不适用于像 PL/I 这样的语言，这些语言在上下文中有大量关键字（对于 PL/I，事实上，每个关键字都只在上下文中！）。

一个不明显的选择是根本不尝试区分。当找到 Id/Keyword 时，将 both 标记提供给解析器，让它找出哪个导致可行的解析。（注意：它可能已经处理了多个不明确标记的叉积，因此在解决这个问题时有很多可能的解析。）这需要一个能够处理歧义的解析器，无论是在解析时，还是在它接受的标记中（或者它不能同时接受 ID 和关键字标记）。当您拥有正确的解析机制时，这是一个非常简单的解决方案。 JavaCC 不是那种机器。

[查看我的 GLR 解析引擎简介，其中所有 3 种解决方案都可以轻松访问。它可以轻松处理 Pl/I。

Answer 2

JavaCC FAQ.

中概述了三种方法可以做到这一点

一种是使用词法状态，就像你所做的那样。这种方法可能很棘手，但它是处理最长匹配的长度取决于上下文或跳过规则取决于上下文的情况的唯一方法。对于您的问题，它可能比您需要的更复杂。
第二种是使用一种标记，并使用基于标记图像的语义先行，让解析器在某些情况下特殊处理某些标记。有关更多信息，请参阅常见问题解答。
第三种（通常也是最简单的）方法是在词法层面进行区分，然后忽略句法层面的区别。这通常是处理可兼作标识符的关键字的最佳方式。

下面我将给出第三种方法的三个例子。

使用关键字作为标识符

如果您只想让关键字class用作变量名，有一种非常简单的方法可以做到这一点。在词法分析器中输入通常的规则。

TOKEN: { <CLASS: "class"> }
TOKEN: { < VARNAME: ["a-"z","A"-Z"](["a-"z","A"-Z"])* > } // Or what you will

在解析器中写一个产生式

Token varName() { Token t ; } : {
{
    (t = <CLASS> | t = <VARNAME>)
    {return t ;}
}

然后在解析器的其他地方使用 varName()。

楼主的汇编

转回原题中的汇编程序例子，我们以JPC指令为例。 JPC（条件跳转）指令后跟一个比较运算符，例如 Z、B 等，然后是一个操作数，它可以是包括标识符在内的许多东西。例如。我们可以

JPC Z fred

但我们也可以有一个名为 JPC 或 Z 的标识符，所以

JPC Z JPC

和

JPC Z Z

也是有效的 JPC 指令。

在词汇部分我们有

TOKEN : // Opcodes
{
    <I_CAL: "CAL"> 
|   <I_JPC: "JPC"> 
|   ... // other op codes
    <CMP_OP: "Z" | "B" | "BE" | "A" | "AE" | "NZ">
|   <T_REGISTER : "R0" | "R1" | "R2" | "R3" | "RP" | "RF" |"RS" | "RB">
}
... // Other lexical rules.

TOKEN : // Be sure this rule comes after all keywords.
{
    < IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)* >
}

在解析器中我们有

Instruction Instruction():{
    Instruction inst = new Instruction();
    Token o = null,dataType = null,calType = null,cmpType = null;
    Operand a = null,b = null; }
{
    ...
    o = <I_JPC> cmpType = <CMP_OP> a = Operand()
    ...
}

Operand Operand():{
    Token t ; ... }
{
     t = <T_REGISTER> ...
|    t = Identifier()  ...
    ...
}

Token Identifier : {
    Token t ; }
{
    t = <IDENTIFIER> {return t ;}
|   t = <I_CAL>      {return t ;}
|   t = <I_JPC>      {return t ;}
|   t = <CMP_OP>     {return t ;}
| ... // All other keywords
}

我建议从可用作标识符的其他关键字列表中排除寄存器名称。

如果您确实在该列表中包含 <T_REGISTER>，那么操作数就会出现歧义，因为 Operand 看起来像这样

Operand Operand():{
    Token t ; ... }
{
     t = <T_REGISTER> ...
|    t = Identifier()  ...
    ...
}

现在有歧义因为

JPC Z R0

有两个解析。在作为操作数的上下文中，我们希望像 "R0" 这样的标记被解析为寄存器而不是标识符。幸运的是，JavaCC 更喜欢早期的选择，所以这正是将会发生的事情。您将从 JavaCC 收到警告。您可以忽略该警告。（我在我的源代码中添加了注释，这样其他程序员就不用担心了。）或者您可以使用先行规范来抑制警告。

Operand Operand():{
    Token t ; ... }
{
     LOOKAHEAD(1) t = <T_REGISTER> ...
|    t = Identifier()  ...
    ...
}

使用正确的上下文

到目前为止，所有示例都使用了左上下文。 IE。我们可以仅根据其左侧的标记序列来判断如何处理标记。让我们看一个例子，其中关键字的解释是基于右边的标记。

考虑这种简单的命令式语言，其中所有关键字都可以用作变量名。

P -> Block <EOF>
Block -> [S Block]
S -> Assignment | IfElse
Assignment -> LHS ":=" Exp
LHS -> VarName
IfElse -> "if" Exp Block ["else" Block] "end"
Exp -> VarName
VarName -> <ID> | if | else | end

这个语法没有歧义。您可以通过添加新的语句、表达式和左侧来使语法更复杂；只要语法保持明确，这些复杂情况可能不会对我接下来要说的内容产生太大影响。随意尝试。

语法不是 LL(1)。有两个地方必须根据不止一种未来代币做出选择。一种是当下一个标记为 "if" 时，在 Assignment 和 IfElse 之间进行选择。考虑块

a := b
if := a

对

a := b
if q
    b := c
end

我们可以像这样向前看“:=”

void S() : {} {
    LOOKAHEAD( LHS() ":=" ) Assignment()
|
    IfElse() 
}

我们需要向前看的另一个地方是在块的开头遇到 "else" 或 "end" 时。考虑

if x
    end := y
    else := z
end

我们可以用

解决这个问题

void Block() : {} {
    LOOKAHEAD( LHS() ":=" | "if" ) S() Block()
|
    {}
}

JavaCC 可以根据上下文区分令牌吗？

Can JavaCC distinguish token by its context?

java

compiler-construction

javacc

token

使用关键字作为标识符

楼主的汇编

使用正确的上下文