package menhir-secondary

  1. Overview
  2. Docs

The module CST offers an algebraic data type cst of concrete syntax trees. This definition is generic, that is, grammar-independent. This module is unsafe: the data constructor NonTerminal has an invariant that is not enforced. A safe, non-generic API can be constructed a posteriori on top of this unsafe, generic API.

The fringe of a CST is a sequence of tokens.

A CST is viable if the parser accepts its fringe and produces the exact same CST again. In general, not every CST is viable: as a typical example, in a grammar of arithmetic expressions where there is a single nonterminal symbol for expressions and where priority declarations are used to resolve shift/reduce conflicts, a CST where an addition node is a child of a multiplication node is not viable. If the grammar is LR(1) then every CST is viable.

type cst =
  1. | Terminal of A.token
  2. | NonTerminal of A.production * cst array

A concrete syntax tree (CST) is either a terminal node Terminal tok or a nonterminal node NonTerminal (prod, csts).

A terminal node carries just a token.

A nonterminal node carries a production index prod and an immutable array of subtrees csts. The length of the array csts must be the length of the right-hand side of the production prod. The sequence of the head symbols of the subtrees csts must match the right-hand side of the production prod. The production prod must not be a start production.

OCaml

Innovation. Community. Security.