Module io.jenetics.ext
Package io.jenetics.ext.grammar

Class Cfg<T>

java.lang.Object
io.jenetics.ext.grammar.Cfg<T>
Type Parameters:
T - the terminal symbol value type
public final class Cfg<T> extends Object
Represents a context-free grammar (CFG).

Formal definition

A context-free grammar G is defined by the 4-tuple G = (N, T, R, S), where

  • N is a finite set; each element n ∈ N is called a non-terminal (Cfg.NonTerminal) character or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories. Each variable defines a sub-language of the language defined by G.
  • T is a finite set of terminals (Cfg.Terminal) disjoint from N, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
  • R is a finite relation in N × (N ∪ T)∗, where the asterisk represents the Kleene star operation. The members of R are called the (rewrite) rules (Cfg.Rule) or productions of the grammar.
  • S is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of N (Cfg.NonTerminal).
Creating Cfg object from a given BNF grammar 
final Cfg<String> cfg = Bnf.parse("""
	<expr> ::= <num> | <var> | '(' <expr> <op> <expr> ')'
	<op>   ::= + | - | * | /
	<var>  ::= x | y
	<num>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
	"""
);

Creating Cfg programmatically 

final Cfg<String> cfg = Cfg.of(
	R("expr",
		N("num"),
		N("var"),
		E(T("("), N("expr"), N("op"), N("expr"), T(")"))
	),
	R("op", T("+"), T("-"), T("*"), T("/")),
	R("var", T("x"), T("y")),
	R("num",
		T("0"), T("1"), T("2"), T("3"),
		T("4"), T("5"), T("6"), T("7"),
		T("8"), T("9")
	)
);

Creating Cfg programmatically with builders

Using the CFG builder makes it easier to define annotation for symbols without pushing the Java generics to its edges. 

final Cfg<String> cfg = Cfg.<String>builder()
	.R(N("expr", "Rule start annotation"), rule -> rule
		.N("num", "Non-terminal annotation 1")
		.N("var", "Non-terminal annotation 2")
		.E(exp -> exp
			.add(T("(").at("Terminal annotation"))
			.N("expr").N("op").N("expr")
			.T(")")
			.at("Expression annotation")))
	.R("op", rule -> rule.T("+").T("-").T("*").T("/"))
	.R("var", rule -> rule.T("x").T("y"))
	.R("num", rule -> rule
		.T("0").T("1").T("2").T("3").T("4")
		.T("5").T("6").T("7").T("8").T("9")
		.at("Rule annotation")
	)
	.build();

Annotating CFG elements can be used to influence the Generator classes, which creates sentences from a given grammar.

