Парсек Haskell, анализирующий строку объектов
У меня есть список, который я должен проанализировать, где все кроме последнего элемента должны быть проанализированы одним синтаксическим анализатором, и последний элемент должен быть проанализирован другим синтаксическим анализатором.
a = "p1 p1b ... p2"
or
a = "p2"
Первоначально я попробовал
parser = do parse1 <- many parser1
parse2 <- parser2
return AParse parse1 parse2
Проблема состоит в том, что parse1 может использовать вход parse2. Так parse1 всегда использует весь список и отпуск parse2 ни с чем.
Существует ли способ сказать, чтобы применить parse1 ко всему помимо последнего элемента в строке и затем применить parse2?
4 ответа
Как насчет:
parseTrain car caboose = choice
[ fmap (:[]) $ try (caboose `endBy` eof),
, liftM2 (:) car (parseTrain car caboose)
[
Eof меня беспокоит, так как это делает этот синтаксический анализатор не композиционным. Т.е. Вы не можете сказать:
char '(' >> parseTrain p1 p2 >> char ')'
Выполнить это компилятивно для синтаксического анализатора очень сложно. Как он должен знать, что нужно переходить к char ')', не пытаясь при каждой возможности и не проверяя, потерпит ли он неудачу? Это может привести к экспоненциальному увеличению времени.
Если вам нужно, чтобы она была композиционной, есть ли в вашей проблеме какая-то дополнительная структура, которую вы можете использовать? Можете ли вы, например, проанализировать список всех элементов, а затем обработать последний постфактум?
Если вы можете разложить на множители 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 позволяет вам использовать комбинаторы между и endBy для выполнения работа для вас. Наконец, try существует для того, чтобы, если parser1 и parser2 совпадают с общим префиксом, endBy выполнит правильное полное резервное копирование в начало. общего префикса.
В зависимости от ваших парсеров, возможно, вы можете оставить соответствие пунктуации внутри ваших суб-парсеров, и все, что вам понадобится, это try вокруг parser1 :
parseTest = do parse1 <- many (try parser1)
parse2 <- parser2
return AParse parse1 parse2
Я как бы объединил два подхода:
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
Я думаю, что это сработает для моих целей. Спасибо!