Парсек на Haskell разбирает строку предметов

Question

У меня есть список, который мне нужно проанализировать, где все, кроме последнего элемента должны быть проанализированы одним анализатором, а последний элемент должен быть проанализирован другим анализатором.

a = "p1 p1b ... p2"
or
a = "p2"

Первоначально я пытался

parser = do parse1 <- many parser1
            parse2 <- parser2
            return AParse parse1 parse2

Проблема в том, что parse1 может использовать вход parse2. Таким образом, parse1 всегда использует весь список и оставляет parse2 ни с чем.

Есть ли способ сказать применить parse1 ко всему, кроме последнего элемента в строке, а затем применить parse2?

Answer 1

Как насчет:

parseTrain car caboose = choice
    [ fmap (:[]) $ try (caboose `endBy` eof), 
    , liftM2 (:) car (parseTrain car caboose) 
    [

Eof вызывает меня, так как это делает этот парсер не композиционным. То есть Вы не могли бы сказать:

char '(' >> parseTrain p1 p2 >> char ')'

Выполнение этого в обязательном порядке очень сложно для парсера. Как он должен знать, чтобы перейти к символу ')', не пытаясь при каждой возможности и увидеть, если он потерпит неудачу? Это может привести к экспоненциальному времени.

Если вам нужно, чтобы он был композиционным, имеет ли ваша проблема какую-то дополнительную структуру, которую вы можете использовать? Можете ли вы, например, проанализировать список всех элементов и затем обработать последний после факта?

Answer 2

Если вы можете вычислить parser1 так, чтобы это было определено так:

parser1 = (try parser2) <|> parser1extra

Тогда проблема становится списком parser1extra или parser2, который должен закончиться позже. Вы можете кодировать это как:

parserList =
    liftM2 (:) (try parser1extra) parserList
    <|>
    liftM2 (:) (try parser2) (option [] parserList)

Вы можете или не можете нуждаться в вызовах try в зависимости от того, имеют ли эти парсеры какое-либо перекрытие префиксов.

Если вы не хотите, чтобы возвращаемое значение было списком, а вместо этого вашим базовым значением AParse, вы можете переписать его следующим образом:

parserList =
    do
        a <- try parser1extra
        prefix a parserList
    <|>
    do
        a <- try parser2
        option (AParse [] a) (prefix a parserList)

    where prefix a p = do
            (AParse as t) <- p
            return $ (AParse (a:as) t)

Или полный пример:

import Control.Monad
import Text.ParserCombinators.Parsec

parseNum = do { v <- many1 digit; spaces; return v }
parseWord = do { v <- many1 letter; spaces; return v }
parsePart = parseNum <|> parseWord

parsePartListEndingInWord =
    liftM2 (:) (try parseNum) parsePartListEndingInWord
    <|>
    liftM2 (:) (try parseWord) (option [] parsePartListEndingInWord)

На самом деле, вызовы try в этом случае не нужны, поскольку parseNum и parseWord не соответствуют общему префиксу. Обратите внимание, что parsePartListEndingInWord на самом деле не ссылается на parsePart, но вместо этого два параметра, которые составляют определение parsePart

---

(Оригинальный ответ, решение несколько иной ситуации:)

Как насчет чего-то вроде:

parserTest = between (char '[') (char ']') $ do
    p1s <- try parser1 `endBy` char ',' 
    p2 <- parser2
    return $ AParse p1s p2

Удаление пунктуации из ваших анализаторов и повышение их в parseTest позволяет вам использовать комбинаторы between и endBy, чтобы выполнить работу за вас. Наконец, try существует, поэтому, если parser1 и parser2 соответствуют общему префиксу, endBy выполнит правильное полное резервное копирование к началу общего префикса.

В зависимости от ваших синтаксических анализаторов, возможно, вы можете оставить знаки препинания внутри своих подпарасеров, и все, что вам нужно, это a try вокруг parser1:

parseTest = do parse1 <- many (try parser1)
               parse2 <- parser2
               return AParse parse1 parse2

Answer 3

Это поможет:

parser1 `manyTill` (try parser2)

Answer 4

Я как бы соединил два подхода:

parserList = try (do a <- parser2
                     eof
                     return $ AParse [] a)
             <|>
             do a <- parser1
                prefix a parserList
             where
                prefix a p = do
                    (AParse as t) <- p
                    return $ AParse a:as t

Я думаю, что это будет работать для моих целей. Спасибо!