Создание компилятора языка для .NET Framework - Генератор кода

ОГЛАВЛЕНИЕ

Генератор кода

Генератор кода для компилятора Good for Nothing в большой степени полагается на библиотеку Reflection.Emit для создания исполняемых сборок .NET. Я опишу и проанализирую важные части класса, оставив прочее читателям для ознакомления, когда им будет удобно.

Конструктор CodeGen, показанный на рис. 9, устанавливает инфраструктуру Reflection.Emit, которая необходима прежде чем я начну выводить код. Я начинаю с определения имени сборки и передачи его компоновщику сборки. В данном примере, я использую имя исходного файла, как имя сборки. Далее идет определение ModuleBuilder – для определения одного модуля, оно использует то же имя, что и сборка. Далее я определяю TypeBuilder на ModuleBuilder, чтобы содержать единственный тип в сборке. Типов, определенных как привилегированные компоненты определения языка Good for Nothing, не существует, но по крайней мере один тип необходим, чтобы содержать метод, выполняющийся при запуске. MethodBuilder определяет Main для содержания IL, создаваемого кодом Good for Nothing. Мне пришлось вызвать SetEntryPoint на этом MethodBuilder, чтобы он выполнялся во время запуска, при активации пользователем исполняемого файла. Я также создаю глобальный ILGenerator (il) из MethodBuilder, используя метод GetILGenerator.

Figure 9 CodeGen Constructor

Emit.ILGenerator il = null;
Collections.Dictionary<string, Emit.LocalBuilder> symbolTable;

public CodeGen(Stmt stmt, string moduleName)
{
  if (Path.GetFileName(moduleName) != moduleName)
  {
    throw new Exception("can only output into current directory!");
  }

  AssemblyName name = new
    AssemblyName(Path.GetFileNameWithoutExtension(moduleName));
  Emit.AssemblyBuilder asmb =
    AppDomain.CurrentDomain.DefineDynamicAssembly(name,
      Emit.AssemblyBuilderAccess.Save);
  Emit.ModuleBuilder modb = asmb.DefineDynamicModule(moduleName);
  Emit.TypeBuilder typeBuilder = modb.DefineType("Foo");

  Emit.MethodBuilder methb = typeBuilder.DefineMethod("Main",
    Reflect.MethodAttributes.Static,
    typeof(void),
    System.Type.EmptyTypes);

  // CodeGenerator
  this.il = methb.GetILGenerator();
  this.symbolTable = new Dictionary<string, Emit.LocalBuilder>();

  // Go Compile
  this.GenStmt(stmt);

  il.Emit(Emit.OpCodes.Ret);
  typeBuilder.CreateType();
  modb.CreateGlobalFunctions();
  asmb.SetEntryPoint(methb);
  asmb.Save(moduleName);
  this.symbolTable = null;
  this.il = null;
}

После того, как инфраструктура Reflection.Emit установлена, генератор кода вызывает метод GenStmt, используемый для пошагового анализа AST. This generates the necessary IL code through the global ILGenerator. рис. 10 показывает подмножество метода GenStmt, которое при первом вызове, начинает с узла Sequence («Последовательность») и затем проводит пошаговый анализ AST, переключаясь на текущий тип узла AST.

Figure 10 Subset of GenStmt Method

