Транспилирование / генерация кода - объявление вопроса о переменных

Question

Я недавно работал над ANTLR и Java, и я создал простую грамматику, которая анализирует этот код и генерирует AST. Я также написал встроенный интерпретатор для выполнения этого кода, и он, кажется, работает хорошо:

Некоторые замечания по моему игрушечному языку:

• В моем языке есть только переменная одного типа " double "
• Все переменные неявно объявляются при присваивании.
• Все переменные имеют глобальную область видимости. Т.е. я могу использовать переменную после того, как она назначена даже вне блока, в котором она назначена.

/* 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, чтобы вывести это в C из Мой класс AST и я получаем этот результат (украшенный):

#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 (или, по крайней мере, поверх основная () функция). Объявление переменных непосредственно перед использованием в C приведет к невозможности компиляции допустимых программ на исходном языке в C, если в моей программе используется переменная вне блока.

Я думал, что смогу решить эту проблему, сначала разрешив все переменные и объявив их в начале программы C, а затем сгенерировав код.

Но если я обновлю таблицу символов (HashMap ) перед генерацией кода у меня не будет способа узнать, действительно ли переменная была назначена перед использованием.

Каков наилучший способ изменить это, чтобы гарантировать:

• генератор кода должен проверить присвоение перед использованием. Т.е. если он находит использование перед присваиванием, он должен выдать ошибку исключения / компиляции.
• в то же время все переменные в моем коде должны быть доступны как глобальные в сгенерированном C источнике. Таким образом, даже использование переменной вне блока возможно, если она назначена ранее во внутреннем блоке, поскольку в моем исходном языке это приемлемо.

Я впервые пытаюсь что-то подобное. Пожалуйста, укажите мне любое возможное решение.

Answer 1

В общем случае обнаружение использования до назначения невозможно. Рассмотрим следующий (не очень хороший) код 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() может быть внешней функцией. Или его возвращаемое значение может зависеть от ввода. Или это может быть основано на сложных вычислениях.

Это не значит, что вы не должны пытаться обнаружить проблему. Например, вы можете использовать symboli c выполнение , чтобы попытаться вычислить консервативную оценку неопределенного использования. Вы можете вызвать исключение, если можете доказать неопределенное использование, и выдать предупреждение, если не можете доказать, что все виды использования определены. (Многие компиляторы используют вариант этого метода.) Это может быть интересным упражнением в анализе потока управления.

Но для реального решения, учитывая, что все переменные имеют числовое значение c, я бы предлагаем просто автоматически инициализировать все переменные в 0, как часть семантики языка.

Answer 2

Я вроде решил эту проблему, удалив объявления переменных из отдельных узлов назначения и просто добавив переменную, используемую в узле назначения, в глобальную хэш-карту, а затем сгенерировал объявления после запуска по дереву.

Это вроде работает так:

• Прогулка по АСТ. Если я сталкиваюсь с использованием переменной (кроме как в операторе присваивания / ввода, генерируем исключение / ошибку.
• Если я сталкиваюсь с оператором присваивания / ввода, добавьте переменную в глобальную хэш-карту. не объявляйте его при генерации кода для конкретного узла.
• После генерации всего кода - запустите глобальную хэш-карту и сгенерируйте объявления
• Соберите основную программу, объединив операторы объявления и сгенерированный код.

Но я понял, что это может привести к потенциальным проблемам, когда переменная может быть инициализирована внутри блока IF и использоваться снаружи. Если программа выполнила блок IF, то нет проблема, но если блок IF пропущен, тогда я получаю исключение в моем интерпретаторе, но генерация кода в C все еще работает должным образом. Однако вывод в программе C является неинициализированной переменной, если блок IF не выполнено.

Взять например (в моем коде)

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) для неинициализации и проверка вместо этого.