Что хотел спросить.

[thesz]

Давным-давно я написал статью по разборщики на потоковых процессорах.

Так вот, работают они совершенно нелинейно. Простой разборщик наподобие \n -> prun (pmany (ptoken '1' `ppar` ptoken '2')) (replicate n '1') работает за квадратичное от n время.

Есть у меня подозрение, что это из-за того, что ppar реализован не как исключающий ppar монадных

Comments

parser

[rvp74]

Глянул твой pseq и решил переписать все с нуля ;)

data SP a b = NullSP | Put b (SP a b) | Get (a -> SP a b)

failSP = NullSP

returnSP a = Put a NullSP

seqSP NullSP f = NullSP
seqSP (Get h) f = Get $ \a -> seqSP (h a) f
seqSP (Put b spa) f = f b `parSP` seqSP spa f

parSP :: SP a b -> SP a b -> SP a b
parSP NullSP spb = spb
parSP spa NullSP = spa
parSP (Put b spa) spb = Put b $ parSP spa spb
parSP spa (Put b spb) = Put b $ parSP spa spb
parSP (Get fa) (Get fb) = Get $ \a -> parSP (fa a) (fb a)

mapSP f NullSP = NullSP
mapSP f (Get g) = Get $ \a -> mapSP f (g a)
mapSP f (Put b sp) = Put (f b) (mapSP f sp)

instance Monad (SP a) where
return = returnSP
(>>=) = seqSP
fail _ = failSP

instance Functor (SP a) where
fmap = mapSP

readInput = Get $ returnSP

char c = do
a <- readInput

Re: parser

[thesz]

С чего бы это она отбрасывается?

Нисколечки она не отбрасывается.

Рассинхронизации не произойдет, поскольку мы сперва выдадим все возможные на данный момент результаты, а затем запросим вход.

Вообще, потоковые процессоры мне нравятся. Только я их дальше разборщиков не освоил. ;)

Re: parser

[rvp74]

В семантику <|> не должна входить выдача результа альтернативы до момента отказа первой альтернативы. Не путай с par

Re: parser

[thesz]

О! Его реализации у тебя нет. Понял.

Re: parser

[rvp74]

Само собой нету. Требования <|> соблюсти проблематично при синхронизированном вводе и/или отсутствии просмотра наперед без чтения (lookAHead) и возврата символов во входной поток (setInput). Максимум что можно сделать сейчас это соблюсти первых три закона. Это даст некий бонус за счет отбрасывания второй альтернативы при наличии вывода в первой альтернативе.

Re: parser

[thesz]

Зато мы останавливаемся там, где ошибка. И легко сделать 2D синтаксис без порчи кода основной грамматики.

Re: parser

[rvp74]

В общем я придумал как сделать altSP (ака <|>)

Где-то так:

altSP NullSP spb = spb
altSP spa NullSP = spa
altSP spa@(Put _ _) _ = spa
altSP (Get fa) (Get fb) = Get $ \a -> parSP (fa a) (fb a)
altSP (Get fa) spb = Get $ \a -> fa a `altSP` bufInput a spb

bufInput a NullSP = NullSP
bufInput a (Get f) = f a
bufInput a (Put b spb) = Put b $ bufInput a spb

Все хорошо, но есть один маленький недостаток - не работает. :)

пробовал на:

option s p = p `altSP` return s

test = parseSP (option '_' (char '1') >> char '2') "2 "

выдает почему-то пустой список

Re: parser

[thesz]

Нельзя всегда отбрасывать возвращаемое второй альтернативой значение.

Я сделал вот так:
altSP NullSP spb = spb
altSP spa NullSP = spa
altSP spa@(Put _ _) _ = spa
altSP (Get fa) (Get fb) = Get $ \a -> parSP (fa a) (fb a)
altSP a@(Get fa) (Put o b) = Put o $ altSP a bи оно заработало. ;)

Re: parser

[rvp74]

Этот вариант неинтересен (потому как кидает второй вариант до отказа первого).
Кстати, там у меня опечатка (которая осталась и в твоем коде: вместо altSP написанно parSP)

Re: parser

[rvp74]

Я отбрасываю альтернативу только в одном случае - если первая успешна