An implementation of a 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, E', T, F
SYMBOLS: *, E, id, E', +, ), T, F, (
FIRST:
E' = { (, id }
E = { id, ( }
T = { (, id }
F = { id, ( }
FOLLOW:
E' = { $ }
E = { $, +, ) }
T = { *, +, ), $ }
F = { *, +, ), $ }
PARSING TABLE:
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| | ACTION | GOTO |
| STATE +--------+--------+--------+--------+--------+--------+--------+--------+--------+
| | * | id | + | ) | ( | $ | E | T | F |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 0 | | s2 | | | s5 | | 1 | 3 | 4 |
| 1 | | | s6 | | | acc | | | |
| 2 | r6 | | r6 | r6 | | r6 | | | |
| 3 | s7 | | r2 | r2 | | r2 | | | |
| 4 | r4 | | r4 | r4 | | r4 | | | |
| 5 | | s2 | | | s5 | | 8 | 3 | 4 |
| 6 | | s2 | | | s5 | | | 9 | 4 |
| 7 | | s2 | | | s5 | | | | 10 |
| 8 | | | s6 | s11 | | | | | |
| 9 | s7 | | r1 | r1 | | 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 $ | shift |
| (5) | 0 3 7 | T * | id + id $ | shift |
| (6) | 0 3 7 2 | T * id | + id $ | reduce by F -> id |
| (7) | 0 3 7 10 | T * F | + id $ | reduce by T -> T * F |
| (8) | 0 3 | T | + id $ | reduce by E -> T |
| (9) | 0 1 | E | + id $ | shift |
| (10) | 0 1 6 | E + | id $ | shift |
| (11) | 0 1 6 2 | E + id | $ | reduce by F -> id |
| (12) | 0 1 6 4 | E + F | $ | reduce by T -> F |
| (13) | 0 1 6 9 | E + T | $ | reduce by E -> E + T |
| (14) | 0 1 | E | $ | accept |
+------+----------+---------+----------------+----------------------+
- Python 3.12+
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.
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
- Each production rule is written with the head and body separated by
->. - Nonterminals are capitalized (e.g.,
E,T); terminals are not (e.g.,id,+). - Symbols in the body of the production are separated by spaces. For multi-character symbols, spaces are omitted (e.g.,
id). - The choice operator
|can be used to separate alternatives in the body. - The null symbol is represented by
^.
The grammar should be provided in a text file. Here's an example grammar.txt:
E -> E + T
E -> T
T -> T * F | F
F -> ( E )
F -> id
The input tokens must be enclosed in double quotes and separated by spaces. For example: "id * id + id".
usage: slr [-h] [-g] grammar_file tokens
positional arguments:
grammar_file Path to the text file used as grammar
tokens Tokens to be parsed, separated by spaces
optional arguments:
-h, --help show this help message and exit
-g Generate automaton
Please read CONTRIBUTING.md for details on code of conduct, and the process for submitting pull requests.
This project is licensed under the MIT License - see the LICENSE file for details.