ebnf

README

ebnf

Package ebnf parses, represents, and inspects a variant of Extended Backus-Naur Form called Wirth Syntax Notation. The first production defines the start nonterminal identifier. Nonterminal identifiers must begin with an uppercase letter. Terminal identifiers must begin with a lowercase letter. Terminal identifiers are assumed to be defined elsewhere and not cause conflicts. Epsilon is represented by an empty literal.

Grammars are written like so:

Grammar = {Production}.
Production = Identifier "=" Expression ".".
Expression = Term {"|" Term}.
Term = Factor {Factor}.
Factor = Group | Identifier | Literal | Option | Repetition.
Group = "(" Expression ")".
Identifier = letter {letter}.
Literal = "\"" {character} "\"".
Option = "[" Expression "]".
Repetition = "{" Expression "}".

Parse parses a grammar into a Grammar. Grammar.Validate determines whether a grammar is valid. Grammar.First computes the first terminals. Grammar.FirstNonterminals and Grammar.Follow compute the first and follow terminals for nonterminal identifiers. Grammar.LL1 determines whether a valid grammar has parse conflicts for an LL(1) parser.

Documentation

Overview

Package ebnf parses, represents, and inspects a variant of Extended Backus-Naur Form called Wirth Syntax Notation. The first production defines the start nonterminal identifier. Nonterminal identifiers must begin with an uppercase letter. Terminal identifiers must begin with a lowercase letter. Terminal identifiers are assumed to be defined elsewhere and not cause conflicts. Epsilon is represented by an empty literal.

Grammars are written like so:

Grammar = {Production}.
Production = Identifier "=" Expression ".".
Expression = Term {"|" Term}.
Term = Factor {Factor}.
Factor = Group | Identifier | Literal | Option | Repetition.
Group = "(" Expression ")".
Identifier = letter {letter}.
Literal = "\"" {character} "\"".
Option = "[" Expression "]".
Repetition = "{" Expression "}".

Parse parses a grammar into a Grammar. Grammar.Validate determines whether a grammar is valid. Grammar.First computes the first terminals. Grammar.FirstNonterminals and Grammar.Follow compute the first and follow terminals for nonterminal identifiers. Grammar.LL1 determines whether a valid grammar has parse conflicts for an LL(1) parser.

Index

• type Error
  • func (e Error) Error() string
• type Expression
  • func (e Expression) String() string
• type Factor
  • func (f Factor) String() string
• type FirstFirstConflictError
  • func (f FirstFirstConflictError) Error() string
• type FirstFollowConflictError
  • func (f FirstFollowConflictError) Error() string
• type Grammar
  • func Parse(s string) (*Grammar, error)
  • func (g Grammar) First() map[any]map[any]struct{}
  • func (g Grammar) FirstNonterminals() map[string]map[any]struct{}
  • func (g Grammar) Follow() map[string]map[any]struct{}
  • func (g Grammar) LL1() error
  • func (g Grammar) String() string
  • func (g Grammar) Validate() error
• type Identifier
  • func (i Identifier) String() string
• type Literal
  • func (l Literal) String() string
• type Production
  • func (p Production) String() string
• type Term
  • func (t Term) String() string

Types

type Error

type Error struct {
	Errors []error
}

Error has all lexer and parser errors.

func (Error) Error

func (e Error) Error() string

Error returns the error strings separated by a line feed.

type Expression

type Expression struct {
	Terms []*Term
}

Expression is a production expression. It has a list of one or more terms. All terms must not be nil.

func (Expression) String

func (e Expression) String() string

String returns the term strings separated by " | ".

type Factor

type Factor struct {
	Group      *Expression
	Identifier *Identifier
	Literal    *Literal
	Option     *Expression
	Repetition *Expression
}

Factor is either a group, identifier, literal, option, or repetition. Group groups syntax. Option is optional syntax. Repetition is syntax that occurs zero or more times. Identifier and Literal are concrete syntax. All fields must be nil except one.

func (Factor) String

func (f Factor) String() string

String returns a string representation of the non-nil field. For Group, its string is surrounded by round brackets like "(...)". For Option, its string is surrounded by square brackets like "[...]". For Repetition, its string is surrounded by curly brackets like "{...}". For Identifier and Literal, their string is returned unchanged.

type FirstFirstConflictError

type FirstFirstConflictError struct {
	Nonterminal string
	Terminal    any // an Identifier or Literal
}

FirstFirstConflictError indicates that a grammar is not LL(1) due to a first/first conflict.

func (FirstFirstConflictError) Error

func (f FirstFirstConflictError) Error() string

Error explains the conflict for the nonterminal and terminal involved.

type FirstFollowConflictError

type FirstFollowConflictError struct {
	Nonterminal string
	Terminal    any // an Identifier or Literal
}

FirstFollowConflictError indicates that a grammar is not LL(1) due to a first/follow conflict.

func (FirstFollowConflictError) Error

func (f FirstFollowConflictError) Error() string

Error explains the conflict for the nonterminal and terminal involved.

type Grammar

type Grammar struct {
	Productions []*Production
}

Grammar is a grammar. It has a list of one or more productions. All productions must not be nil.

func Parse

func Parse(s string) (*Grammar, error)

Parse returns a Grammar for a valid grammar, or an error otherwise.

func (Grammar) First

func (g Grammar) First() map[any]map[any]struct{}

First returns the first terminals of a valid grammar. The map keys are *Production, *Expression, *Term, *Factor, Identifier, or Literal values. The map values are sets of Identifier and Literal values.

func (Grammar) FirstNonterminals

func (g Grammar) FirstNonterminals() map[string]map[any]struct{}

FirstNonterminals returns the first terminals of the nonterminals of a valid grammar.

func (Grammar) Follow

func (g Grammar) Follow() map[string]map[any]struct{}

Follow returns the follow terminals of a valid grammar. The map keys are nonterminal identifier strings. The map values are sets of Identifier and Literal values.

func (Grammar) LL1

func (g Grammar) LL1() error

LL1 determines whether a valid grammar is LL(1). It returns first/first and first/follow conflicts.

func (Grammar) String

func (g Grammar) String() string

String returns the production strings joined by a line feed.

func (Grammar) Validate

func (g Grammar) Validate() error

Validate checks that production nonterminal identifiers are capitalized, defined, and used.

type Identifier

type Identifier struct {
	Text string
}

Identifier is the text of a terminal or nonterminal identifier. The text must contain only lowercase and uppercase English letters and must not be empty.

func (Identifier) String

func (i Identifier) String() string

String returns the text. For example, for "foo", it returns "foo".

type Literal

type Literal struct {
	Text string
}

Literal is the text between the quotes of a literal. If the text is empty, it represents epsilon, the empty string.

func (Literal) String

func (l Literal) String() string

String returns the text surrounded by quotes. For example, for "foo", it returns `"foo"`.

type Production

type Production struct {
	Identifier *Identifier
	Expression *Expression
}

Production is a grammar production. The identifier and expression must not be nil.

func (Production) String

func (p Production) String() string

String returns the identifier and expression strings separated by " = " and followed by a period.

type Term

type Term struct {
	Factors []*Factor
}

Term is an expression alternative. It has a list of one or more factors. All factors must not be nil.

func (Term) String

func (t Term) String() string

String returns the factor strings separated by a space.