SLR Parser
Implementation of Simple LR (SLR) Parser for educational purposes.
$ slr -g grammar.txt "id + id * id"
AUGMENTED GRAMMAR:
0: E' -> E
1: E -> E + T
2: E -> T
3: T -> T * F
4: T -> F
5: F -> ( E )
6: F -> id
TERMINALS: ), id, +, *, (
NONTERMINALS: E, F, E', T
SYMBOLS: ), E, id, +, T, *, F, E', (
FIRST:
E' = { id, ( }
E = { id, ( }
T = { id, ( }
F = { id, ( }
FOLLOW:
E' = { $ }
E = { $, ), + }
T = { ), +, $, * }
F = { ), +, $, * }
PARSING TABLE:
+--------+-----------------------------------------------------+--------------------------+
| | ACTION | GOTO |
| STATE +--------+--------+--------+--------+--------+--------+--------+--------+--------+
| | ) | id | + | * | ( | $ | E | F | T |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 0 | | s2 | | | s5 | | 1 | 4 | 3 |
| 1 | | | s6 | | | acc | | | |
| 2 | r6 | | r6 | r6 | | r6 | | | |
| 3 | r2 | | r2 | s7 | | r2 | | | |
| 4 | r4 | | r4 | r4 | | r4 | | | |
| 5 | | s2 | | | s5 | | 8 | 4 | 3 |
| 6 | | s2 | | | s5 | | | 4 | 9 |
| 7 | | s2 | | | s5 | | | 10 | |
| 8 | s11 | | s6 | | | | | | |
| 9 | r1 | | r1 | s7 | | r1 | | | |
| 10 | r3 | | r3 | r3 | | r3 | | | |
| 11 | r5 | | r5 | r5 | | r5 | | | |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
+------+--------------+-------------+----------------+----------------------+
| | STACK | SYMBOLS | INPUT | ACTION |
+------+--------------+-------------+----------------+----------------------+
| (1) | 0 | | id + id * id $ | shift |
| (2) | 0 2 | id | + id * id $ | reduce by F -> id |
| (3) | 0 4 | F | + id * id $ | reduce by T -> F |
| (4) | 0 3 | T | + id * id $ | reduce by E -> T |
| (5) | 0 1 | E | + id * id $ | shift |
| (6) | 0 1 6 | E + | id * id $ | shift |
| (7) | 0 1 6 2 | E + id | * id $ | reduce by F -> id |
| (8) | 0 1 6 4 | E + F | * id $ | reduce by T -> F |
| (9) | 0 1 6 9 | E + T | * id $ | shift |
| (10) | 0 1 6 9 7 | E + T * | id $ | shift |
| (11) | 0 1 6 9 7 2 | E + T * id | $ | reduce by F -> id |
| (12) | 0 1 6 9 7 10 | E + T * F | $ | reduce by T -> T * F |
| (13) | 0 1 6 9 | E + T | $ | reduce by E -> E + T |
| (14) | 0 1 | E | $ | accept |
+------+--------------+-------------+----------------+----------------------+
Installation
Requirements
- Python 3.6+
Stable release
To install slr-parser, run this command in your terminal:
pip install slr-parser
This is the preferred method to install slr-parser, as it will always install the most recent stable release.
If you don't have pip installed, this Python installation guide can guide you through the process.
From sources
The sources for slr-parser can be downloaded from the Github repo.
You can either clone the public repository:
git clone git://github.com/Vipul97/slr-parser
Or download the tarball:
curl -OJL https://github.com/Vipul97/slr-parser/tarball/master
Once you have a copy of the source, you can install it with:
python setup.py install
Usage
Grammar Syntax
- For every production, the head and the body of the production is separated by
->. - Capitalized symbols are treated as nonterminals and non-capitalized symbols are treated as terminals.
- All symbols in the body of the production are separated by spaces. Multicharacter symbols can be made by not including spaces between the characters.
- The choice operator
|can be used in the body of the production to match either the expression before or the expression after the operator. -
^is treated as the null symbol.
Grammar File
A text file containing the grammar is required. For example, the contents of a grammar file grammar.txt looks like this:
E -> E + T
E -> T
T -> T * F | F
F -> ( E )
F -> id
Tokens
The tokens enclosed within double quotes are required as the input to the SLR Parser. All tokens are separated with spaces. For example, "id + id * id".
usage: slr [-h] [-g] grammar_file tokens
positional arguments:
grammar_file text file to be used as grammar
tokens tokens to be parsed - all tokens are separated with spaces
optional arguments:
-h, --help show this help message and exit
-g generate automaton
Contributing
Please read CONTRIBUTING.md for details on code of conduct, and the process for submitting pull requests.
License
This project is licensed under the MIT License - see the LICENSE file for details.
