Можно ли реализовать этот парсер исключительно в ReadPrec?

В Haskell я попытался реализовать парсер для выражений, содержащих гипероперации, и наконец это удалось. Действительные выражения должны содержать:

• Скобки.

• Неотрицательные целые числа.

• Дополнение представлено +. Он имеет приоритет 6, и его ассоциативность должна использоваться.

• Умножение представлено *. Он имеет приоритет 7, и его ассоциативность должна использоваться.

• Возведение в степень, представленное ^. Он имеет приоритет 8.

• Тетрация представлена ^^. Он имеет приоритет 9.

• Пентация представлена ^^^. Он имеет приоритет 10.

• до бесконечности.

Я месяцами пытался реализовать это с помощью ReadPrec. Это был действительно момент «Эврики», когда я обнаружил, что у меня есть обходной путь:

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

Хитрость заключается в том, чтобы найти самую высокую операцию во входной строке. Это делает choice конечно.

Тем не менее, я считаю, что использовать readPrec_to_S. Можно ли это реализовать без использования readPrec_to_S и компания?

Простое практическое правило: никогда не используйте readS_to_Prec и readS_to_P. Учтите, что после преобразования парсера в ReadS запустить его, пути назад нет.

При этих ограничениях единственное место, где можно узнать максимальный уровень opn of hyperoperators находится на самом верхнем уровне, где вы фактически применяете свой синтаксический анализатор к строке; это единственное место, где вы можете сканировать строку для вычисления opn. Это означает, что все ваши парсеры должны быть параметризованы opn чтобы передать это 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"

Наличие бесконечного числа уровней приоритета делает анализ сверху вниз (популярный подход с использованием комбинаторов синтаксического анализа) довольно проблематичным, поскольку на самом деле нет «вершины», с которой можно было бы начать. Рассмотрите возможность отказа от этой функции (сделав все операторы сверх определенного уровня неассоциативными на одном уровне) или переключившись на восходящая стратегия синтаксического анализа.