Q.What is Left Recursion ?
Ans. In the grammar any production in the form of A -> Αα /β called Left Recursion production.
LHS of the production ,A is appears in the left symbol of the RHS production.That's why it is left recursion.
when parser try to parse it, recursively it come back to the origin and will not be terminate.
Q.How to remove ?
Ans. write the production in the form Α -> βΑ' and A' -> αΑ'/ε .
Step 1 :-write the production A -> βΑ', // where A' is another Non -terminal.
Step 2 :- Again A' -> αΑ'/ε
Example :-
Q 1. E -> E+T / T T -> T*F / F
F -> (E) / id
Ans. Here first and second production contain left recursion.
for first production E -> E+T / T
α =+Τ and β =T,so
E -> TE'
E'-> +TE'/ε
for second production T -> T*F / F
α =*F and β =F,so
T -> FT'
T'-> *T'/ε
Hence, The complete solution will be E -> TE'
E'-> +TE'/ε
Example :-
Q 1. E -> E+T / T
F -> (E) / id
Ans. Here first and second production contain left recursion.
for first production E -> E+T / T
α =+Τ and β =T,so
E -> TE'
E'-> +TE'/ε
for second production T -> T*F / F
α =*F and β =F,so
T -> FT'
T'-> *T'/ε
Hence, The complete solution will be E -> TE'
E'-> +TE'/ε
T -> FT'
T'-> *T'/ε
F -> (E) / id
Q 2. A -> Aa /b/Ac/d
Ans. Here Aa and Ac contain left recursion.
for first production A -> Aa / b
α =a and β =b,so
A -> bA'
A' -> aA'/ε
for second production A -> Ac / d
α =c and β =d,so
A -> dA"
A"-> cA"/ε
Hence, The complete solution will be A -> bA'/dA"
A' -> aA'/ε
Ans. Here Aa and Ac contain left recursion.
for first production A -> Aa / b
α =a and β =b,so
A -> bA'
A' -> aA'/ε
for second production A -> Ac / d
α =c and β =d,so
A -> dA"
A"-> cA"/ε
Hence, The complete solution will be A -> bA'/dA"
A' -> aA'/ε
A"-> cA"/ε
Note:- The order of the A -> Aa /b/Ac/d may be any but we have to combine two - two part separately and try to solve.
Program
input format:-
Enter the number of productions : 3
Enter the productions
E->E+T/T // note that there is not space
T->T*F/F
F->(E)/id
output:-
Given Productions
E->E+T/T
T->T*F/F
F->(E)/id
Non Terminals : ETF
T -> T*F/F
E -> E+T/T
F -> (E)/id
After removing Left Recursions
T ->
E ->
F -> (E)/id
kT -> *F/F *F/FkT
kE -> +T/T +T/TkE
import java.util.Stack;
import java.util.Iterator;
import java.util.Set;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
class EliminateLeftRecursion {
static String[] productions;
static String tempNT = "";
static HashMap<String, String[]> hmap = new HashMap<String, String[]>();
static void initHash() {
Stack<String> stack[] = new Stack[tempNT.length()];
String[] hmapString;
for(int i = 0; i < stack.length; i++)
stack[i] = new Stack<String>();
for(int i = 0; i < productions.length; i++)
stack[tempNT.indexOf(productions[i].charAt(0))].push(productions[i].substring(3));
for(int i = 0; i < stack.length; i++) {
hmapString = new String[stack[i].size()];
if(!stack[i].empty()) {
for(int j = 0; !stack[i].empty(); j++)
hmapString[j] = stack[i].pop();
hmap.put((tempNT.charAt(i) + ""), hmapString);
}
}
}
static void printProductions() {
for(int i = 0; i < productions.length; i++)
System.out.println(productions[i]);
}
static void removeImmediate(String indexName, String[] q) {
Stack<String> q1 = new Stack<String>();
Stack<String> q2 = new Stack<String>();
for(int i = 0; i < q.length; i++) {
if (indexName.equals(q[i].charAt(0) + ""))
q1.push(q[i]); //Recursive productions
else
q2.push(q[i]);
}
if(!q1.empty()) {
hmap.remove(indexName);
String[] hmapString = new String[2 * q2.size()];
int i = 0;
while(!q2.empty()) {
hmapString[i++] = q2.peek();
hmapString[i++] = (q2.pop() + "k" + indexName);
}
hmap.put(indexName, hmapString);
hmapString = new String[2 * q1.size()];
i = 0;
while(!q1.empty()) {
hmapString[i++] = q1.peek().substring(1);
hmapString[i++] = (q1.pop().substring(1) + "k" + indexName);
}
hmap.put(("k" + indexName), hmapString);
}
}
static void printHashMap() {
Set set = hmap.entrySet();
Iterator i = set.iterator();
String keyName;
String keyValues[];
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
keyName = me.getKey().toString();
keyValues = hmap.get(keyName);
System.out.print("\n" + keyName + " -> ");
for(int j = 0; j < keyValues.length; j++)
System.out.print(keyValues[j] + " ");
}
}
static void findNonTerminals() {
for(int i = 0; i < productions.length; i++)
for(int j = 0; j < productions[i].length(); j++)
if((productions[i].charAt(j) >= 'A' && productions[i].charAt(j) <= 'Z') && (tempNT.indexOf(productions[i].charAt(j)) == -1))
tempNT += productions[i].charAt(j);
System.out.println("\nNon Terminals : " + tempNT);
}
public static void main(String ar[]) {
Scanner terminal = new Scanner(System.in);
System.out.print("Enter the number of productions : ");
int noProductions = terminal.nextInt();
terminal = new Scanner(System.in);
productions = new String[noProductions];
System.out.println("Enter the productions");
for(int i = 0; i < noProductions; i++)
productions[i] = terminal.nextLine();
System.out.println("\nGiven Productions");
printProductions();
findNonTerminals();
initHash();
printHashMap();
for(int i = 0; i < tempNT.length(); i++)
if(hmap.containsKey(tempNT.charAt(i) + ""))
removeImmediate((tempNT.charAt(i) + ""), hmap.get(tempNT.charAt(i) + ""));
while(removeIndirect()){}
for(int i = 0; i < tempNT.length(); i++)
if(hmap.containsKey(tempNT.charAt(i) + ""))
removeImmediate((tempNT.charAt(i) + ""), hmap.get(tempNT.charAt(i) + ""));
System.out.print("\n\nAfter removing Left Recursions");
printHashMap();
System.out.println();
}
static boolean removeIndirect() {
Set set = hmap.entrySet();
Iterator i = set.iterator();
String keyName;
String keyValues[];
Stack<String> tempp = new Stack<String>();
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
keyName = me.getKey().toString();
keyValues = hmap.get(keyName);
for(int j = 0; j < keyValues.length; j++)
if(keyValues[j].charAt(0) >= 'A' && keyValues[j].charAt(0) <= 'Z' && hmap.containsKey(keyValues[j].charAt(0) + ""))
if(tempNT.indexOf(keyName.charAt(0)) > tempNT.indexOf(keyValues[j].charAt(0))) {
String[] sub = hmap.get(keyValues[j].charAt(0) + "");
for(int z = 0; z < keyValues.length; z++)
if(z != j)
tempp.push(keyValues[z]);
for(int z = 0; z < sub.length; z++)
tempp.push(sub[z] + keyValues[j].substring(1));
String[] hmapString = new String[tempp.size()];
for(int z = 0; !tempp.empty(); z++)
hmapString[z] = tempp.pop();
hmap.put(keyName, hmapString);
return true;
}
}
return false;
}
}
No comments:
Post a Comment
Please do not enter any spam link in the comment Box