2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 18:59 


05/09/12
2587
Вчера решал одну тренировочную задачку с сайта Codewars - Regular expression parser Собственно, задание не сложное:
Цитата:
Your task is to implement a simple regular expression parser. We will have a parser that outputs the following AST of a regular expression:
Используется синтаксис Haskell
data RegExp = Normal Char       -- ^ A single regular character
            | Any               -- ^ Any charater
            | ZeroOrMore RegExp -- ^ Zero or more occurances of the same regexp
            | Or RegExp RegExp  -- ^ A choice between 2 regexps
            | Str [RegExp]      -- ^ A sequence of regexps.
Цитата:
As with the usual regular expressions, Any is denoted by the '.' character, ZeroOrMore is denoted by a subsequent '*' and Or is denoted by '|'. Brackets are allowed to group sequence of regular expressions into Str [RegExp].
Operator precedences from highest to lowest are: *, sequencing and |. Therefore the followings hold:
Используется синтаксис Haskell
"ab*"     -> Str [Normal 'a', ZeroOrMore (Normal 'b')]
"(ab)*"   -> ZeroOrMore (Str [Normal 'a', Normal 'b'])
"ab|a"    -> Or (Str [Normal 'a',Normal 'b']) (Normal 'a')
"a(b|a)"  -> Str [Normal 'a',Or (Normal 'b') (Normal 'a')]
"a|b*"    -> Or (Normal 'a') (ZeroOrMore (Normal 'b'))
"(a|b)*"  -> ZeroOrMore (Or (Normal 'a') (Normal 'b'))
"a"          -> Normal 'a'
"ab"         -> Str [ Normal 'a', Normal 'b']
"a.*"        -> Str [ Normal 'a', ZeroOrMore Any ]
"(a.*)|(bb)" -> Or (Str [Normal a, ZeroOrMore Any]) (Str [Normal 'b', Normal 'b'])
Цитата:
Feel free to use any parser combinator libraries available
Я написал простенькую программку в несколько строк безо всяких библиотек, она прошла тесты:
код: [ скачать ] [ спрятать ]
Используется синтаксис Haskell
parseRegExp :: String -> Maybe RegExp
parseRegExp s = Just $ go s [] where

    packlist [a] = a
    packlist  l  = Str $ reverse l

    spanclose s = (init l, drop (length l) s) where
        l = head.dropWhile ((/=(-1)).sum.map f).inits $ s
        f '(' = 1
        f ')' = -1
        f  _  = 0

    go []     l = packlist l
    go (c:cs) l = case c of
        '(' -> go sr $ go sl [] : l where (sl,sr) = spanclose cs
        '|' -> Or (packlist l) $ go cs []
        '*' -> go cs $ ZeroOrMore (head l) : (tail l)
        '.' -> go cs $ Any : l
        _   -> go cs $ Normal c : l
и это позволило мне посмотреть коды остальных участников. Начиная с кода автора задачи там были представлены обширные простыни со щедрым использованием монад/функторов/трансформеров да еще и со специализированными парсерными библиотеками нередко при этом (я не буду их приводить, но если попросите - скопипастю). И хотя я их детально не разбирал, но я примерно представляю себе их источники вдохновения, хотя я не разбираюсь в теории синтаксического разбора, порождающих грамматиках и прочему Хомскому и Брюне. Но тут на фоне всего этого великолепия я внезапно обнаружил код, который вызвал (и продолжает вызывать) у меня яркий эмоциональный отклик - вот он:
Используется синтаксис Haskell
instance Eq RegExp where
  _ == _ = True

parseRegExp _ = Just Any
и всё :D Не могли бы уважаемые участники форума просветить меня, как и на каких принципах работает это волшебство?

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 20:52 


11/12/14
893
Лол, я далеко не хаскелист, только _пробовал_ начинать вникать, не смог осилить самый вменяемый учебник дальше места где собственно начались монады.
Но здесь, имхо, всё очень просто - типу RegExp перебивается оператор сравнения на то чтобы возвращать всегда True.
Таким образом сравнение с образцом теста всегда проходит :) И всего лишь.

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:01 
Заслуженный участник


