[Haskell] Пишем интерпретатор простого языка

 
0
 
Functional languages
ava
Sardar | 08.05.2009, 02:06
Началось (и закончилось) это всё как лаба по Vertallerbouw (построение компилеров), сдана, доцент в восторге. Это уже вторая моя прога более 20 строк на Haskell, из которой можно почерпнуть базовые приёмы.

Код не блещет, можно лучше. Отсылать буду частями, комментируя отдельные участки. Постараюсь разжевать подробно, пусть это и вызовет приторно сладкий привкус у знатоков, но для начинающих думаю будет полезно. Убедительная просьба писать замечания/улучшения после того как закончу.

И так: Simply

Simply это простой функциональный язык программирования со следующими свойствами:
  •  Динамические типы -- это скорее недостаток  smile   Но если вводить строгие типы + декомпозицию (patterns), то недалеко и до Haskell.
  •  Ленивые вычисления -- конечно используя Haskell мы их получаем "в подарок", но интереса ради они были реализованы явно. Пока не будем думать о эффективности.
  •  Higher order functions или всё это функция.
  •  Традиционные для функциональных языков partial function application, т.е. передача не всех параметров функции, порождая новую функцию.
  •  Static scoping, видимость функциями значений в своём (lexical) scope.
Simply работает только с целыми и действительными числами, а также с логическими значениями (true, false). Списков, строк и т.п. нет в целях простоты. Без структурной декомпозиции (голова:хвост) пробежаться по списку нельзя, а вводить "магические" built-in функции способные пробегаться по спискам как то не красиво.

Пример кода (чрезвычайно надуманный  smile ):

-- сумма аргументов
LET sum(a, b) = a + b;
-- по сути тоже сумма
LET inc(v, s:1) = v + s;

-- inc это lambda(v, s:1)
-- sum(inc, 4) -- это тоже lambda(v, s:1), почему так, узнаем позже
-- sum(inc, 4)(5) -- это lambda(v:5, s:1)
-- так как консоль пытается напечатать значение, она потребует выполнения кода,
-- а раз все параметры даны, то вычисление окончиться в 10.
return sum(inc, 4)(5);


Первое что бросается в глаза это вычисления с функциями, такие как (sum + sum) приведёт к lambda(a, b, c, d). Оба операнда являются функциями с двумя аргументами, значит результат это новая функция, где (a, b) это аргументы первого операнда, а (c, d) аргументы второго. Вообще это удобно, хотелось бы видеть где нибудь в PHP :)

Вызов функции выполняется через оператор ( arguments ), который на самом деле просто присваивает значения параметрам функции, что не приведёт к её немедленному исполнению. Только когда потребуется окончательное значение (например что бы напечатать на консоль), интерпретатор проверит для всех ли аргументов есть значение. Если да, то функция выполнится, иначе результат это функция (выводиться как "lambda(параметры)" ).

Видим что структура проги есть список LET определений, завершаемых одним return expression, который и скомбинирует все функции в некоторое окончательное значение. В языке всего две конструкции: if-else и with. Первое это условие, возвращающее значение одной из веток. Второе это подпрограмма (scoping), аналогичное выражениям let something in expression встречаемое в других функциональных языках. Подробнее об этом при рассмотрении формальной грамматики.

С языком определились, приступаем к формальной грамматике.


Comments (4)
ava
Sardar | 08.05.2009, 01:40 #
Для генерации parser'а воспользуемся parser generator'ом Happy. Этот генератор создаёт LALR(1) парсер, реализованный как recursive descent parser. Что это значит лучше почитать где нибудь в другом месте, просто запомним, что для грамматики Simply LALR(1) парсера с головой хватит. А вот то, что реализован он на функциях (recursive descent parser), потенциально может привести к переполнению стека. Именно по этому мы будем писать лево-рекурсивные правила грамматики, везде где только можно. При левой рекурсии стек не используется.

