LL Parsing

LL parsing reads input from Left to write and and produces a Left most derivation. Following Java program uses the example provided at Wikipedia LL page.

/*
* converted to Java by Ali R+ SARAL
*/

package nbParse;

import com.sun.xml.internal.fastinfoset.util.CharArray;
import java.nio.CharBuffer;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
*
* @author Ali Riza SARAL
*/

public class LLparser {

public enum Symbols {
TS_L_PARENS, // (
TS_R_PARENS, // )
TS_A, // a
TS_PLUS, // +
TS_EOS, // $
TS_INVALID, // invalid token

// Non-terminal symbols:
NTS_S, // S
NTS_F
}



Symbols lexer(char c) {

switch (c) {

case '(':
return Symbols.TS_L_PARENS;

case ')':
return Symbols.TS_R_PARENS;

case 'a':
return Symbols.TS_A;

case '+':
return Symbols.TS_PLUS;

case '\0':
return Symbols.TS_EOS;

default:
return Symbols.TS_INVALID;
}
}

public static void main(String[] args) {

LLparser llparser = new LLparser();
System.out.println("Hello wonderful world!");
HashMap tt = new HashMap();
HashMap> table = new HashMap(); // LL Parser
Stack ss = new Stack(); // symbol stack

// char[] p = {'(','a', '+', 'a',')'}; // input buffer
char[] p = {'(','a', '+','(','a', '+', 'a',')',')'}; // input buffer
// char[] p = {'a','+','(','a', '+', 'a',')'}; // input buffer
// char[] p = {'(', 'a', '+', 'a', ')'}; // input buffer

int ppointer = 0;

// initialize the symbols stack
ss.addElement(Symbols.TS_EOS);
ss.addElement(Symbols.NTS_S);

//initialize the symbol stream cursor
ppointer = 0;

//setup the parsing table
tt.put(Symbols.TS_L_PARENS, 2);
table.put(Symbols.NTS_S, tt);

tt.put(Symbols.TS_A, 1);
table.put(Symbols.NTS_S, tt);

tt.put(Symbols.TS_A, 3);
table.put(Symbols.NTS_F, tt);

System.out.println("ss= " + ss.toString());
System.out.println("tt=" + tt);
System.out.println("table=" + table);
System.out.println("p= " + "(a+a)");

while (ss.size() > 1) {
System.out.println("\nppointer= " + ppointer);
System.out.println("lexer(p(ppointer))= " + llparser.lexer(p[ppointer]));
System.out.println("ss.lastElement= " + ss.lastElement());

if (llparser.lexer(p[ppointer]) == ss.lastElement()) {
System.out.println("Matched symbols " + llparser.lexer(p[ppointer]));

ppointer++;

ss.pop();

if (ppointer > (p.length - 1)) {

System.out.println("\nEnd of input string");
System.out.println(ss.toString());

if (ss.size() > 1) {
System.out.println("Parse is unsuccessful");
}

return;
}
} else {
HashMap tableItem = table.get(ss.lastElement());
System.out.println("Rule " + tableItem.get(llparser.lexer(p[ppointer])));

switch (tableItem.get(llparser.lexer(p[ppointer]))) {

case 1: // 1. s-> F
System.out.println("1. s-> F");
ss.pop();
ss.push(Symbols.NTS_F); // F
break;

case 2: // 2. s-> ( S + F )
System.out.println("2 s-> ( S + F )");
ss.pop();
ss.push(Symbols.TS_R_PARENS); // )
ss.push(Symbols.NTS_F); // F
ss.push(Symbols.TS_PLUS); // +
ss.push(Symbols.NTS_S); // S
ss.push(Symbols.TS_L_PARENS); // (

break;

case 3: // F -> A
System.out.println("3 F -> A");

ss.pop();
ss.push(Symbols.TS_A); // a

break;

default:
System.out.println("Parsing table default");

return;
}
}

System.out.println("ss= " + ss.toString());
System.out.println("ss.size()= " + ss.size());
}

System.out.println("Finished parsing");

return;
}
}



Output:

run:

Hello wonderful world!

ss= [TS_EOS, NTS_S]
tt={TS_A=3, TS_L_PARENS=2}
table={NTS_F={TS_A=3, TS_L_PARENS=2}, NTS_S={TS_A=3, TS_L_PARENS=2}}
p= (a+a)
ppointer= 0
lexer(p(ppointer))= TS_L_PARENS
ss.lastElement= NTS_S

Rule 2
2 s-> ( S + F )
ss= [TS_EOS, TS_R_PARENS, NTS_F, TS_PLUS, NTS_S, TS_L_PARENS]
ss.size()= 6

ppointer= 0
lexer(p(ppointer))= TS_L_PARENS
ss.lastElement= TS_L_PARENS

Matched symbols TS_L_PARENS
ss= [TS_EOS, TS_R_PARENS, NTS_F, TS_PLUS, NTS_S]
ss.size()= 5



ppointer= 1
lexer(p(ppointer))= TS_A
ss.lastElement= NTS_S

Rule 3
3 F -> A
ss= [TS_EOS, TS_R_PARENS, NTS_F, TS_PLUS, TS_A]
ss.size()= 5

ppointer= 1
lexer(p(ppointer))= TS_A
ss.lastElement= TS_A

Matched symbols TS_A
ss= [TS_EOS, TS_R_PARENS, NTS_F, TS_PLUS]
ss.size()= 4

ppointer= 2
lexer(p(ppointer))= TS_PLUS
ss.lastElement= TS_PLUS

Matched symbols TS_PLUS
ss= [TS_EOS, TS_R_PARENS, NTS_F]
ss.size()= 3

ppointer= 3
lexer(p(ppointer))= TS_L_PARENS
ss.lastElement= NTS_F

Rule 2
2 s-> ( S + F )
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS, NTS_F, TS_PLUS, NTS_S, TS_L_PARENS]
ss.size()= 7

ppointer= 3
lexer(p(ppointer))= TS_L_PARENS
ss.lastElement= TS_L_PARENS

Matched symbols TS_L_PARENS
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS, NTS_F, TS_PLUS, NTS_S]
ss.size()= 6

ppointer= 4
lexer(p(ppointer))= TS_A
ss.lastElement= NTS_S

Rule 3
3 F -> A
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS, NTS_F, TS_PLUS, TS_A]
ss.size()= 6

ppointer= 4
lexer(p(ppointer))= TS_A
ss.lastElement= TS_A

Matched symbols TS_A
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS, NTS_F, TS_PLUS]
ss.size()= 5

ppointer= 5
lexer(p(ppointer))= TS_PLUS
ss.lastElement= TS_PLUS

Matched symbols TS_PLUS
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS, NTS_F]
ss.size()= 4

ppointer= 6
lexer(p(ppointer))= TS_A
ss.lastElement= NTS_F

Rule 3
3 F -> A
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS, TS_A]
ss.size()= 4

ppointer= 6
lexer(p(ppointer))= TS_A
ss.lastElement= TS_A

Matched symbols TS_A
ss= [TS_EOS, TS_R_PARENS, TS_R_PARENS]
ss.size()= 3

ppointer= 7
lexer(p(ppointer))= TS_R_PARENS
ss.lastElement= TS_R_PARENS

Matched symbols TS_R_PARENS
ss= [TS_EOS, TS_R_PARENS]
ss.size()= 2

ppointer= 8
lexer(p(ppointer))= TS_R_PARENS
ss.lastElement= TS_R_PARENS

Matched symbols TS_R_PARENS


End of input string
[TS_EOS]

BUILD SUCCESSFUL (total time: 0 seconds)