编译抽象语法树

编译抽象语法树

对大多数开发人员来说，编译就意谓着产生本地代码，给人感觉就是一个字，难。但是，并不一定要产生本地代码，对于 DSL，通常产生其他更加通用的编程语言。.NET 框架提供几个把抽象语法树编译成程序的功能。

技术的选择取决于几个因素。例如，如果语言针对的是开发人员，那么，生成文本文件就足够了，内容可以是 F#，也可以是其他语言，或者是编译过的程序集，能在程序中使用；然而，如果针对的是最终用户，那么几乎可以肯定，必须编译然后动态[ on the fly ]执行。表12-1 汇总了各种可用选项。

表12-1 .NET 的代码生成技术

我们System.Reflection.Emit.DynamicMethod 类，并不是因为我们特别需要中间语言的灵活性，而是因为中间语言内置了浮点运算的指令，可以很适合实现我们的小语言。DynamicMethod 还提供了快捷、容易的方法可以调用产生的程序。

createDynamicMethod 方法才真正编译抽象语法树，通过扫描抽象语法树和生成代码。首先，创建DynamicMethod 类的实例，来操作这个中间语言，是定义来表示这个方法的：

let temp = new DynamicMethod("",(type float), paramsTypes, meth.Module)

然后，createDynamicMethod 开始遍历树。遇到标识符，输出的代码是加载动态方法的参数：

| Ident name ->

   il.Emit(OpCodes.Ldarg, paramNames.IndexOf(name))

当遇到文字时，输出的中间语言代码是加载这个文字的值：

| Val x ->il.Emit(OpCodes.Ldc_R8, x)

当遇到操作时，必须递归评估计算表达式的两项，然后输出的是表示要求操作的指令：

| Multi (e1 , e2) ->

 generateIlInner e1

  generateIlInner e2

  il.Emit(OpCodes.Mul)

注意，如何运算是最后输出的，在表达式的两项递归评估之后。这样做原因是中间语言基于堆栈，因此，来自其他运算的数据，在评估运算符之前，必须压栈。

清单 12-7 是完整的编译器。

清单 12-7 编译从命令行输入生成的抽象语法树

openSystem.Collections.Generic

open System.Reflection

open System.Reflection.Emit

openStrangelights.ExpressionParser

// get a list of all the parameter names

let rec getParamList e =

    let recgetParamListInner e names =

        match e with

        | Identname ->

            if not (List.exists (funs -> s = name) names) then

               name :: names

            else

               names

        | Multi(e1 , e2) ->

           names

           |> getParamListInner e1

           |> getParamListInner e2

        | Div(e1 , e2) ->

           names

            |> getParamListInner e1

           |> getParamListInner e2

        | Plus(e1 , e2) ->

           names

           |> getParamListInner e1

           |> getParamListInner e2

        | Minus(e1 , e2) ->

           names

           |> getParamListInner e1

           |> getParamListInner e2

        | _ -> names

   getParamListInner e []

// create the dynamic method

letcreateDynamicMethod e (paramNames: string list) =

    let generateIl e (il : ILGenerator) =

        let recgenerateIlInner e =

            match e with

            |Ident name ->

               let index = List.find_index (fun s -> s = name)paramNames

               il.Emit(OpCodes.Ldarg, index)

            |Val x -> il.Emit(OpCodes.Ldc_R8, x)

            |Multi (e1 , e2) ->

               generateIlInner e1

               generateIlInner e2

               il.Emit(OpCodes.Mul)

            |Div (e1 , e2) ->

               generateIlInner e1

               generateIlInner e2

               il.Emit(OpCodes.Div)

            | Plus (e1 , e2) ->

               generateIlInner e1

               generateIlInner e2

               il.Emit(OpCodes.Add)

            |Minus (e1 , e2) ->

               generateIlInner e1

               generateIlInner e2

               il.Emit(OpCodes.Sub)

       generateIlInner e

       il.Emit(OpCodes.Ret)

    let paramsTypes = Array.create paramNames.Length (typeof<float>)

    let meth = MethodInfo.GetCurrentMethod()

    let temp = newDynamicMethod("", (typeof<float>), paramsTypes, meth.Module)

    let il = temp.GetILGenerator()

    generateIle il

    temp

// function to read the arguments fromthe command line

let collectArgs(paramNames : string list) =

    paramNames

    |> Seq.map

        (fun n ->

           printf "%s: " n

            box(float(Console.ReadLine())))

    |>Array.ofSeq

// the expression to be interpreted

let e = Multi(Val 2.,Plus(Val 2., Ident "a"))

// get a list of all the parameters fromthe expression

let paramNames =getParamList e

// compile the tree to a dynamic method

let dm =createDynamicMethod e paramNames

// print collect arguments from the user

let args =collectArgs paramNames

// execute and print out final result

printf "result:%O" (dm.Invoke(null, args))

运行结果如下：

编译清单 12-7 的代码产生下面的结果：

a: 4

result: 32

编译抽象语法树,布布扣,bubuko.com

编译抽象语法树

原文：http://blog.csdn.net/hadstj/article/details/28888657