Ivan Veselov (dying_sphynx) wrote,
Ivan Veselov
dying_sphynx

Category:

Haskell: комбинаторные парсеры Parsec.

Что же, в прошлый раз мы вспомнили формы записи операторов и рассмотрели написание простого вычислителя постфиксных выражений на Haskell. Следующим шагом является создание транслятора выражений из инфиксной формы - в префиксную. Однако, перед этим нам необходимо улучшить разбор выражения на токены, поэтому в данной статье мы рассмотрим монадические комбинаторные парсеры на примере модуля Parsec, а также использование их на практике.


Haskell postfix: часть вторая. Комбинаторные парсеры Parsec.


Как мы уже убедились, постфиксная форма предоставляет массу преимуществ, которыми было бы неплохо пользоваться. Хотя в реальной жизни чаще используется инфиксная форма, существуют несложные алгоритмы для преобразования. Наиболее известным их представителем является алгоритм "сортировочная станция", предложенный Дейкстрой. Алгоритм получил своё название из-за сходства его операций с действиями, происходящими на железнодорожных сортировочных станциях. Подробно приводить его здесь я не стану, ибо он хорошо описан в указанной выше статье. Работает алгоритм на основе стека, в процессе работы используется входная и выходная строки, в стеке находятся символы, ещё не выведенные в выходную строку. Из входной строки считывается очередной символ и в зависимости от его типа (оператор, операнд, функция, скобка, запятая и т.д.) производятся определённые действия по манипулированию со стеком и выходной строкой.

Вернёмся к программированию.
Поскольку "сортировочная станция" работает не только с операндами и операторами, но и c функциями со списками аргументов, нам необходимо расширить наше описание токена:
data Token = Atom String | Op String | LParen | RParen | Comma | Func String deriving (Eq, Ord, Show)

Данный типа реализует и скобки, и запятые, и специальный токен функции Func String.

Очевидно, что для проведения парсинга такого рода функции типа parseToken из предыдущей части будет недостаточно, поскольку требуется некий предпросмотр (lookahead) для того, чтобы определить будет ли строка функцией или же простым идентификатором, а также хотелось бы не разделять токены пробелами во входной строке, как это было сделано в предыдущей версии программы.

Что же, для задач подобного рода существует хороший готовый инструмент - монадические парсеры Parsec. Подход, используемый Parsec, вполне естественен для создания рекурсивных парсеров в рамках функционального программирования и базируется на следующих принципах:

1) Каждый парсер представляется в виде некоторой функции.

2) Эта функция принимает на вход некоторую строку, которую надо обработать. Подумаем, что является результатом разбора. Вообще говоря, это может быть почти всё, что угодно - к примеру результатом парсинга строки "23" вполне может быть число 23, результатом разбора строки "2 + 3" может быть некое дерево с корнем (+) и листьями 2 и 3. Поэтому назовём тип результата просто a. Получим следующий тип:
type Parser a = String -> a

где a - параметр типа Parser, показывающий, что именно мы хотим от него получить. Например, парсер целых чисел будет иметь тип Parser Int, а парсер деревьев - Parser Tree.

Однако, парсер может обработать не всю строку, а только её часть и вернуть остаток. К примеру, если мы подадим на вход парсеру целых чисел строку "2s", то он обработает только "2" и должен бы вернуть "s". Поэтому было бы неплохо расширить возвращаемый тип до пары (a, String), получив следующее:
type Parser a = String -> (a, String)

Также парсер может вообще не вернуть результат, то есть не распарсить даже части входной строки, а также может распарсить какую-то строку несколькими способами. Это подводит нас к мысли, что способов разбора может быть от нуля до бесконечности. В следствие этого понимания, мы расширяем тип возвращаемого парсером значения до списка пар, то есть:
type Parser a = String -> [(a, String)] 

Причём возврат пустого списка будет свидетельствовать о неуспешном разборе, а возврат списка с более чем одним элементом - о неоднозначном разборе. Наиболее удачный вариант - возврат в точности одного элемента в списке.

Таким образом мы определились с типом парсеров-функций.

