Haskell：将表达式转换为指令列表

我的目标是转换型表达的形式“到CPU指令的列表中给出的数据结构

data Expr = Const Double | Var String | Add Expr Expr | Mult Expr Expr 

    data Instr = LoadImmediate RegisterNumber -- put value here 
           RegisterValue -- the value 
       | Addition RegisterNumber -- put result here 
          RegisterNumber -- first thing to add 
          RegisterNumber -- second thing to multiply 
       | Multiply RegisterNumber -- put result here 
          RegisterNumber -- first thing to multiply 
          RegisterNumber -- second thing to multiply 
    type RegisterNumber = Int 
    type RegisterValue = Double

类型表达有四个主要功能

Const：将一字符型（即“x”）转换为类型表达式，可以将它应用于常量
然后再Add和Mult命令，让你添加和乘两个类型表达式

而且我们可以假设，我们将看到的唯一的变量是“X”，它已经在寄存器2的结果将在寄存器1到帐总共有4个寄存器。

所以Add Const 1 (Mult (Var "x") (Const 2)) 型[INSTR]将

[LoadImmediate 3 1, 
LoadImmediate 4 2, 
Multiply 1 4 2, 
Addition 1 3 1]

编辑：对不起，我为GOT提，因为这是一个初学者课程中，我们只需要考虑的形式表达

(Const a) `Add` ((Var "x") `Mult` Expr)

其中'Expr'是一些表达式。或以数学形式a0 + x（a1 + x（a2 + x ...））

我修复了一点我的代码，现在我得到的错误是“不在范围内：数据构造函数'RegNum '“

expr2Code :: Expr -> [Instr] 
expr2Code expr = e2C 1 expr 
e2C:: Int -> Expr -> Instr 
e2C RegNum (Const y) = [LoadImmediate RegNum y] 
e2C RegNum (Var "x") = [] 
e2C RegNum (Add expr1 expr2) = e2C 3 expr1 ++ e2C 4 expr2 ++ [Addition RegNum 3 4] 
e2C RegNum (Mult expr1 expr2) = e2C 3 expr1 ++ e2C 4 expr2 ++ [Multiply RegNum 3 4]

对不起，对于很长的文章，任何帮助将不胜感激。

来源

2013-11-25 Iceandele

那么我假设你有无数的寄存器。如果没有，你可以体验注册溢出的喜悦，但是你需要更多的指令来处理动态内存。

有3种简单的方法可以做到这

表达式 - > SSA - > INSTR
表达式 - > CPS - > INSTR
表达式 - > INSTR

第一2提供了更容易的机会来优化您对寄存器的使用，但不涉及中间语言。由于我们是懒惰的，让我们做3.

import Control.Monad.State 

type Gensym = State Int 

gensym :: Gensym RegisterNumber 
gensym = modify (+1) >> fmap (subtract 1) get

现在我们有独特的寄存器产生的方式，我们可以做的奇妙低效的做法。

withRegister :: (RegisterNumber -> [Instr]) -> Gensym (RegisterNumber, [Instr]) 
withRegister f = gensym >>= \r -> return (r, f r) 

compile :: Expr -> Gensym (RegisterNumber, [Instr]) 
compile (Const d) = withRegister $ \r -> [LoadImmediate r d] 
compile (Var "x") = return (2, []) 
compile (Add e1 e2) = do 
    (t1, c1) <- compile e1 -- Recursively compile 
    (t2, c2) <- compile e2 -- Each subexpression like you were 
    withRegister $ \r -> Addition t1 t2 r : (c1 ++ c2) -- Make sure we 
                -- use a unique register 
compile (Mult e1 e2) = do 
    (t1, c1) <- compile e1 
    (t2, c2) <- compile e2 
    withRegister $ \r -> Multiply t1 t2 r : (c1 ++ c2) 

compileExpr :: Expr -> [Instr] 
compileExpr = reverse . snd . flip evalState 3 . compile

这基本上递归编译每个表达式，concatting它们的代码不同的块一起。这与您的相似，但有3个主要区别，但有3个主要区别，

我正在使用monad来为我处理寄存器。你必须确保你永远不会因为使用monad而破坏你需要的注册表，我确保我使用的所有寄存器都是唯一的。这确实是低效率的，但是非常正确。
当处理Var时，我只是加载寄存器2中的任何内容，因为LoadImmediate想要加倍，并且您没有实际绑定表达式中变量的机制。
因为你没有处理表达式，所以每个计算块都必须明确地停留在寄存器中。你不能再做x + y * z。这就是为什么如果你看Add或Mult的代码，每个子表达式都被编译成一个新的寄存器。

你的榜样产生

[LoadImmediate 4 2.0,Multiply 2 4 5,LoadImmediate 3 1.0,Addition 3 5 6]

是正确的，它乘以其中4和x，然后将3

来源

2013-11-25 15:42:52 jozefg

e2C _ (Var "x") = LoadImmediate 2 "x"

如果x已经在寄存器2你根本不需要加载它。 Var "x"不会转换为任何加载操作。相反，它转换为2的一些操作数其他操作（加法或乘法）。例如，(Add (Const 25) (Var "x"))将转换为[LoadImmediate 3 25, Addition 1 3 2]。

e2C _ (Mult x y) = Multiply 4 (e2C _ x) (e2C _ y)

这当然是不行的，作为Multiply操作数是寄存器，而不是指令。你必须翻译x并注意注册rx结果如何;然后翻译y并注意到哪个寄存器ry其结果去;确保rx != xy;最后，发出Multiply rz rx ry。

现在，如何确定rz以及如何确定rx != ry？一个简单的策略是确保每个结果到达它自己的寄存器（假设它们的数量是无限的，当然这对于真正的机器体系结构来说不是这样）。

顶层结果将进入寄存器1.

来源

2013-11-25 15:46:57

Haskell：将表达式转换为指令列表

回答

相关问题