Parse the String ( a + b ) * c using Shift Reduce
Parsing from the given grammar.
1.
E →(E)
2.
E →E+E
3.
E →E*E
4.
E →a | b | c
Answer:
|
Stack
|
Input
|
Operation
|
|
$
|
( a + b ) * c
|
Push (
|
|
$ (
|
a + b ) * c
|
Push a
|
|
$ ( a
|
+ b ) * c
|
Pop a & push E as E →a
|
|
$ ( E
|
+ b ) * c
|
Push +
|
|
$ ( E +
|
b ) * c
|
Push b
|
|
$ ( E + b
|
) * c
|
Pop b & push E as E →b
|
|
$ ( E + E
|
) * c
|
Pop E + E & push E as E →E + E
|
|
$ ( E
|
) * c
|
Push )
|
|
$ ( E )
|
* c
|
Pop ( E ) & push E as E → ( E )
|
|
$ E
|
* c
|
Push *
|
|
$ E *
|
c
|
Push c
|
|
$ E * c
|
$
|
Pop c & push E as E → c
|
|
$ E * E
|
$
|
Pop E * E & push E as E →E * E
|
|
$ E
|
$
|
Accept
|
Implementation in JAVA:
Compiler.java
import static java.lang.System.out;
import java.util.Scanner;
public class Compiler
{
static Scanner
s=new Scanner(System.in);
public static void
main(String args[])
{
out.print("How many Rule? :");
int
r=s.nextInt();
String[][]
rule=new String[r][2];
out.println("Enter The Rule:");
int i,j;
for(i=0;i
{
for(j=0;j<2 j="j" p="p">
rule[i][j]=s.next();
}
out.println("Rules are:");
for(i=0;i
{
for(j=0;j<2 j="j" p="p">
{
out.print(rule[i][j]);
if(j==0) out.print(" -> ");
}
out.println();
}
int choice;
do
{
out.println("Enter the String:");
String
str=s.next();
Stack stck=new
Stack(str.length());
for(j=0;j
{
out.println("PUSH
: "+str.charAt(j));
stck.push(str.charAt(j));
out.println("top:"+stck.top);
int isPush;
do
{
isPush=0;
String
str2 = "";
for(i=stck.top-1;i>=0;i--)
{
int pos=0;
str2=new
StringBuffer(str2).insert(pos, stck.stack[i]).toString();
pos++;
for(int
k=0;k
{
out.println("Check Rule : String:"+str2);
if(str2.equals(rule[k][1]))
{
out.println("RULE MATCHED");
for(int pop=0;pop
{
out.println("POP : "+stck.pop());
}
stck.push(rule[k][0].charAt(0));
isPush=1;
out.println("PUSH : "+rule[k][0].charAt(0));
}
}
for(int
m=0;m
out.print("\nStack: "+stck.stack[m]);
out.println();
}
}while(isPush==1);
}
out.println("\nFINALLY IN THE STACK:");
for(i=0;i
out.print(stck.stack[i]);
out.print("\nDo you want to check for another String(0-NO/1-YES)?
");
choice=s.nextInt();
if(choice==0)
System.exit(0);
}while(choice==1);
}
}
Stack.java:
public class Stack
{
public int
top,size;
public char
stack[];
Stack(int
sizeOfStack)
{
this.size=sizeOfStack;
stack=new
char[size];
top=0;
}
public boolean
push(char x)
{
if(top==size)
return false;
else
{
stack[top++]=x;
return true;
}
}
public char pop()
{
if(top==0)
return '0';
else return
stack[--top];
}
public boolean
isEmpty()
{
if(top==0)
return true;
else return
false;
}
public boolean
isFull()
{
if(top==size)
return true;
else return
false;
}
}
OUTPUT:
How many Rule? :6
Enter The Rule:
E
a
E
b
E
c
E
E+E
E
E*E
E
(E)
Rules are:
E -> a
E -> b
E -> c
E -> E+E
E -> E*E
E -> (E)
Enter the String:
(a+b)*c
PUSH : (
top:1
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Stack: (
PUSH : a
top:2
Check Rule : String:a
RULE MATCHED
POP : a
PUSH : E
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Stack: (
Stack: E
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Stack: (
Stack: E
PUSH : +
top:3
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Stack: (
Stack: E
Stack: +
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Stack: (
Stack: E
Stack: +
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Stack: (
Stack: E
Stack: +
PUSH : b
top:4
Check Rule : String:b
Check Rule : String:b
RULE MATCHED
POP : b
PUSH : E
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
RULE MATCHED
POP : E
POP : +
POP : E
PUSH : E
Check Rule : String:E+E
Check Rule : String:E+E
Stack: (
Stack: E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Stack: (
Stack: E
PUSH : )
top:3
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Stack: (
Stack: E
Stack: )
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Stack: (
Stack: E
Stack: )
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
RULE MATCHED
POP : )
POP : E
POP : (
PUSH : E
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: E
PUSH : *
top:2
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Stack: E
Stack: *
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Stack: E
Stack: *
PUSH : c
top:3
Check Rule : String:c
Check Rule : String:c
Check Rule : String:c
RULE MATCHED
POP : c
PUSH : E
Check Rule : String:c
Check Rule : String:c
Check Rule : String:c
Stack: E
Stack: *
Stack: E
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Stack: E
Stack: *
Stack: E
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Stack: E
Stack: *
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: E
Stack: *
Stack: E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Stack: E
Stack: *
Stack: E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
RULE MATCHED
POP : E
POP : *
POP : E
PUSH : E
Check Rule : String:E*E
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: E
FINALLY IN THE STACK:
E
Do you want to check for another String(0-NO/1-YES)? 1
Enter the String:
(a+b)
PUSH : (
top:1
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Stack: (
PUSH : a
top:2
Check Rule : String:a
RULE MATCHED
POP : a
PUSH : E
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Stack: (
Stack: E
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Stack: (
Stack: E
PUSH : +
top:3
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Stack: (
Stack: E
Stack: +
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Stack: (
Stack: E
Stack: +
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Stack: (
Stack: E
Stack: +
PUSH : b
top:4
Check Rule : String:b
Check Rule : String:b
RULE MATCHED
POP : b
PUSH : E
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
RULE MATCHED
POP : E
POP : +
POP : E
PUSH : E
Check Rule : String:E+E
Check Rule : String:E+E
Stack: (
Stack: E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Stack: (
Stack: E
PUSH : )
top:3
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Stack: (
Stack: E
Stack: )
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Stack: (
Stack: E
Stack: )
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
RULE MATCHED
POP : )
POP : E
POP : (
PUSH : E
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Stack: E
FINALLY IN THE STACK:
E
Do you want to check for another String(0-NO/1-YES)? 0
BUILD SUCCESSFUL (total time: 48 seconds)
No comments:
Post a Comment