Привет, Хабр! В этой статье мы рассмотрим, как сделать свой (не)интерпретатор на Haskell. Если вам интересно, пожалуйста, следите за разрезом! Однажды мне пришла в голову идея написать свой интерпретатор, и обязательно на Хаскеле.
Написание его с нуля – занятие не для слабонервных, да и зачем, если все для этого уже написано другими, (возможно) более опытными людьми!
Шаг 1: формулирование технического задания самому себе
Наш (не)интерпретатор будет работать следующим образом:Только впускной, только Int, из операций: сложение, вычитание, умножение, деление (целое).let a = 2 in a*2 4 let a = 8 in (let b = a - 1 in a*b) 56
Идти!
Шаг 2: Алекс
Первое, что нам понадобится — это лексер (программа, которая будет разбивать код на частицы — токены).Те, кто писал свои трансляторы на великом и могучем C, наверняка помнили flex — великий и могучий генератор лексеров.
Мы будем использовать не менее великий и мощный alex — тоже лексер-генератор, но для Haskell. Скачать Алекс отсюда или $ 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), потом говорим, что хотим использовать базовую обертку, то есть без всяких наворотов - дешево и сердито, потом приходим с определениями наборов символов (charsets) — имя набора символов должно начинаться с $, значение — (почти) регулярное выражение.
$digit — это все цифры, $alpha — все буквы.
Теперь самое главное — жетоны.
после :- должны быть их определения, слева регулярное выражение, справа токен.
Пробелы игнорируем (слева кодировка для пробелов, справа точка с запятой), let — токен TLet, in — TIn, одна или несколько цифр — TNum, всякие плюсы и минусы — TSym, буквы, подчеркивания и ' — это TVar. Далее мы видим, что все страшные слова, начинающиеся на букву Т, являются значениями типа Токен — ничего сложного.
Теперь пришло время волшебства.
Сохраните файл как Lex.x, затем $ alex Lex.x
Готовый! У нас есть модуль лексера — Lex.hs!
Шаг 3: Счастлив
Теперь нам нужен генератор парсера — доволен.
Его аналогами на языке 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) — это пусть переменная = выражение в выражении или подвыражении (Exp1).
В первом случае нужно создать конструкцию Let (ее тип — Exp, см.
объявление ниже) и взять в качестве аргументов второе, четвертое и шестое слова (т.е.
var, Exp и Exp), а во втором случае , создайте конструкцию Exp1 с первым словом в качестве аргумента.
Exp1 может быть операцией сложения или вычитания с первым и третьим словами в качестве аргументов или термина.
Термин устроен аналогично, но для операций сложения и умножения.
Читатель спросит: «Зачем делить его на два типа? Неужели нельзя запихнуть умножение и деление в Exp1Э» Дело в том, что работа парсера заключается в построении так называемого «дерева разбора».
Сначала выполняются наиболее глубоко вложенные операции.
Наш Term будет глубже, чем Exp1, а это значит, что операции умножения будут выполняться перед сложением! Фактор, в свою очередь, может быть числом, переменной или выражением в круглых скобках — опять же для порядка операций.
Далее мы объявим функцию 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) с именами переменных и их значениями, функцию извлечения, которая возвращает значение переменной, если она существует, в противном случае она выдает ошибку.
Функция createContext просто создает пустой контекст, getValue ищет значение переменной в контексте.
Теперь самое интересное! Чтобы понять, что здесь происходит, давайте представим, что наша строка кода такая: 8
Тогда дерево разбора будет таким: let res = Exp (Exp1 (Term (Num 8)))
и результат (т.е.
8) будет после ((solveFactor ctx) <- (solveTerm ctx) <- (solveExp1 ctx) <- (solveExp ctx)) res
Это не код на Haskell, а диаграмма:solveExp передаст ressolveExp1 и т.д.
ctx здесь лишь некоторый контекст.
То есть работа функцииsolveExp заключается в том, чтобы, если она получает на вход конструкцию let-in, добавить переменную в контекст и вычислить Exp после in, в противном случае просто вычислить Exp1.
ФункцияsolveExp1 складывает или вычитает, аsolveTerm умножает и делит. solveFactor извлекает значения переменных, возвращает числа и, если на его входе Exp в скобках, он передает их вsolveExp (не снова, а снова).
Основная функция принимает строки из стандартного ввода в EOF, разбивает их на список строк, выделяет в каждой токены (alexScanTokens), пропускает их через парсер (synt), вычисляет значение выражения (solveExp) с пустым контекстом (createContext ) и превращает Maybe Int в Int. а затем String, после чего печатает результат. Все! Вот и все! Давайте все скомпилируем, и наш интерпретатор готов! Отзывы, комментарии, предложения - оставляйте комментарии.
Теги: #haskell #alex #happy #haskell
-
Измерение Качества Поиска В Mail
19 Oct, 24 -
Дебиану 15 Лет!
19 Oct, 24 -
Как Я Писал В Scad. Часть Четвертая
19 Oct, 24 -
Первый Жесткий Диск Емкостью 1,5 Тб
19 Oct, 24 -
Дайджест It-Событий За Декабрь
19 Oct, 24
