# Can this parser (concerning about infinite hierarchy of operators) be implemented purely in ReadPrec?

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.

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

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?

• "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? Feb 7 '21 at 17:12
• @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. Feb 7 '21 at 20:16
• 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?. Feb 8 '21 at 8:42

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 parser str =
let opn = highestOp str in

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.