LR(0) - Parsing

The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a wide class of context-free grammar which makes it the most efficient syntax analysis technique. LR parsers are also known as LR(k) parsers, where L stands for left-to-right scanning of the input stream; R stands for the construction of right-most derivation in reverse, and k denotes the number of lookahead symbols to make decisions.

Running the Code

The complete code for LR(0) has been written in main.py file. All the grammars are added in grammar directory.

Sample Execution

Grammar Used:

S->AA  
A->aA  
A->b

The following is the preview of the excecution:

 _        _______      _  _______  _   
( \      (  ____ )    / )(  __   )( \  
| (      | (    )|   / / | (  )  | \ \ 
| |      | (____)|  ( (  | | /   |  ) )
| |      |     __)  | |  | (/ /) |  | |
| |      | (\ (     ( (  |   / | |  ) )
| (____/\| ) \ \__   \ \ |  (__) | / / 
(_______/|/   \__/    \_)(_______)(_/  
                                       
 _______  _______  _______  _______ _________ _        _______ 
(  ____ )(  ___  )(  ____ )(  ____ \\__   __/( (    /|(  ____ \
| (    )|| (   ) || (    )|| (    \/   ) (   |  \  ( || (    \/
| (____)|| (___) || (____)|| (_____    | |   |   \ | || |      
|  _____)|  ___  ||     __)(_____  )   | |   | (\ \) || | ____ 
| (      | (   ) || (\ (         ) |   | |   | | \   || | \_  )
| )      | )   ( || ) \ \__/\____) |___) (___| )  \  || (___) |
|/       |/     \||/   \__/\_______)\_______/|/    )_)(_______)
                                                               

Enter grammar number: 4


---------------------------------------------------------------
Augmented Grammar
['X->.S', 'S->AA', 'A->aA', 'A->b']
---------------------------------------------------------------
Total States:  7
0 : ['X->.S', 'S->.AA', 'A->.aA', 'A->.b']
1 : ['X->S.']
2 : ['S->A.A', 'A->.aA', 'A->.b']
3 : ['A->a.A', 'A->.aA', 'A->.b']
4 : ['A->b.']
5 : ['S->AA.']
6 : ['A->aA.']
---------------------------------------------------------------


+---+----+--------+----+---+--------+
|   |    | Action |    |   | Goto   |
+===+====+========+====+===+========+
|   | $  | a      | b  | A | S      |
+---+----+--------+----+---+--------+
| 0 |    | S3     | S4 | 2 | 1      |
+---+----+--------+----+---+--------+
| 1 |    |        |    |   | Accept |
+---+----+--------+----+---+--------+
| 2 |    | S3     | S4 | 5 |        |
+---+----+--------+----+---+--------+
| 3 |    | S3     | S4 | 6 |        |
+---+----+--------+----+---+--------+
| 4 | r4 | r4     | r4 |   |        |
+---+----+--------+----+---+--------+
| 5 | r5 | r5     | r5 |   |        |
+---+----+--------+----+---+--------+
| 6 | r6 | r6     | r6 |   |        |
+---+----+--------+----+---+--------+


Enter the string to be parsed: aabb


The string aab is parsable! Please find the parsing table in parsable_strings/4/a2b1.txt.

If the string is parsable, the output parsing table is saved in the parsable_strings directory. Here is how it looks like:

+-----------------------+------------+--------+-----------------------------+  
| Process               | Look Ahead | Symbol | Stack                       |  
+=======================+============+========+=============================+  
| Action(0, a) = S3     | 0          | a      | [0, 'a', 3]                 |  
+-----------------------+------------+--------+-----------------------------+  
| Action(3, a) = S3     | 1          | a      | [0, 'a', 3, 'a', 3]         |  
+-----------------------+------------+--------+-----------------------------+  
| Action(3, b) = S4     | 2          | b      | [0, 'a', 3, 'a', 3, 'b', 4] |  
+-----------------------+------------+--------+-----------------------------+  
| Action(4, b) = r3     | 3          | b      | [0, 'a', 3, 'a', 3, 'A']    |  
+-----------------------+------------+--------+-----------------------------+  
| goto(3, A) = 6        | 3          | b      | [0, 'a', 3, 'a', 3, 'A', 6] |  
+-----------------------+------------+--------+-----------------------------+  
| Action(6, b) = r2     | 3          | b      | [0, 'a', 3, 'A']            |  
+-----------------------+------------+--------+-----------------------------+  
| goto(3, A) = 6        | 3          | b      | [0, 'a', 3, 'A', 6]         |  
+-----------------------+------------+--------+-----------------------------+  
| Action(6, b) = r2     | 3          | b      | [0, 'A']                    |  
+-----------------------+------------+--------+-----------------------------+  
| goto(0, A) = 2        | 3          | b      | [0, 'A', 2]                 |  
+-----------------------+------------+--------+-----------------------------+  
| Action(2, b) = S4     | 3          | b      | [0, 'A', 2, 'b', 4]         |  
+-----------------------+------------+--------+-----------------------------+  
| Action(4, $) = r3     | 4          | $      | [0, 'A', 2, 'A']            |  
+-----------------------+------------+--------+-----------------------------+  
| goto(2, A) = 5        | 4          | $      | [0, 'A', 2, 'A', 5]         |  
+-----------------------+------------+--------+-----------------------------+  
| Action(5, $) = r1     | 4          | $      | [0, 'S']                    |  
+-----------------------+------------+--------+-----------------------------+  
| goto(0, S) = 1        | 4          | $      | [0, 'S', 1]                 |  
+-----------------------+------------+--------+-----------------------------+  
| Action(1, $) = Accept | 4          | $      | [0, 'S', 1]                 |  
+-----------------------+------------+--------+-----------------------------+

Packages Used

• pyfiglet
• termtables

Grammar Syntax

• For every production, the head and the body of the production is separated by ->.
• Capitalized symbols are treated as non-terminals and non-capitalized symbols are treated as terminals.
• The choice operator is currently not supported and should be entered as a separate production.