benknoble / loner

EBNF parser and LL(1) computation

Loner

An EBNF parser and LL(1) checker, written in Scala.

This project consists of

• ebnf: an EBNF parser and formatting filter
• loner: an LL(1) checker that depends on the ebnf library

Each project is split into an API component and a Main.scala CLI component. The CLI driver serves as an example of the API usage, as a proof-of-concept, and as a useful tool for developers (especially those working on language and compiler design).

The CLI drivers have the same interface: they read from standard in, or from a file if passed one as a parameter. They output to standard out a formatted grammar, suitable for machine consumption, or an error message if the input is not EBNF-formatted (see below). Loner additionally errors if the grammar is not LL(1). The exit status reflects the success state (0: success, 1: not ebnf, 2: invalid arguments). Given the -h flags gives a help message. Given the -q suppresses output.

Getting Started

You can find pre-built executables in the Releases section.

Run the tools on some examples!

Documentation

Generated HTML documentation can be found on the website.

Check out the live demo!

EBNF File Format

See the docs for the EbnfParser. In brief:

From Matt Might's specification

• Rules look like name ::= expansion

• Every name is surrounded by angle brackets, < >.

• 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 in single-quotes.

• Simply juxtaposing expressions indicates sequencing.

• A vertical bar | indicates choice.

Example:

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

• Square brackets around an expansion, [ expansion ], indicates that this expansion is optional.

For example, the rule:

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

allows factors to be negated.

• 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.

• To indicate precedence, 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.

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
        ;

All whitespace is ignored.

Developer Guide

See primarily build.sbt, as well as

• Dependencies
• plugins

Loner is configured and built using sbt, and conforms to all the standard commands. Because it provides main methods, the project code may be run via run.

The two primary projects are loner and ebnf. Switch between them with project; loner depends on ebnf, for ease of development.

Documentation is generated via scaladocSite. sbt-site and sbt-ghpages provide site-generation tools for the website.

Tests are written using scalatest and are accessible via the standard test commands. All API features require tests—new features or bug-fixes should ensure test coverage, in the style of the originals.

It also uses the assembly plugin (providing an assembly command), which is used to generated FAT executable jars—these jars have no dependencies other than a working java runtime environment, and are uploaded in the releases section. They can be executed directly (chmod -u+x <jar> ; ./<jar>) or via java (java -jar <jar>).

Bugs

Does not support escaping special characters (yet).

Credits

This project was built while enrolled in Comp 520 at UNC Chapel Hill, taught by Dr. Jan Prins, in Spring 2019. The topics of this compilers course inspired loner.

loner's Issues

Support escaped characters

Describe the bug
EbnfParser doesn't support escaped characters via the .

To Reproduce

Run ebnf on the grammar

<S> ::= <A>$ ;
<A> ::= ( <A> );
<A> ::= x;

The parens will be eliminated, despite the intent clearly being the balanced parens grammar.

Expected behavior

Support escaping:

<S> ::= <A>$ ;
<A> ::= \( <A> \);
<A> ::= x;

Or some form of "quoting":

<S> ::= <A>$ ;
<A> ::= "(" <A> ")";
<A> ::= x;

Terminals with spaces between them do not output correctly

Describe the bug
Consider the following grammar:

<A> ::= a | b | {<C>};
<B> ::= [<A>]d<C>;
<C> ::= c;
<A> ::= edit me | ε;

Notice the space in edit me: we expect this to be preserved on output (technically, if it isn't, it's a different grammar).

ebnf gives:

<A> ::= a|b|{<C>}|editme|ε ;
<B> ::= [<A>]d<C> ;
<C> ::= c ;

While the difference is harmless for LL(1) computation, it is not in general.

To Reproduce
Steps to reproduce the behavior:

1. Access the demo
2. See error

Desktop (please complete the following information):

• OS: OS X 10.11.6
• Scala/JVM Version: 2.12.8
• ebnf/loner version: 0.2.0

Additional context

The parser builds the correct syntax tree, but fails to keep the space separating the terminals edit and me...

Grammar(
  List(
    Production(
      Nonterminal('A),
      Alternation(
        Alternation(
          Alternation(
            Terminal(a),
            Terminal(b)),
          Repetition(
            Nonterminal('C))),
        Alternation(
          Sequence(
            Terminal(edit),
            Terminal(me)),
          ε))),
    Production(
      Nonterminal('B),
      Sequence(
        Sequence(
          Option(
            Nonterminal('A)),
          Terminal(d)),
        Nonterminal('C))),
    Production(
      Nonterminal('C),
      Terminal(c))))

Simplify build process

Currently, anyone with sbt can clone the project and do whatever they want in terms of build.

Every one else has the option of downloading a fully executable jar file, built by the command assembly in sbt.

This seems... non-standard. Is there a cleaner/simpler way to do this?

Web demo: display Starter/Follower/Predict sets

What it says on the box. Could be a simple addition.

Do a better job parsing command line arguments

The code over in ebnf/src/.../Main.scala to handle the arguments is a bit messy. We could consider some kind of third-party library, but I'd rather not inflate the size of the FAT jar needlessly.