- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Использование и архитектураParsec презентация
Содержание
- 1. Использование и архитектураParsec
- 2. Синтаксический анализ Задачи: Проверка правильности исходных данных
- 3. Подходы Полностью ручная реализация Генераторы парсеров (YACC, Happy) Комбинаторные библиотеки “List of successes” Монадические Parsec
- 4. Монадические парсеры type Parser a return ::
- 5. Parsec import Text.ParserCombinators.Parsec simple :: Parser Char
- 6. Последовательность парсеров bracketedLetter :: Parser Char bracketedLetter
- 7. Последовательность парсеров > parseTest bracketedLetter “(a)” ‘a’
- 8. Альтернативы parens :: Parser () parens =
- 9. Предпросмотр test1 = string “OCaml” string “Haskell”
- 10. Предпросмотр test1 = string “OCaml” string “Haskell”
- 11. Предпросмотр Причина: Parsec строит LL(1)-парсер Ограничение: решение
- 12. Предпросмотр Вариант 1: test2 = do {
- 13. Предпросмотр Вариант 2: test2 = try (string
- 14. Архитектурные принципы Эффективность: отказ от затрат на
- 15. Ограничение предпросмотра В конструкции p q парсер
- 16. Ограничение предпросмотра Упрощенная реализация: type Parser a
- 17. Базовые комбинаторы return x = \input ->
- 18. Базовые комбинаторы char c = satisfy (==c) letter = satisfy isAlpha digit = satisfy isDigit
- 19. Базовые комбинаторы (>>=) :: Parser a ->
- 20. Базовые комбинаторы Consumed reply1 ->
- 21. Базовые комбинаторы () :: Parser a ->
- 22. try try :: Parser a -> Parser
- 23. Обработка ошибок К типу Parser добавляется состояние:
- 24. Обработка ошибок Меняется реализация return, satisfy, ()
- 25. Семантика nesting :: Parser Int nesting =
- 26. Дополнительные возможности Лексический анализ: Лексический анализ объединяется
- 27. Источники информации Сайт Parsec: http://legacy.cs.uu.nl/daan/parsec.html Daan Leijen.
Синтаксический анализ Задачи: Проверка правильности исходных данных - соответствие текста грамматике Содержательная обработка исходных данных
Слайд 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
satisfy :: (Char -> Bool) -> Parser Char
(<|>) :: Parser a -> Parser a -> Parser a
Слайд 5Parsec
import Text.ParserCombinators.Parsec
simple :: Parser Char
simple = letter
> parseTest simple “a”
‘a’
Примитивные парсеры:
letter, char, string, …
Слайд 6Последовательность парсеров
bracketedLetter :: Parser Char
bracketedLetter = do { char ‘(‘
; c <- letter
; char ‘)’
; return c
}
; char ‘)’
; return c
}
Слайд 7Последовательность парсеров
> parseTest bracketedLetter “(a)”
‘a’
> parseTest bracketedLetter “(ab)”
parse error at (line
1, column 3):
unexpected "b"
expecting ")"
unexpected "b"
expecting ")"
Слайд 8Альтернативы
parens :: Parser ()
parens = do { char ‘(‘
; parens
; char ‘)’
; parens
}
<|> return ()
; char ‘)’
; parens
}
<|> return ()
Слайд 9Предпросмотр
test1 = string “OCaml” string “Haskell”
test2 = string “(lisp)”
string “(scheme)”
> parseTest test1 “Haskell”
“Haskell”
> parseTest test2 “(lisp)”
“(lisp)”
> 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)"
> parseTest test2 “(scheme)”
parse error at (line 1, column 1):
unexpected "s"
expecting "(lisp)"
Слайд 11Предпросмотр
Причина: Parsec строит LL(1)-парсер
Ограничение: решение принимается на основании анализа только первого
символа строки
Осознанный выбор: эффективность
Есть возможность преодолеть ограничения LL(1)
Осознанный выбор: эффективность
Есть возможность преодолеть ограничения LL(1)
Слайд 12Предпросмотр
Вариант 1:
test2 = do { char ‘(‘
; s <- string “lisp” <|> string “scheme”
; char ‘)’
; return ( “(“ ++ s ++ “)” )
}
; 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
| 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
satisfy test = \input -> case (input) of
[] -> Empty Error
(c:cs) | test c -> Consumed (Ok c cs)
| otherwise -> Empty Error
Слайд 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
...
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)
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
consumed -> consumed
Empty Error -> (q input)
Empty ok -> case (q input) of
Empty _ -> Empty ok
consumed -> consumed
consumed -> consumed
Слайд 22try
try :: Parser a -> Parser a
try p = \input ->
case (p input) of
Consumed Error -> Empty Error
other -> other
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
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 <- nesting
; char ‘)’
; m <- nesting
; return (max (n + 1) m)
} <|> return 0
; char ‘)’
; m <- nesting
; return (max (n + 1) m)
} <|> return 0
Слайд 26Дополнительные возможности
Лексический анализ:
Лексический анализ объединяется с синтаксическим анализом
Лексический анализ выполняется отдельными
специализированными парсерами
Реализованными в библиотеке
Разработанными самостоятельно с помощью комбинаторов
Использование отдельного сканера, параметризация по типу потока (не только Char)
Возможность генерации парсера выражений по набору операций с учетом ассоциативности и приоритета
Реализованными в библиотеке
Разработанными самостоятельно с помощью комбинаторов
Использование отдельного сканера, параметризация по типу потока (не только Char)
Возможность генерации парсера выражений по набору операций с учетом ассоциативности и приоритета
Слайд 27Источники информации
Сайт Parsec: http://legacy.cs.uu.nl/daan/parsec.html
Daan Leijen. Parsec, a fast combinator parser, 2001
Daan
Leijen, Erik Meijer. Parsec: Direct Style Monadic Parser Combinators For The Real World, 2001
