Привет!
В этой статье мы рассмотрим, как сделать своими руками (недо)интерпретатор на Haskell.
Заинтересовавшихся прошу под кат!
Однажды мне пришла мысль написать свой интерпретатор, причем обязательно на Haskell. Писать его с нуля — занятие не для слабых духом, да и зачем, если для этого уже все написано другими, (возможно) более опытными людьми!
Шаг 1: формулировка ТЗ самим себе
Наш (недо)интерпретатор будет работать так:
let a = 2 in a*2
4
let a = 8 in (let b = a - 1 in a*b)
56
Только let-in, только Int, из операций: сложение, вычитание, умножение, деление (целочисленное). Поехали!
Шаг 2: alex
Первое, что нам нужно — лексер (программа, которая будет делить код на частички — токены). Те, кто писал свои трансляторы на великом и могучем C, наверное, вспомнили про flex — великий и могучий генератор лексеров. Мы будем использовать не менее великий и могучий alex — тоже генератор лексеров, но для Haskell. Скачиваем alex отсюда или
$ 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)
}
Страшновато.
На самом деле, все просто. Сначала мы объявляем модуль Lex (код в фигурных скобках — чистый Haskell), затем говорим, что хотим использовать basic wrapper, т. е. без всяких наворотов — дешево и сердито, дальше идут определения наборов символов (charsets) — имя charset'а должно начинаться с $, значение — (почти) регулярное выражение. $digit — это все цифры, $alpha — все буквы. Теперь самое главное — токены. после :- должны идти их определения, слева регулярное выражение, справа токен. Пробелы мы игнорируем (слева charset для пробельных символов, справа точка с запятой), let — это токен TLet, in — TIn, одна или более цифр — TNum, всякие плюсы-минусы — TSym, буквы, подчерки и ' — TVar. Дальше мы видим, что все страшные слова на букву T — это значения типа Token — ничего сложного.
Теперь настало время магии.
Сохраняем файл как Lex.x, затем
$ alex Lex.x
Готово! Унас есть модуль нашего лексера — Lex.hs!
Шаг 3: happy
Теперь нам нужен генератор парсеров — happy. Его аналоги для C — это bison и yacc. Качаем его отсюда или
$ sudo apt-get install happy
Создаем файл Synt.y
{
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)
}
Еще страшней.
Здесь тоже код на Haskell берется в фигурные скобки, так что сначала мы объявляем модуль Synt, затем импортируем Lex (нам нужен тип Token оттуда). "%name synt" значит, то наша функция-парсер будет называться synt, "%tokentype { Token }" — что мы используем тип Token в качестве типа токенов никогда бы не догадался, "%error { parseError }" задает функцию, которая будет обрабатывать ошибки. Далее идут соответствия токенов их псевдонимам. А вот сейчас будет страшно. Мы говорим, что выражение (Exp) — это let переменная = выражение in выражение или подвыражение (Exp1). В первом случае нужно создать конструкцию Let (ее тип — Exp, см. объявление ниже), а в качестве аргументов взять второе, четвертое, и шестое слова (т. е. var, Exp и Exp), а во втором случае создать конструкцию Exp1 с первым словом в качестве аргумента. Exp1 же может быть операцией сложения или вычитания с первым и третьим словами в качестве аргументов или Term'ом. Term устроен аналогично, но для операций сложения и умножения. Читатель спросит: «Зачем разбивать на два типа, неужели нельзя запихнуть умножение и деление в Exp1?» Дело в том, что работа парсера заключается в том, чтобы построить так называемое «дерево парсинга». Самые глубоко вложенные операции выполняются первыми. Term у нас будет глубже, чем Exp1, а значит операции умножения выполнятся раньше, чем сложения! Factor, в свою очередь, может быть числом, переменной или выражением в скобках — опять же для порядка действий. Далее мы объявлем функцию parseError для «обработки» ошибок и все типы данных вроде Exp или Factor.
Все, парсер готов!
$ happy Synt.y
Теперь у нас есть файл Synt.hs
Последний рывок: интерпретатор
Код интерпретатора представлен ниже:
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
Здесь мы объявляем тип Context, который содержит ассоциотивный массив (Map) с именами переменных и их значениями, функцию pull, которая возвращает значение переменной, если оно есть, иначе поднимает ошибку. Функция createContext просто создает пустой контекст, getValue ищет значение переменной в контексте. Теперь самое интересное! Чтобы понять, что здесь происходит, представим, что строчка нашего кода такова:
8
Тогда дерево парсинга будет таково:
let res = Exp (Exp1 (Term (Num 8)))
а результат (т. е. 8) будет после
((solveFactor ctx) <- (solveTerm ctx) <- (solveExp1 ctx) <- (solveExp ctx)) res
Это не код на Haskell, а схема: solveExp передаст res solveExp1 и т. д.
ctx здесь — это просто некий контекст.
Т. е. работа функции solveExp заключается в том, чтобы если ей на вход идет конструкция let-in добавить переменную в контекст и вычислить Exp после in, иначе просто вычислить Exp1.
Функция solveExp1 складывает или вычитает, solveTerm — умножает и делит. solveFactor достает значения переменных, возвращает числа, а если ей на вход идет Exp в скобках — передает его solveExp (не опять а снова).
Функция main берет с stdin строки до EOF, разбивает их на список строк, выделяет в каждой токены (alexScanTokens), прогоняет через парсер (synt), вычисляет значение выражения (solveExp) с пустым контекстом (createContext), и делает из Maybe Int Int, а затем String, после чего выводит результат.
Все! Теперь точно все! Компилируем все, и наш интерпретатор готов! Отзывы, замечания, предложения — прошу в комментарии.
Автор: s2002kir
