使用 Megaparsec 解析时的运算符优先级问题

Question

我正在用数组和结构解析类 C 语言。按照 C 运算符优先级，. 和 [] 具有相同的优先级。

opTable :: [[Operator Parser Expr]]
opTable = [[ InfixL $ Access <$ symbol "." , opSubscript]]

opSubscript = Postfix $ foldr1 (.) <$> some singleIndex
singleIndex = do
    index < brackets expr
    return $ \l -> ArrayIndex l index

解析时

Struct S {
  int[3] a;
}
Struct S s;
s.a[1]

它产生了 Access (Var "s") (ArrayIndex (Var "a") 1) 代替 ArrayIndex (Access (Var "s") (Var "a")) 1 为什么？是不是因为[]没有被解析为InfixL？

更新： changing之后到

opTable :: [[Operator Parser Expr]]
opTable = [[ PostFix $ (\ident expr -> Access expr ident) <$ symbol "." <*> identifier, opSubscript]]

我又遇到了一个错误

s.a[1]
|  ^
unexpected '['
expecting ')', '_', alphanumeric character, or operator

Answer 1

来自 parser-combinators 的 makeExprParser 文档在前缀和后缀运算符方面很糟糕。

首先，它无法解释在假设的“相同”优先级别混合使用 prefix/postfix/infix 运算符，prefix/postfix 运算符总是被视为比中缀运算符具有更高的优先级。

其次，当声明“相同优先级的前缀和后缀运算符只能出现一次”，然后以--2作为前缀运算符-的例子时，实际上意味着甚至两个 separate 前缀运算符（或两个 separate 后缀运算符）也是不允许的，因此 +-2 带有单独的前缀运算符 + 和 - 也是不允许的。是允许的是同一级别的单个前缀运算符和单个后缀运算符，在这种情况下，关联位于左侧，因此 -2! 可以（假设 - 和 ! 是同一优先级的前缀和后缀运算符）并被解析为 (-2)!.

哦，第三，文档从未明确表示 manyUnaryOp 的示例代码仅适用于多个前缀运算符，并且需要进行不明显的更改才能正确使用多个后缀运算符订单。

因此，您的第一次尝试没有成功，因为后缀运算符的优先级秘密地高于中缀运算符。您的第二次尝试无效，因为无法解析同一优先级的两个不同后缀运算符。

最好的办法是解析由访问链和索引操作组成的单个“后缀运算符”。请注意需要 flip 才能获得后缀运算符的正确排序。

opTable :: [[Operator Parser Expr]]
opTable = [[ indexAccessChain ]]

indexAccessChain = Postfix $ foldr1 (flip (.)) <$> some (singleIndex <|> singleAccess)

singleIndex = flip ArrayIndex <$> brackets expr
singleAccess = flip Access <$> (char '.' *> identifier)

一个独立的例子：

{-# OPTIONS_GHC -Wall #-}
module Operators where

import Text.Megaparsec
import Text.Megaparsec.Char
import Control.Monad.Combinators.Expr
import Data.Void

type Parser = Parsec Void String

data Expr
  = Access Expr String
  | ArrayIndex Expr Expr
  | Var String
  | Lit Int
  deriving (Show)

expr :: Parser Expr
expr = makeExprParser term opTable

identifier :: Parser String
identifier = some letterChar

term :: Parser Expr
term = Var <$> identifier
  <|>  Lit . read <$> some digitChar

opTable :: [[Operator Parser Expr]]
opTable = [[ indexAccessChain ]]

indexAccessChain :: Operator Parser Expr
indexAccessChain = Postfix $ foldr1 (flip (.)) <$> some (singleIndex <|> singleAccess)

singleIndex, singleAccess :: Parser (Expr -> Expr)
singleIndex = flip ArrayIndex <$> brackets expr
singleAccess = flip Access <$> (char '.' *> identifier)

brackets :: Parser a -> Parser a
brackets = between (char '[') (char ']')

main :: IO ()
main = parseTest expr "s.a[1][2][3].b.c[4][5][6]"

使用 Megaparsec 解析时的运算符优先级问题

Operator precedence issue when parsing with Megaparsec

haskell

parsec

parser-combinators

megaparsec