Приоритет оператора в мегапарсек

Question

У меня проблемы с использованием помощника Megaparsec 6 makeExprParser. Кажется, я не могу понять, как связать как двоичный ^, так и унарный - на ожидаемых уровнях приоритета.

Использование этого makeExprParser парсера выражений:

expressionParser :: Parser Expression
expressionParser =
    makeExprParser termParser
      [
        [InfixR $ BinOp BinaryExp <$ symbol "^"],
        [
          Prefix $ MonOp MonoMinus <$ symbol "-",
          Prefix $ MonOp MonoPlus <$ symbol "+"
        ],
        [
          InfixL $ BinOp BinaryMult <$ symbol "*",
          InfixL $ BinOp BinaryDiv <$ symbol "/"
        ],
        [
          InfixL $ BinOp BinaryPlus <$ symbol "+",
          InfixL $ BinOp BinaryMinus <$ symbol "-"
        ]
      ]

Я ожидаю, что эти тесты пройдут:

testEqual expressionParser "1^2" "(1)^(2)"
testEqual expressionParser "-1^2" "-(1^2)"
testEqual expressionParser "1^-2" "1^(-2)"
testEqual expressionParser "-1^-2" "-(1^(-2))"

То есть -1^-2 должен анализироваться так же, как и -(1^(-2)). Вот как, например, Python разбирает его:

>>> 2**-2
0.25
>>> -2**-2
-0.25
>>> -2**2
-4

и Ruby:

irb(main):004:0> 2**-2
=> (1/4)
irb(main):005:0> -2**-2
=> (-1/4)
irb(main):006:0> -2**2
=> -4

Но этот парсер Megaparsec вместо этого вообще не разбирает 1^-2, вместо этого выдает мне полезную ошибку:

