1 -- | Symantics to handle 'Prefix', 'Postfix' or 'Infix' operators,
2 -- of different 'Precedence's and possibly with left and/or right 'Associativity'.
3 module Language.Symantic.Grammar.Operators where
5 import Control.Applicative (Applicative(..))
6 import Control.Monad (void)
7 import Data.Either (Either(..))
10 import Data.Function (($), (.), flip, id)
11 import Data.Functor ((<$>))
12 import Data.Maybe (Maybe(..))
13 import Data.Ord (Ord(..), Ordering(..))
14 import Data.Tuple (curry)
15 import Text.Show (Show, showChar, showParen, showString, showsPrec)
17 import Language.Symantic.Grammar.Fixity
18 import Language.Symantic.Grammar.EBNF
19 import Language.Symantic.Grammar.Terminal
20 import Language.Symantic.Grammar.Regular
21 import Language.Symantic.Grammar.ContextFree
24 -- | Symantics for operators.
36 :: CF g a -- ^ expression
37 -> CF g (Unifix, a -> a) -- ^ prefix operator
38 -> CF g (Infix , a -> a -> a) -- ^ infix operator
39 -> CF g (Unifix, a -> a) -- ^ postfix operator
40 -> CF g (Either Error_Fixity a)
41 operators g prefixG infixG postfixG =
42 (evalOpTree <$>) <$> go g prefixG infixG postfixG
46 -> CF g (Unifix, a -> a)
47 -> CF g (Infix , a -> a -> a)
48 -> CF g (Unifix, a -> a)
49 -> CF g (Either Error_Fixity (OpTree a))
50 go = rule4 "operators" $ \aG preG inG postG ->
54 (foldl' (flip insertUnifix) (OpTree0 a) posts)
57 Just (in_, b) -> insertInfix nod_a in_ b
58 Nothing -> Right nod_a)
62 <*> option Nothing (curry Just <$> try inG <*> go aG preG inG postG)
63 infixrG :: CF g a -> CF g (a -> a -> a) -> CF g a
64 infixrG = rule2 "infixr" $ \g opG ->
66 Just (op, b) -> a `op` b
69 <*> option Nothing (try $ curry Just <$> opG <*> infixrG g opG)
70 infixlG :: CF g a -> CF g (a -> a -> a) -> CF g a
71 infixlG = rule2 "infixl" $ \g opG ->
72 -- NOTE: infixl uses the same grammar than infixr,
73 -- but build the parsed value by applying
74 -- the operator in the opposite way.
77 go :: CF g a -> CF g (a -> a -> a) -> CF g ((a -> a) -> a)
80 Just (op, kb) -> \k -> kb (k a `op`)
83 <*> option Nothing (try $ curry Just <$> opG <*> go g opG)
84 deriving instance Gram_Op g => Gram_Op (CF g)
85 instance Gram_Op RuleEBNF
88 -- ** Type 'Error_Fixity'
90 = Error_Fixity_Infix_not_combinable Infix Infix
92 Error_Fixity_NeedPostfixOrInfix
93 Error_Fixity_NeedPrefix
94 Error_Fixity_NeedPostfix
95 Error_Fixity_NeedInfix
100 -- | Tree of operators.
102 -- Useful to recombine operators according to their 'Precedence'.
105 | OpTree1 Unifix (a -> a) (OpTree a)
106 | OpTree2 Infix (a -> a -> a) (OpTree a) (OpTree a)
107 instance Show a => Show (OpTree a) where
108 showsPrec n (OpTree0 a) =
109 showParen (n > 10) $ showString "OpTree0 "
111 showsPrec n (OpTree1 f _ a) =
112 showParen (n > 10) $ showString "OpTree1 "
114 . showChar ' ' . showsPrec 11 a
115 showsPrec n (OpTree2 f _ a b) =
116 showParen (n > 10) $ showString "OpTree2 "
118 . showChar ' ' . showsPrec 11 a
119 . showChar ' ' . showsPrec 11 b
121 -- | Insert an 'Unifix' operator into an 'OpTree'.
122 insertUnifix :: (Unifix, a -> a) -> OpTree a -> OpTree a
123 insertUnifix a@(uni_a@(Prefix prece_a), op_a) nod_b =
125 OpTree0{} -> OpTree1 uni_a op_a nod_b
126 OpTree1 Prefix{} _op_b _nod -> OpTree1 uni_a op_a nod_b
127 OpTree1 uni_b@(Postfix prece_b) op_b nod ->
128 case prece_b `compare` prece_a of
129 GT -> OpTree1 uni_a op_a nod_b
130 EQ -> OpTree1 uni_a op_a nod_b
131 LT -> OpTree1 uni_b op_b $ insertUnifix a nod
132 OpTree2 inf_b op_b l r ->
133 case infix_prece inf_b `compare` prece_a of
134 GT -> OpTree1 uni_a op_a nod_b
135 EQ -> OpTree1 uni_a op_a nod_b
136 LT -> OpTree2 inf_b op_b (insertUnifix a l) r
137 insertUnifix a@(uni_a@(Postfix prece_a), op_a) nod_b =
139 OpTree0{} -> OpTree1 uni_a op_a nod_b
140 OpTree1 uni_b@(Prefix prece_b) op_b nod ->
141 case prece_b `compare` prece_a of
142 GT -> OpTree1 uni_a op_a nod_b
143 EQ -> OpTree1 uni_a op_a nod_b
144 LT -> OpTree1 uni_b op_b $ insertUnifix a nod
145 OpTree1 Postfix{} _op_b _nod -> OpTree1 uni_a op_a nod_b
146 OpTree2 inf_b op_b l r ->
147 case infix_prece inf_b `compare` prece_a of
148 GT -> OpTree1 uni_a op_a nod_b
149 EQ -> OpTree1 uni_a op_a nod_b
150 LT -> OpTree2 inf_b op_b l (insertUnifix a r)
152 -- | Insert an 'Infix' operator into an 'OpTree'.
155 -> (Infix, a -> a -> a)
156 -> Either Error_Fixity (OpTree a)
157 -> Either Error_Fixity (OpTree a)
158 insertInfix nod_a in_@(inf_a, op_a) e_nod_b = do
161 OpTree0{} -> Right $ OpTree2 inf_a op_a nod_a nod_b
162 OpTree1 uni_b op_b nod ->
163 case unifix_prece uni_b `compare` infix_prece inf_a of
164 EQ -> Right $ OpTree2 inf_a op_a nod_a nod_b
165 GT -> Right $ OpTree2 inf_a op_a nod_a nod_b
167 n <- insertInfix nod_a in_ (Right nod)
168 Right $ OpTree1 uni_b op_b n
169 OpTree2 inf_b op_b l r ->
170 case infix_prece inf_b `compare` infix_prece inf_a of
171 GT -> Right $ OpTree2 inf_a op_a nod_a nod_b
173 n <- insertInfix nod_a in_ (Right l)
174 Right $ OpTree2 inf_b op_b n r
180 case (ass <$> infix_assoc inf_b, ass <$> infix_assoc inf_a) of
181 (Just SideL, Just SideL) -> do
182 n <- insertInfix nod_a in_ (Right l)
183 Right $ OpTree2 inf_b op_b n r
184 (Just SideR, Just SideR) ->
185 Right $ OpTree2 inf_a op_a nod_a nod_b
186 _ -> Left $ Error_Fixity_Infix_not_combinable inf_a inf_b
187 -- NOTE: non-associating infix ops
188 -- of the same precedence cannot be mixed.
190 -- | Collapse an 'OpTree'.
191 evalOpTree :: OpTree a -> a
192 evalOpTree (OpTree0 a) = a
193 evalOpTree (OpTree1 _uni op n) = op $ evalOpTree n
194 evalOpTree (OpTree2 _inf op l r) = evalOpTree l `op` evalOpTree r
196 gram_operators :: (Gram_Op g, Gram_RuleEBNF g) => [CF g ()]
198 [ void $ operators (argEBNF "expr") (argEBNF "prefix") (argEBNF "infix") (argEBNF "postfix")