Parsec не разбирает это выражение, и я не могу понять, почему

Я пытаюсь написать парсер для простого языка; в основном прямо сейчас у него есть литералы, ifs, применение функций и многое другое.

Вот код, который у меня есть:

import Text.ParserCombinators.Parsec
import Control.Monad (liftM)

data Expr = Term Term
          | Apply Expr Expr
          | If Expr Expr Expr
          deriving (Show)

data Term = Bool Bool
          | Num Double
          | String String
          | Identifier String
          | Parens Expr
          deriving (Show)

sstring s = spaces >> string s
schar c = spaces >> char c

keyword k = do
  kw <- try (sstring k)
  notFollowedBy alphaNum
  return kw

pBool :: Parser Bool
pBool = do
  bool <- keyword "True" <|> keyword "False"
  case bool of
    "True" -> return True
    "False" -> return False

pDouble :: Parser Double
pDouble = do
  ds <- many1 digit
  dot <- optionMaybe $ char '.'
  case dot of
    Nothing -> return $ read ds
    _ -> do
      ds' <- many1 digit
      return $ read (ds ++ "." ++ ds')

pString :: Parser String
pString = do
  char '"'
  str <- many1 $ noneOf "\""
  char '"'
  return str

pIdentifier :: Parser String
pIdentifier = spaces >> many1 letter

pParens :: Parser Expr
pParens = do
  schar '('
  expr <- pExpr
  schar ')'
  return expr

pTerm :: Parser Term
pTerm = try (liftM Bool pBool)
  <|> try (liftM Num pDouble)
  <|> try (liftM String pString)
  <|> try (liftM Identifier pIdentifier)
  <|> try (liftM Parens pParens)

-- TODO: make this left-associative
pApply :: Parser Expr
pApply = do
  term <- pTerm'
  mApp <- spaces >> optionMaybe pApply
  return $ case mApp of
    Just app -> Apply term app
    Nothing -> term

-- pulls "parens" expressions out of terms
pTerm' :: Parser Expr
pTerm' = do
  term <- pTerm
  case term of 
    Parens expr -> return expr
    otherwise -> return $ Term term

pIf :: Parser Expr
pIf = do
  keyword "if"
  cond <- pExpr
  keyword "then"
  ifTrue <- pExpr
  keyword "else"
  ifFalse <- pExpr
  return $ If cond ifTrue ifFalse

pExpr :: Parser Expr
pExpr = try pIf <|> pApply

test parser = parse parser ""

Теперь, если я попытаюсь проанализировать одно числовое выражение в ghci, все будет хорошо:

> test pExpr "1"
Right (Term (Num 1.0))

Здорово! И многие другие вещи тоже работают:

> test pExpr "1.234"
Right (Term (Num 1.234))
> test pApply "neg 1"
Right (Apply (Term (Identifier "neg")) (Term (Num 1.0)))
> test pExpr "f g 1"
Right (Apply (Term (Identifier "f")) (Apply (Term (Identifier "g")) (Term (Num 1.0))))

Но теперь, если я попытаюсь разобрать оператор if, я получу ошибку:

> test pIf "if 1 then 2 else 3"
Left (line 1, column 4):
unexpected "1"
expecting space, "if", "True", "False", letter or "("

Это не имеет для меня смысла! Давайте рассмотрим это, взглянув на правило разбора оператора if:

Разбираем ключевое слово "if" (без проблем). Затем для следующего синтаксического анализа (1) нам нужно проанализировать pExpr, который сам может быть pIf или pApply. Ну, это не если, поэтому мы пытаемся применить, которое само пытается pTerm', которое пытается pTerm, которое пытается pBool, которое терпит неудачу, а затем pNum, которое успешно! Затем pTerm преуспевает с Num 1.0, pTerm' преуспевает с Term (Num 1.0), что означает pExpr преуспевает с Term (Num 1.0), и это передается в переменную cond... верно? Ну, явно нет, потому что он терпит неудачу! Я не понимаю, почему это должно потерпеть неудачу здесь.


person limp_chimp    schedule 23.10.2013    source источник


Ответы (2)


У вас проблемы с тем, что вы не съедаете все пробелы, а then и else интерпретируются как идентификаторы. Правило lexeme удобно для использования пробелов после любого токена. Ваш pIdentifier должен явно проверить, не проглотил ли он зарезервированное слово. Я исправил эти проблемы и взял на себя смелость использовать некоторые из существующих комбинаторов и перешел на аппликативный стиль...

import Text.ParserCombinators.Parsec
import Control.Applicative hiding ((<|>))

data Expr = Term Term
          | Apply Expr Expr
          | If Expr Expr Expr
          deriving (Show)

data Term = Bool Bool
          | Num Double
          | String String
          | Identifier String
          | Parens Expr
          deriving (Show)

keywords = ["if", "then", "else", "True", "False"]
lexeme p = p <* spaces
schar = lexeme . char

keyword k = lexeme . try $
  string k <* notFollowedBy alphaNum

pBool :: Parser Bool
pBool = (True <$ keyword "True") <|> (False <$ keyword "False")

pDouble :: Parser Double
pDouble = lexeme $ do
  ds <- many1 digit
  option (read ds) $ do
    char '.'
    ds' <- many1 digit
    return $ read (ds ++ "." ++ ds')

pString :: Parser String
pString = lexeme . between (char '"') (char '"') . many1 $ noneOf "\""

pIdentifier :: Parser String
pIdentifier = lexeme . try $ do
  ident <- many1 letter
  if ident `elem` keywords
    then unexpected $ "reserved word " ++ show ident
    else return ident

pParens :: Parser Expr
pParens = between (schar '(') (schar ')') pExpr

pTerm :: Parser Term
pTerm = choice [ Bool       <$> pBool
               , Num        <$> pDouble
               , String     <$> pString
               , Identifier <$> pIdentifier
               , Parens     <$> pParens
               ]

-- TODO: make this left-associative
pApply :: Parser Expr
pApply = do
  term <- pTerm'
  option term $
    Apply term <$> pApply

-- pulls "parens" expressions out of terms
pTerm' :: Parser Expr
pTerm' = do
  term <- pTerm
  case term of
    Parens expr -> return expr
    _ -> return $ Term term

pIf :: Parser Expr
pIf = If <$ keyword "if"   <*> pExpr 
         <* keyword "then" <*> pExpr
         <* keyword "else" <*> pExpr

pExpr :: Parser Expr
pExpr = pIf <|> pApply

test parser = parse (spaces *> parser <* eof) ""
person pat    schedule 23.10.2013
comment
Превосходно! Это действительно круто. Я новичок в этом аппликативном стиле; Я должен буду изучить это подробнее. - person limp_chimp; 23.10.2013

Вам нужно внести несколько изменений.

pExpr :: Parser Expr
pExpr = try pIf <|> pTerm'


pIf :: Parser Expr
pIf = do
  keyword "if"
  spaces
  cond <- pExpr
  keyword "then"
  spaces
  ifTrue <- pExpr
  keyword "else"
  spaces
  ifFalse <- pExpr
  return $ If cond ifTrue ifFalse
person Ankur    schedule 23.10.2013
comment
Это правильно анализирует базовый оператор if; однако нельзя отнимать опцию pApply у pExpr. В конце концов, применение функции — это вполне допустимое выражение. И нам нужно уметь говорить, например, if even a then "even" else "odd". Однако хороший призыв к добавлению пробелов. Одна из самых больших неприятностей при использовании Parsec: P - person limp_chimp; 23.10.2013