3

我正在尝试用 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 }

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

4

1 回答 1

8

您与解析器非常接近。但是您要构建的是一个与解析逻辑分开的小表达式语言的解释器。解析器只会为程序生成 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 }

For the interpreter we'll use a StateT + IO monad to hold the assigned variables and invoke Haskell's print function for each Print function in our program. The state monad will hold an association list of variables to values. Assign will simply add a new reference to the list, and a Var reference will use the lookup function over the state.

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) []

And that's about it.

于 2015-01-15T06:50:00.893 回答