ebnf

README

ebnf

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

Grammars are written like so:

Expression = Term { ( "+" | "-" ) Term } .
Term = Factor { ( "*" | "/" ) Factor } .
Factor = Number | "(" Expression ")" .
Number = Digit { Digit } .
Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .

They can be parsed by Parse into a Grammar. Grammar.Validate determines whether a grammar is valid. Grammar.First and Grammar.Follow compute the first and follow sets for non-terminal identifiers. Grammar.Conflict determines whether a valid grammar can be parsed by an LL(1) parser.

Documentation

Overview

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

Grammars are written like so:

Expression = Term { ( "+" | "-" ) Term } .
Term = Factor { ( "*" | "/" ) Factor } .
Factor = Number | "(" Expression ")" .
Number = Digit { Digit } .
Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .

They can be parsed by Parse into a Grammar. Grammar.Validate determines whether a grammar is valid. Grammar.First and Grammar.Follow compute the first and follow sets for non-terminal identifiers. Grammar.Conflict determines whether a valid grammar can be parsed by 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) Conflict() 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) 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 parse errors.

func (Error) Error

func (e Error) Error() string

Error returns all the error strings joined by a line feed.

type Expression

type Expression struct {
	Terms []*Term
}

Expression is the right side of a production. There must be at least one term. All terms must not be nil.

func (Expression) String

func (e Expression) String() string

String returns the term strings joined by " | ".

type Factor

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

Factor is a term sequence. One, and only one, of the fields must not be nil.

func (Factor) String

func (f Factor) String() string

String returns a group string surrounded by round brackets, an option string surrounded by square brackets, a repetition string surrounded by curly brackets, and an identifier or literal string as itself.

type FirstFirstConflictError

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

FirstFirstConflictError is a first/first LL(1) grammar parse conflict.

func (FirstFirstConflictError) Error

func (f FirstFirstConflictError) Error() string

Error indicates a first/first conflict exists for an LL(1) parser

type FirstFollowConflictError

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

FirstFollowConflictError is a first/follow LL(1) grammar parse conflict.

func (FirstFollowConflictError) Error

func (f FirstFollowConflictError) Error() string

type Grammar

type Grammar struct {
	Productions []*Production
}

Grammar is an abstract syntax tree for a grammar. There must be at least one production.

func Parse

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

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

func (Grammar) Conflict

func (g Grammar) Conflict() error

Conflict returns whether a valid grammar has a first/first or first/follow conflict for an LL(1) parser. Either a FirstFirstConflictError, a FirstFollowConflictError, or nil are returned.

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 non-terminals 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 non-terminal Identifier text values. The map values are sets of Identifier and Literal values.

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 identifiers are capitalized, defined, and used.

type Identifier

type Identifier struct {
	Text string
}

Identifier is a terminal or non-terminal identifier. The text must not be empty.

func (Identifier) String

func (i Identifier) String() string

String returns the text.

type Literal

type Literal struct {
	Text string
}

Literal is the content of a quoted string. 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 double quotes.

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 separated by " = ", followed by a period.

type Term

type Term struct {
	Factors []*Factor
}

Term is an expression alternative. There must be at least one factor. All factors must not be nil.

func (Term) String

func (t Term) String() string

String returns the factor strings joined by a space.