Haskell Happy 实现分配给变量

Question

我正在尝试使用 x = 4 和 pritn x 实现一些语言，使用 haskell 构建快乐到目前为止，我已经定义了这样的语法

 terms 
    : term                   { [$1] }
    | term terms             { $1 : $2 }

 term 
    : var '=' int             { Assign $1 $3 }
    | print var               { Print $2 }

当我在类似的东西上运行它时

x = 4
print x
y = 5
print y

我明白了

[Assign "x" 4, Print "x", Assign "y" 5, Print "y"]

现在我想做实际的实现，但我不知道如何实现“分配”

虽然我不擅长haskell，但我从快乐的文档中看到了“让”实现，并得到了一些环境p的想法，并在其中进行了评估

Exp   : let var '=' Exp in Exp  { \p -> $6 (($2,$4 p):p) }
  | Exp1                    { $1 }

Exp1  : Exp1 '+' Term           { \p -> $1 p + $3 p }
  | Exp1 '-' Term           { \p -> $1 p - $3 p }
  | Term                    { $1 }

Term  : Term '*' Factor         { \p -> $1 p * $3 p }
  | Term '/' Factor         { \p -> $1 p `div` $3 p }
  | Factor                  { $1 }

Factor            
  : int                     { \p -> $1 }
  | var                     { \p -> case lookup $1 p of
                                    Nothing -> error "no var"
                    Just i  -> i }
  | '(' Exp ')'             { $2 }

我猜“分配”实现必须对这个环境做一些事情，但我找不到任何例子。如何实现分配和打印，或者在哪里可以找到相关信息或示例？

Answer 1

您与解析器非常接近。但是您想要构建的是一个解释器，用于独立于解析逻辑的小表达式语言。解析器只会为程序生成 AST，然后我们将分别对其进行评估。

代码实际上很小，但它被分成几个模块，所以我把它放在这个要点中:https://gist.github.com/sdiehl/c2dd1880e0ec6b65a120

我猜你的 AST 看起来像这样:

data Expr
  = Var String
  | Num Int
  | Print Expr
  | Assign String Int
  deriving (Eq,Show)

解析器看起来不错，但我认为您需要添加一个 var 产生式，这样 print x 和 print 1 等表达式都可以语法格式正确。

%token
    int   { TokenNum $$ }
    var   { TokenSym $$ }
    print { TokenPrint }
    '='   { TokenEq }

%%

terms 
    : term                   { [$1] }
    | term terms             { $1 : $2 }

term 
   : var                     { Var $1 }
   | var '=' int             { Assign $1 $3 }
   | print term              { Print $2 }

对于解释器，我们将使用 StateT + IO monad 来保存分配的变量，并为程序中的每个 Print 函数调用 Haskell 的 print 函数。 state monad 将保存一个变量与值的关联列表。 Assign 将简单地向列表添加一个新引用，而 Var 引用将使用 lookup 函数覆盖状态。

data Value
  = VInt Int
  | VUnit

instance Show Value where
  show (VInt x) = show x

type Eval = StateT Env IO
type Env = [(String, Value)]

eval1 :: Expr -> Eval Value
eval1 expr = case expr of
  Num a -> return (VInt a)
  Var a -> do
    env <- get
    case lookup a env of
      Just val -> return val
      Nothing -> error "Not in scope"
  Print a -> do
    a' <- eval1 a
    liftIO $ print a'
    return VUnit
  Assign ref val -> do
    modify $ \s -> (ref, VInt val) : s
    return VUnit

eval :: [Expr] -> IO ()
eval xs = evalStateT (mapM_ eval1 xs) []

就是这样。