2
\$\begingroup\$

In Haskell, I tried to implement a parser for expressions containing hyperoperations, and finally succeeded. Valid expressions shall contain:

  • Parentheses.

  • Nonnegative integers.

  • Addition represented by +. It has precedence of 6, and its associativity shall be exploited.

  • Multiplication represented by *. It has precedence of 7, and its associativity shall be exploited.

  • Exponentiation represented by ^. It has precedence of 8.

  • Tetration represented by ^^. It has precedence of 9.

  • Pentation represented by ^^^. It has precedence of 10.

  • ad infinitum.

I was struggling for months to implement this with ReadPrec. It was truly a "Eureka" moment when I found that I have a workaround:

import Control.Monad
import Text.ParserCombinators.ReadPrec
import Text.Read
import Text.Read.Lex

hyperOp :: Int -> Integer -> Integer -> Integer
hyperOp 0 _ y = y + 1
hyperOp 1 x y = x + y
hyperOp 2 x y = x * y
hyperOp 3 x y = x ^ y
hyperOp n x 0 = 1
hyperOp n x y = hyperOp (n-1) x (hyperOp n x (y-1))

parseHyperOp :: Int -> ReadPrec Integer
parseHyperOp opn = parens . choice $
    lift readDecP
    : prec 6 (do
        m <- step (parseHyperOp opn)
        Symbol "+" <- lexP
        n <- parseHyperOp opn
        return (m + n))
    : prec 7 (do
        m <- step (parseHyperOp opn)
        Symbol "*" <- lexP
        n <- parseHyperOp opn
        return (m * n))
    : fmap (\c -> prec (7 + c) $ do
        m <- step (parseHyperOp opn)
        Symbol op <- lexP
        guard (replicate c '^' == op)
        n <- step (parseHyperOp opn)
        return (hyperOp (2 + c) m n)
        ) [1 .. opn]

highestOp :: String -> Int
highestOp "" = 0
highestOp ('^':str) = let
    (str1, str2) = span ('^'==) str
    in max (1 + length str1) (highestOp str2)
highestOp (_  :str) = highestOp str

parseOp :: Prec -> ReadS Integer
parseOp c str = readPrec_to_S (parseHyperOp (highestOp str)) c str

The trick is to find the highest operation within the input string. That makes the choice finite.

Still, I think it's quite ugly to use readPrec_to_S. Can this be implemented without using readPrec_to_S and co?

\$\endgroup\$
3
  • \$\begingroup\$ "Can this be implemented without using readPrec_to_S and co?" I would cheekily answer "remove the last two lines". Why are you using ReadS and what is "and co"? And are you aware that a common way to parse arithmetic expressions is to use a stack? \$\endgroup\$ – Li-yao Xia Feb 7 at 17:12
  • \$\begingroup\$ @Li-yaoXia parseHyperOp is just an auxiliary function for implementing parseOp, and is not to be used on its own. I tried implementing parseOp without using readPrec_to_S and readS_to_Prec because using them might cause potential runtime errors thereafter (say, by invoking gather). And I don't know whether Haskell has stacks. \$\endgroup\$ – Dannyu NDos Feb 7 at 20:16
  • \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?. \$\endgroup\$ – BCdotWEB Feb 8 at 8:42
2
\$\begingroup\$

A simple rule of thumb is that you should never use readS_to_Prec and readS_to_P. Consider that once you've converted a parser to a ReadS to run it, there is no way back. (One handwavy explanation is that those functions are really dirty hacks, which is also why gather is undefined when they are used.)

Under those constraints, the only place where you can find out the maximal level opn of hyperoperators is at the very top level where you actually apply your parser to a string; that is the one location where you can scan the string to compute opn. That means that all your parsers need to be parameterized by opn in order to pass it down to parseHyperOp.

parseOp :: Int -> P.ReadP Integer
parseOp opn = readPrec_to_P (parseHyperOp opn) 0

-- Top-level runner for parsers parameterized by opn
runP :: (Int -> P.ReadP a) -> ReadS a
runP parser str =
  let opn = highestOp str in
  P.readP_to_S (parser opn) str

example = runP parseOp "(1 + 2) ^ 3 + 2 ^ 2"

Having an infinite number of precedence levels makes top-down parsing (the popular approach using parser combinators) rather problematic, since there isn't really a "top" to start from. Consider giving up that feature (by making all operators beyond a certain level non-associative at the same level), or switching to a bottom-up parsing strategy.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.