3) Определяются функции высшего порядка (комбинаторы), которые определённым образом сочетают парсеры, позволяя производить такие операции определения грамматик, как последовательное распознавание двух символов грамматики (sequencing), параллельное - то есть выбор из двух альтернатив (choice) или же более сложные конструкции расширенной нотации Бэкуса-Наура вроде повторов (repeating).

Рассмотрим данные конструкции более подробно на примере правила грамматики для идентификатора некоторого языка программирования. Предположим, что первым символом идентификатора может быть любая буква, а последующими символами буква или цифра. Тогда правило будет выглядеть так:
identifier = letter (letter | digit)*

где последовательная запись означает последовательное распознавание (то есть сначала необходмо распознать letter, а затем (letter | digit)*,
| - означает выбор между альтернативами,
* - означает возможность повтора любое количество раз.

Для всех описанных конструкций существуют аналоги в Parsec. Последовательное выполнение парсеров записывается с помощью операции связывания >>, выбор с помощью комбинатора <|>, а повтор - с помощью комбинатора many. Таким образом парсер индентификаторов в Parsec будет выглядеть так:
identifier = letter >> many (letter <|> digit)

Затем на основе элементарных комбинаторов строятся более сложные комбинаторы и так далее. Рассматривать подробно этот процесс я не стану, ему посвящены целые отдельные статьи, ссылки на которые будут даны в конце статьи.

4) Как оказалось, комбинаторы и парсеры формируют некую абстрактую структуру, называемую "монадой", пришедшую в Haskell из теории категорий. Монаду можно представить как некий контейнерный тип, в котором элементы контейнера могут быть связаны друг с другом некоторой стратегией вычислений. В данном случае, каждой составляющей контейнера является конкретный парсер, а под их связыванием подразумевается последовательное выполнение двух парсеров с промежуточной передачей результата разбора первым - второму. "Упаковка" парсеров в монаду помогает сокрыть такие вещи, как явную передачу промежуточного состояния парсинга, а также позволяет записывать парсеры в более компактной и удобочитаемой форме.

Таким образом, можно отметить, что использование комбинаторных монадических парсеров является типичным функциональным подходом к разбору, позволяет избежать специфических языков, изучение которых необходимо для написания грамматик (как при работе с yacc, ANTLR), кромего того, в случае Parsec - парсеры являются first-class citizens языка, что позволяет значительно ускорить процесс их создания.

Попробуем продемонстрировать сказанное на нашем примере. Задача стоит следующим образом: создать парсер, которые превращает строки вида "4 * (f(1, 2) + 3)" в список токенов, то есть осуществляет лексический анализ строки. Проверять синтаксическую корректность выражений мы пока не станем, этим займётся будущий транслятор в постфиксную форму.

Начнём с самых простых токенов - LParen, RParen, которым соответствуют символы открывающейся и закрывающейся скобок.
Поскольку мы хотим чтобы парсер возвращал токен, то его типом будет Parser Token.
lparen :: Parser Token
lparen =  char '(' >> return LParen

Мы воспользовались стандартным парсером char, уже определённым в Parsec. Несложно догадаться, что он распознаёт один заданный символ, в данном случае '('. В случае успешного распознания нам нужно вернуть токен LParen. Это можно сделать с помощью специальной монадической функции return, которую необходимо связать с парсером char. Делается это с помощью оператора связывания >>. В данном случае связывание означает последовательное выполнение, то есть в начале выполняется распознавание скобки, а затем возвращается токен LParen. Если скобка не будет распознана - возникнет ошибка, о которой Parsec незамедлительно сообщит.

Попробуем протестировать наш парсер левой скобки. Сделать это можно в интерпретаторе GHCi. Запишем наше определение типа токен (data Token) и новосозданный парсер. Ключевое слово deriving в определении типа означает, что данный тип автоматически имплементирует некоторые классы. Если тип имлементирует класс Show - он может быть отображён, то есть существует некоторая функция, которая преобразует этот тип в строку, в данном случае (при употреблении ключевого слова deriving) эта функция генерируется автоматически.

