LL1-Parser

LL1 parser implementation. A program to generate an LL(1) parser for a given grammar and to parse input strings.

For following grammer and input string: a+a*a+a

Output:

Grammar:

   E -> TX
   X -> +TX
   X -> ε
   T -> FY
   Y -> *FY
   Y -> ε
   F -> (E)
   F -> a

First sets: 

   E : [ '(', 'a' ]
   T : [ '(', 'a' ]
   F : [ '(', 'a' ]
   ( : [ '(' ]
   a : [ 'a' ]
   X : [ '+', 'ε' ]
   + : [ '+' ]
   Y : [ '*', 'ε' ]
   * : [ '*' ]
   ) : [ ')' ]

Follow sets: 

   E : [ '$', ')' ]
   X : [ '$', ')' ]
   T : [ '+', '$', ')' ]
   Y : [ '+', '$', ')' ]
   F : [ '*', '+', '$', ')' ]

NonTerminals: E,X,T,Y,F
Terminals: +,ε,*,(,),a

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │ + │ ε │ * │ ( │ ) │ a │ $ │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ E │   │   │   │ 1 │   │ 1 │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ X │ 2 │   │   │   │ 3 │   │ 3 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ T │   │   │   │ 4 │   │ 4 │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ Y │ 6 │   │ 5 │   │ 6 │   │ 6 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ F │   │   │   │ 7 │   │ 8 │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

┌───────────────┬───────────┬──────────┬──────────┐
│ CONSUMEDINPUT │ STACK     │ REMAIN   │ ACTION   │
├───────────────┼───────────┼──────────┼──────────┤
│               │ $,X,T     │ a+a*a+a$ │ TX       │
├───────────────┼───────────┼──────────┼──────────┤
│               │ $,X,Y,F   │ a+a*a+a$ │ FY       │
├───────────────┼───────────┼──────────┼──────────┤
│               │ $,X,Y,a   │ a+a*a+a$ │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X,Y     │ +a*a+a$  │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X,ε     │ +a*a+a$  │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X       │ +a*a+a$  │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X,T,+   │ +a*a+a$  │ +TX      │
├───────────────┼───────────┼──────────┼──────────┤
│ a+            │ $,X,T     │ a*a+a$   │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+            │ $,X,Y,F   │ a*a+a$   │ FY       │
├───────────────┼───────────┼──────────┼──────────┤
│ a+            │ $,X,Y,a   │ a*a+a$   │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a           │ $,X,Y     │ *a+a$    │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a           │ $,X,Y,F,* │ *a+a$    │ *FY      │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*          │ $,X,Y,F   │ a+a$     │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*          │ $,X,Y,a   │ a+a$     │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X,Y     │ +a$      │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X,ε     │ +a$      │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X       │ +a$      │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X,T,+   │ +a$      │ +TX      │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+        │ $,X,T     │ a$       │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+        │ $,X,Y,F   │ a$       │ FY       │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+        │ $,X,Y,a   │ a$       │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,X,Y     │ $        │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,X,ε     │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,X       │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,ε       │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $         │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $         │ $        │ Accept!  │
└───────────────┴───────────┴──────────┴──────────┘
Ans: Accept! (a+a*a+a)