Список упражнений

Упражнение 1

Словом парсер называется механизм, вычленяющий из текстовых данных какую-либо информацию. Типичный пример парсера – функция reads. Напомним его тип:

reads :: Read a => String -> [(a,String)]

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

type Parser a = String -> Maybe (a,String)

Договоримся, что выходной текст любого парсера является суффиксом (возможно, полным) входного.

Напишите семейство парсеров char :: Char -> Parser Char, распознающих заданный символ в начале текста.

Упражнение 2

Напишите парсер integer :: Parser Integer, распознающий целое число (знак перед числом не допускается).

Упражнение 3

Напишите комбинатор inject :: (a->b) -> Parser a -> Parser b, применяющий заданное преобразование к результату работы парсера в случае его успеха.

Упражнение 4

Напишите комбинатор alt :: [Parser a] -> Parser a, делающий из последовательности парсеров сложный парсер, пробующий по очереди парсеры этой последовательности до первого удачного исхода.

Упражнение 5

Напишите комбинатор bind :: Parser a -> (a -> Parser b) -> Parser b, делающий из парсера и генератора парсеров сложный парсер, строящий новый парсер по результату первого парсера, а затем применяющий его к оставшейся после первого парсера части текста.

Также напишите генератор trivial :: a -> Parser a, делающий из входной величины парсер, всегда распознающий эту величину, оставляя текст неизменным.

Договоримся дальше иногда использовать комбинатор

thenP :: Parser a -> Parser b -> Parser b
thenP x y = x `bind` const y

Упражнение 6

Рассмотрим следующий комбинатор:

sim :: [Parser a] -> Parser [a]
sim []     text = trivial [] text
sim (p:ps) text = case p text of
    Just (x,rest) -> case sim ps rest of
        Just (xs,last) -> Just (x:xs,last)
        Nothing        -> Nothing
    Nothing       -> Nothing

Выразите этот комбинатор при помощи foldr без явной рекурсии. Вам может пригодиться комбинатор bind из прошлого упражнения.

Упражнение 7

Приведём пример парсера, вычисляющиего значение арифметического выражения, состоящего из цифр и знаков сложения.

expr :: Parser Integer
expr = sum `inject` sim [integer, alt [char '+' `thenP` expr, trivial 0]]

Сделайте этот парсер нечувствительным к пробелам.

Упражнение 8

Добавьте к этому парсеру возможность обработки знаков умножения.

Упражнение 9

Добавьте к получившемуся в результате выполнения предыдущего упражнения парсеру возможность обработки знаков вычитания, а также – знака перед первым числом выражения.

Упражнение 10

И, наконец, добавьте возможность обработки скобок.

Упражнение 11

Сделайте последнее упражнение к главе 6.