2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 18:59 
Вчера решал одну тренировочную задачку с сайта 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 
Лол, я далеко не хаскелист, только _пробовал_ начинать вникать, не смог осилить самый вменяемый учебник дальше места где собственно начались монады.
Но здесь, имхо, всё очень просто - типу RegExp перебивается оператор сравнения на то чтобы возвращать всегда True.
Таким образом сравнение с образцом теста всегда проходит :) И всего лишь.

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:01 
_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 
arseniiv в сообщении #965818 писал(а):
Тут только одна нестыковка — вроде, инстансы не могут перекрывать видимость друг друга, и два в одной и той же области видимости должны вызвать реакцию компилятора из-за невозможности выбора одной из них.


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

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:06 
Вы правы, я только что это понял :facepalm: Но это вызвало у меня не менее сильные эмоции чем в первый раз :lol: Просто делается заглушка чтобы все тесты на сравнение выдавали истину. А я дурак не додумался :facepalm:

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

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:16 
aa_dav в сообщении #965824 писал(а):
Так что он по видимому просто и перебил дефолтное поведение ==.
Не бывает инстанса по-дефолту. Хотя есть способ определить такой «обычный» инстанс для некоторых классов, в т. ч. Eq, в месте описания типа с помощью добавления в конце него deriving (классы)/deriving класс.

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

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение20.01.2015, 21:20 
Да, тесты только на валидные входные данные. Но мой парсер нетрудно доработать чтобы выдавал Nothing на невалидных строках.
Извините что не разобрался и создал тему по такому как оказалось смешному вопросу :D

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

(Оффтоп)

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

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 00:47 
На сайте изменились тесты, добавились невалидные входные данные, я доработал свой код с этим учетом с использованием монады Maybe, но проверки его процентов на 20 загромоздили. Мне это уже не так нравится, как мой исходный красивый и лаконичный вариант, может придумаю как написать лучше.

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 00:53 
Тут как раз может пригодиться инстанс 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 
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 
if fall sp || fall p then Nothing else v = (sp `mplus` p) >> v, хм?

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 01:58 
Ваш вариант не понял, но мой тоже лучше того что было
Используется синтаксис 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 
_Ivana в сообщении #965947 писал(а):
Ваш вариант не понял
MonadPlus. По существу, это одновременно Monad и Alternative. Применительно к Maybe сложение mplus означает выбор первого не провалившегося вычисления; соответственно, ноль mzeroNothing. :-)

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

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

 
 
 
 Re: Парсинг регулярных выражений на Haskell
Сообщение21.01.2015, 02:17 
MonadPlus буду кусать после Monad. Сейчас хочу запаковать
Код:
f l == True = Nothing
чтобы остальные строки нижней функции без ифов написать.

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group