0

我最近一直在研究 ANTLR 和 Java，我构建了一个简单的语法来解析这段代码并生成一个 AST。我还编写了一个内置解释器来执行这段代码，它似乎运行良好：

关于我的玩具语言的一些注释：

  • 我的语言只有一种可变的“双”
  • 所有变量都在赋值时隐式声明。
  • 所有变量都具有全局范围。即，即使在分配它的块之外，我也可以在分配变量之后使用它。
/* A sample program */
BEGIN
    j := 1;
    WHILE j <= 5 DO
        PRINT "ITERATION NO: "; PRINTLN j;
        sumA1 := 0;
        WHILE 1 = 1 DO 
            PRINT "Enter a number, 0 to quit: ";
            i := INPUT;
            IF i = 0 THEN
                BREAK;
            ENDIF
            sumA1 := ADD sumA1, i;
        ENDWHILE
        j := ADD j, 1;
        PRINT "The sum is: "; PRINTLN sumA1;
    ENDWHILE
    j := MINUS j;
    PRINTLN j;
END

然后我将代码生成函数写入 AST 以将其从我的 AST 类输出到 C，我得到了这个结果（美化）：

#include <stdio.h>

#include <stdlib.h>

int main(int argc, char * argv[]) {
  double j;
  j = 1.00000;
  while (j <= 5.0) {
    printf("ITERATION NO: ");
    printf("%g\n", j);
    double sumA1;
    sumA1 = 0.00000;
    while (1.0 == 1.0) {
      printf("Enter a number, 0 to quit: ");
      double i;
      scanf("%lf", & i);
      if (i == 0.0) {
        break;
      }
      sumA1 = sumA1 + i;
    }
    j = j + 1.00000;
    printf("The sum is: ");
    printf("%g\n", sumA1);
  }
  j = -j;
  printf("%g\n", j);
}

在代码生成期间，我首先检查变量名称是否在 HashMap 中可用。对于赋值语句/输入语句，我在赋值之前添加了变量声明，如您所见。对于赋值以外的变量的使用，我会在使用前抛出一个非初始化变量的异常。

一切都很好。上面的代码适用于这个例子，因为在我的源程序中，我没有在声明它的范围之外使用任何变量。

但是有一个问题。由于我正在初始化块内的某些变量（就像while它们不能在范围外使用），我需要一种方法来收集源程序中使用的所有变量作为 C 中的全局变量（或至少在 main() 函数的顶部）。如果在块外的程序中使用该变量，则在 C 中使用之前声明变量将导致源语言中的有效程序无法在 C 中编译。

我想我可以通过首先解析所有变量并在 C 程序开始时声明它们然后生成代码来解决它。

但是如果我在生成代码之前更新符号表（HashMap），我将无法知道变量是否在使用前被实际分配。

重新设计它以确保：

  • 代码生成器应在使用前检查分配。即，如果它在赋值之前发现了一个用法，它应该抛出一个异常/编译错误。
  • 同时，我的代码中的所有变量都应该在 C 生成的源代码中作为全局变量可用。因此，如果之前在内部块中分配变量，则即使在块外使用变量也是可能的，因为在我的源语言中它是可以接受的。

这是我第一次尝试这样的事情。请为我提供任何可能的解决方案的指针。

4

2 回答 2

2

在一般情况下，在分配之前检测使用是不可能的。考虑以下（不是很好）C 代码：

int sum;          /* uninitialised */
for (i = 0; i < n; ++i) {
  if (check(i)) sum = 0;
  sum += val[i];  /* Is sum initialised here? */
  process(sum);
}

如果check(i)是，比如说，，i % 10 == 0那么sum肯定会被初始化。但如果是i % 10 == 1，则sum在第一次迭代中未初始化使用。一般来说，是否sum使用未初始化取决于 的值check(0)。但可能没有办法知道那是什么。check()可能是一个外部函数。或者它的返回值可能取决于输入。或者它可能基于一个困难的计算。

这并不意味着您不应该尝试检测问题。例如，您可以使用符号执行来尝试计算未定义使用的保守估计。如果您可以证明未定义的使用，您可以抛出异常，如果您不能证明所有的使用都已定义，则发出警告。（许多编译器使用这种技术的变体。）这可能是控制流分析中一个有趣的练习。

但是对于现实世界的解决方案，鉴于所有变量都是数字的，我建议将所有变量自动初始化为 0，作为语言语义的一部分。

于 2020-04-12T13:19:40.747 回答
0

我已经通过从各个分配节点中删除变量声明并将分配节点中使用的变量添加到全局哈希图中来解决它，然后在运行树后生成声明。

它的工作原理是这样的：

  • 走 AST。如果我遇到变量的用法（除了在赋值/输入语句中，生成异常/错误。
  • 如果我遇到赋值/输入语句，请将变量添加到全局哈希图中。但不要在特定节点的代码生成中声明它。
  • 生成整个代码后 - 运行全局哈希图并生成声明
  • 通过连接声明语句和生成的代码来组合主程序。

但我意识到，这可能会导致潜在的问题，即变量可能在 IF 块内初始化并在外部使用。如果程序已经执行了 IF 块，那么没有问题，但是如果 IF 块被跳过，那么我的解释器中会出现异常，但 C 中的代码生成仍然可以正常工作。但是，如果不执行 IF 块，则 C 程序中的输出是未初始化的变量。

举个例子（在我的代码中）

BEGIN
   i := INPUT;
   IF i < 10 THEN
      j := MUL i, 10;
   ENDIF
   PRINT j;
END

吐出这个C代码（美化）

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
   double i;
   double j;
   scanf("%lf", &i);
   if (i < 10.0)
   {
      j = i *10.0000;
   }
   printf("%g\n", j);
}

IF在这种情况下，如果未到达并编译块，即何时i >= 10（因为j将未初始化），我的内置解释器将抛出异常。但是，等效的 C 代码会正确生成和编译，但j将是导致运行时行为的未初始化变量。

但就目前而言，我认为我可以接受这种行为，因为无论如何，使用可能未初始化的变量是程序本身设计的问题。

我想另一种选择是使用隐式 NULL（或 NaN）值初始化变量以进行未初始化并检查它。

于 2020-04-12T13:34:58.723 回答