Использование и архитектура Parsec Дмитрий Тимофеев Санкт-Петербургская группа пользователей Haskell 15 декабря 2007 г. - презентация

1 Использование и архитектура Parsec Дмитрий Тимофеев Санкт-Петербургская группа пользователей Haskell 15 декабря 2007 г.

2 Синтаксический анализ Задачи: Проверка правильности исходных данных - соответствие текста грамматике Содержательная обработка исходных данных

3 Подходы Полностью ручная реализация Генераторы парсеров (YACC, Happy) Комбинаторные библиотеки List of successes Монадические Parsec

4 Монадические парсеры type Parser a return :: a -> Parser a (>>=) :: Parser a -> (a -> Parser b) -> Parser b satisfy :: (Char -> Bool) -> Parser Char ( ) :: Parser a -> Parser a -> Parser a

5 Parsec import Text.ParserCombinators.Parsec simple :: Parser Char simple = letter > parseTest simple a a Примитивные парсеры: letter, char, string, …

6 Последовательность парсеров bracketedLetter :: Parser Char bracketedLetter = do { char ( ; c

7 Последовательность парсеров > parseTest bracketedLetter (a) a > parseTest bracketedLetter (ab) parse error at (line 1, column 3): unexpected "b" expecting ")"

8 Альтернативы parens :: Parser () parens = do { char ( ; parens ; char ) ; parens } return ()

9 Предпросмотр test1 = string OCaml string Haskell test2 = string (lisp) string (scheme) > parseTest test1 Haskell Haskell > parseTest test2 (lisp) (lisp)

10 Предпросмотр test1 = string OCaml string Haskell test2 = string (lisp) string (scheme) > parseTest test2 (scheme) parse error at (line 1, column 1): unexpected "s" expecting "(lisp)"

11 Предпросмотр Причина: Parsec строит LL(1)-парсер Ограничение: решение принимается на основании анализа только первого символа строки Осознанный выбор: эффективность Есть возможность преодолеть ограничения LL(1)

12 Предпросмотр Вариант 1: test2 = do { char ( ; s string scheme ; char ) ; return ( ( ++ s ++ ) ) }

13 Предпросмотр Вариант 2: test2 = try (string (lisp)) string (scheme) Комбинатор try так изменяет наш парсер, что он в случае неудачи оставляет уже прочитанные символы в потоке

14 Архитектурные принципы Эффективность: отказ от затрат на поддержку неограниченного предпросмотра, LL(1) по умолчанию, можно увеличить количество просматриваемых символов, используя try Информативность сообщений об ошибках

15 Ограничение предпросмотра В конструкции p q парсер q в принципе не вызывается, если p обработал больше одного символа Каждый парсер отслеживает, сколько символов он обработал

16 Ограничение предпросмотра Упрощенная реализация: type Parser a = String -> Consumed a data Consumed a = Consumed (Reply a) | Empty (Reply a) data Reply a = Ok a String | Error

17 Базовые комбинаторы return x = \input -> Empty (Ok x input) satisfy :: (Char -> Bool) -> Parser Char satisfy test = \input -> case (input) of []-> Empty Error (c:cs) | test c-> Consumed (Ok c cs) | otherwise-> Empty Error

18 Базовые комбинаторы char c= satisfy (==c) letter = satisfy isAlpha digit= satisfy isDigit

19 Базовые комбинаторы (>>=) :: Parser a -> (a -> Parser b) -> Parser b p >>= f = \input -> case (p input) of Empty reply1 -> case (reply1) of Ok x rest -> ((f x) rest) Error-> Empty Error...

20 Базовые комбинаторы Consumed reply1 -> Consumed (case (reply1) of Ok x rest -> case ((f x) rest) of Consumed reply2 -> reply2 Empty reply2-> reply2 error -> error)

21 Базовые комбинаторы ( ) :: Parser a -> Parser a -> Parser a p q = \input -> case (p input) of Empty Error -> (q input) Empty ok-> case (q input) of Empty _ -> Empty ok consumed -> consumed

22 try try :: Parser a -> Parser a try p = \input -> case (p input) of Consumed Error-> Empty Error other-> other

23 Обработка ошибок К типу Parser добавляется состояние: type Parser a = State -> Consumed a data State= State String Pos К результатам разбора добавляется сообщение об ошибках, причем к удачному разбору – тоже data Message = Message Pos String [String] data Reply a = Ok a State Message | Error Message

24 Обработка ошибок Меняется реализация return, satisfy, ( ) – [Leijen, Meijer, 2001] В результате получаем возможность приписывать парсерам информативные обозначения – комбинатор

25 Семантика nesting :: Parser Int nesting = do { char ( ; n

26 Дополнительные возможности Лексический анализ: Лексический анализ объединяется с синтаксическим анализом Лексический анализ выполняется отдельными специализированными парсерами Реализованными в библиотеке Разработанными самостоятельно с помощью комбинаторов Использование отдельного сканера, параметризация по типу потока (не только Char) Возможность генерации парсера выражений по набору операций с учетом ассоциативности и приоритета

27 Источники информации Сайт Parsec: Daan Leijen. Parsec, a fast combinator parser, 2001 Daan Leijen, Erik Meijer. Parsec: Direct Style Monadic Parser Combinators For The Real World, 2001