Packages

  • package root
    Definition Classes
    root
  • package org
    Definition Classes
    root
  • package benknoble
    Definition Classes
    org
  • package ebnf

    Provides classes for dealing with context-free grammars in EBNF form.

    Provides classes for dealing with context-free grammars in EBNF form.

    Provides a org.benknoble.ebnf.Grammar model, complete with scala DSL for creating complex grammars in code, and an org.benknoble.ebnf.EbnfParser to generate Grammars from a String.

    Overview

    The main class is org.benknoble.ebnf.Grammar:

    scala> val grammar = Grammar(
     |   new Production(
     |     Nonterminal('A),
     |     Alternation(Nonterminal('A),
     |     Sequence(Repetition(Terminal("abc")), Option(Terminal("def"))))))
grammar: org.benknoble.ebnf.Grammar = Grammar(List(Production(Nonterminal('A), Alternation(Nonterminal('A),Sequence(Repetition(Terminal(abc)),Option(Terminal(def)))))))

scala> val s = grammar.format
s: String = <A> ::= <A>|{'abc'}['def'] ;

    If you include org.benknoble.ebnf.ExprImplicits and take advantage of org.benknoble.ebnf.Expr syntax, it looks a lot cleaner:

    scala> val grammar = Grammar('A ::= 'A || Terminal("abc").* ~ "def".?)
grammar: org.benknoble.ebnf.Grammar = Grammar(List(Production(Nonterminal('A), Alternation(Nonterminal('A),Sequence(Repetition(Terminal(abc)),Option(Terminal(def)))))))

scala> val s = grammar.format
s: String = <A> ::= <A>|{'abc'}['def'] ;

    Finally, you can take advantage of org.benknoble.ebnf.EbnfParser:

    scala> val grammar = EbnfParser("<A> ::= <A>|{'abc'}['def'] ;")
grammar: Either[String,org.benknoble.ebnf.Grammar] = Right(Grammar(List(Production(Nonterminal('A), Alternation(Nonterminal('A),Sequence(Repetition(Terminal(abc)),Option(Terminal(def))))))))

scala> val msg = grammar.fold(s => s, g => g.format)
msg: String = <A> ::= <A>|{'abc'}['def'] ;
    Definition Classes
    benknoble
  • Alternation
  • EbnfParser
  • Expr
  • ExprImplicits
  • Grammar
  • Main
  • Nonterminal
  • Option
  • Production
  • Repetition
  • Sequence
  • Terminal
  • Word
  • ε
o

org.benknoble.ebnf

EbnfParser

object EbnfParser extends RegexParsers

Parser for EBNF specifications

Intended usage is via the apply method to Strings, or via standard parser combinator mechanisms. apply returns either the error message or the org.benknoble.ebnf.Grammar in an Either.

From Matt Might's specification

BNF

When describing languages, Backus-Naur form (BNF) is a formal notation for encoding grammars intended for human consumption.

Many programming languages, protocols or formats have a BNF description in their specification.

Every rule in Backus-Naur form has the following structure:

name ::= expansion

The symbol ::= means "may expand into" and "may be replaced with."

In some texts, a name is also called a non-terminal symbol.

Every name in Backus-Naur form is surrounded by angle brackets, < >, whether it appears on the left- or right-hand side of the rule.

An expansion is an expression containing terminal symbols and non-terminal symbols, joined together by sequencing and choice.

A terminal symbol is a literal like ("+" or "function") or a class of literals (like integer). It must be quoted using single quotes. Any metacharacters may appear within the quotes.

Simply juxtaposing expressions indicates sequencing.

A vertical bar | indicates choice.

For example, in BNF, the classic expression grammar is:

<expr> ::= <term> "+" <expr> |  <term>
<term> ::= <factor> "*" <term> |  <factor>
<factor> ::= "(" <expr> ")" |  <const>
<const> ::= integer

EBNF

Extended Backus-Naur form (EBNF) is a collection of extensions to Backus-Naur form.

More important than the minor syntactic differences between the forms of EBNF are the additional operations it allows in expansions.

Option

In EBNF, square brackets around an expansion, [ expansion ], indicates that this expansion is optional.

For example, the rule:

<term> ::= [ "-" ] <factor>

allows factors to be negated.

Repetition

In EBNF, curly braces indicate that the expression may be repeated zero or more times.

For example, the rule:

<args> ::= <arg> { "," <arg> }

defines a conventional comma-separated argument list.

Grouping

To indicate precedence, EBNF grammars may use parentheses, (), to explictly define the order of expansion.

For example, the rule:

<expr> ::= <term> ("+" | "-") <expr>

defines an expression form that allows both addition and subtraction.

Extensions

