Парсек зависает при использовании buildExpressionParser

Я пытаюсь создать базовый синтаксический анализатор математических уравнений с помощью Parsec, и у меня возникают проблемы с использованием функции buildExpressionParser.

Я создал функцию parsecParse, но она просто зависает навсегда, когда я вызываю ее в ghci: parse parsecParse "" "200*6". Я не могу понять, почему. Любые идеи?

module Equation where

import Control.Applicative hiding (many, (<|>))

import Text.Parsec.Char (char, digit)
import Text.Parsec.Combinator (many1, option)
import Text.Parsec.Expr (Assoc (..), Operator (..), buildExpressionParser)
import Text.Parsec.Prim ((<|>), try)
import Text.Parsec.String (Parser)

data Equation = Leaf Double | Tree Op Equation Equation deriving (Show)
data Op = Plus | Minus | Multiply | Divide deriving (Show)

parsecParse :: Parser Equation
parsecParse = try parseOperator <|> parseDouble

parseDouble :: Parser Equation
parseDouble = fmap (Leaf . read) $ (++) <$> integer <*> fraction
    where integer  = many1 digit
          fraction = option "" $ (:) <$> char '.' <*> many1 digit

parseOperator :: Parser Equation
parseOperator = buildExpressionParser table parsecParse
    where table     = [[ getOp '*' Multiply, getOp '/' Divide ],
                       [ getOp '+' Plus,     getOp '-' Minus ]]
          getOp c o = Infix (char c >> return (Tree o)) AssocLeft

haskell parsec
person Blake Haswell    schedule 12.08.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы получаете проблемы, потому что parseOperator рекурсивно возвращается к самому себе в крайнем левом положении, что Parsec не может обработать напрямую и что дает бесконечную рекурсию.

Последним аргументом buildExpressionParser должен быть синтаксический анализатор, который анализирует более «базовые» элементы.

Можно косвенно рекурсировать на parseOperator, например. для обработки элементов в скобках, но не таким образом, чтобы он оказывался в самом левом положении самого себя.

person Ørjan Johansen    schedule 12.08.2014
comment
Я немного запутался, потому что примеры, которые я видел[1][2], также рекурсивно передают себя buildExpressionParser. В чем разница между тем, что они делают, и тем, что я пытаюсь сделать? [1]: hackage.haskell.org/ package/parsec-3.1.5/docs/ [2]: blog.moertel.com/posts/ - person Blake Haswell; 12.08.2014
comment
Учитывая это, если я изменю свою функцию на parsecParse = char '(' *> parseOperator <* char ')' <|> parseDouble и вызову ее с помощью parse parseOperator "" "200*6+5", тогда все будет работать. - person Blake Haswell; 12.08.2014