Как мне проанализировать операторы цепочки в стиле Python в Haskell с помощью parsec?

В проекте, над которым я сейчас работаю, я создаю анализатор выражений в 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 выше. Скажите мне, могу ли я использовать приведенный выше анализатор выражений. Если нет, скажите мне, что это не так, и я построю его вручную.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
0
79
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Синтаксически нет никакой реальной разницы между вашей цепочкой и арифметическими операторами. Это (левые или правые) ассоциативные операторы с разными уровнями приоритета, и у стандартного анализатора выражений не должно возникнуть проблем с их анализом. Все, что вам нужно сделать, это убедиться, что соответствующий 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))

Другие вопросы по теме