trifecta 0.15 → 0.15.1
raw patch · 4 files changed
+172/−1 lines, 4 files
Files
- LICENSE +1/−0
- Text/Trifecta.hs +2/−0
- Text/Trifecta/Parser/Expr.hs +167/−0
- trifecta.cabal +2/−1
LICENSE view
@@ -1,4 +1,5 @@ Copyright 2011 Edward Kmett+Copyright 2007 Paolo Martini Copyright 1999-2000 Daan Leijen All rights reserved.
Text/Trifecta.hs view
@@ -18,6 +18,7 @@ , module Text.Trifecta.Parser.Step , module Text.Trifecta.Parser.Token , module Text.Trifecta.Parser.Token.Class+ , module Text.Trifecta.Parser.Expr , module Text.Trifecta.Path , module Text.Trifecta.Render.Caret , module Text.Trifecta.Render.Fixit@@ -44,6 +45,7 @@ import Text.Trifecta.Parser.Step import Text.Trifecta.Parser.Token import Text.Trifecta.Parser.Token.Class+import Text.Trifecta.Parser.Expr import Text.Trifecta.Path import Text.Trifecta.Render.Caret import Text.Trifecta.Render.Fixit
+ Text/Trifecta/Parser/Expr.hs view
@@ -0,0 +1,167 @@+-----------------------------------------------------------------------------+-- |+-- Module : Text.Trifecta.Parser.Expr+-- Copyright : (c) Edward Kmett+-- (c) Paolo Martini 2007+-- (c) Daan Leijen 1999-2001, +-- License : BSD-style (see the LICENSE file)+-- +-- Maintainer : ekmett@gmail.com+-- Stability : experimental+-- Portability : non-portable+-- +-- A helper module to parse \"expressions\".+-- Builds a parser given a table of operators and associativities.+-- +-----------------------------------------------------------------------------++module Text.Trifecta.Parser.Expr+ ( Assoc(..), Operator(..), OperatorTable+ , buildExpressionParser+ ) where++import Control.Applicative+import Text.Trifecta.Parser.Class+import Text.Trifecta.Parser.Combinators++-----------------------------------------------------------+-- Assoc and OperatorTable+-----------------------------------------------------------++-- | This data type specifies the associativity of operators: left, right+-- or none.++data Assoc + = AssocNone+ | AssocLeft+ | AssocRight++-- | This data type specifies operators that work on values of type @a@.+-- An operator is either binary infix or unary prefix or postfix. A+-- binary operator has also an associated associativity.++data Operator m a + = Infix (m (a -> a -> a)) Assoc+ | Prefix (m (a -> a))+ | Postfix (m (a -> a))++-- | An @OperatorTable m a@ is a list of @Operator m a@+-- lists. The list is ordered in descending+-- precedence. All operators in one list have the same precedence (but+-- may have a different associativity).++type OperatorTable m a = [[Operator m a]]++-----------------------------------------------------------+-- Convert an OperatorTable and basic term parser into+-- a full fledged expression parser+-----------------------------------------------------------++-- | @buildExpressionParser table term@ builds an expression parser for+-- terms @term@ with operators from @table@, taking the associativity+-- and precedence specified in @table@ into account. Prefix and postfix+-- operators of the same precedence can only occur once (i.e. @--2@ is+-- not allowed if @-@ is prefix negate). Prefix and postfix operators+-- of the same precedence associate to the left (i.e. if @++@ is+-- postfix increment, than @-2++@ equals @-1@, not @-3@).+--+-- The @buildExpressionParser@ takes care of all the complexity+-- involved in building expression parser. Here is an example of an+-- expression parser that handles prefix signs, postfix increment and+-- basic arithmetic.+--+-- > expr = buildExpressionParser table term+-- > <?> "expression"+-- >+-- > term = parens expr +-- > <|> natural+-- > <?> "simple expression"+-- >+-- > table = [ [prefix "-" negate, prefix "+" id ]+-- > , [postfix "++" (+1)]+-- > , [binary "*" (*) AssocLeft, binary "/" (div) AssocLeft ]+-- > , [binary "+" (+) AssocLeft, binary "-" (-) AssocLeft ]+-- > ]+-- > +-- > binary name fun assoc = Infix (do{ reservedOp name; return fun }) assoc+-- > prefix name fun = Prefix (do{ reservedOp name; return fun })+-- > postfix name fun = Postfix (do{ reservedOp name; return fun })++buildExpressionParser :: MonadParser m+ => OperatorTable m a+ -> m a+ -> m a+buildExpressionParser operators simpleExpr+ = foldl (makeParser) simpleExpr operators+ where+ makeParser term ops+ = let (rassoc,lassoc,nassoc,prefix,postfix) = foldr splitOp ([],[],[],[],[]) ops++ rassocOp = choice rassoc+ lassocOp = choice lassoc+ nassocOp = choice nassoc+ prefixOp = choice prefix <?> ""+ postfixOp = choice postfix <?> ""++ ambigious assoc op= try $ op *> fail ("ambiguous use of a " ++ assoc ++ " associative operator")++ ambigiousRight = ambigious "right" rassocOp+ ambigiousLeft = ambigious "left" lassocOp+ ambigiousNon = ambigious "non" nassocOp++ termP = do{ pre <- prefixP+ ; x <- term+ ; post <- postfixP+ ; return (post (pre x))+ }++ postfixP = postfixOp <|> return id++ prefixP = prefixOp <|> return id++ rassocP x = do{ f <- rassocOp+ ; y <- termP >>= rassocP1+ ; return (f x y)+ }+ <|> ambigiousLeft+ <|> ambigiousNon+ -- <|> return x++ rassocP1 x = rassocP x <|> return x++ lassocP x = do{ f <- lassocOp+ ; y <- termP+ ; lassocP1 (f x y)+ }+ <|> ambigiousRight+ <|> ambigiousNon+ -- <|> return x++ lassocP1 x = lassocP x <|> return x++ nassocP x = do{ f <- nassocOp+ ; y <- termP+ ; ambigiousRight+ <|> ambigiousLeft+ <|> ambigiousNon+ <|> return (f x y)+ }+ -- <|> return x++ in do{ x <- termP+ ; rassocP x <|> lassocP x <|> nassocP x <|> return x+ <?> "operator"+ }+++ splitOp (Infix op assoc) (rassoc,lassoc,nassoc,prefix,postfix)+ = case assoc of+ AssocNone -> (rassoc,lassoc,op:nassoc,prefix,postfix)+ AssocLeft -> (rassoc,op:lassoc,nassoc,prefix,postfix)+ AssocRight -> (op:rassoc,lassoc,nassoc,prefix,postfix)++ splitOp (Prefix op) (rassoc,lassoc,nassoc,prefix,postfix)+ = (rassoc,lassoc,nassoc,op:prefix,postfix)++ splitOp (Postfix op) (rassoc,lassoc,nassoc,prefix,postfix)+ = (rassoc,lassoc,nassoc,prefix,op:postfix)
trifecta.cabal view
@@ -1,6 +1,6 @@ name: trifecta category: Text, Parsing, Diagnostics, Pretty Printer, Logging-version: 0.15+version: 0.15.1 license: BSD3 cabal-version: >= 1.6 license-file: LICENSE@@ -36,6 +36,7 @@ Text.Trifecta.Parser.Step Text.Trifecta.Parser.Token Text.Trifecta.Parser.Token.Class+ Text.Trifecta.Parser.Expr Text.Trifecta.Path Text.Trifecta.Render.Prim Text.Trifecta.Render.Caret