| Copyright | (c) 2021 comp |
|---|---|
| License | MIT |
| Maintainer | onecomputer00@gmail.com |
| Stability | stable |
| Portability | portable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Expression.Reorder
Description
Reorders expressions in a syntax tree so that prefix, postfix, and infix operator chains are correct according to their associativity and precedence.
Get started by creating a SyntaxTree instance for your syntax types.
Synopsis
- class SyntaxTree t e | t -> e where
- reorderChildren :: t -> Validation (NonEmpty e) t
- structureOf :: t -> Node t
- makeError :: Ambiguity -> t -> e
- reorder :: SyntaxTree t e => t -> Validation (NonEmpty e) t
- data Node t
- = NodePrefix Precedence t (t -> t)
- | NodePostfix Precedence t (t -> t)
- | NodeInfix Fixity t t (t -> t -> t)
- | NodeLeaf
- data Validation e a
- data Fixity = Fixity {}
- data Assoc
- type Precedence = Double
- data Ambiguity
Syntax tree reordering
class SyntaxTree t e | t -> e where Source #
Typeclass for syntax trees t with ambiguity errors e.
The reason for the error type is because there may be different types of expressions, e.g. value expressions and pattern matching patterns, so there is no way to return the offending expression without combining the types first.
Methods
reorderChildren :: t -> Validation (NonEmpty e) t Source #
Applies reorder to all children of this node that may have expressions to reorder.
This is usually in the form of a traversal over the children, which will aggregate errors via Validation.
structureOf :: t -> Node t Source #
Gets the structure of a node.
makeError :: Ambiguity -> t -> e Source #
Builds an error for the ambiguous expression given.
reorder :: SyntaxTree t e => t -> Validation (NonEmpty e) t Source #
Reorders a syntax tree to have correct precedence and associativity.
Returns either the reordered tree or a list of ambiguous expression errors.
The structure of a node in a syntax tree in regards to operations.
A non-leaf node is made up of:
- An operator (associativity and precedence for infix nodes, just precedence for unary nodes).
- The open children of the node i.e. the children that may have reordering happen.
- A rebuilding function, which replaces the children of node and rebuilds it e.g. updating source locations.
Note that the arity referred to is the number of open children, not the arity of the operation itself.
Constructors
| NodePrefix Precedence t (t -> t) | A prefix operator, where only the right-hand side is open, e.g. |
| NodePostfix Precedence t (t -> t) | A postfix operator, where only the left-hand side is open, e.g. |
| NodeInfix Fixity t t (t -> t -> t) | An infix operator, where both sides are open, e.g. |
| NodeLeaf | A leaf node where expressions may be contained, but are not open, e.g. |
data Validation e a Source #
Validation applicative, similar to Either but aggregates errors.
Instances
Operator properties
The fixity of an operator.
Constructors
| Fixity | |
Fields
| |
Instances
| Generic Fixity Source # | |||||
Defined in Expression.Reorder Associated Types
| |||||
| Show Fixity Source # | |||||
| Eq Fixity Source # | |||||
| type Rep Fixity Source # | |||||
Defined in Expression.Reorder type Rep Fixity = D1 ('MetaData "Fixity" "Expression.Reorder" "reorder-expression-0.1.0.2-inplace" 'False) (C1 ('MetaCons "Fixity" 'PrefixI 'True) (S1 ('MetaSel ('Just "fixityAssoc") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Assoc) :*: S1 ('MetaSel ('Just "fixityPrec") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Precedence))) | |||||
The associativity of an operator.
Constructors
| AssocLeft | Associates to the left: |
| AssocRight | Associates to the right: |
| AssocNone | Does not associate at all: |
Instances
| Generic Assoc Source # | |||||
Defined in Expression.Reorder Associated Types
| |||||
| Show Assoc Source # | |||||
| Eq Assoc Source # | |||||
| type Rep Assoc Source # | |||||
Defined in Expression.Reorder type Rep Assoc = D1 ('MetaData "Assoc" "Expression.Reorder" "reorder-expression-0.1.0.2-inplace" 'False) (C1 ('MetaCons "AssocLeft" 'PrefixI 'False) (U1 :: Type -> Type) :+: (C1 ('MetaCons "AssocRight" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "AssocNone" 'PrefixI 'False) (U1 :: Type -> Type))) | |||||
type Precedence = Double Source #
The precedence of the operator.
Higher precedence binds tighter.
An ambiguity in the operator chain.
Constructors
| AmbiguityMismatchAssoc | Multiple operators with same precedence but different associativities in a chain. |
| AmbiguityAssocNone | Multiple non-associative infix operators in a chain e.g. |
Example usage
First, we implement the SyntaxTree class for our expression type:
data Expr
= ExprBinary BinOp Expr Expr
| ExprPrefix PreOp Expr
| ExprTuple [Expr]
| ExprInt Int
fixityOf :: BinOp -> Fixity
precOf :: PreOp -> Precedence
instance SyntaxTree Expr String where
reorderChildren expr = case expr of
ExprBinary op l r -> ExprBinary op <$> reorder l <*> reorder r
ExprPrefix op x -> ExprPrefix op <$> reorder x
ExprTuple xs -> ExprTuple <$> traverse reorder xs
_ -> pure expr
structureOf expr = case expr of
ExprBinary binop l r -> NodeInfix (fixityOf binop) l r (ExprBinary binop)
ExprPrefix preop x -> NodePrefix (precOf preop) x (ExprPrefix preop)
_ -> NodeLeaf
makeError err _ = show errWriting the traversals manually for reorderChildren can be tedious, but can easily be done with other libraries, such
as types from generic-lens or gplate from optics.
Then, use reorder to apply the reordering to a tree:
>>>reorder $ ExprBinary BinOpMul (ExprBinary BinOpAdd (ExprInt 1) (ExprInt 2)) (ExprInt 3) -- (1 + 2) * 3ExprBinary BinOpAdd (ExprInt 1) (ExprBinary BinOpMul (ExprInt 2) (ExprInt 3)) -- 1 + (2 * 3)
If your syntax tree is annotated with e.g. source positions, you can rebuild those in the function of Node:
(<~>) :: (HasSourcePos a, HasSourcePos b) => a -> b -> SourcePos
structureOf (Located _ expr) = case expr of
ExprBinary binop l r -> NodeInfix (fixityOf binop) l r (\l' r' -> Located (l' <~> r') $ ExprBinary binop l' r')
ExprPrefix preop x -> NodePrefix (precOf preop) x (\x' -> Located (preop <~> x') $ ExprPrefix preop x')
_ -> NodeLeafHigher arity operations, where at most two child expressions are open, are supported; they can be treated as a prefix, postfix, or infix operator depending on how many open child expressions there are:
structureOf expr = case expr of
ExprTernary x y z -> NodeInfix ternaryFixity x z (\x' z' -> ExprTernary x' y z') -- x ? y : z
ExprIfThenElse x y z -> NodePrefix ifThenElsePrec z (\z' -> ExprIfThenElse x y z') -- if x then y else z
ExprIndex x y -> NodePostfix indexPrec x (\x' -> ExprIndex x' y) -- x[y]
_ -> NodeLeaf