haskell - 在 Haskell 中创建解释器

Question

因此，我需要编写一个函数 evalS::Statement -> Store -> Store ，它将语句和存储作为输入，并返回可能修改的存储。

我收到了以下案例:

evalS w@(While e s1) s = case (evalE e s) of
                          (BoolVal True,s')  -> let s'' = evalS s1 s' in evalS w s''
                          (BoolVal False,s') -> s'
                          _                  -> error "Condition must be a BoolVal 

我需要写:

evalS Skip s             = ...
evalS (Expr e) s         = ...
evalS (Sequence s1 s2) s = ...
evalS (If e s1 s2) s     = ...

在 If 情况下，如果 e 计算结果为非 bool 值，我需要使用错误函数抛出错误。

示例输入/输出:

> run stmtParser "x=1+1" evalS
fromList [("x",2)]
> run stmtParser "x = 2; x = x + 3" evalS
fromList [("x",5)]
> run stmtParser "if true then x = 1 else x = 2 end" evalS
fromList [("x",1)]
> run stmtParser "x=2; y=x + 3; if y < 4 then z = true else z = false end" evalS
fromList [("x",2),("y",5),("z",false)]
> run stmtParser "x = 1; while x < 3 do x = x + 1 end" evalS
fromList [("x",3)]
> run stmtParser "x = 1 ; y = 1; while x < 5 do x = x + 1 ; y = y * x end" evalS
fromList [("x",5),("y",120)] 

stmtParser 代码:

-- Sequence of statements
stmtParser :: Parser Statement
stmtParser = stmtParser1 `chainl1` (P.semi lexer >> return Sequence)

-- Single statements
stmtParser1 :: Parser Statement
stmtParser1 = (Expr <$> exprParser)
          <|> do
              P.reserved lexer "if"
              cond <- exprParser
              P.reserved lexer "then"
              the <- stmtParser
              P.reserved lexer "else"
              els <- stmtParser
              P.reserved lexer "end"
              return (If cond the els)
          <|> do
              P.reserved lexer "while"
              cond <- exprParser
              P.reserved lexer "do"
              body <- stmtParser
              P.reserved lexer "end"
              return (While cond body)

我尝试过的:

我不确定在这个问题中是否需要使用 evalE。我在之前的问题中已经写过。 evalE 的签名是 evalE::Expression -> Store -> (Value, Store) 并要求我写:

evalE (Var x) s = ...
evalE (Val v) s = ...
evalE (Assignment x e) s = ...

我已经完成了上述操作。

尝试:

evalS Skip s             = show s -- I am assuming that since Skip returns an empty String, I just need to return an empty String.
evalS (Sequence s1 s2) s = evalS s1 >> evalS s2 -- sequence1 then sequence2. I am not quite sure what to do with the s.
evalS (Expr e) s         = ... Not sure what to do, here.
evalS (If e s1 s2) s     = do
   x <- evalE e
   case x of
      BoolVal True -> evalS s1
      BoolVal False -> evalS s2

我在写上述陈述时遇到困难。

作为引用，这是给我使用的整个骨架:

-- Necessary imports
import Control.Applicative ((<$>),liftA,liftA2)
import Data.Map
import Text.Parsec
import Text.Parsec.Expr
import Text.Parsec.Language (emptyDef)
import Text.Parsec.String (Parser)
import qualified Text.Parsec.Token as P


--------- AST Nodes ---------

-- Variables are identified by their name as string
type Variable = String

-- Values are either integers or booleans
data Value = IntVal Int       -- Integer value
           | BoolVal Bool     -- Boolean value

-- Expressions are variables, literal values, unary and binary operations
data Expression = Var Variable                    -- e.g. x
                | Val Value                       -- e.g. 2
                | BinOp Op Expression Expression  -- e.g. x + 3
                | Assignment Variable Expression  -- e.g. x = 3

-- Statements are expressions, conditionals, while loops and sequences
data Statement = Expr Expression                   -- e.g. x = 23
               | If Expression Statement Statement -- if e then s1 else s2 end
               | While Expression Statement        -- while e do s end
               | Sequence Statement Statement      -- s1; s2
               | Skip                              -- no-op

-- All binary operations
data Op = Plus         --  +  :: Int -> Int -> Int
        | Minus        --  -  :: Int -> Int -> Int
        | Times        --  *  :: Int -> Int -> Int
        | GreaterThan  --  >  :: Int -> Int -> Bool
        | Equals       --  == :: Int -> Int -> Bool
        | LessThan     --  <  :: Int -> Int -> Bool

-- The `Store` is an associative map from `Variable` to `Value` representing the memory
type Store = Map Variable Value

--------- Parser ---------

-- The Lexer

lexer = P.makeTokenParser (emptyDef {
  P.identStart = letter,
  P.identLetter = alphaNum,
  P.reservedOpNames = ["+", "-", "*", "!", ">", "=", "==", "<"],
  P.reservedNames = ["true", "false", "if", "in", "then", "else", "while", "end", "to", "do", "for"]
})

-- The Parser

-- Number literals
numberParser :: Parser Value
numberParser = (IntVal . fromIntegral) <$> P.natural lexer

-- Boolean literals
boolParser :: Parser Value
boolParser =  (P.reserved lexer "true" >> return (BoolVal True))
          <|> (P.reserved lexer "false" >> return (BoolVal False))

-- Literals and Variables
valueParser :: Parser Expression
valueParser =  Val <$> (numberParser <|> boolParser)
           <|> Var <$> P.identifier lexer

-- -- Expressions
exprParser :: Parser Expression
exprParser = liftA2 Assignment
                    (try (P.identifier lexer >>= (\v ->
                          P.reservedOp lexer "=" >> return v)))
                    exprParser
          <|> buildExpressionParser table valueParser
    where table = [[Infix (op "*" (BinOp Times)) AssocLeft]
                  ,[Infix (op "+" (BinOp Plus)) AssocLeft]
                  ,[Infix (op "-" (BinOp Minus)) AssocLeft]
                  ,[Infix (op ">" (BinOp GreaterThan)) AssocLeft]
                  ,[Infix (op "==" (BinOp Equals)) AssocLeft]
                  ,[Infix (op "<" (BinOp LessThan)) AssocLeft]]
          op name node = (P.reservedOp lexer name) >> return node

-- Sequence of statements
stmtParser :: Parser Statement
stmtParser = stmtParser1 `chainl1` (P.semi lexer >> return Sequence)

-- Single statements
stmtParser1 :: Parser Statement
stmtParser1 = (Expr <$> exprParser)
          <|> do
              P.reserved lexer "if"
              cond <- exprParser
              P.reserved lexer "then"
              the <- stmtParser
              P.reserved lexer "else"
              els <- stmtParser
              P.reserved lexer "end"
              return (If cond the els)
          <|> do
              P.reserved lexer "while"
              cond <- exprParser
              P.reserved lexer "do"
              body <- stmtParser
              P.reserved lexer "end"
              return (While cond body)

-------- Helper functions --------

-- Lift primitive operations on IntVal and BoolVal values
liftIII :: (Int -> Int -> Int) -> Value -> Value -> Value
liftIII f (IntVal x) (IntVal y) = IntVal $ f x y
liftIIB :: (Int -> Int -> Bool) -> Value -> Value -> Value
liftIIB f (IntVal x) (IntVal y) = BoolVal $ f x y

-- Apply the correct primitive operator for the given Op value
applyOp :: Op -> Value -> Value -> Value
applyOp Plus        = liftIII (+)
applyOp Minus       = liftIII (-)
applyOp Times       = liftIII (*)
applyOp GreaterThan = liftIIB (>)
applyOp Equals      = liftIIB (==)
applyOp LessThan    = liftIIB (<)

-- Parse and print (pp) the given WHILE programs
pp :: String -> IO ()
pp input = case (parse stmtParser "" input) of
    Left err -> print err
    Right x  -> print x

-- Parse and run the given WHILE programs
run :: (Show v) => (Parser n) -> String -> (n -> Store -> v) -> IO ()
run parser input eval = case (parse parser "" input) of
    Left err -> print err
    Right x  -> print (eval x empty)

Answer 1

回答你的问题有点困难，因为你实际上并没有问过这个问题。让我摘录一下你所说的一些内容，以便给你一些线索。

I am not sure if I need to use evalE in this problem or not. I have written it in a previous problem. The signature for evalE is evalE :: Expression -> Store -> (Value, Store)

evalS (Expr e) s = ... Not sure what to do, here.

执行由表达式组成的语句是什么意思？如果它与评估表达式有关，那么您有一个可用的表达式评估器这一事实可能有助于“在这里做什么”。

接下来，比较您为“while”提供的代码(顺便说一句，其中包含一个与表达式相关的合理示例)...

evalS w@(While e s1) s = case (evalE e s) of`
  (BoolVal True,s')  -> let s'' = evalS s1 s' in evalS w s''
  (BoolVal False,s') -> s'
  _                  -> error "Condition must be a BoolVal"

...并将其与“if”代码进行比较

evalS (If e s1 s2) s     = do
   x <- evalE e
   case x of
      BoolVal True -> evalS s1
      BoolVal False -> evalS s2

你的代码采用了一种相当不同的风格——“monadic”风格。你从哪里得到的？如果评估者的类型类似于

evalE :: Expression -> State Store Value
evalS :: Statement  -> State Store ()

一元风格是一种非常好的方式，可以让变异存储通过评估过程，而无需过多讨论。例如，您的x <- evalE e意思是“让 x 成为评估 e 的结果(安静地接收初始存储并传递结果存储)”。这是一种很好的工作方式，我希望您能在适当的时候进行探索。

但这些不是您所获得的类型，并且单子(monad)样式也不合适。你有

evalE :: Expression -> Store -> (Value, Store)
evalS :: Statement  -> Store ->         Store

并且示例代码显式地线程化存储。再看一遍

evalS w@(While e s1) s = case (evalE e s) of`
  (BoolVal True,s')  -> let s'' = evalS s1 s' in evalS w s''
  (BoolVal False,s') -> s'
  _                  -> error "Condition must be a BoolVal"

看到了吗？ evalS收到其初始存储，s ，显式地，并在 evalE e s 中显式地使用它。由此产生的新商店名为 s'两者皆 case分支机构。如果循环结束，则s'作为最终商店归还。否则，s'用作循环体一次传递的存储，s1 ，以及商店s''由此产生的结果将用于下一次循环， w .

您的代码在每个评估阶段的命名和使用存储的方式也需要同样明确。让我们来看看。

evalS Skip s             = show s -- I am assuming that since Skip returns an empty String, I just need to return an empty String.

你的假设是错误的。 evalS函数不返回 String 、空或其他:它返回 Store 。现在，哪个Store ？您的初始商店是s :“跳过”后的商店将如何与s相关？

evalS (Sequence s1 s2) s = evalS s1 >> evalS s2 -- sequence1 then sequence2. I am not quite sure what to do with the s.

同样，这是一种不适合这个问题的单一方法。您需要首先对商店进行线程 s ，通过评估语句s1的过程和s2按顺序。 “while”案例有一个很好的例子来说明如何做类似的事情。

evalS (Expr e) s         = ... Not sure what to do, here.

“while”示例再次向您展示了一种通过计算表达式来提取值和更新存储的方法。值得深思，不是吗？

evalS (If e s1 s2) s     = ...

现在“if”从评估条件开始，很像“while”，不是吗？

所以，我的建议如下:

• 暂时放弃一元样式代码，但稍后在适当的时候再回来使用它；
• 阅读“while”的示例实现，了解它如何处理表达式和语句序列，并显式传递存储；
• 部署类似的技术来实现其他构造。

提出问题的人很友善地为您提供了代码，其中给出了您需要的一切的示例。请通过理解并接受提示来返回这种善意!