README
¶
github.com/cznic/ebnfutil has moved to modernc.org/ebnfutil (vcs).
Please update your import paths to modernc.org/ebnfutil.
This repo is now archived.
Documentation
¶
Overview ¶
Package ebnfutil (WIP:TODO) provides some utilities for messing with EBNF grammars.
Positions attached to particular ebnf package types instances are ignored in most, if not all places. Positions make sense after Parse, but usually no more after mutating the grammar in any way.
Index ¶
- func NormalizeExpression(expr ebnf.Expression) ebnf.Expression
- func NormalizeProduction(prod *ebnf.Production) *ebnf.Production
- type Grammar
- func (g Grammar) Analyze(start string) (r *Report, err error)
- func (g Grammar) BNF(start string, nameInventor func(name string) string) (r Grammar, repetitions map[string]bool, err error)
- func (g Grammar) Inline(start string, all bool) (err error)
- func (g Grammar) InlineOne(name string, all bool) (err error)
- func (g Grammar) Normalize() (r Grammar)
- func (g Grammar) String() string
- func (g Grammar) Verify(start string) error
- type Report
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NormalizeExpression ¶
func NormalizeExpression(expr ebnf.Expression) ebnf.Expression
NormalizeExpression returns a normalized clone of expr. Positions are ignored.
func NormalizeProduction ¶
func NormalizeProduction(prod *ebnf.Production) *ebnf.Production
NormalizeProduction returns a normalized clone of prod. Positions are ignored.
Types ¶
type Grammar ¶
Grammar is ebnf.Grammar extended with utility methods.
func Parse ¶
Parse parses a set of EBNF productions from source src. It returns a set of productions. Errors are reported for incorrect syntax and if a production is declared more than once; the filename is used only for error positions.
func (Grammar) Analyze ¶
Analyze analyzes g with starting production 'start' and returns a Report about it.
If start == "" then all of the grammar productions are considered.
If start != "" then only productions reachable from the start production are considered. Additionally, analysis stop at the token level.
Note: The grammar should be verified before invoking this method. Otherwise errors may occur.
func (Grammar) BNF ¶
func (g Grammar) BNF(start string, nameInventor func(name string) string) (r Grammar, repetitions map[string]bool, err error)
BNF returns g converted to a grammar without any of:
*ebnf.Group *ebnf.Option *ebnf.Repetition
Removing the above items requires expanding them via adding new productions to the grammar. Names for such productions are obtained via nameInventor. The name of the production for which the item must be expanded is passed to the nameInventor function. nameInventor must not return a name already existing in the grammar nor it may return any name more than once. Nil nameInventor can be passed to use a default implementation.
'start' is the name of the start production.
func (Grammar) Inline ¶
Inline attempts to remove some of the g's productions by inlining them into the places where they are used. For example this grammar:
Start = "0" Abc "9". Abc = "abc" .
becomes
Start = "0" "abc" "9" .
Eligible productions are non self referential (eg. `P = P | P Q .`) non terminals used only once (or unlimited times when all == true).
If g is a BNF grammar, it will still be a BNF grammar after Inline.
Note: If no productions can be inlined, no error is reported. Comparing the number of productions before and after calling Inline can reveal if any inlining was performed.
'start' is the name of the start production.
func (Grammar) InlineOne ¶
InlineOne attempts to inline production 'name' into all places where it is used. For example, consider this grammar:
Start = "0" Abc Def "9". Def = "X" | Abc . Abc = "abc" .
Performing InlineOne("Abc", true), it becomes:
Start = "0" "abc" Def "9" . Def = "X" | "abc .
Eligible productions are non self referential (eg. `P = P | P Q .`) non terminals used only once (or unlimited times when all == true).
If g is a BNF grammar, it will still be a BNF grammar after InlineOne.
Consider this EBNF grammar:
S = A B ( C | "5" ) . A = "1" . B = "2" | "3" . C = "4" .
Performing InlineOne("B", true) produces this EBNF grammar:
S = A ( "2" | "3" ) ( C | "5" ) . A = "1" . C = "4" .
Consider this BNF grammar:
S = A B C . A = "1" . B = "2" | "3" . C = "4" .
Performing InlineOne("B", true) produces this BNF grammar:
S = A "2" C | A "3" C . A = "1" . C = "4" .
Note: If the production cannot be inlined, no error is reported. Comparing the number of productions before and after calling InlineOne can reveal if inlining was performed.
Note: Invoking InlineOne for the start production may render the grammar unusable.
type Report ¶
type Report struct {
// The grammar uses no groups (`( expr )`), options (`[ expr ]`) or repetitions (`{ expr }`).
IsBNF bool
// Set of lexical productions names.
Lexical map[string]bool
// Set of all ebnf.Token.String values
Literals map[string]bool
// Set of all non terminal productions names.
NonTerminals map[string]bool
// Set of all ebnf.Range.{Begin,End} pairs.
Ranges map[struct{ Begin, End string }]bool
// Set of all lexical production names referenced from within a
// non-terminal production.
Tokens map[string]bool
// Used maps a production name to the count of its references.
Used map[string]int
// UsedBy maps a production name to its referencing production names
// set ie. a cross-reference. For example a grammar:
//
// Start = number | Start number .
// number = "0" … "9" .
//
// produces:
//
// map[string]map[string]bool{
// "Start":map[string]bool{"Start": true},
// "number":map[string]bool{"Start": true},
// }
UsedBy map[string]map[string]bool
}
Report is returned from Analyze.
Source Files