This version of EBNF admits a "comment-like" extension syntax: a # escapes the rest of the line, such that it is not parsed at all. Indeed, it is not kept in the grammar object at all, so the result of formatting loses the comments (considered a feature: it cleans the output for consumption by another tool).

The following grammar from the tests is thus valid:

# this is a comment
<A> ::= 'a'     # a values
        | 'b'   # b values
        | 'c'   # c values
        ;
Annotations
@JSExportTopLevel( "EbnfParser" )
Linear Supertypes
RegexParsers, Parsers, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. EbnfParser
  2. RegexParsers
  3. Parsers
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Type Members

  1. type Elem = Char
    Definition Classes
    RegexParsers → Parsers
  2. case class Error extends NoSuccess with Product with Serializable
    Definition Classes
    Parsers
  3. case class Failure extends NoSuccess with Product with Serializable
    Definition Classes
    Parsers
  4. type Input = Reader[Elem]
    Definition Classes
    Parsers
  5. sealed abstract class NoSuccess extends ParseResult[Nothing]
    Definition Classes
    Parsers
  6. trait OnceParser[+T] extends Parser[T]
    Definition Classes
    Parsers
  7. sealed abstract class ParseResult[+T] extends AnyRef
    Definition Classes
    Parsers
  8. abstract class Parser[+T] extends (Input) ⇒ ParseResult[T]
    Definition Classes
    Parsers
  9. case class Success[+T] extends ParseResult[T] with Product with Serializable
    Definition Classes
    Parsers
  10. case class ~[+a, +b] extends Product with Serializable
    Definition Classes
    Parsers

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. def OnceParser[T](f: (Input) ⇒ ParseResult[T]): Parser[T] with OnceParser[T]
    Definition Classes
    Parsers
  5. def Parser[T](f: (Input) ⇒ ParseResult[T]): Parser[T]
    Definition Classes
    Parsers
  6. def accept[U](expected: String, f: PartialFunction[Elem, U]): Parser[U]
    Definition Classes
    Parsers
  7. def accept[ES](es: ES)(implicit f: (ES) ⇒ List[Elem]): Parser[List[Elem]]
    Definition Classes
    Parsers
  8. implicit def accept(e: Elem): Parser[Elem]
    Definition Classes
    Parsers
  9. def acceptIf(p: (Elem) ⇒ Boolean)(err: (Elem) ⇒ String): Parser[Elem]
    Definition Classes
    Parsers
  10. def acceptMatch[U](expected: String, f: PartialFunction[Elem, U]): Parser[U]
    Definition Classes
    Parsers
  11. def acceptSeq[ES](es: ES)(implicit f: (ES) ⇒ Iterable[Elem]): Parser[List[Elem]]
    Definition Classes
    Parsers
  12. def alternation: Parser[Expr]

    Parser for an alternation

    Parser for an alternation

    Top level of stratified gramamr: basically repeated sequences separated by pipes

  13. def apply(input: String): Either[String, Grammar]

    Parses a grammar from a String

    Parses a grammar from a String

    A fun trick is

    println(EbnfParser(grammar).map(_.format))
    returns

    Either the error message or the grammar

  14. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  15. def chainl1[T, U](first: ⇒ Parser[T], p: ⇒ Parser[U], q: ⇒ Parser[(T, U) ⇒ T]): Parser[T]
    Definition Classes
    Parsers
  16. def chainl1[T](p: ⇒ Parser[T], q: ⇒ Parser[(T, T) ⇒ T]): Parser[T]
    Definition Classes
    Parsers
  17. def chainr1[T, U](p: ⇒ Parser[T], q: ⇒ Parser[(T, U) ⇒ U], combine: (T, U) ⇒ U, first: U): Parser[U]
    Definition Classes
    Parsers
  18. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @native() @throws( ... )
  19. val commentPrefix: String
    Attributes
    protected
  20. def commit[T](p: ⇒ Parser[T]): Parser[T]
    Definition Classes
    Parsers
  21. def elem(e: Elem): Parser[Elem]
    Definition Classes
    Parsers
  22. def elem(kind: String, p: (Elem) ⇒ Boolean): Parser[Elem]
    Definition Classes
    Parsers
  23. def epsilon: Parser[Expr]

    Parser for ε

  24. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  25. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  26. def err(msg: String): Parser[Nothing]
    Definition Classes
    Parsers
  27. def exp: Parser[Expr]

    Parser for top-level expression

  28. def failure(msg: String): Parser[Nothing]
    Definition Classes
    Parsers
  29. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  30. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  31. def goesTo: Parser[Any]

    Parser for ::=

  32. def grammar: Parser[Grammar]

    Parser for grammar

  33. def group: Parser[Expr]

    Parser for parenthesized groups

  34. def guard[T](p: ⇒ Parser[T]): Parser[T]
    Definition Classes
    Parsers
  35. def handleWhiteSpace(source: CharSequence, offset: Int): Int
    Attributes
    protected
    Definition Classes
    RegexParsers
  36. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  37. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  38. implicit def literal(s: String): Parser[String]
    Definition Classes
    RegexParsers
  39. def log[T](p: ⇒ Parser[T])(name: String): Parser[T]
    Definition Classes
    Parsers
  40. def mkList[T]: (~[T, List[T]]) ⇒ List[T]
    Definition Classes
    Parsers
  41. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  42. def nonterminal: Parser[Nonterminal]

    Parser for nonterminals

  43. def not[T](p: ⇒ Parser[T]): Parser[Unit]
    Definition Classes
    Parsers
  44. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  45. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  46. def opt: Parser[Expr]

    Parser for options

  47. def opt[T](p: ⇒ Parser[T]): Parser[scala.Option[T]]
    Definition Classes
    Parsers
  48. def parse[T](p: Parser[T], in: Reader): ParseResult[T]
    Definition Classes
    RegexParsers
  49. def parse[T](p: Parser[T], in: CharSequence): ParseResult[T]
    Definition Classes
    RegexParsers
  50. def parse[T](p: Parser[T], in: Reader[Char]): ParseResult[T]
    Definition Classes
    RegexParsers
  51. def parseAll[T](p: Parser[T], in: CharSequence): ParseResult[T]
    Definition Classes
    RegexParsers
  52. def parseAll[T](p: Parser[T], in: Reader): ParseResult[T]
    Definition Classes
    RegexParsers
  53. def parseAll[T](p: Parser[T], in: Reader[Char]): ParseResult[T]
    Definition Classes
    RegexParsers
  54. def parseJS_format(input: String): String
    Attributes
    protected
    Annotations
    @JSExport()
  55. def parseJS_grammar(input: String): Grammar
    Attributes
    protected
    Annotations
    @JSExport()
  56. def parseJS_scala(input: String): String
    Attributes
    protected
    Annotations
    @JSExport()
  57. def phrase[T](p: Parser[T]): Parser[T]
    Definition Classes
    RegexParsers → Parsers
  58. def positioned[T <: Positional](p: ⇒ Parser[T]): Parser[T]
    Definition Classes
    RegexParsers → Parsers
  59. implicit def regex(r: Regex): Parser[String]
    Definition Classes
    RegexParsers
  60. def rep[T](p: ⇒ Parser[T]): Parser[List[T]]
    Definition Classes
    Parsers
  61. def rep1[T](first: ⇒ Parser[T], p0: ⇒ Parser[T]): Parser[List[T]]
    Definition Classes
    Parsers
    Annotations
    @migration
    Migration

    (Changed in version 2.9.0) The p0 call-by-name arguments is evaluated at most once per constructed Parser object, instead of on every need that arises during parsing.

  62. def rep1[T](p: ⇒ Parser[T]): Parser[List[T]]
    Definition Classes
    Parsers
  63. def rep1sep[T](p: ⇒ Parser[T], q: ⇒ Parser[Any]): Parser[List[T]]
    Definition Classes
    Parsers
  64. def repN[T](num: Int, p: ⇒ Parser[T]): Parser[List[T]]
    Definition Classes
    Parsers
  65. def repetition: Parser[Expr]

    Parser for repetition

  66. def repsep[T](p: ⇒ Parser[T], q: ⇒ Parser[Any]): Parser[List[T]]
    Definition Classes
    Parsers
  67. def root: Parser[Grammar]

    Parser for top-level Gramamr

    Parser for top-level Gramamr

    Considers the entire input as a grammar, failing otherwise

    See also

    org.benknoble.ebnf.EbnfParser.phrase

  68. def rule: Parser[Production]

    Parser for productions

  69. def sequence: Parser[Expr]

    Parser for a sequence of expressions

    Parser for a sequence of expressions

    Anything but an alternation

  70. def skipWhitespace: Boolean
    Definition Classes
    RegexParsers
  71. def success[T](v: T): Parser[T]
    Definition Classes
    Parsers
  72. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  73. def terminal: Parser[Expr]

    Parser for terminals

  74. def toString(): String
    Definition Classes
    AnyRef → Any
  75. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  76. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  77. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @throws( ... )
  78. val whiteSpace: Regex
    Attributes
    protected
    Definition Classes
    EbnfParser → RegexParsers
  79. object NoSuccess
    Definition Classes
    Parsers

Inherited from RegexParsers

Inherited from Parsers

Inherited from AnyRef

Inherited from Any

Ungrouped