Как выполнить поиск с помощью комбинаторов парсера? - PullRequest
Новая
       64

Как выполнить поиск с помощью комбинаторов парсера?

1 голос
/ 11 октября 2019

У меня есть список парсеров, например, [string "a",string "ab"], которые "перекрываются". Я не могу изменить ни сами парсеры, ни их порядок.

С помощью этих парсеров я хочу проанализировать последовательность токенов, каждый из которых будет точно соответствовать одному из парсеров, например, "aaaab", "ab", "abab", но не "abb"

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

Я дошел до этого далеко: 

import Control.Applicative
import Text.Trifecta

parsers = [string "a",string "ab"]

parseString (many (choice parsers) <* eof) mempty "aab"

Это не удалось, потому что он будет анализировать "a" оба раза, а не возвращатьсяпотому что choice этого не делает. Более того, string "a" успешно выполнялся оба раза, поэтому потребляемый ввод, вероятно, больше не может быть получен. Как реализовать синтаксический анализатор, который может возвращать и выводить список результатов анализа, например, Success ["a","ab"]?

Если мне требуется, чтобы вход разделил токены, я все равно не могу заставить его работать:

Это работает: 

parseString (try (string "a" <* eof) <|> (string "ab" <*eof)) mempty "ab"

Но это не так: 

parseString (try (foldl1 (<|>) $ map (\x -> x <* eof) parsers)) mempty "ab"

1 Ответ

1 голос
/ 11 октября 2019

Уровень try выполнен слишком высоким. Вы должны выполнить это на отдельных парсерах. Например: 

parseString (foldl1 (<|>) $ map (\x -> <b>try</b> (x <* eof)) parsers) mempty "ab"

В исходном парсере вы написали: 

parseString (<b>(</b>try (string "a" <* eof)<b>)</b> <|> (string "ab" <*eof)) mempty "ab"

Обратите внимание, что левый операнд <|> равен try (string "a" <* eof) с включенным try.

тогда как в той, которую вы выполняли с foldl1, вы написали: 

parseString (try <b>(</b>(string "a" <* eof) <|> (string "ab" <*eof)<b>)</b>) mempty "ab"

Так что здесь try не является частью левого операнда. В результате, если первый синтаксический анализатор дает сбой, «курсор» не вернется к точке, в которой он принял решение попробовать первый операнд.

Мы можем улучшить вышеупомянутое, используяasum :: (Foldable t, Alternative f) -> t (f a) -> f a: 

import Data.Foldable(asum)

parseString (asum (map (\x -> try (x <* eof)) parsers)) mempty "ab"
...