Library

Module

Module type

Parameter

Class

Class type

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

Transform strings of tokens and mixfix operators into full binary trees. Operators are characterised by their associativity and their fixity.

To parse expressions of type `'a`

, you need to tell the parser

- how to concatenate two expressions with a function of type
`'a -> 'a -> 'a`

; this function can be seen as the concatenation of two binary trees (and in that case, the input of the parser is a string of leaves); - how to determine whether a value of
`'a`

should be considered as an operator.

The algorithm implemented is an extension of the Pratt parser. The Shunting Yard algorithm could also be used.

`type fixity = `

`| Infix of associativity`

(*The operator is between its arguments, such as

*)`=`

in`x = y`

.`| Prefix`

(*The operator is before its argument, such as

*)`¬`

in`¬ P`

.`| Postfix`

(*The operator is after its argument, such as

*)`²`

in`x²`

.

The fixity allows to determine where the arguments of an operator are.

`type 't error = [ `

`| `OpConflict of 't * 't`

(*Priority or associativiy conflict between two operators. In

*)``OpConflict (t,o)`

,`o`

is an operator which generates a conflict preventing term`t`

to be parsed.`| `UnexpectedInfix of 't`

(*An infix operator appears without left context. If

*)`+`

is an infix operator, it is raised in, e.g.,`+ x x`

or`x + + x x`

.`| `UnexpectedPostfix of 't`

(*A postfix operator appears without left context. If

*)`!`

is a postfix operator, it is raised in`! x`

.`| `TooFewArguments`

(*More arguments are expected. It is raised for instance on partial application of operators, such as

*)`x +`

.

` ]`

Errors that can be encountered while parsing a stream of terms.

```
val expression :
appl:('a -> 'a -> 'a) ->
is_op:('a -> (fixity * float) option) ->
'a Stream.t ->
('a, 'a error) Stdlib.result
```

`expression appl is_op s`

parses the stream of tokens `s`

and turns it into a full binary tree.

If tokens are seen as leaves of binary trees, the function `appl`

is the concatenation of two binary trees. If tokens are seen as terms, `appl`

is the application.

The function `is_op`

is in charge of specifying which tokens are operators: for any term `t`

, `is_op t`

must return `Some (f, p)`

whenever `t`

is an operator with fixity `f`

and binding power (or precedence) `p`

. If `t`

isn't an operator, `is_op`

should return `None`

.

For instance, assuming that `+`

is declared infix and we're working with numbers, it can transform `3 + 5 × 2`

encoded as the stream of terms ```
3, +,
5, ×, 2
```

into the binary tree `@(@(×,@(@(+,3),5)),2)`

where `@`

denotes nodes.

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">