private void GenStmt(Stmt stmt)
{
    if (stmt is Sequence)
    {
        Sequence seq = (Sequence)stmt;
        this.GenStmt(seq.First);
        this.GenStmt(seq.Second);
    }        
    
    else if (stmt is DeclareVar)
    {
        ...    
    }        
    
    else if (stmt is Assign)
    {
        ...        
    }                
    else if (stmt is Print)
    {
        ...    
    }

Ниже приведен код, необходимый для DeclareVar (декларации переменной AST:

else if (stmt is DeclareVar)
{
    // declare a local
    DeclareVar declare = (DeclareVar)stmt;
    this.symbolTable[declare.Ident] =
        this.il.DeclareLocal(this.TypeOfExpr(declare.Expr));

    // set the initial value
    Assign assign = new Assign();
    assign.Ident = declare.Ident;
    assign.Expr = declare.Expr;
    this.GenStmt(assign);
}

Первое что здесь нужно сделать, это добавить переменную к таблице символов. Таблица символов – это центральная структура данных компилятора, используемая для привязки символического идентификатора (в данном случае, имени переменной на основе строки) к его типу, расположению и масштабу внутри программы. Таблица символов Good for Nothing несложна и все декларации переменных являются локальными для метода Main. Так что я связываю символ с LocalBuilder, используя простой Dictionary<string, LocalBuilder>.

После добавления символа к таблице символов, я преобразую узел AST DeclareVar в узел Assign («Назначения»), чтобы назначить переменной выражения ее деклараций. Для создания оператора Assignment («Назначение») я пользуюсь следующим кодом:

else if (stmt is Assign)
{
    Assign assign = (Assign)stmt;
    this.GenExpr(assign.Expr, this.TypeOfExpr(assign.Expr));
    this.Store(assign.Ident, this.TypeOfExpr(assign.Expr));
}    

Выполнение этого создает код IL для загрузки выражения на стек и затем выдает IL для сохранения выражения в подходящем LocalBuilder.

Код GenExpr, показанный на рис. 11, берет узел Expr AST и выдает IL, необходимый для загрузки выражения на машину стека. StringLiteral и IntLiteral похожи по части наличия прямых инструкций IL загрузить соответствующие строки и целые числа на стек: ldstr и ldc.i4.

Figure 11 GenExpr Method

private void GenExpr(Expr expr, System.Type expectedType)
{
  System.Type deliveredType;
    
  if (expr is StringLiteral)
  {
    deliveredType = typeof(string);
    this.il.Emit(Emit.OpCodes.Ldstr, ((StringLiteral)expr).Value);
  }
  else if (expr is IntLiteral)
  {
    deliveredType = typeof(int);
    this.il.Emit(Emit.OpCodes.Ldc_I4, ((IntLiteral)expr).Value);
  }        
  else if (expr is Variable)
  {
    string ident = ((Variable)expr).Ident;
    deliveredType = this.TypeOfExpr(expr);

    if (!this.symbolTable.ContainsKey(ident))
    {
      throw new Exception("undeclared variable '" + ident + "'");
    }

    this.il.Emit(Emit.OpCodes.Ldloc, this.symbolTable[ident]);
  }
  else
  {
    throw new Exception("don't know how to generate " +
      expr.GetType().Name);
  }

  if (deliveredType != expectedType)
  {
    if (deliveredType == typeof(int) &&
        expectedType == typeof(string))
    {
      this.il.Emit(Emit.OpCodes.Box, typeof(int));
      this.il.Emit(Emit.OpCodes.Callvirt,
        typeof(object).GetMethod("ToString"));
    }
    else
    {
      throw new Exception("can't coerce a " + deliveredType.Name +
        " to a " + expectedType.Name);
    }
  }
}

Переменные выражения просто загружают локальную переменную метода на стек, вызывая ldloc и передавая соответствующий LocalBuilder. Последний раздел кода, показанного на рис. 11 занимается преобразованием типа выражение в ожидаемый тип (что называется принуждением типа). Например, типу может требоваться преобразование в вызове метода отображения, где целое число необходимо преобразовать в строку, чтобы отображение было успешным.

рис. 12 демонстрирует, как переменным назначаются выражения в методе Store. Имя находится в таблице символов и соответствующий LocalBuilder затем передается инструкции stloc IL. Это просто выталкивает текущее выражение со стека и назначает его локальной переменной.

Figure 12 Store Expressions to a Variable

private void Store(string name, Type type)
{
  if (this.symbolTable.ContainsKey(name))
  {
    Emit.LocalBuilder locb = this.symbolTable[name];

    if (locb.LocalType == type)
    {
      this.il.Emit(Emit.OpCodes.Stloc, this.symbolTable[name]);
    }
    else
    {
      throw new Exception("'" + name + "' is of type " +
        locb.LocalType.Name + " but attempted to store value of type " +
        type.Name);
    }
  }
  else
  {
    throw new Exception("undeclared variable '" + name + "'");
  }
}

Код, используемый для создания IL для узла отображения AST, интересен тем, что вызывает метол BCL. Выражение создается на стеке и инструкция вызова IL используется, чтобы вызвать метод System.Console.WriteLine. Reflection («Отражение») используется для получения дескриптора метода WriteLine, необходимой для передачи инструкции вызова:

else if (stmt is Print)
{
  this.GenExpr(((Print)stmt).Expr, typeof(string));
  this.il.Emit(Emit.OpCodes.Call,
    typeof(System.Console).GetMethod("WriteLine",
    new Type[] { typeof(string) }));
}

При выполнении вызова метода, аргументы метода выталкиваются из стека по принципу «последний на входе, первый внутри». Другими словами, первый аргумент метода становится верхним элементом стека, второй аргумент – следующим элементом и так далее.

Наиболее сложным кодом является здесь код, создающий IL для моих циклов Good for Nothing (см. рис. 13). Он довольно похож на способы создания подобного кода коммерческими компиляторами. Однако, лучшим способом уяснить код цикла, является взгляд на создаваемый IL, который показан на рис. 14.

Figure 14 For Loop IL Code

// for x = 0
IL_0006:  ldc.i4     0x0
IL_000b:  stloc.0

// jump to the test
IL_000c:  br         IL_0023

// execute the loop body
IL_0011:  ...

// increment the x variable by 1
IL_001b:  ldloc.0
IL_001c:  ldc.i4     0x1
IL_0021:  add
IL_0022:  stloc.0

// TEST
// load x, load 100, branch if
// x is less than 100
IL_0023:  ldloc.0
IL_0024:  ldc.i4     0x64
IL_0029:  blt        IL_0011

Figure 13 For Loop Code

else if (stmt is ForLoop)
{
    // example:
    // var x = 0;
    // for x = 0 to 100 do
    //   print "hello";
    // end;

    // x = 0
    ForLoop forLoop = (ForLoop)stmt;
    Assign assign = new Assign();
    assign.Ident = forLoop.Ident;
    assign.Expr = forLoop.From;
    this.GenStmt(assign);            
    // jump to the test
    Emit.Label test = this.il.DefineLabel();
    this.il.Emit(Emit.OpCodes.Br, test);

    // statements in the body of the for loop
    Emit.Label body = this.il.DefineLabel();
    this.il.MarkLabel(body);
    this.GenStmt(forLoop.Body);

    // to (increment the value of x)
    this.il.Emit(Emit.OpCodes.Ldloc, this.symbolTable[forLoop.Ident]);
    this.il.Emit(Emit.OpCodes.Ldc_I4, 1);
    this.il.Emit(Emit.OpCodes.Add);
    this.Store(forLoop.Ident, typeof(int));

    // **test** does x equal 100? (do the test)
    this.il.MarkLabel(test);
    this.il.Emit(Emit.OpCodes.Ldloc, this.symbolTable[forLoop.Ident]);
    this.GenExpr(forLoop.To, typeof(int));
    this.il.Emit(Emit.OpCodes.Blt, body);
}

Код IL начинается с первоначального назначения счетчика цикла и немедленно переходит к тестированию цикла, используя инструкцию IL br (ответвление). Метки, подобные перечисленным слева от кода IL используются, чтобы дать среде выполнения знать, где ответвлять следующую инструкцию. Тестовый код проверяет, меньше ли переменная x, чем 100, используя инструкцию blt (ответвление если меньше чем). Если это так, исполняется тело цикла, переменная x увеличивается и тест запускается снова.

Код цикла на рис. 13 создает код необходимый для выполнения операций назначения и увеличения на переменной счетчика. Он также использует метод MarkLabel на ILGenerator для создания меток, в которые могут ответвляться ветви инструкций.