EBNF

EBNF parser and generic parser generator.

Description

This is a Ruby implementation of an EBNF and BNF parser and parser generator.

LL(1) Parser

In one mode, it parses EBNF grammars to BNF, generates First/Follow and Branch tables for LL(1) grammars, which can be used with the stream Tokenizer and LL(1) Parser.

As LL(1) grammars operate using alt and seq primitives, allowing for a match on alternative productions or a sequence of productions, generating a parser requires turning the EBNF rules into BNF:

Transform a ::= b? into a ::= _empty | b
Transform a ::= b+ into a ::= b b*
Transform a ::= b* into a ::= _empty | (b a)
Transform a ::= op1 (op2) into two rules: a ::= op1 _a_1 _a_1_ ::= op2

Of note in this implementation is that the tokenizer and parser are streaming, so that they can process inputs of arbitrary size.

See EBNF::LL1 and EBNF::LL1::Parser for further information.

PEG/Packrat Parser

An additional Parsing Expression Grammar (PEG) parser generator is also supported. This performs more minmal transformations on the parsed grammar to extract sub-productions, which allows each component of a rule to generate its own parsing event.

Usage

Parsing an EBNF Grammar

require 'ebnf'

ebnf = EBNF.parse(File.open('./etc/ebnf.ebnf'))

Output rules and terminals as S-Expressions, Turtle, HTML or BNF

puts ebnf.to_sxp
puts ebnf.to_ttl
puts ebnf.to_html
puts ebnf.to_s

Transform EBNF to PEG (generates sub-rules for embedded expressions) and the RULES table as Ruby for parsing grammars:

ebnf.make_peg
ebnf.to_ruby

Transform EBNF to BNF (generates sub-rules using alt or seq from plus, star or opt)

ebnf.make_bnf

Generate First/Follow rules for BNF grammars (using "ebnf" as the starting production):

ebnf.first_follow(:ebnf)

Generate Terminal, First/Follow, Cleanup and Branch tables as Ruby for parsing grammars:

ebnf.build_tables
ebnf.to_ruby

Generate formatted grammar using HTML (requires Haml gem):

ebnf.to_html

Parser debugging

Inevitably while implementing a parser for some specific grammar, a developer will need greater insight into the operation of the parser. While this can involve sorting through a tremendous amount of data, the parser can be provided a Logger instance which will output messages at varying levels of detail to document the state of the parser at any given point. Most useful is likely the INFO level of debugging, but even more detail is revealed using the DEBUG level. WARN and ERROR statements will typically also be provided as part of an exception if parsing fails, but can be shown in the context of other parsing state with appropriate indentation as part of the logger.

Parser errors

On a parsing failure, and exception is raised with information that may be useful in determining the source of the error.

EBNF Grammar

The EBNF variant used here is based on W3C EBNF (see EBNF grammar) as defined in the XML 1.0 recommendation, with minor extensions:

The general form of a rule is:

symbol ::= expression

which can also be proceeded by an optional number enclosed in square brackets to identify the rule number:

[1] symbol ::= expression

Symbols are written with an initial capital letter if they are the start symbol of a regular language (terminals), otherwise with an initial lowercase letter (non-terminals). Literal strings are quoted.

Within the expression on the right-hand side of a rule, the following expressions are used to match strings of one or more characters:

`#xN`	where `N` is a hexadecimal integer, the expression matches the character whose number (code point) in ISO/IEC 10646 is `N`. The number of leading zeros in the `#xN` form is insignificant.
`[a-zA-Z], [#xN-#xN]`	matches any Char with a value in the range(s) indicated (inclusive).
`[abc], [#xN#xN#xN]`	matches any Char with a value among the characters enumerated. Enumerations and ranges can be mixed in one set of brackets.
`[^a-z], [^#xN-#xN]`	matches any Char with a value outside the range indicated.
`[^abc], [^#xN#xN#xN]`	matches any Char with a value not among the characters given. Enumerations and ranges of forbidden values can be mixed in one set of brackets.
`"string"`	matches a literal string matching that given inside the double quotes.
`'string'`	matches a literal string matching that given inside the single quotes.
`A (B \| C)`	`(B \| C)` is treated as a unit and may be combined as described in this list.
`A?`	matches A or nothing; optional A.
`A B`	matches `A` followed by `B`. This operator has higher precedence than alternation; thus `A B \| C D` is identical to `(A B) \| (C D)`.
`A \| B`	matches `A` or `B`.
`A - B`	matches any string that matches `A` but does not match `B`.
`A+`	matches one or more occurrences of `A`. Concatenation has higher precedence than alternation; thus `A+ \| B+` is identical to `(A+) \| (B+)`.
`A*`	matches zero or more occurrences of `A`. Concatenation has higher precedence than alternation; thus `A* \| B` is identical to `(A) \| (B*)`.
`@pass " "*`	Defines consumed whitespace in the document. Any whitespace found between non-terminal rules is consumed and ignored.
`@terminals`	Introduces terminal rules. All rules defined after this point are treated as terminals.

