具有 void * 类型的 Lemon 解析器标记值

Question

我试图为我的柠檬解析器使用 void* 类型，但我遇到了一些奇怪的问题。

最初我使用自定义令牌类型，一个用于保存令牌值的结构，然后我切换到 void* 因为我的令牌值类型不同。

这是我的一些解析器代码；

expression(A) ::= expression(B) PLUS expression(C). { *((double *)A)=  *((double *)B)  +  *((double *)C) ; }
expression(A) ::= expression(B) MINUS expression(C). { *((double *)A)= *((double *) B)  -  *((double *)C) ;  }
expression(A) ::= expression(B) MULT expression(C). { *((double *)A)=  *((double *)B)  *   *((double *)C) ; }
expression(A) ::= expression(B) DIV expression(C). {
        if( *((double *)C)  != 0)
                *((double *)A)=  *((double *)B)  /  *((double *)C) ;
        else
                printf("Math Error!");
}

expression(A) ::= number(B). { *((double *)A)=  *((double *)B) ;}
number ::= INT.
number ::= FLOAT.

这是我的词法分析器，它是 re2c 文件；

while ((token = lex()) != EOL) {
        sy[size].val = tkn.val;

        parse(parser, token, &sy[size].val);
        size++;
}

sy[size].val是double类型。

但是当我运行1+2它returns4,当我运行1+4它返回8

我的猜测是解析器将最右边的值放入其堆栈并在它看到标记参数的任何地方使用它。

Answer 1

这是一个简单但错误的程序：

double* add_indirect(double* b, double* c) {
  double *a;
  *a = *b + *c;    /* Undefined behaviour! */
  return a;        /* This, too! */
}

应该清楚为什么那个程序是错误的：a 从未被初始化。它的声明说它是一个指向 double 的指针，但它从来没有指向任何东西。因此，当第 3 行中尝试通过该指针存储一个值时，随机内存将被修改——无论未初始化的指针偶然指向什么。然后，函数返回该随机值，使用它会造成更大的破坏。

如果程序员足够幸运，他们会在执行第 3 行时遇到段错误，因为 a 的随机未初始化值不是有效指针。但是很有可能从堆栈中取出的值是一个有效的指针。例如，它可能是 b 的值，放在堆栈上以便调用该函数。（大多数现代编译器不会像这样使用调用堆栈，但可能会发生类似的事情。）

现在，让我们看看您程序中的操作。

expression(A) ::= expression(B) PLUS expression(C). {
    *((double *)A)=  *((double *)B)  +  *((double *)C) ;
}

制作 A、B 和 C void* 并将它们强制转换为 double* 会使该操作更难阅读，但可以识别是相同的如上面失败程序中的第 3 行。 Lemon 操作应该设置左侧非终结符的值（在本例中由 A 表示），但该代码假定 A 已经有一个值，产生与上面相同的未定义行为。同样，分段错误本来是一个幸运的结果，因为它可能会突出显示程序，但在解析器生成器的情况下，与现代编译代码不同，A 的未初始化值很可能恰好是一些值已经在解析器堆栈中。

我看不出有任何明显的理由说明为什么您需要将此计算器中标记的语义值作为指向任何内容的指针。这样做会使您的代码变得相当复杂；例如，您被迫将每个标记化的值存储在一个向量中（如果输入文本太大，它可能会溢出），以便它们都有唯一的地址。只使用值类型会简单得多：

%token-type { double }
%default-type { double }

expression(A) ::= expression(B) PLUS expression(C).  { A = B + C; }
expression(A) ::= expression(B) MINUS expression(C). { A = B - C;  }
expression(A) ::= expression(B) MULT expression(C).  { A = B * C; }
expression(A) ::= expression(B) DIV expression(C).   {
        if( C != 0)
          A = B / C;
        else
          fprintf(stderr, "%s\n", "Math Error! Divide by zero.");
}

expression(A) ::= number(B). { A = B ;}

那么你的驱动就变得简单了：

while ((token = lex()) != EOL) {
        parse(parser, token, tkn.val);
}

显然，您希望值具有不同的类型。使值成为指针并不能帮助你实现这个目标，因为 C 中指针的实现，即使是 void*，也是原始内存地址；它不记录任何类型信息。不可能通过查询指针来确定它恰好指向的数据类型。（因此，使 number 成为指向 double 的指针或指向 int 的指针会丢失有关其原始内容的信息。）如果您需要此功能，您的令牌类型将需要可以是 union——如果每个标记和非终结符都有特定类型——或者你自己实现的通常称为 "discriminated union" 的东西；即 struct 包含 union 和一个枚举值，说明 union 的哪个成员有效。但是在这两种情况下，值都不是指针（除了令牌值确实是指针的情况，例如字符串）；语义值是令牌对象的直接值，即使该值是（希望很小）struct。

具有 void * 类型的 Lemon 解析器标记值

Lemon parser token value with void * type

parsing

parameters

terminal

lemon

re2c