Разбор арифметического выражения с Haskell Parsec - PullRequest
Новая
       43

Разбор арифметического выражения с Haskell Parsec

0 голосов
/ 22 сентября 2018

Я пишу арифметический парсер для обработки выражений типа "1 + 2-3".Я использую этот пост в качестве ссылки.Чтобы обработать левую ассоциативность и приоритет, я пишу парсер с парсек в соответствии с этим BNF (из сообщения в блоге). 

<exp> ::= <term> { ("+" | "-") <term> }
<term> ::= <factor> { ("*" | "/") <factor> }
<factor> ::= "(" <exp> ")" | <unary_op> <factor> | <int>

Это мой код парсера. 

parseExp :: Parser Exp
parseExp = do
  t1 <- parseTerm
  loop t1
  where termSuffix t1 = do
          op <- lexeme $ oneOf "+-"
          t2 <- parseTerm
          case op of
            '+' -> termSuffix (Binary Plus t1 t2)
            '-' -> termSuffix (Binary Minus t1 t2)
        loop t = termSuffix t <|> return t

parseTerm :: Parser Exp
parseTerm = do
  f1 <- parseFactor
  loop f1
  where factorSuffix f1 = do
          op <- lexeme $ oneOf "*/"
          f2 <- parseFactor
          case op of
            '*' -> factorSuffix (Binary Mul f1 f2)
            '/' -> factorSuffix (Binary Div f1 f2)
        loop t = factorSuffix t <|> return t

parseFactor :: Parser Exp
parseFactor = parseConst <|> parseParen <|> parseUnary

parseParen = do
  void $ lexeme $ char '('
  e <- parseExp
  void $ lexeme $ char ')'
  return e

parseUnary :: Parser Exp
parseUnary = do
  op <- lexeme $ oneOf "!~-"
  f <- parseFactor
  case op of
    '!' -> return $ Unary LogNeg f
    '~' -> return $ Unary BitCompl f
    '-' -> return $ Unary ArithNeg f

parseConst :: Parser Exp
parseConst = do
  i <- many1 digit
  return (Const $ read i)

Я также использовалэтот учебный код в качестве ссылки. учебник 

simpleExpr7 :: Parser SimpleExpr
simpleExpr7 = do
    -- first parse a term
    e <- term7
    -- then see if it is followed by an '+ expr' suffix
    maybeAddSuffix e
  where
    -- this function takes an expression, and parses a
    -- '+ expr' suffix, returning an Add expression
    -- it recursively calls itself via the maybeAddSuffix function
    addSuffix e0 = do
        void $ lexeme $ char '+'
        e1 <- term7
        maybeAddSuffix (Add e0 e1)
    -- this is the wrapper for addSuffix, which adapts it so that if
    -- addSuffix fails, it returns just the original expression
    maybeAddSuffix e = addSuffix e <|> return e

Мой код не работает.Этот код работает следующим образом. 

*Main CodeGen Parser> parseWithEof parseExp "-2"
Right (Unary ArithNeg (Const 2))
*Main CodeGen Parser> parseWithEof parseExp "(2)"
Right (Const 2)
*Main CodeGen Parser> parseWithEof parseExp "-!(((2)))"
Right (Unary ArithNeg (Unary LogNeg (Const 2)))
*Main CodeGen Parser> parseWithEof parseExp "1+2"
Left (line 1, column 4):
unexpected end of input
expecting digit
*Main CodeGen Parser> parseWithEof parseExp "1+2+3"
Left (line 1, column 6):
unexpected end of input
expecting digit
*Main CodeGen Parser> parseWithEof parseExp "1+2*3"
Left (line 1, column 6):
unexpected end of input
expecting digit

Я не могу понять, почему это приводит unexpected end of input.

1 Ответ

0 голосов
/ 22 сентября 2018

Рассмотрим разбор 1+2.В parseExp это анализирует 1 в t1 = Const 1 и затем входит в цикл loop (Const 1).Цикл пробует первую альтернативу termSuffix (Const 1), которая успешно анализирует оператор +, следующий член t2 = Const 2, а затем возвращается к termSuffix (Binary Plus (Const 1) (Const 2)), который ожидает либо +, либо -.Разбор не удаётся.Вместо того, чтобы вернуться к termSuffix, вы должны вернуться к loop, чтобы разрешить один член после первого +: 

parseExp :: Parser Exp
parseExp = do
  t1 <- parseTerm
  loop t1
  where termSuffix t1 = do
          op <- lexeme $ oneOf "+-"
          t2 <- parseTerm
          case op of
            -- *** use `loop` here, not `termSuffix` ***
            '+' -> loop (Binary Plus t1 t2)
            '-' -> loop (Binary Minus t1 t2)
        loop t = termSuffix t <|> return t

После внесения аналогичного изменения в parseTerm, ваш тестдела все работают нормально.

...