Привет, Хабр! В этой статье мы рассмотрим, как сделать своими руками (недо)интерпретатор на Haskell. Заинтересовавшихся прошу под кат!
Однажды мне пришла мысль написать свой интерпретатор, причем обязательно на Haskell. Писать его с нуля — занятие не для слабых духом, да и зачем, если для этого уже все написано другими, (возможно) более опытными людьми!
let a = 2 in a*2
4
let a = 8 in (let b = a - 1 in a*b)
56
$ sudo apt-get install alex
{
module Lex where
}
%wrapper "basic"
$digit = 0-9
$alpha = [a-zA-Z]
tokens :-
$white ;
let { \s -> TLet }
in { \s -> TIn }
$digit+ { \s -> TNum (read s)}
[\=\+\-\*\/\(\)] { \s -> TSym (head s)}
$alpha [$alpha $digit \_ \']* { \s -> TVar s}
{
data Token = TLet | TIn | TNum Int | TSym Char | TVar String deriving (Eq, Show)
}
$ alex Lex.x
$ sudo apt-get install happy
{
module Synt where
import Lex
}
%name synt
%tokentype { Token }
%error { parseError }
%token
let { TLet }
in { TIn }
num { TNum $$ }
var { TVar $$ }
'=' { TSym '=' }
'+' { TSym '+' }
'-' { TSym '-' }
'*' { TSym '*' }
'/' { TSym '/' }
'(' { TSym '(' }
')' { TSym ')' }
%%
Exp:
let var '=' Exp in Exp { Let $2 $4 $6 }
| Exp1 { Exp1 $1 }
Exp1:
Exp1 '+' Term { Plus $1 $3 }
| Exp1 '-' Term { Minus $1 $3 }
| Term { Term $1 }
Term:
Term '*' Factor { Mul $1 $3 }
| Term '/' Factor { Div $1 $3 }
| Factor { Factor $1 }
Factor:
num { Num $1 }
| var { Var $1 }
| '(' Exp ')' { Brack $2 }
{
parseError :: [Token] -> a
parseError _ = error "Parse error"
data Exp = Let String Exp Exp | Exp1 Exp1 deriving (Show)
data Exp1 = Plus Exp1 Term | Minus Exp1 Term | Term Term deriving (Show)
data Term = Mul Term Factor | Div Term Factor | Factor Factor deriving (Show)
data Factor = Num Int | Var String | Brack Exp deriving (Show)
}
$ happy Synt.y
module Main where
import qualified Data.Map as M
import Lex
import Synt
newtype Context = Context {getContext :: M.Map String Int} deriving (Show)
pull :: Maybe a -> a
pull (Just m) = m
pull Nothing = error "Undefined variable"
createContext :: Context
createContext = Context {getContext = M.empty}
getValue :: Context -> String -> Maybe Int
getValue ctx name = M.lookup name $ getContext ctx
solveExp :: Context -> Exp -> Maybe Int
solveExp ctx exp = case exp of (Let name expl rexp) -> solveExp newCtx rexp where newCtx = Context {getContext = M.insert name (pull (solveExp ctx expl)) (getContext ctx)}
(Exp1 exp1) -> solveExp1 ctx exp1
solveExp1 :: Context -> Exp1 -> Maybe Int
solveExp1 ctx exp1 = case exp1 of (Plus lexp1 rterm) -> (+) <$> (solveExp1 ctx lexp1) <*> (solveTerm ctx rterm)
(Minus lexp1 rterm) -> (-) <$> (solveExp1 ctx lexp1) <*> (solveTerm ctx rterm)
(Term term) -> solveTerm ctx term
solveTerm :: Context -> Term -> Maybe Int
solveTerm ctx term = case term of (Mul lterm rfactor) -> (*) <$> (solveTerm ctx lterm) <*> (solveFactor ctx rfactor)
(Div lterm rfactor) -> (div) <$> (solveTerm ctx lterm) <*> (solveFactor ctx rfactor)
(Factor factor) -> solveFactor ctx factor
solveFactor :: Context -> Factor -> Maybe Int
solveFactor ctx factor = case factor of (Num n) -> (Just n)
(Var s) -> getValue ctx s
(Brack exp) -> solveExp ctx exp
main = do
s <- getContents
mapM putStrLn $ (map (show . pull . (solveExp createContext) . synt . alexScanTokens) . lines) s
8
let res = Exp (Exp1 (Term (Num 8)))
((solveFactor ctx) <- (solveTerm ctx) <- (solveExp1 ctx) <- (solveExp ctx)) res
К сожалению, не доступен сервер mySQL