Comments include // and # through end of line (other than hex character) and /* ... */ (* ... *) which may cross lines
All rules MAY start with an identifier, contained within square brackets. For example [1] rule, where the value within the brackets is a symbol ([a-z] | [A-Z] | [0-9] | "_" | ".")+
@terminals causes following rules to be treated as terminals. Any terminal which is all upper-case (egTERMINAL), or any rules with expressions that match characters (#xN, [a-z], [^a-z], [abc], [^abc], "string", 'string', or A - B), are also treated as terminals.
@pass defines the expression used to detect whitespace, which is removed in processing.
No support for wfc (well-formedness constraint) or vc (validity constraint).

Parsing this grammar yields an S-Expression version: ebnf (or LL(1) version ebnf.ll1 or PEG version ebnf.peg).

Parser S-Expressions

Intermediate representations of the grammar may be serialized to Lisp-like S-Expressions. For example, the rule

[1] ebnf        ::= (declaration | rule)*

is serialized as

(rule ebnf "1" (star (alt declaration rule)))

Different components of an EBNF rule expression are transformed into their own operator:

`#xN`	`(hex "#xN")`
`[a-z#xN-#xN]`	`(range "a-z#xN-#xN")`
`[abc#xN]`	`(range "abc#xN")`
`[^a-z#xN-#xN]`	`(range "^a-z#xN-#xN")`
`[^abc#xN]`	`(range "^abc#xN")`
`"string"`	`"string"`
`'string'`	`"string"`
`A (B \| C)`	`(seq (A (alt B C)))`
`A?`	`(opt A)`
`A B`	`(seq A B)`
`A \| B`	`(alt A B)`
`A - B`	`(diff A B)`
`A+`	`(plus A)`
`A*`	`(star A)`
`@pass " "*`	`(pass (star " "))`
`@terminals`

Additionally, rules defined with an UPPERCASE symbol are treated as terminals.

For an LL(1) parser generator, the EBNF::BNF#make_bnf method can be used to transform the EBNF rule into a BNF rule.

(rule ebnf "1" (alt _empty _ebnf_2))
(rule _ebnf_1 "1.1" (alt declaration rule))
(rule _ebnf_2 "1.2" (seq _ebnf_1 ebnf))
(rule _ebnf_3 "1.3" (seq ebnf))

This allows First/Follow and other tables used by a parser to parse examples of the associated grammar. For more, see EBNF::LL1.

For a PEG parser generator, there is a simpler transformation that reduces rules containing sub-expressions (composed of star, alt, seq and similar expressions) and creates named rules to allow appropriate callbacks and for naming elements of the generating abstract syntax tree. The EBNF::PEG#make_peg method transforms the original rule into the following two rules:

(rule ebnf "1" (star _ebnf_1))
(rule _ebnf_1 "1.1" (alt declaration rule))

Example parsers

For a PEG parser for a simple grammar implementing a calculator see [Calc example](http://dryruby.github.io/ebnf/examples/calc/doc/calc.html

For an example parser built using this gem that parses the EBNF grammar, see EBNF PEG Parser example. This example creates a parser for the EBNF grammar which generates the same Abstract Syntax Tree as the built-in parser in the gem.

There is also an EBNF LL(1) Parser example.

Acknowledgements

Much of this work, particularly the generic parser, is inspired by work originally done by Tim Berners-Lee's Python predictive parser.

The LL(1) parser was inspired by Dan Connolly's EBNF to Turtle processor, EBNF to BNF Notation-3 rules, and First Follow Notation-3 rules.

Documentation

Full documentation available on Rubydoc.info.

Future Work

Better LL(1) parser tests

Author

Gregg Kellogg - https://greggkellogg.net/

Contributing

This repository uses Git Flow to mange development and release activity. All submissions must be on a feature branch based on the develop branch to ease staging and integration.

Do your best to adhere to the existing coding conventions and idioms.
Don't use hard tabs, and don't leave trailing whitespace on any line.
Do document every method you add using YARD annotations. Read the tutorial or just look at the existing code for examples.
Don't touch the .gemspec, VERSION or AUTHORS files. If you need to change them, do so on your private branch only.
Do feel free to add yourself to the CREDITS file and the corresponding list in the the README. Alphabetical order applies.
Do note that in order for us to merge any non-trivial changes (as a rule of thumb, additions larger than about 15 lines of code), we need an explicit public domain dedication on record from you.

License

This is free and unencumbered public domain software. For more information, see https://unlicense.org/ or the accompanying UNLICENSE file.

A copy of the Turtle EBNF and derived parser files are included in the repository, which are not covered under the UNLICENSE. These files are covered via the W3C Document License.