В проекте, над которым я сейчас работаю, я создаю анализатор выражений в parsec. Код примерно такой:
opTable :: [[Operator Parser Expr]]
opTable =
[
-- ...
[ InfixL $ binary (ArithOp . Exp) TokExp ]
, [ InfixL $ binary (ArithOp . Mod) TokMod
, InfixL $ binary (ArithOp . Mul) TokMul
, InfixL $ binary (ArithOp . Div) TokDiv
]
, [ InfixL $ binary (ArithOp . Add) TokAdd
, InfixL $ binary (ArithOp . Sub) TokSub
]
, [ InfixL $ binary (ArithOp . Max) TokMax
, InfixL $ binary (ArithOp . Min) TokMin
]
-- =
, [ InfixL $ binary (ChainOp . EQ) TokEQ
-- ~, <, <=, >, >=
, InfixL $ binary (ChainOp . NEQ) TokNEQ
, InfixL $ binary (ChainOp . NEQU) TokNEQU
, InfixL $ binary (ChainOp . LT) TokLT
, InfixL $ binary (ChainOp . LTE) TokLTE
, InfixL $ binary (ChainOp . LTEU) TokLTEU
, InfixL $ binary (ChainOp . GT) TokGT
, InfixL $ binary (ChainOp . GTE) TokGTE
, InfixL $ binary (ChainOp . GTEU) TokGTEU
]
-- &&
, [ InfixL $ binary (ArithOp . Conj) TokConj
, InfixL $ binary (ArithOp . ConjU) TokConjU
-- ||
, InfixL $ binary (ArithOp . Disj) TokDisj
, InfixL $ binary (ArithOp . DisjU) TokDisjU
]
-- =>
, [ InfixR $ binary (ArithOp . Implies) TokImpl
, InfixR $ binary (ArithOp . ImpliesU) TokImplU
-- <=>
, InfixL $ binary (ChainOp . EQProp) TokEQProp
, InfixL $ binary (ChainOp . EQPropU) TokEQPropU
]
]
Обратите внимание, что существует два типа операторов, а именно ArithOp
и ChainOp
. ArithOp
— это обычные операторы, а ChainOp
— это операторы цепочки в стиле Python, например a <= b < c
. Существует множество операторов цепочки. Например, есть TokLT
(<
) и TokEQProp
(<=>
). К сожалению, приоритет ArithOp
и ChainOp
перепутан. Теперь предположим, что я хочу проанализировать выражения в этом синтаксическом дереве:
data Expr
= Lit Lit
| Var Name
| Op Op
| App Expr Expr
| Chain Chain
-- ...
-- ...
data Chain = Pure Expr | Ch Chain Op Expr
Возможно ли, что мы сможем использовать анализатор выражений для построения таких синтаксических деревьев с цепочками? Например, что-то вроде 1 <= 1 + 1 < 3
должно выглядеть так:
Ch (
Ch (
Lit 1
)
( Op "< = ")
(
App (
App (Op "+") (Lit 1)
)
(Lit 1)
)
)
(Op "<")
(Lit 3)
(Для ясности я опустил некоторые конструкторы.)
Можно ли разобрать операторы такого типа с помощью анализатора выражений? Я знаю, что могу построить парсер вручную, переписав его на слои парсеров. Однако использовать анализатор выражений определенно проще.
Я нашел несколько комбинаторов, например chainl
. Однако кажется невозможным использовать его для формирования Chain
выше. Скажите мне, могу ли я использовать приведенный выше анализатор выражений. Если нет, скажите мне, что это не так, и я построю его вручную.
Синтаксически нет никакой реальной разницы между вашей цепочкой и арифметическими операторами. Это (левые или правые) ассоциативные операторы с разными уровнями приоритета, и у стандартного анализатора выражений не должно возникнуть проблем с их анализом. Все, что вам нужно сделать, это убедиться, что соответствующий AST создан, что вы можете сделать, используя два варианта вашей функции binary
в элементах таблицы операторов:
В качестве урезанного примера должно работать что-то вроде следующего:
opTable :: [[Operator Parser Expr]]
opTable =
[ [ InfixL $ arithOp Mul "*" ]
, [ InfixL $ arithOp Add "+" ]
, [ InfixL $ chainOp Eq " = " ]
, [ InfixL $ arithOp Conj "&&" ]
, [ InfixR $ arithOp Implies "=>" ]
, [ InfixL $ chainOp EQProp "<=>" ]
]
where arithOp op tok = makeArith <$ string tok
where makeArith a b = App (App (Op op) a) b
chainOp op tok = makeChain <$ string tok
where makeChain a b = Chain $ Ch (asChain a) op b
asChain (Chain c) = c
asChain e = Pure e
Единственная сложная часть здесь — правильное определение makeChain
, который должен обрабатывать как цепочки, так и нецепочки в качестве первого аргумента.
Полный работоспособный пример:
import Text.Parsec
import Text.Parsec.String
import Control.Monad.Combinators.Expr
type Lit = Int
type Name = String
data Expr
= Lit Lit
| Var Name
| Op Op
| App Expr Expr
| Chain Chain
deriving (Show)
data Chain = Pure Expr | Ch Chain Op Expr
deriving (Show)
data Op = Mul | Add | Eq | Lte | Lt | Conj | Implies | EQProp
deriving (Show)
reservedOp :: String -> Parser String
reservedOp s = try $ string s <* notFollowedBy (oneOf "*+=<>&")
opTable :: [[Operator Parser Expr]]
opTable =
[ [ InfixL $ arithOp Mul "*" ]
, [ InfixL $ arithOp Add "+" ]
, [ InfixL $ chainOp Eq " = "
, InfixL $ chainOp Lte "< = "
, InfixL $ chainOp Lt "<"
]
, [ InfixL $ arithOp Conj "&&" ]
, [ InfixR $ arithOp Implies "=>" ]
, [ InfixL $ chainOp EQProp "<=>" ]
]
where arithOp op tok = makeArith <$ reservedOp tok
where makeArith a b = App (App (Op op) a) b
chainOp op tok = makeChain <$ reservedOp tok
where makeChain a b = Chain $ Ch (asChain a) op b
asChain (Chain c) = c
asChain e = Pure e
expr :: Parser Expr
expr = makeExprParser term opTable
term :: Parser Expr
term = Lit . read <$> many1 digit
main :: IO ()
main = do
parseTest expr "1<=1+1<3"
-- output: Chain (Ch (Ch (Pure (Lit 1)) Lte (App (App (Op Add) (Lit 1)) (Lit 1))) Lt (Lit 3))