时间戳

首页 > 解决方案 > 使用 Megaparsec 解析时的运算符优先级问题

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

问题描述

我正在用数组和结构解析类似 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？

更新：将其更改为

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

我有另一个错误

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

标签： haskellparsecparser-combinatorsmegaparsec

解决方案

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

首先，它无法解释在假定的“相同”优先级级别混合使用前缀/后缀/中缀运算符，前缀/后缀运算符始终被视为比中缀运算符更高的优先级。

其次，当它声称“相同优先级的前缀和后缀运算符只能出现一次”然后给出--2前缀运算符的示例时-，它实际上意味着即使是两个单独的前缀运算符（或两个单独的后缀运算符）也不是' t 允许，因此+-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]"

推荐阅读