Синтаксис файла грамматики Happy почти идентичен yacc'у, так что всё будет знакомо. Всё что между { } как есть отсылается в код парсера. Там мы определяем все import'ы и название модуля. Далее декларируем "точки входа", это стартовые не-терминалы вместе с генерируемой функцией. В нашем случае их две, одна читает весь файл целиком, другая только выражения (используется позже shell'ом).


{-----------------------------------------------------------------------------
  Formal grammar of Simply programming language.

  Author: Sardar  ([email protected])
-----------------------------------------------------------------------------}

{
module SimplyParser (parseProgram, parseShell) where
import ParseMonad   -- gives all necessary type defs
import Lexer              -- lexer definition
import AbsSynTree    -- represents abstract syntax tree
}

-- parse whole program
%name parseProgram      Program

-- parse expression only
%name parseShell  ShellProgram


Мы хотим видеть нормальные ошибки, указывающие на строку и колонку, а не вылетать с убийственным (error "сообщение"). Для этого нужно скрыть как правильный результат, так и ошибки в один тип, иными словами пишем монад. В нашем монаде будет скрыта инфа о позиции в файле и собственно строка на ввод. Подробнее об этом позже, сейчас просто скажем Happy, что все actions в грамматике возвращают значение скрытое в монаде P.


-- monadic parser, this monad keeps parse result, line numbers etc
%monad { P }

-- monadic lexer, allows reading tokens one by one until TokenEOF
%lexer { lexer } { TokenEOF }

-- when parse error is detected, this funciton will be called with current look-ahead token.
%error { parseError }


Сканер (lexer) тоже монадный, что позволяет нам "скрыть" ввод. Тип функции lexer будет:
 lexer :: (Token -> P a) -> P a 

Т.е. функция принимает принимает другую функцию (передаваемую парсером), что примет следующий токен и рекурсивно вызовет lexer для следующего токена. Вся информация (текст, текущая позиция, файл etc) скрыты в монаде P, как и специальное ошибочное значение.

Далее декларируем все токены, что могут появится на входе в парсер:

-- token 'stream' produced by the lexer.
%tokentype  { Token }

-- All tokens produced by the lexer.
%token
    return  { TokenReturn $$ }
    ';'     { TokenSeparator $$ }
    let     { TokenLet $$ }
    '('     { TokenROpen $$ }
    ','     { TokenComma $$ }
    ')'     { TokenRClose $$ }
    ':'     { TokenWithDefValue $$ }
    '='     { TokenSet $$ }
-- math
    '+'     { TokenAdd $$ }
    '-'     { TokenSub $$ }
    '*'     { TokenMul $$ }
    '/'     { TokenRDiv $$ }
    '\\'    { TokenIDiv $$ }
    '%'     { TokenMod $$ }
    '^'     { TokenPower $$ }
-- comparison
    '<'     { TokenLT $$ }
    '>'     { TokenGT $$ }
    '<='    { TokenLEq $$ }
    '>='    { TokenGEq $$ }
    '=='    { TokenEq $$ }
    '!='    { TokoenNEq $$ }
-- boolean
    '&&'    { TokenAnd $$ }
    '||'    { TokenOr $$ }
    '^^'    { TokenXor $$ }
    '!'     { TokenNot $$ }
-- special expressions
    if      { TokenIf $$ }
    then    { TokenThen $$ }
    else    { TokenElse $$ }
    with    { TokenWith $$ }
-- values
    int     { TokenInteger $$ }
    real    { TokenReal $$ }
    boolean { TokenBoolean $$ }
    sym     { TokenSymbol $$ }


Видим их много smile   Первой строкой декларируем тип токенов, мы его уже видели в типе функции lexer. Далее идут все конструкторы, что бы распознать значение. Специальное значение $$ указывает на то, что конструктор принимает одно значение и его нужно использовать как значение токена (об этом позже). Без $$ значением токена будет он сам. Мы передаём в каждом токене его позицию в исходном файле для более подробных сообщениях об ошибках.

На этом месте лучше прерваться с определением формальной грамматики и стоит перейти к lexer'у, что будет зачитывать выше названные токены.
ava
Sardar | 08.05.2009, 02:05 #
Сканнер традиционно пишется на регулярных выражениях. В Haskell 98 нет регулярных выражений, но они есть в regexp библиотеке, поставляемой вместе с GHC.

В целях обучения Haskell'у мы не будем выходить за пределы Haskell 98 и попытаемся реализовать сканнер в ручную. Это простая задача, небольшие сложности возникнут только при чтении действительных чисел, которые в самом сложном варианте могут быть "45.23Е-3".

Перед тем как приступить к lexer'у стоит взглянуть на упоминавшийся ранее монад P, т.к. именно в него мы всё и завернём.


module ParseMonad where

-- Resulting expression
data ParseResult a = ParseOK { parseValue::a } | ParseFail String deriving Show

-- Used to track the source position for error reporting
data LinePos = Pos { line::Int, column::Int, file::String } deriving Show

-- Monadic (threaded lexer/parser)
newtype P a = P { runP::(String -> LinePos -> ParseResult a) }


ParseResult заворачивает результат парсера в два возможных значения: собственно прочтённая и построенная прога или ошибка. Наследуем от Show для дебагга, удобно выводить в Hugs результат.

Монад P определён всего единственным конструктором, скрывающим строку ввода, текущую позицию и результат парсера. Конечно монадом новый тип станет только после создания instance.


-- Standard monadic operators
instance Monad P where
    -- bind value
    return m = P $ \ _ _ -> ParseOK m
    
    -- then operator, pass through failure, otherwise evaluate/fetch exp'ression and pass to cont'inuation
    exp >>= cont =  P $ \src pos -> case runP exp src pos of
                                        -- exp successfull, pass value through to continuation
                                        ParseOK a -> runP (cont a) src pos   -- :: ParseResult a
                                        -- bubble up error
                                        ParseFail s -> ParseFail s

    -- raise error, ignore anything, result in parse fail
    fail msg = P $ \ _ _ -> ParseFail msg


Всё, теперь доступны returnfail и do выражения, жизнь становится проще :)

