Производительность uu-parsinglib по сравнению с "try" в Parsec

Question

Вопрос

я знаю Parsec а также uu-parsinglib и я написал парсеры в них обоих. Недавно я обнаружил, что есть проблема в uu-parsinglib, что может существенно повлиять на его производительность, и я не вижу пути ее решения.

Рассмотрим следующие парсеры Parsec:

pa = char 'a'
pb = char 'b'
pTest = many $ try(pa <* pb)

Что будет эквивалентно в uu-parsinglib? Это не будет следующим:

pa = pSym 'a'
pb = pSym 'b'
pTest = pList_ng (pa <* pb)

Разница в том, что в Parsec, many будет есть (pa <* pb) (пара "ab") жадный до тех пор, пока он больше не совпал uu-parsinglib, pList_ng не жадный, поэтому он сохранит в памяти возможные пути возврата после разбора каждого (pa <* pb),

Есть ли способ написать что-то вроде pList(try(pa <* pb)) в uu-parsinglib?

пример

Хороший пример будет

pExample = pTest <* (pa <* pb)

и образец ввода "ababab",

С Parsecмы бы получили ошибку (потому что pTest это жадный разбор пар "ab"), но в uu-parsinglibстрока будет проанализирована без проблем.

редактировать

Мы не можем перейти от pList_ng в pListпотому что это было бы не эквивалентно Parsec версия. Например:

pExample2 = pTest <* pa

и образец ввода "ababa" будет успех в Parsec, но потерпеть неудачу в uu-parsinglib, при использовании жадных pList,

Конечно uu-parsinglib удастся, если мы будем использовать pList_ng здесь, но это может быть намного медленнее для некоторых входов и правил. Например, учитывая вход "ababab", Parsec просто потерпит неудачу, потому что pTest будет потреблять всю строку и pa не будет соответствовать. uu-parsinglib также потерпит неудачу, но проверит дополнительные шаги - он будет соответствовать целой строке и потерпит неудачу, а затем выбросит последний "ab" пара и ошибка снова и т. д. Если у нас есть несколько вложенных правил и забавный ввод текста, это будет иметь огромное значение.

Маленький ориентир

Чтобы доказать, что проблема существует в реальности, рассмотрите следующую грамматику (в псевдокоде - но я думаю, что это очень интуитивно понятно):

pattern = many("ab") + "a"
input   = many(pattern)

Таким образом, в качестве входных данных для нашей программы мы получаем строку, содержащую шаблоны, например, "abababaaba" содержит 2 шаблона "abababa" и "aba".

Давайте сделаем парсеры в обеих библиотеках!

uu-parsinglib:

import Data.Char
import qualified Text.ParserCombinators.UU      as UU
import Text.ParserCombinators.UU                hiding(parse)
import Text.ParserCombinators.UU.BasicInstances hiding (Parser)

import System.TimeIt (timeIt)

pa = pSym 'a'
pb = pSym 'b'
pTest = pList $ pList_ng ((\x y -> [x,y]) <$> pa <*> pb) <* pa

main :: IO ()
main = do
    timeIt maininner
    return ()

maininner = do
    let (x,e) = UU.parse ((,) <$> pTest <*> pEnd) (createStr (LineColPos 0 0 0) (concat $ replicate 1000 (concat (replicate 1000 "ab") ++ "a")))
    print $ length x

Parsec:

import           Control.Applicative
import           Text.Parsec          hiding (many, optional, parse, (<|>))
import qualified Text.Parsec          as Parsec

import System.TimeIt (timeIt)

pa = char 'a'
pb = char 'b'
pTest = many $ many (try ((\x y -> [x,y]) <$> pa <*> pb)) <* pa

main :: IO ()
main = do
    timeIt maininner2
    return ()

maininner2 = do
    let Right x = Parsec.runParser pTest (0::Int) "test" $ (concat $ replicate 1000 (concat (replicate 1000 "ab") ++ "a"))
    print $ length x

Результат? uu-parsinglib медленнее> 300%:

uu-parsinglib - 3.19s
Parsec        - 1.04s

(составлено с ghc -O3 флаг)

Answer 1

Чтобы понять тонкости, важно понять различия между конструкцией try в Haskell и стратегией не жадного синтаксического анализа, используемой в uu-parsinglib. По сути, последняя попытка, которая просто смотрит вперед на один символ. В этом отношении он менее мощный, чем конструкция try из Parsec, в которой вы указываете, что конкретная конструкция должна присутствовать полностью. И тогда есть основополагающая другая общая стратегия. Parsec использует стратегию обратного отслеживания с явными попытками фиксации, тогда как uu-parsinglib использует стратегию первой ширины со случайным прогнозированием на один символ.

Поэтому неудивительно, что между ними существует разница во времени. В случае Parsec решается, что опробованная альтернатива действительно применяется после того, как увидела полную конструкцию (два символа), тогда как жадный uu-parsinglib решает, что это должна быть правильная альтернатива после успешного просмотра первого символа. И этот вывод может быть неоправданным.

