Haskell - Happy, math expressions and variables parser

Question

I'm working on a Happy math expressions and variables parser. The problem is that I don't know how to save the value for a variable and use it later. Any ideas?

This is how I recognize expressions and variables assignment:

genExp   : exp                    { $1 }
         | variable '=' exp            { //here I want to save the value of the variable; something like this: insert variables $1 $3, where 'variables' is a Data.Map }

A expression can contain a variable. For example:

a = 2 + 1
a + 2 (now the parser must print 5)

I need to save the value of the variable 'a' when the parser is parsing the line 'a = 2 + 1' and to get the value of the variable 'a' when the parser is parsing the line 'a + 2'

Answer 1

What you want to do is to keep track of the value of variables during evaluation of expressions, not during parsing. Let's assume you parse your expressions into the following types:

data Expr = Literal Int | Variable Var | Assign Var Expr | Add Expr Expr | ...
newtype Var = Var String deriving (Ord, Eq, Show)

Then you could simply pass a Map around your evaluation function with the current value of all variables:

import qualified Data.Map as M
import Control.Monad.State

data Expr = Literal Int | Variable Var | Assign Var Expr | Add Expr Expr
newtype Var = Var String deriving (Ord, Eq, Show)

-- Each Expr corresponds to a single line in your language, so
-- a = 2+1
-- a + 2
-- corresponds to
-- [Assign (Var "a") (Add (Literal 2) (Literal 1)),
--  Add (Variable (Var "a")) (Literal 2)]
eval :: [Expr] -> Int
eval es = last $ evalState (mapM eval' es) M.empty -- M.empty :: M.Map Var Int
  where
    eval' (Literal n)  = return n
    eval' (Variable v) = do
      vs <- get
      case M.lookup v vs of
        Just x -> return x
        _      -> error $ "variable " ++ show v ++ " is undefined!"
    eval' (Assign v ex) = do
      x <- eval' ex
      modify (M.insert v x)
      return x
    eval' (Add a b) = do
      x <- eval' a
      y <- eval' b
      return (x+y)

Of course, there's nothing to prevent you from evaluating expressions as you parse them, eliminating the need for an abstract syntax tree such as this. The general idea is the same there; you'll need to keep some state with you during the entire parsing, that keeps track of the current value of all your variables.