cfg

README

Context Free Grammar (CFG)

Formal Definition

A context-free grammar G is a 4-tuple G = (V, Σ, R, S) where:

1. V is a finite set; each element v ∈ V is called a variable. Each variable represents a different type of phrase or clause in the sentence.
2. Σ is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
3. R is a finite relation in (V × (V ∪ Σ)*). The members of R are called productions of the grammar (symbolized by P).
4. S is the start variable, used to represent the whole sentence. It must be an element of V.

References

• Wikipedia

Documentation

Index

• Constants
• type Alpha
• type Alphabet
• type Beta
• type CFG
  • func New(variables V, alphabet Alphabet, rules R, start Variable) (*CFG, error)
  • func Parse(input string) (*CFG, error)
  • func (g *CFG) CNF() R
  • func (g *CFG) Depth(depth int)
  • func (g *CFG) Evaluate(s string) (Path, bool)
  • func (g *CFG) String() string
• type Path
  • func (p Path) Replay() string
  • func (p Path) String() string
• type Production
  • func NewProduction(alpha Alpha, beta []Beta) Production
  • func (p Production) Equal(other Production) bool
  • func (p Production) String() string
• type R
  • func (r R) Sort()
  • func (r R) String() string
• type Terminal
  • func (t Terminal) String() string
• type V
• type Variable
  • func (v Variable) String() string

Examples

• CFG
• CFG (Parentheses)

Constants

const Epsilon = Terminal("ε")

Epsilon is the empty string.

Types

type Alpha

type Alpha interface {
	fmt.Stringer
	// contains filtered or unexported methods
}

Alpha is the wrapper for `α` in production rules (variables).

type Alphabet

type Alphabet []Terminal

Alphabet is the alphabet of a context-free grammar.

type Beta

type Beta interface {
	fmt.Stringer
	// contains filtered or unexported methods
}

Beta is the wrapper for `β` in production rules (variables and terminals).

type CFG

type CFG struct {
	Variables     V
	Alphabet      Alphabet
	Rules         R
	StartVariable Variable
	// contains filtered or unexported fields
}

CFG is a context-free grammar (`G = (V, Σ, R, S)`).

Example

package main

import (
	"fmt"
	"github.com/0x51-dev/cfg"
)

func main() {
	g, _ := cfg.Parse(`
		S → aSa
		S → bSb
		S → ε
	`)

	in := "aabbaa"
	fmt.Println(g)
	p, ok := g.Evaluate(in)
	fmt.Println(p, ok)
	fmt.Println(p.Replay())
}

Output:

( { S }, { a, b }, [ S → aSa, S → bSb, S → ε ], S )
[ S → aSa, S → aSa, S → bSb, S → ε ] true
S → aSa → aaSaa → aabSbaa → aabbaa

Example (Parentheses)

package main

import (
	"fmt"
	"github.com/0x51-dev/cfg"
)

func main() {
	S := cfg.Variable("S")
	lp := cfg.Terminal("(")
	rp := cfg.Terminal(")")
	lb := cfg.Terminal("[")
	rb := cfg.Terminal("]")
	g, _ := cfg.New(
		[]cfg.Variable{S},
		[]cfg.Terminal{lp, rp, lb, rb},
		[]cfg.Production{
			cfg.NewProduction(S, []cfg.Beta{S, S}),      // SS
			cfg.NewProduction(S, []cfg.Beta{lp, rp}),    // ()
			cfg.NewProduction(S, []cfg.Beta{lp, S, rp}), // (S)
			cfg.NewProduction(S, []cfg.Beta{lb, rb}),    // []
			cfg.NewProduction(S, []cfg.Beta{lb, S, rb}), // [S]
		},
		S,
	)
	g.Depth(15) // Needed since the default depth is 10, 14 is needed for the example.

	in := "([[[()()[][]]]([])])"
	fmt.Println(g)
	p, ok := g.Evaluate(in)
	fmt.Println(p, ok)
	fmt.Println(p.Replay())
}

Output:

( { S }, { (, ), [, ] }, [ S → SS, S → (), S → (S), S → [], S → [S] ], S )
[ S → (S), S → [S], S → SS, S → [S], S → [S], S → SS, S → SS, S → SS, S → (), S → (), S → [], S → [], S → (S), S → [] ] true
S → (S) → ([S]) → ([SS]) → ([[S]S]) → ([[[S]]S]) → ([[[SS]]S]) → ([[[SSS]]S]) → ([[[SSSS]]S]) → ([[[()SSS]]S]) → ([[[()()SS]]S]) → ([[[()()[]S]]S]) → ([[[()()[][]]]S]) → ([[[()()[][]]](S)]) → ([[[()()[][]]]([])])

func New

func New(variables V, alphabet Alphabet, rules R, start Variable) (*CFG, error)

New creates a new context-free grammar from the given variables, alphabet, rules, and start symbol. The order of the rules is important, since the first rule that matches will be used. Infinite loops can be prevented by using the repeat flag.

func Parse

func Parse(input string) (*CFG, error)

func (*CFG) CNF

func (g *CFG) CNF() R

CNF converts a context-free grammar to Chomsky Normal Form.

func (*CFG) Depth

func (g *CFG) Depth(depth int)

Depth allows the setting of the maximum depth of the production rules. Default is 10.

func (*CFG) Evaluate

func (g *CFG) Evaluate(s string) (Path, bool)

func (*CFG) String

func (g *CFG) String() string

type Path

type Path []Production

func (Path) Replay

func (p Path) Replay() string

func (Path) String

func (p Path) String() string

type Production

type Production struct {
	A Alpha
	B []Beta
}

Production is a production rule.

func NewProduction

func NewProduction(alpha Alpha, beta []Beta) Production

func (Production) Equal

func (p Production) Equal(other Production) bool

Equal checks if two production rules are equal.

func (Production) String

func (p Production) String() string

type R

type R []Production

R is a set of production rules. Formalized: `(α, β) ∈ R`, with `α ∈ V` and `β ∈ (V ∪ Σ)*`.

func (R) Sort

func (r R) Sort()

func (R) String

func (r R) String() string

type Terminal

type Terminal string

Terminal is an elementary symbol of a context-free grammar.

func (Terminal) String

func (t Terminal) String() string

type V

type V []Variable

V is a variable of a context-free grammar.

type Variable

type Variable string

Variable is a variable of a context-free grammar.

func (Variable) String

func (v Variable) String() string