Since:
7.1
Version:
8.2
See Also:

  • Constructor Details

  • Method Details

    • nonTerminals

      public List<Cfg.NonTerminal<T>> nonTerminals()
      Return the non-terminal symbols of this grammar. The returned symbols have no annotation.
      Returns:
      the non-terminal symbols of this grammar

    • terminals

      public List<Cfg.Terminal<T>> terminals()
      Return the terminal symbols of this grammar. The returned symbols have no annotation.
      Returns:
      the terminal symbols of this grammar

    • rules

      public List<Cfg.Rule<T>> rules()
      Return the rules of this grammar.
      Returns:
      the rules of this grammar

    • start

      public Cfg.NonTerminal<T> start()
      Return the start symbol of this grammar.
      Returns:
      the start symbol of this grammar

    • rule

      public Optional<Cfg.Rule<T>> rule(Cfg.NonTerminal<?> start)
      Return the rule for the given start symbol.
      Parameters:
      start - the start symbol of the rule
      Returns:
      the rule for the given start symbol
      Throws:
      NullPointerException - if the given start symbol is null

    • map

      public <A> Cfg<A> map(Function<? super Cfg.Terminal<? extends T>,? extends A> mapper)
      Maps the values of the terminal symbols from type T to type A.
      Type Parameters:
      A - the new value type of the terminal symbols
      Parameters:
      mapper - the mapper function
      Returns:
      the mapped grammar
      Throws:
      NullPointerException - if the given mapper is null

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • of

      public static <T> Cfg<T> of(List<? extends Cfg.Rule<? extends T>> rules)
      Create a grammar object with the given rules. Duplicated rules are merged into one rule. The start symbol of the first rule is chosen as the start symbol of the created CFG
      Parameters:
      rules - the rules the grammar consists of
      Throws:
      IllegalArgumentException - if the rule list is empty or a rule is defined more than once, the start symbol points to a missing rule or the rules uses symbols not defined in the list of nonTerminals() or terminals()
      NullPointerException - if the list of rules is null

    • of

      @SafeVarargs public static <T> Cfg<T> of(Cfg.Rule<? extends T>... rules)
      Create a grammar object with the given rules.
      Parameters:
      rules - the rules the grammar consists of
      Throws:
      IllegalArgumentException - if the list of rules is empty or there are duplicate rules
      NullPointerException - if the list of rules is null

    • T

      public static <T> Cfg.Terminal<T> T(String name, T value)
      Factory method for creating a terminal symbol with the given name and value.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      name - the name of the terminal symbol
      value - the value of the terminal symbol
      Returns:
      a new terminal symbol

    • T

      public static <T> Cfg.Terminal<T> T(String name, T value, Object annotation)
      Factory method for creating a terminal symbol with the given name and value.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      name - the name of the terminal symbol
      value - the value of the terminal symbol
      annotation - the terminal annotation
      Returns:
      a new terminal symbol
      Since:
      8.2

    • T

      public static Cfg.Terminal<String> T(String name)
      Factory method for creating a terminal symbol with the given name.
      Parameters:
      name - the name of the terminal symbol
      Returns:
      a new terminal symbol

    • N

      public static <T> Cfg.NonTerminal<T> N(String name)
      Factory method for creating non-terminal symbols.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      name - the name of the symbol.
      Returns:
      a new non-terminal symbol

    • N

      public static <T> Cfg.NonTerminal<T> N(String name, Object annotation)
      Factory method for creating non-terminal symbols.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      name - the name of the symbol.
      annotation - the annotation of the symbol
      Returns:
      a new non-terminal symbol
      Since:
      8.2

    • E

      @SafeVarargs public static <T> Cfg.Expression<T> E(Cfg.Symbol<T>... symbols)
      Factory method for creating an expression with the given symbols.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      symbols - the expression symbols
      Returns:
      a new expression
      Throws:
      IllegalArgumentException - if the list of symbols is empty

    • R

      @SafeVarargs public static <T> Cfg.Rule<T> R(String name, Cfg.Element<T>... elements)
      Factory method for creating a new rule. The elements array doesn't allow Cfg.Rule objects.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      name - the name of start symbol of the rule
      elements - the list of alternative rule expressions
      Returns:
      a new rule
      Throws:
      IllegalArgumentException - if the given list of alternatives is empty
      NullPointerException - if one of the arguments is null

    • R

      @Deprecated(forRemoval=true, since="8.2") @SafeVarargs public static <T> Cfg.Rule<T> R(String name, Cfg.Expression<T>... alternatives)
      Deprecated, for removal: This API element is subject to removal in a future version.
      Will be removed, use R(String, Element[]) instead
      Factory method for creating a new rule. The elements array doesn't allow Cfg.Rule objects.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      name - the name of start symbol of the rule
      alternatives - the list of alternative rule expressions
      Returns:
      a new rule
      Throws:
      IllegalArgumentException - if the given list of alternatives is empty
      NullPointerException - if one of the arguments is null

    • R

      @SafeVarargs public static <T> Cfg.Rule<T> R(Cfg.NonTerminal<T> start, Cfg.Element<T>... elements)
      Factory method for creating a new rule. The elements array doesn't allow Cfg.Rule objects.
      Type Parameters:
      T - the terminal symbol value type
      Parameters:
      start - the start symbol of the rule
      elements - the list of alternative rule expressions
      Returns:
      a new rule
      Throws:
      NullPointerException - if one of the arguments is null
      Since:
      8.2

    • builder

      public static <T> Cfg.Builder<T> builder()
      Return a new CFG builder.
      Type Parameters:
      T - the terminal symbol value type
      Returns:
      a new CFG builder
      Since:
      8.2