27/04/09
28128
_Ivana в сообщении #965726 писал(а):
Не могли бы уважаемые участники форума просветить меня, как и на каких принципах работает это волшебство?
Последнее-то? Ни на каких. Вы же ясно видите, что любой вход тут эквивалентен входу ".". Это точно весь код? Инстанс Eq RegExp тоже не пойму для чего. :o В общем, что-то здесь не так.

Кстати, а почему у вас parseRegExp s = Just something? Входу "(" должно бы соответствовать Nothing, а система тестирования почему-то съела. В ней всяко должен был быть тест на не-регексп, если уж они типом функции сделали String -> Maybe RegExp!

aa_dav в сообщении #965813 писал(а):
Но здесь, имхо, всё очень просто - типу RegExp перебивается оператор сравнения на то чтобы возвращать всегда True.
А, об этом не подумал. Тут только одна нестыковка — вроде, инстансы не могут перекрывать видимость друг друга, и два в одной и той же области видимости должны вызвать реакцию компилятора из-за невозможности выбора одной из них.

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:06 


11/12/14
893
arseniiv в сообщении #965818 писал(а):
Тут только одна нестыковка — вроде, инстансы не могут перекрывать видимость друг друга, и два в одной и той же области видимости должны вызвать реакцию компилятора из-за невозможности выбора одной из них.


Опять таки я не прожженый хаскелист, но у RegExp в изначальной постановке задачи вообще инстанс Eq не был определен. Так что он по видимому просто и перебил дефолтное поведение ==.

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:06 


05/09/12
2587
Вы правы, я только что это понял :facepalm: Но это вызвало у меня не менее сильные эмоции чем в первый раз :lol: Просто делается заглушка чтобы все тесты на сравнение выдавали истину. А я дурак не додумался :facepalm:

ЗЫ там изначально стояло
Используется синтаксис Haskell
deriving (Show, Eq)
но участник предложивший это решение убрал Eq :D

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:16 
Заслуженный участник


27/04/09
28128
aa_dav в сообщении #965824 писал(а):
Так что он по видимому просто и перебил дефолтное поведение ==.
Не бывает инстанса по-дефолту. Хотя есть способ определить такой «обычный» инстанс для некоторых классов, в т. ч. Eq, в месте описания типа с помощью добавления в конце него deriving (классы)/deriving класс.

_Ivana в сообщении #965825 писал(а):
но участник предложивший это решение убрал Eq :D
А, вот как. Теперь всё сходится. Правда, непонятно, почему это позволительно (могли бы немного на модули разбить, что ли), и почему нет тестов со входом типа "(".

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:20 


05/09/12
2587
Да, тесты только на валидные входные данные. Но мой парсер нетрудно доработать чтобы выдавал Nothing на невалидных строках.
Извините что не разобрался и создал тему по такому как оказалось смешному вопросу :D

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:59 
Заслуженный участник


27/04/09
28128

(Оффтоп)

_Ivana в сообщении #965838 писал(а):
Извините что не разобрался и создал тему по такому как оказалось смешному вопросу :D
По-моему, нормальная тема.

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 00:47 


05/09/12
2587
На сайте изменились тесты, добавились невалидные входные данные, я доработал свой код с этим учетом с использованием монады Maybe, но проверки его процентов на 20 загромоздили. Мне это уже не так нравится, как мой исходный красивый и лаконичный вариант, может придумаю как написать лучше.

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 00:53 
Заслуженный участник


27/04/09
28128
Тут как раз может пригодиться инстанс Monad Maybe, т. к.

Используется синтаксис Haskell
Nothing >>= f = Nothing
Just v  >>= f = f v

Это имеет смысл вычислений, которые могут выдать ошибку, и она распространится до самого конца.

-- Ср янв 21, 2015 03:00:00 --

(Кстати ещё, инстанс Monad (Either left) аналогичен, но передаётся информация типа left об ошибке. У подобного использования Either простая мнемоника: right — не только правое, но и «правильное», а информация об ошибке — это то, что «осталось» — left. В явном виде я этого не встречал, но, наверно, переизобретается мнемоника часто.)

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 01:28 


