如何在Haskell中编写编译器？在C#中我使用了很多状态

Question

我正在C#中为一个学校项目做一个编译器,我不禁想知道如何在Haskell中做到这一点.

例如:

我为While循环生成的代码是:

public override void generateCode(Compiler compiler)
    {
        int jumpToTheBeginningInstructionIndex = compiler.getIndexOfNextActionInCurrentFunction();
        MachineInstructions.JMP jumpTotheBeginning = new MachineInstructions.JMP(jumpToTheBeginningInstructionIndex);
        MachineInstructions.JMPF jumpToTheEnd = new MachineInstructions.JMPF();

        booleanExpression.generateCode(compiler);

        //I insert the jump to the end here:
        compiler.addAction(jumpToTheEnd);

        foreach(IAction action in this.thenActions)
        {
            action.generateCode(compiler);
        }
        compiler.addAction(jumpTotheBeginning);

        //...But is here where I know where should it jump to:
        jumpToTheEnd.whereToJump = compiler.getIndexOfNextActionInCurrentFunction();
    }

您可以看到我如何在方法的中间插入jumpToTheEnd的代码,但直到我知道跳转的行的末尾.幸运的是,我保留了一个指向该跳转的指针,我可以轻松地在方法的最后设置其whereToJump属性.

你会怎么做Haskell!？任何推荐的教程？

Answer 1

我不知道.我不确定你是否想要在Haskell中构建代码生成阶段.但是假设你做了,你可以做的一件事就是把你的标签放在一个懒惰的状态monad中并使用结mfix.

这是这种技术的完整可运行示例.我们将有一个简单的AST,只有while循环和不做任何事情的语句; 和一个简单的指令类型,只有标签,跳转和不做任何事情的语句.我们的编译器将在某些状态下维护最新分配的标签.然后我想你的问题是如何生成"前进"跳转到尚未分配的标签.

{-# LANGUAGE FlexibleContexts #-}
import Control.Monad.State
import Control.Monad.Writer

data Instruction = Nop | Jump Int | Label Int deriving (Eq, Ord, Show, Read)
data AST = While AST AST | Rest               deriving (Eq, Ord, Show, Read)
type Compiler = StateT Int (Writer [Instruction])

generateLabel :: Compiler Int
generateLabel = do
    v <- get
    put (v+1)
    tell [Label v]
    return v

compile :: AST -> Compiler ()
compile Rest = tell [Nop]
compile (While b c) = do
    start <- generateLabel
    compile b
    mfix $ \end -> do
        tell [Jump end] -- here we generate a forward jump
        compile c
        tell [Jump start]
        generateLabel   -- here we allocate the label we're forward-jumping to
    return ()

runCompiler :: Compiler () -> [Instruction]
runCompiler = execWriter . flip evalStateT 0

在ghci中,尝试例如runCompiler (compile (While Rest Rest))最简单的例子.