Пишем (недо)интерпретатор на Haskell с помощью alex и happy +9


Привет, Хабр! В этой статье мы рассмотрим, как сделать своими руками (недо)интерпретатор на 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, после чего выводит результат.

Все! Теперь точно все! Компилируем все, и наш интерпретатор готов! Отзывы, замечания, предложения — прошу в комментарии.




К сожалению, не доступен сервер mySQL