Bachelor's thesis binary

Thesis title: Parsing algorithms for context-free languages

Installation

Download and install Rust via the installer rustup.

Set the Rust version to 1.33.0.

rustup default 1.33.0

To install the binary system-wide, issue the following command:

cargo install --path .

(working directory should be thesis_bin)

Afterwards, a REPL can be started, by executing the following command for a grammar file of your choice.

thesis_bin -g <your/grammar/file>

Notice that the input must be separated by whitespace. When submitting your input to the REPL the whole string is regarded as one possible word of the language generated by the grammar. Thus typing e.g. "aaa" may lead to different results than "a a a".

Parameters and configuration

+-----------+-----------------------------------------------------+
| Parameter | Description                                         |
+===========+=====================================================+
| -p        | Selects the parsing algorithm to use                |
|           | Possible options: 'earley', 'harrison', 'll1', 'lr1'|
|           | Will default to 'earley' if not specified otherwise |
+-----------+-----------------------------------------------------+
| -g        | Selects the grammar file to use                     |
+-----------+-----------------------------------------------------+
| -i        | Input word to use                                   |
|           | Default to REPL if not specified                    |
+-----------+-----------------------------------------------------+
| -o        | Path to output SPPF Dot file                        |
|           | Only works for the option 'earley'                  |
+-----------+-----------------------------------------------------+
| -f        | Outputs the FIRST and FOLLOW sets                   |
+-----------+-----------------------------------------------------+

For more information use

thesis_bin --help

Grammar files

Grammar files contain production rules in extended Backus-Naur form (EBNF).

Example:

S' = S .
S = S S | "a" | .

Terminal symbols must be enclosed by quotes. See the grammars folder for more examples.

Extended syntax

Symbol	Meaning
Pipe	Alternative
( )	Group
{ }	One or more
[ ]	Zero or more

Local installation and testing

To generate the debug-build, issue the following command:

cargo build

In order to run the unit tests use the following command:

cargo test

If you want to run the program without installing it system-wide, use

cargo run -- <parameters-for-bin>

Test system application versions

Tested on macOS Mojave, Ubuntu 18.10

rustup 1.18.3
rustc 1.33.0
cargo 1.33.0

If you have a newer version installed, please revert to 1.33.0 with

rustup default 1.33.0

License

Copyright (c) Alexander Koch 2019