(TrivialError (SourcePos {sourceName = \"test.txt\", sourceLine = Pos 1, sourceColumn = Pos 3} :| []) (Just (Tokens ('-' :| \"\"))) (fromList [Tokens ('(' :| \"\"),Label ('i' :| \"nteger\")]))")

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

Если я откорректирую некоторые из приоритетов таблицы операторов следующим образом (перемещая экспоненту после унарного числа -):

expressionParser =
    makeExprParser termParser
      [
        [
          Prefix $ MonOp MonoMinus <$ symbol "-",
          Prefix $ MonOp MonoPlus <$ symbol "+"
        ],
        [InfixR $ BinOp BinaryExp <$ symbol "^"],
        [
          InfixL $ BinOp BinaryMult <$ symbol "*",
          InfixL $ BinOp BinaryDiv <$ symbol "/"
        ],
        [
          InfixL $ BinOp BinaryPlus <$ symbol "+",
          InfixL $ BinOp BinaryMinus <$ symbol "-"
        ]
      ]

тогда я больше не получаю ошибку разбора, но -1^2 неправильно анализирует как (-1)^2 (вместо правильного -(1^2)).

Вот полный автономный анализатор, показывающий проблему (для этого требуется HUnit и, конечно, мегапарсек):

module Hascas.Minimal where

import Data.Void (Void)
import Test.HUnit hiding (test)
import Text.Megaparsec hiding (ParseError)
import Text.Megaparsec.Char
import Text.Megaparsec.Expr
import qualified Text.Megaparsec as MP
import qualified Text.Megaparsec.Char.Lexer as L

data Expression
    = Literal Integer
    | MonOp MonoOperator Expression
    | BinOp BinaryOperator Expression Expression
  deriving (Read, Show, Eq, Ord)

data BinaryOperator
    = BinaryPlus
    | BinaryMinus
    | BinaryDiv
    | BinaryMult
    | BinaryExp
  deriving (Read, Show, Eq, Ord)

data MonoOperator
    = MonoPlus
    | MonoMinus
  deriving (Read, Show, Eq, Ord)

type Parser a = Parsec Void String a
type ParseError = MP.ParseError (Token String) Void

spaceConsumer :: Parser ()
spaceConsumer = L.space space1 lineComment blockComment
  where
    lineComment  = L.skipLineComment "//"
    blockComment = L.skipBlockComment "/*" "*/"

lexeme :: Parser a -> Parser a
lexeme = L.lexeme spaceConsumer

symbol :: String -> Parser String
symbol = L.symbol spaceConsumer

expressionParser :: Parser Expression
expressionParser =
    makeExprParser termParser
      [
        [InfixR $ BinOp BinaryExp <$ symbol "^"],
        [
          Prefix $ MonOp MonoMinus <$ symbol "-",
          Prefix $ MonOp MonoPlus <$ symbol "+"
        ],
        [
          InfixL $ BinOp BinaryMult <$ symbol "*",
          InfixL $ BinOp BinaryDiv <$ symbol "/"
        ],
        [
          InfixL $ BinOp BinaryPlus <$ symbol "+",
          InfixL $ BinOp BinaryMinus <$ symbol "-"
        ]
      ]

termParser :: Parser Expression
termParser = (
        (try $ Literal <$> L.decimal)
    <|> (try $ parens expressionParser))

parens :: Parser a -> Parser a
parens x = between (symbol "(") (symbol ")") x

main :: IO ()
main = do
    -- just to show that it does work in the + case:
    test expressionParser "1+(-2)" $
      BinOp BinaryPlus (Literal 1) (MonOp MonoMinus $ Literal 2)
    test expressionParser "1+-2" $
      BinOp BinaryPlus (Literal 1 ) (MonOp MonoMinus $ Literal 2)

    -- but not in the ^ case
    test expressionParser "1^-2" $
      BinOp BinaryExp (Literal 1) (MonOp MonoMinus $ Literal 2)
    test expressionParser "-1^2" $
      MonOp MonoMinus $ BinOp BinaryExp (Literal 1) (Literal 2)
    test expressionParser "-1^-2" $
      MonOp MonoMinus $ BinOp BinaryExp (Literal 1) (MonOp MonoMinus $ Literal 2)

    -- exponent precedence is weird
    testEqual expressionParser "1^2" "(1)^(2)"
    testEqual expressionParser "-1^2" "-(1^2)"
    testEqual expressionParser "1^-2" "1^(-2)"
    testEqual expressionParser "-1^-2" "-(1^(-2))"
    testEqual expressionParser "1^2^3^4" "1^(2^(3^(4))))"
  where
    test :: (Eq a, Show a) => Parser a -> String -> a -> IO ()
    test parser input expected = do
      assertEqual input (Right expected) $ parse (spaceConsumer >> parser <* eof) "test.txt" input

    testEqual :: (Eq a, Show a) => Parser a -> String -> String -> IO ()
    testEqual parser input expected = do
        assertEqual input (p expected) (p input)
      where
        p i = parse (spaceConsumer >> parser <* eof) "test.txt" i

Можно ли заставить Мегапарсек анализировать эти операторы на уровнях приоритета, которые делают другие языки?

Answer 1

makeExprParser termParser [precN, ..., prec1] создаст синтаксический анализатор восхождения по приоритету, который работает таким образом, что каждый уровень приоритета вызывает следующий более высокий уровень приоритета. Так что, если вы определите его вручную, у вас будет правило для инфиксов + и -, в котором в качестве операндов используется правило mult-and-div. Это, в свою очередь, будет использовать правило префикса в качестве операндов, и это будет использовать правило ^ в качестве операнда. Наконец, правило ^ использует termParser для операндов.

Здесь важно отметить, что правило ^ (или в более общем смысле: любое правило с более высоким приоритетом, чем префиксные операторы) вызывает синтаксический анализатор, который вначале не принимает префиксные операторы. Таким образом, префиксные операторы не могут появляться справа от таких операторов (за исключением скобок).

В основном это означает, что ваш вариант использования не поддерживается makeExprParser.

Чтобы обойти это, вы можете использовать makeExprParser, чтобы обрабатывать только инфиксные операторы с более низким приоритетом, чем префиксные операторы, а затем обрабатывать префиксные операторы и ^ вручную, так что правый операнд ^ будет "вернуться назад" к префиксным операторам. Примерно так:

expressionParser =
    makeExprParser prefixParser
      [
        [
          InfixL $ BinOp BinaryMult <$ symbol "*",
          InfixL $ BinOp BinaryDiv <$ symbol "/"
        ],
        [
          InfixL $ BinOp BinaryPlus <$ symbol "+",
          InfixL $ BinOp BinaryMinus <$ symbol "-"
        ]
      ]

prefixParser =
  do
    prefixOps <- many prefixOp
    exp <- exponentiationParser
    return $ foldr ($) exp prefixOps
  where
    prefixOp = MonOp MonoMinus <$ symbol "-" <|> MonOp MonoPlus <$ symbol "+"

exponentiationParser =
  do
    lhs <- termParser
    -- Loop back up to prefix instead of going down to term
    rhs <- optional (symbol "^" >> prefixParser)
    return $ maybe lhs (BinOp BinaryExp lhs) rhs

Обратите внимание, что, в отличие от makeExprParser, это также позволяет использовать несколько последовательных префиксных операторов (например, --x для двойного отрицания). Если вы не хотите этого, замените many на optional в определении prefixParser.