module Main where

import Text.ParserCombinators.Parsec

data Token = Atom String | Op String | LParen | RParen | Comma | Func String deriving (Eq, Ord, Show)

lparen :: Parser Token
lparen =  char '(' >> return LParen

Теперь можно сохранить и загрузить в GHCi. Тестировать парсеры можно с помощью стандартной функции parseTest, которая принимает в качестве первого параметра парсер, а в качество второго - входную строку:

*Main> parseTest lparen "("
LParen

Как видим, тест успешно пройден, парсер распознал токен LParen и вывел его. Попробуем теперь следующее:

*Main> parseTest lparen "a"
parse error at (line 1, column 1):
unexpected "a"
expecting "("


Здесь Parsec выдал вполне информативную ошибку. На формат выдачи ошибок, вернее описание того, ожидалось можно немного влиять с помощью комбинатора <?>
Достаточно написать
char '('  "left parenthesis" >> return LParen

как описание ошибки станет таким:
*Main> parseTest lparen "a"
parse error at (line 1, column 1):
unexpected "a"
expecting "left parentheses"


Продолжим описывать необходимые функции. Парсеры для закрывающейся скобки и запятой выглядят аналогично:

rparen =  char ')' >> return RParen
comma  =  char ',' >> return Comma


Парсер для токена Atom (то есть переменной или числа), выглядит следующим образом:
atom :: Parser Token
atom = do
  a <- many1 alphaNum <?> "atom"
  return (Atom a)

Здесь мы используем do-нотацию, которая помогает записывать монадические выражения в более читабельной форме и, возможно, придаёт им более императивный вид, поскольку все операции в данном случае выполняются строго последовательно.
Запись
do 
  a 
  b 

аналогична записи:
a >> b

Стрелка <- означает, что результат выполнения парсера помещается в некоторую переменную a, которая затем может использоваться далее внутри do-выражения. В частности, здесь мы используем полученную в результате строку a для того, чтобы сконструировать токен Atom. Комбинатор many1 - производит из парсера alphaNum (который различает одну букву или цифру) новый парсер, который различает одну и больше букв или цифр.
<?> "atom" - как и в прошлом примере влияет на вывод ошибок парсинга, делая его более информативным.
return (Atom a) - возвращает токен Atom c лексемой a, полученной в результате работы many1 alphaNum.

operator представляет собой альтернативу между несколькими символами и возвращает токен Op.

operator :: Parser Token
operator = do
  c <- char '-' <|> char '+' <|> char '*' <|> char '/' <|> char '^' <|> char '.' <?> "operator"
  return $ Op (c:[])


Попробуем теперь определить парсера для токена Func. Его можно отличить от других токенов с помощью последующей скобки, то есть при входной строке вида "f(1) + 2", f - будет токеном Func "f", а если входная строка имеет вид "f - 1", то f - это Atom "f". Таким образом в процессе парсинга нам необходимо "заглянуть вперёд" (lookahead) , чтобы определить каким будет следующий токен. Данное действие можно реализовать с помощью комбинатора lookahead, который не поглощает символы из входной строки, а лишь проверяет успешность работы своего парсера-аргумента.

func :: Parser Token
func = do
  Atom a <- atom
  skipMany space
  lookAhead lparen
  return (Func a)


В начале распознаётся Atom, затем с помощью skipMany комбинатора пропускается свободное место (парсер space распознаёт пробелы, табуляции и т.д.), затем проверяется успешно ли отработает парсер lparen и, наконец, возвращается токен Func со строкой а, которую уже распознал парсер atom.

Теперь объединим все парсеры токенов вместе - в едином парсере токенов tok:

tok :: Parser Token
tok = do
  t <- try (func) <|> atom <|> operator <|> lparen <|> rparen <|> comma
  skipMany space
  return t

Здесь нам придётся использовать комбинатор try, который "пробует" распарсить функцию с помощью парсера func, и если у него "не получится" - нужно продолжить разбирать альтернативы. Если этого не сделать, то в случае входной строки "f + 1" парсер func начнёт парсить функцию f, однако не обнаружит скобки и выдаст ошибку, что неверно, поскольку f - в данном случае Atom. Таким образом, в случае сбоя парсера func - необходимо продолжить парсинг с другими альтернативами, например atom.

