Module Private.Raw_grammar

Goals and non-goals

Encoding of generated grammars to maximize sharing

Processing of grammars

type label = string

The label of a field, constructor, or constant.

type generic_group_id = string

type group_id

type var_name = string

Variable names. These are used to improve readability of the printed grammars. Internally, we use numerical indices to represent variables; see Implicit_var below.

type type_name = string

module Atom : sig ... end

A grammatical type which classifies atoms.

type 't type_ =

| Any	Any list or atom.
| Apply of 't type_ * 't type_ list	Assign types to (explicit) type variables.
| Atom of Atom.t	An atom, in particular one of the given Atom.t.
| Explicit_bind of var_name list * 't type_	In Bind ([ "a"; "b" ], Explicit_var 0), Explicit_var 0 is "a". One must bind all available type variables: free variables are not permitted.
| Explicit_var of int	Indices for type variables, e.g. 'a, introduced by polymorphic definitions. Unlike de Bruijn indices, these are always bound by the nearest ancestral Explicit_bind.
| Grammar of 't	Embeds other types in a grammar.
| Implicit_var of int	Indices for type constructors, e.g. int, in scope. Unlike de Bruijn indices, these are always bound by the implicit_vars of the nearest enclosing generic_groups.
| List of 't sequence_type	A list of a certain form. Depending on the sequence_type, this might correspond to an OCaml tuple, list, or embedded record.
| Option of 't type_	An optional value. Either syntax recognized by option_of_sexp is supported: (Some 42) or (42) for a value and None or () for no value.
| Record of 't record_type	A list of lists, representing a record of the given record_type. For validation, Record recty is equivalent to List [Fields recty].
| Recursive of type_name	A type in the same mutually recursive group, possibly the current one.
| Union of 't type_ list	Any sexp matching any of the given types. Variant should be preferred when possible, especially for complex types, since validation and other algorithms may behave exponentially. One useful special case is Union [], the empty type. This is occasionally generated for things such as abstract types.
| Variant of 't variant_type	A sexp which matches the given variant_type.

A grammatical type which classifies sexps. Corresponds to a non-terminal in a context-free grammar.

and 't sequence_type = 't component list

A grammatical type which classifies sequences of sexps. Here, a "sequence" may mean either a list on its own or, say, the sexps following a constructor in a list matching a variant_type.

Certain operations may greatly favor simple sequence types. For example, matching List [ Many type_ ] is easy for any type type_ (assuming type_ itself is easy), but List [ Many type1; Many type2 ] may require backtracking. Grammars derived from OCaml types will only have "nice" sequence types.

and 't component =

| One of 't type_	Exactly one sexp of the given type.
| Optional of 't type_	One sexp of the given type, or nothing at all.
| Many of 't type_	Any number of sexps, each of the given type.
| Fields of 't record_type	A succession of lists, collectively defining a record of the given record_type. The fields may appear in any order. The number of lists is not necessarily fixed, as some fields may be optional. In particular, if all fields are optional, there may be zero lists.

Part of a sequence of sexps.

and 't variant_type = {

ignore_capitalization : bool;

If true, the grammar is insensitive to the case of the first letter of the label. This matches the behavior of derived sexp_of_t functions.

alts : (label * 't sequence_type) list;

An association list of labels (constructors) to sequence types. A matching sexp is a list whose head is the label as an atom and whose tail matches the given sequence type. As a special case, an alternative whose sequence is empty matches an atom rather than a list (i.e., label rather than (label)). This is in keeping with generated t_of_sexp functions. As a workaround, to match (label) one could use ("label", [ Optional (Union []) ]).

}

A tagged union of grammatical types. Grammars derived from OCaml variants will have variant types.

and 't record_type = {

allow_extra_fields : bool;

fields : (label * 't field) list;

}

A collection of field definitions specifying a record type. Consists only of an association list from labels to fields.

and 't field = {

optional : bool;	If true, the field is optional.
args : 't sequence_type;	A sequence type which the arguments to the field must match. An empty sequence is permissible but would not be generated for any OCaml type.

}

A field in a record.

type t =

| Ref of type_name * group

| Inline of t type_

and group = {

gid : group_id;
generic_group : generic_group;
origin : string;	origin provides a human-readable hint as to where the type was defined. For a globally unique identifier, use gid instead. See ppx/ppx_sexp_conv/test/expect/test_origin.ml for examples.
apply_implicit : t list;

}

and generic_group = {

implicit_vars : var_name list;

ggid : generic_group_id;

types : (type_name * t type_) list;

}