почему parsecs "выбор" комбинатор, казалось бы, застрял на первом выборе? - PullRequest
Новая
       15

почему parsecs "выбор" комбинатор, казалось бы, застрял на первом выборе?

7 голосов
/ 18 апреля 2011

Посмотрев пример кода CSV в реальном мире на Haskell, я попытался создать небольшой анализатор XML. Но закрывайте теги с ошибками «неожиданно» / «». Можете ли вы сказать мне, почему мой синтаксический анализатор "closeTag" не работает (или, возможно, никогда не вызывается)? Спасибо! 

import Text.ParserCombinators.Parsec

xmlFile = manyTill line eof
line = manyTill tag eol
eol = char '\n'

word = many1 (noneOf "></")

tag = choice [openTag, closeTag, nullTag, word]

nullTag = between (char '<') (string "/>") word
closeTag = between (string "</") (char '>') word
openTag = between (char '<') (char '>')  tagContent
attrval = between (char '"') (char '"') word

atts = do {
        (char ' ')
        ; sepBy attr (char ' ')
}

attr = do {
                word
                ; char '='
                ; attrval
        }

tagContent = do {
                w <- word
                ; option []  atts
                ; return w
        }

parseXML :: String -> Either ParseError [[String]]
parseXML input = parse xmlFile "(unknown)" input

main =
    do c <- getContents
       case parse xmlFile "(stdin)" c of
            Left e -> do putStrLn "Error parsing input:"
                         print e
            Right r -> mapM_ print r

1 Ответ

15 голосов
/ 18 апреля 2011

Стратегия Parsec - это, по сути, LL (1), что означает, что он «фиксирует» текущую ветвь всякий раз, когда используется какой-либо вход. Ваш синтаксический анализатор openTag потребляет < с его char '<', что означает, что, если он видит > вместо /, весь анализ завершается неудачей вместо попытки нового выбора. Если openTag не потребляет никакого ввода и потерпит неудачу, будет выбран другой вариант. Parsec делает это для эффективности (альтернатива - экспоненциальное время!) И для разумных сообщений об ошибках.

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

tag = word <|> (char '<' >> tagbody)
    where
    tagbody = do
        content <- tagcontent
        choice [ string "/>", char '>' ]

Ошибки и стиль по модулю (мой мозг сейчас немного жарен :-P).

Другой способ, который локально изменяет семантику parsec (за счет вышеупомянутых сообщений об ошибках и эффективности - но обычно это не так уж и плохо, поскольку он локальный), - использовать комбинатор try, который позволяет анализатору потреблять ввод и по-прежнему не «мягко», поэтому можно попробовать другой выбор: 

nulltag = try $ between (char '<') (string "/>") word
-- etc.

Иногда использование try проще и проще, чем факторинг, как описано выше, что может скрыть «глубокую структуру» языка. Это стилистический компромисс.

...