Написание парсера для S-выражений

Question

Я пытаюсь написать парсер для S Expressions у профессора Йорги 2013 homework.

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

Учитывая следующие определения, представленные в домашней:

type Ident = String 

-- An "atom" is either an integer value or an identifier. 
data Atom = N Integer | I Ident 
    deriving Show 

-- An S-expression is either an atom, or a list of S-expressions. 
data SExpr = A Atom 
      | Comb [SExpr] 
    deriving Show 

я написал парсер для Parser Atom и Parser SExpr для A Atom.

parseAtom :: Parser Atom 
parseAtom = alt n i 
    where n = (\_ z -> N z) <$> spaces <*> posInt 
     i = (\ _ z -> I z) <$> spaces <*> ident 

parseAAtom :: Parser SExpr 
parseAAtom = fmap (\x -> A x) parseAtom 

Затем я попытался написать синтаксический анализатор для обработки с Parser SExpr для Comb ... случая:

parseComb :: Parser SExpr 
parseComb = (\_ _ x _ _ _ -> x) <$> (zeroOrMore spaces) <*> (char '(') <*> 
            (alt parseAAtom parseComb) <*> (zeroOrMore spaces) 
             <*> (char ')') <*> (zeroOrMore spaces) 

Если предположить, что parseComb был прав, я мог бы просто сделать использование oneOrMore для Parser [SExpr].

parseCombElements :: Parser [SExpr] 
parseCombElements = oneOrMore parseComb 

Итак, мои две последние функции компиляции, но работает runParser parseComb "(foo)" никогда не заканчивается.

Что не так с моим определением parseComb? Пожалуйста, не дайте мне весь ответ, а скорее намек - на мое собственное обучение.

Answer 1

Я очень подозрительно zeroOrMore spaces, потому spaces, как правило, синтаксический анализатор, который сам разбирает ноль или более пробелов. Это означает, что он может разобрать пустую строку, если в этой точке нет пробелов. В частности, парсер spacesвсегда преуспевает.

Но когда вы применяете zeroOrMore к парсеру, который всегда преуспевает, объединенный синтаксический анализатор никогда не останавливается - потому что zeroOrMore только перестает пытаться повторить попытку после того, как аргумент его анализатора завершится неудачно.

Как и в сторону, Applicative выражения, как (\_ _ x _ _ _ -> x) <$> ... <*> ... <*> ......, которые используют только сингл из subparsers обычно может быть написана более сжато с *> и <* комбинаторов:

... *> ... *> x_parser_here <* ... <* ...