Если вы переходите к стратегии "в ширину", которую использует uu-parsinglib, нужно отслеживать несколько альтернатив одновременно, и на это нужно время. Два варианта, вдвое больше времени и т. Д.

Преимущество Parsec заключается в том, что вы можете настроить анализатор обратного отслеживания путем свободного использования конструкций try и размещения альтернатив в правильном порядке, но вы также с большей вероятностью будете задавать вопросы в списке рассылки о том, почему ваши анализаторы не работают должным образом, Вы не столько пишете грамматику, сколько пишете парсер. Uu-parsinglib начинается с другого конца спектра: мы пытаемся принять довольно большую коллекцию грамматик (и парсеры, подразумеваемые ими).

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

Answer 2

Поведение, которое вы описываете (используя pList_ng) действительно применяется к другим синтаксическим анализаторам (таким как простой метод списка успешных действий, описанный, например, в комбинаторах Jeroen Fokker's Functional), но не к uu-parsinglib. Библиотека использует стратегию первой ширины, чтобы избежать утечек пространства (в результате зависания всего ввода, как в случае использования стратегии первой глубины). Вот почему я спросил, создавали ли вы контрольный пример или смотрели на внутренности.

Более подробное описание см. В документе Text.ParserCombinators.UU.README (и, возможно, после этого исходный код). Здесь я буду использовать pExample2 сделать набросок процесса разбора. Ветвление происходит в pList_ng (в pTest), который использует <|> распознать либо пустую строку, либо другой элемент. Так как pTest сопровождается paвместо пустой строки альтернативой парсинга другого элемента фактически является распознавание одного 'a',

Когда мы видим первый 'a' на входе обе альтернативы могут успешно проанализировать этот символ. Далее мы видим 'b', Теперь альтернатива, которая разбирает только один 'a' не может добиться дальнейшего прогресса, поэтому мы отбрасываем это. Осталась одна альтернатива: распознающая (список) 'a' с последующим 'b' (pTest). Далее идет еще один 'a'и есть еще две альтернативы для рассмотрения. Но тогда мы видим 'b' и, опять же, мы можем немедленно отказаться от второго варианта. Тогда есть один последний персонаж, 'a', что еще раз означает две альтернативы. Но теперь мы доходим до конца строки и получаем только альтернативу pa признать финал a приводит к успешному анализу.

Учитывая альтернативный вклад "ababab"мы видим, что pa Альтернатива снова терпит неудачу, когда мы добираемся до финала 'b'так что только pTest альтернатива остается. Это заканчивается, потому что мы дошли до конца, а затем pa (следующий pTest в pExample2) не получается, поэтому мы получаем ошибку.

В любом случае, uu-parsinglib нужно только хранить альтернативы в памяти, которые еще не вышли из строя, а стратегия в ширину гарантирует, что все альтернативы оцениваются в слежении, поэтому нет необходимости держаться за первый 'a' а также 'b' пока не будет достигнут конец строки, и он не будет совпадать с целой строкой перед возвратом.

Редактировать:

Из того, что я понял о Parsec, это действительно менее эффективно, потому что Parsec не учитывает pa до тех пор pTest отделки. Раздел 5.1 в статье говорит несколько слов о чем-то вроде try для uu-parsinglib, включая некоторые возражения. Необработанная скорость не является основной целью, и однажды я увидел презентацию некоторых тестов, где uu-parsinglib также не вышел на первое место, но в целом он показал себя достаточно хорошо. Если скорость так важна для этого компилятора, который вы упомянули, и если вам не нужны какие-либо дополнительные функции, такие как онлайн-результаты или исправление ошибок, возможно, вам стоит просто придерживаться Parsec? (Или сначала найдите более подробные тесты.)

Очевидно, что между этими двумя библиотеками есть существенные различия, поэтому я не удивлен, что Parsec в некоторых случаях работает быстрее, хотя разница в этом случае действительно довольно большая. Может быть, есть способ настроить версию uu-parsinglib дальше (без изменения внутренних компонентов, на что намекает этот раздел о жадном разборе в статье), но это не очевидно (для меня в любом случае).

Ну, одна вещь, которую вы могли бы сделать, это переписать грамматику:

pTest' = pList $ pa *> pList ((\x y -> [x,y]) <$$> pb <*> pa)

Я думаю, что для Parsec было бы следующее (но это, кажется, делает его медленнее):

pTest' = many $ pa *> many (flip (\x y -> [x,y]) <$> pb <*> pa)

Это помогает, но недостаточно, чтобы побить версию Parsec. Используя ваш тест, я получаю следующие результаты:

 uu-parsinglib (pTest)  - 1.98s
 uu-parsinglib (pTest') - 1.11s
 Parsec (pTest)         - 0.59s
 Parsec (pTest')        - 0.67s