#### earley

Parsing library based on Earley Algorithm
IN THIS PACKAGE
Module . .
`type 'a grammar = info * 'a rule list`

The type of a grammar, with its information

`and _ symbol = `
`| Term : {`
 `input : 'a input;` `info : info;` `memo : 'a tref;` `name : string;`
`} -> 'a symbol`
(*

terminal symbol just read the input buffer

*)
`| Ter2 : {`
 `input : 'a input2;` `info : info;` `memo : 'a tref;` `name : string;`
`} -> 'a symbol`
(*

Ter2 correspond to a recursive call to the parser. We can change the blank function for instance, or parse input as much as possible. In fact it is only in the combinators in earley.ml that we see the use Ter2 to call the parser back.

*)
`| Test : {`
 `input : 'a test;` `info : info;` `memo : 'a tref;` `name : string;`
`} -> 'a symbol`
(*

Test on the input, can for instance read blanks, usefull for things like ocamldoc (but not yet used by earley-ocaml).

*)
`| NonTerm : {`
 `mutable rules : 'a rule list;` `mutable info : info;` `memo : 'a ntref;` `name : string;`
`} -> 'a symbol`
(*

Non terminals trough a mutable field to define recursive rule lists

*)

The symbol, a more general concept that terminals

`and 'a ntref = 'a rule list cref`

Type of a container ref to memoize treatment of non terminal

`and _ prerule = `
 `| Empty : 'a pos -> 'a prerule` (*Empty rule.*) `| Next : info * 'a symbol * ( 'a, 'c ) next -> 'c prerule` (*Sequence of a symbol and a rule, with a possible name for debugging, the information on the rule, the symbol to read, an action and the rest of the rule*) `| Dep : ( 'a -> 'b rule ) -> ( 'a -> 'b ) prerule` (*Dependant rule, gives a lot of power! but costly! use only when no other solution is possible*)

BNF rule.

`and ('a, 'c) next = `
 `| Arg : ( 'a -> 'c ) rule -> ( 'a, 'c ) next` `| Pos : ( 'a -> 'c ) fpos rule -> ( 'a, 'c ) next` `| Ign : 'c rule -> ( 'a, 'c ) next`
`and 'a rule = {`
 `rule : 'a prerule;` `ptr : 'a StackContainer.container;` `adr : int;`
`}`

Each rule holds a container to associate data to the rule in O(1). see below the description of the type ('a,'b) pre_stack

`type _ final = `
`| D : {`
 `start : pos2;` (*position in buffer, before and after blank*) `stack : ( 'c, 'r ) stack;` (*tree of stack representing what should be done after reading the `rest` of the rule*) `acts : 'b -> 'c;` (*action to produce the final 'c.*) `rest : 'b rule;` (*remaining to parse, will produce 'b*) `full : 'c rule;` (*full rule. rest is a suffix of full.*)
`} -> 'r final`

Type of an active element of the earley table. In a description of earley, each table element is `(start, end, done * rest)` meaning we parsed the string from `start` to `end` with the rule `done` and it remains to parse `rest`. The `*` therefore denotes the current position. Earley is basically a dynamic algorithm producing all possible elements.

We depart from this representation in two ways:

• we do not represent `done`, we keep the whole whole rule: `full = done rest`
• we never keep `end`. It is only used when we finish parsing of a rule and we have an element `(start, end, done * Empty)` then, we look for other elements of the form `(start', end', done' * rest')` where `end' = start`, `rest' = nonterm' rest''` and `nonterm'` is a non terminal containing the `done` rule. We represent this situation by a stack in the element `(start, end, done * Empty)`, which is maintained to lists all the elements satisfying the above property (no more, no less, each element only once)

The type `'a final` represent an element of the earley table where `end` is the current position in the string being parsed.

`and (_, _) element = `
`| B : ( 'a -> 'r ) pos -> ( 'a, 'r ) element`(*

End of the stack, with an action to produce the final parser value

*)
`| C : {`
 `start : pos2;` `stack : ( 'c, 'r ) stack;` `acts : ( 'a -> 'b -> 'c ) pos;` (*Here we wait `x:'a` from parents*) `rest : 'b rule;` `full : 'c rule;`
`} -> ( 'a, 'r ) element`
(*

Cons cell of the stack with a record similar to D's

*)

Type of the element that appears in stacks. Note: all other elements no reachable from stacks will be collected by the GC, which is what we want to release memory.

The type is similar to the previous: `('a, 'r) element`, means that from a value of type 'a, comming from our parent in the stack, we could produce a value of type `'r` using `rest`.

The action needs to be prametrised by the future position which is unknown.

`and ('a, 'b) stack = ( 'a, 'b ) element list ref`

Stack themselves are an acyclic graph of elements (sharing is important to be preserved). We need a reference for the stack construction.

For the construction of the stack, all elements of the same list ref of type ('a,'b) stack have the same en position `end'`. And all elements that points to this stack have their begin position `start = end'`. Moreover, all elements with the same `full` and `start` must point to the same stack. Recall that `end` is not represented in elements.

We call the position `end'` associated to a stack (as said the `start` of the element that point to this stack, the "stack position". An important point: new stack elements are constructed when the stack position is the current position.

Moreover, when we add a point from an element `(start, end, rest, full)` to a stack (which is therefore at position `start`, we have `start = end` and `rest = full`. The rule has not parsed anything! This is the "prediction" phase of earley.

To do this construction, we use the record below with a hook that we run on all elements added to that stack. This record is only used with stack whose position are the current position: all these records will become inaccessible when we advance in parsing.

Morevoer, a direct pointer (thanks to the Container module) is kept from the `full` rule of all elements that point to these stack and that have the current position as `end`. This is the role of the functor call below.

`type ('a, 'b) pre_stack = {`
 `stack : ( 'a, 'b ) stack;` `mutable hooks : ( ( 'a, 'b ) element -> unit ) list;`
`}`

stack in construction ... they have a hook, to run on elements added to the stack later !