05/09/12
2587
arseniiv вы все правильно пишете, я это читал у Мирана Липовачи раз 10, но вот сейчас пытаюсь вместо моих ручных понятных ифов протащить через эту монаду и пока не удается. Но я вообще это делаю впервые, и вдобавок не понимаю теорию этой концепции.

-- 21.01.2015, 01:35 --

Сейчас мой безмонадный но рабочий вариант вот такой
код: [ скачать ] [ спрятать ]
Используется синтаксис Haskell
parseRegExp :: String -> Maybe RegExp
parseRegExp s  = go s nl where

    nl = Just []
    fall x = x == Nothing

    packlist []  = Nothing
    packlist [a] = Just $ a
    packlist  l  = Just $ Str $ reverse l

    spanclose s
        | null w    = Nothing
        | otherwise = Just (init l, drop (length l) s) where
            w = filter ((==(-1)).sum.map f).inits $ s
            l = head w
            f '(' = 1
            f ')' = -1
            f  _  = 0

    go _       Nothing = Nothing
    go []     (Just l) = packlist l
    go (c:cs) (Just l) = case c of

        '(' -> if fall sp || fall p then Nothing else go sr $ Just $ (fromJust p) : l where
            sp = spanclose cs
            (sl,sr) = fromJust sp
            p = go sl nl

        '|' -> if fall pl || fall p  then Nothing else Just $ Or (fromJust pl) (fromJust p) where
            pl = packlist l
            p = go cs nl

        '*' -> if null l then Nothing else go cs $ Just $ ZeroOrMore (head l) : (tail l)

        '.' -> go cs $ Just $ Any : l

        _   -> if not (isAlpha c) then Nothing else go cs $ Just $ Normal c : l
как его облагородить чтобы не мозолили глаза эти ифы в проверках пока думаю.

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 01:55 
Заслуженный участник


27/04/09
28128
if fall sp || fall p then Nothing else v = (sp `mplus` p) >> v, хм?

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 01:58 


05/09/12
2587
Ваш вариант не понял, но мой тоже лучше того что было
Используется синтаксис Haskell
'(' -> spanclose cs >>= \(sl,sr) -> go sr $ go sl nl >>= Just.(:l)


-- 21.01.2015, 02:06 --

Вот как мне на текущий момент удалось облагородить
код: [ скачать ] [ спрятать ]
Используется синтаксис Haskell
parseRegExp :: String -> Maybe RegExp
parseRegExp s  = go s nl where

    nl = Just []

    packlist []  = Nothing
    packlist [a] = Just $ a
    packlist  l  = Just $ Str $ reverse l

    spanclose s
        | null w    = Nothing
        | otherwise = Just (init l, drop (length l) s) where
            w = filter ((==(-1)).sum.map f).inits $ s
            l = head w
            f '(' = 1
            f ')' = -1
            f  _  = 0

    go _       Nothing = Nothing
    go []     (Just l) = packlist l
    go (c:cs) (Just l) = case c of
        '(' -> spanclose cs >>= \(sl,sr) -> go sr $ go sl nl >>= Just.(:l)
        '|' -> packlist l >>= \pl -> go cs nl >>= \pr -> Just $ Or pl pr
        '*' -> if null l then Nothing else go cs $ Just $ ZeroOrMore (head l) : (tail l)
        '.' -> go cs $ Just $ BAny : l
        _   -> if not (isAlpha c) then Nothing else go cs $ Just $ Normal c : l

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 02:13 
Заслуженный участник


27/04/09
28128
_Ivana в сообщении #965947 писал(а):
Ваш вариант не понял
MonadPlus. По существу, это одновременно Monad и Alternative. Применительно к Maybe сложение mplus означает выбор первого не провалившегося вычисления; соответственно, ноль mzeroNothing. :-)

-- Ср янв 21, 2015 04:14:32 --

(Или я там с типами напортачил? Мало ли, не проверял.)

 Профиль  
                  
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 02:17 


05/09/12
2587
MonadPlus буду кусать после Monad. Сейчас хочу запаковать
Код:
f l == True = Nothing
чтобы остальные строки нижней функции без ифов написать.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group