Для полноты картины реализуем дополнительные функции, что будут помогать изменять позицию в момент чтения.

-- Advance column iterator
nextCol (Pos line col file) = Pos line (col + 1) file

-- Advance column iterator by N
skipCol n (Pos line col file) = Pos line (col + n) file

-- Advance line iterator, reset column iterator
nextLine (Pos line col file) = Pos (line + 1) 0 file

-- Print file and position, used by error reports
printPos (Pos line col file) = file ++ ": line " ++ (show line) ++ " at " ++ (show col)

-- Print position without file name
printShortPos (Pos line col file) = "line " ++ (show line) ++ " at " ++ (show col)

-- Create (1, 0) position for given file
startPos file = Pos 1 0 file


nextCol мы будем далее вызывать в сканнере при чтении каждого следующего символа, nextLine при чтении '\n'. Остальные функции печатают текущую позицию как строку, используемую при выводе ошибок. startPos позволяет нам создать позицию в самом начале заданного файла.

Всё, теперь приступим к самому сканнеру.
ava
Void | 11.05.2009, 11:17 #
Когда продолжение? На самом интересном месте остановился smile
(потом этот пост удалю)
ava
Бонифаций | 22.05.2009, 13:05 #
Цитата


Этот генератор создаёт LALR(1) парсер, реализованный как recursive descent parser



это вы что-то напутали. Лучше уберите.. LALR - look ahead LR парсер, то есть он явно не рекурсивный и явно не нисходящий (descent).. Он как бы наоборот,  как все LR() - восходящий.

 
Цитата


Сканнер традиционно пишется на регулярных выражениях.



Это неправда.. Он как правило пишется на конечном автомате. Потому что регулярки получаются гораздо медленнее, и их используют только в простых сканерах.. Или где скорость неважна вообще..

Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
advanced
Submit