peggen

8.6

peggen

Elton M. Cardoso, Rodrigo G. Ribeiro, Leonardo V. S. Reis

()

package: peg-gen

1 Overview

This module defines a collection of PEG rackcheck generators. To generate well-formed PEGs, each term is always generated as a tern (peg, nullable, headset). This approach allows for incremental type correct construction of the term.

When generating a grammar, the context of all possible variables (Γ) is kept and updated accordingly. An additional context called Δ is used to avoid generated calls to non-terminals that would result in left recursion.

The general use case for this library is the function gen:peg whose arguments are the maximum number of variables, the maximum number of terminal symbols, and the maximum depth of a peg.

> (sample (gen:peg 3 2 1) 3)
'((∅ 0 ())
  (∅ 0 ())
  ((R (• 0 S) (S (/ 2 0) (F (/ 2 ε) ∅)))
   (/ 0 0)
   ((F #t ()) (S #f ()) (R #f ()))))

The output of the generator is a list of triple (G, e, Context)

G (Grammar) : A list of variables followe by a peg. The list ends with ∅ (empty grammar)
e: A peg expression
Context : The type context for gamma

2 Generators reference

procedure
(gen:Γ maxVars [#:varSize varSize]) → gen?
maxVars : exact-positive-integer?
varSize : exact-positive-integer? = 0

Creates a generator that generates a list of variable names (as symbols) with no more than maxVars elements. The varSize is the number of letters in the variable (0 means one letter, 1 means two letters, and so on).

procedure
(initΔ Γ) → (hash/c symbol? (listof symbol?))
Γ : (list/c symbol? boolean? (listof symbol?))

Constructs an initial correct Δ table from the given Γ.

procedure
(gen:peg maxVars maxLits maxDepth) → gen?
  maxVars : exact-positive-integer?
  maxLits : exact-positive-integer?
  maxDepth : exact-positive-integer?

Creates a PEG generator that generates a PEG grammar, a start expression, and the type context for each variable in grammar.

maxVars : The maximum number of variables to be present in the grammamr
maxVars : The maximum number of literals to be present in the grammamr
maxDepth : The maximum height of a PEG AST (all leaves have high 0)

procedure
(gen:grm G Γ Δ Σ n pmax) → gen?
  G : (list/c symbol? peg G)
  Γ : (list/c symbol? boolean? (listof symbol?))
  Δ : (hash/c symbol? (listof symbol?))
  Σ : (listof natural?)
  n : exact-positive-integer?
  pmax : exact-positive-integer?

Construc a generator for grammar from a context Γ. The Δ is a hashtable that maps each variable to its respective forbidden variables list. The G parameter is accumulative and will contain the generated grammar at the end. the Σ is the alphabet. The n parameter is from which variable the generation should start and pmax is the depth.

procedure
(gen:expr Γ Δ Σ b p) → gen?
  Γ : (list/c symbol? boolean? (listof symbol?))
  Δ : (listof symbol?)
  Σ : (listof natural?)
  b : boolean?
  p : exact-positive-integer?

Γ: is a list of terns: v is a variable name; nullable is a value that determines whether or not that variable is nullable; italic{headset} is a list of possible variables starting the body of v.
Δ: is a list of constraints - forbidden variables
Σ: is an alphabet
b: Should be #t whenever the generated expression must be nullable.
p: Depth of the expression. If p is 0, only generate terminals or allowed variables. Samples n values from g.

procedure
(gen:var varSize) → gen?
varSize : exact-positive-integer?

Creates a generator for a variable (as a string) the varSize is the maximum length of the string.

procedure
(gen:symbolVar varSize) → gen?
varSize : exact-positive-integer?

Creates a generator for a variable (as a symbol) the varSize is the maximum length of the symbol.