Наконец сформируем парсер для всего выражения:

expression :: Parser [Token]
expression = do
  skipMany space
  ts <- many1 tok
  eof
  return ts


Здесь из нового - только парсер eof, который распознаёт конец файла.

Теперь нужно правильно вызывать парсер и обработать возможные ошибки:

parse' :: String -> [Token]
parse' s = case (parse expression "expr" s) of
  Left err -> error (show err)
  Right x -> x


Делается это с помощью функции parse, первый параметер которой - парсер, второй - название строки (можно оставить любым), и третий - сама строка.
Результат её типа Either ParserError a - то есть либо ошибка парсинга (ParserError), либо тип возвращаемого парсером значения (то есть - некий любой тип a).
Вообще, тип Either представляет значения с двумя возможностями - значение типа Either a b может быть либо Left a, либо Right b (то есть data Either a b = Left a | Right b). Иногда тип Either используется для представления значения которое является либо ошибкой, либо правильным значением. Обычно, конструктор Left используется для представления ошибочного значения и конструктор Right для правильного (можно легко запомнить поскольку "right" означает ещё и "правильный").

Затем с помощью case of мы определяем правильное или ошибочное значение получено: в случае ошибки - выводим её с помощью функции error, которая выводит сообщение и останавливает вычисления, а в случаего успешного парсинга - выводим его результат.

Можно сказать, что код получился вполне читабельным и несложным. Следует отметить, что в статье продемонстрированы лишь базовые возможности Parsec.
Если говорить о его возможностях более серьёзно, то можно отметить следующее:
- Parsec может обеспечивать разбор грамматики с бесконечным предпросмотром (lookahead) с помощью комбинатора try, который обеспечивает так называемый синтаксичечкий предпросмотр, но лучше всего работает с LL(1)-грамматиками;
- как заявляет автор Parsec, он обеспечивает достаточно неплохую скорость разбора, в особенности в сравнении с другими комбинаторными парсерами;
- выбор стандартных библиотечных парсеров весьма богат;
- простота разработки и читабельность кода парсеров - на высоте;
- парсер может работать на любых данных, необязательно строках. Таким образом синтаксический разбор можно производить на списках токенов, а не списках символов;
- возможность быстрой реализации лексических анализаторов, использующих готовые схемы языков (например схема для языка Haskell или Java);
- достаточно хорошая документация.


Полезные ссылки:
Parsec
G.Hutton, E.Meijer "Monadic parser combinators" [PDF]
G.Hutton, E.Meijer "Monadic parsing in Haskell" [PDF]



В качестве приложения стоит привести полный код парсера.

module Main where

import Text.ParserCombinators.Parsec

data Token = Atom String | Op String | LParen | RParen | Comma | Func String deriving (Eq, Ord, Show)

parse' :: String -> [Token]
parse' s = case (parse expression "expr" s) of
  Left err -> error (show err)
  Right x -> x

-- operator token
operator :: Parser Token
operator = do
  c <- char '-' <|> char '+' <|> char '*' <|> char '/' <|> char '^' <|> char '.' <?> "operator"
  return $ Op (c:[])

-- atom token
atom :: Parser Token
atom = do
  a <- many1 alphaNum <?> "atom"
  return (Atom a)

-- 1-char tokens
lparen =  char '(' >> return LParen
rparen =  char ')' >> return RParen
comma  =  char ',' >> return Comma

-- func token
func :: Parser Token
func = do
  Atom a <- atom
  skipMany space
  lookAhead lparen
  return (Func a)

-- one token
tok :: Parser Token
tok = do
  t <- try (func) <|> atom <|> operator <|> lparen <|> rparen <|> comma
  skipMany space
  return t

-- all expression
expression :: Parser [Token]
expression = do
  skipMany space
  ts <- many1 tok
  eof
  return ts

Tags: geek, haskell, parsing
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 6 comments