Jitu's Pensieve: SPCC (System Programming and Compiler Construction) practical programs

Views:

These are the System Programming and Compiler Construction (SPCC) programs for practical exam of TE COMPS (2011-12). Refer it and modify according to the need.
(You can download all the SPCC programs from SkyDrive. Click here to download...)

1. TWO PASS ASSEMBLER

/* Note: Please create a Sp.txt file at the same place where you are saving this .java file. Copy the these lines in the text file

JOHN START 0

USING *,15

L 1,FIVE

A 1,FOUR

ST 1,TEMP

FOUR DC F'4'

FIVE DC F'5'

TEMP DS 1F

END

and only then compile and run the program.
*/

import java.io.*;

class Assembler

{

FileInputStream fin= new FileInputStream("Sp.txt");

DataInputStream in= new DataInputStream(fin);

String s[]=new String[20]; int n,i;

String mot[][]=new String[20][20]; int top;

String pot[][]=new String[20][20]; int top1;

String st[][]=new String[20][20]; int top2;

String bt[][]=new String[20][2];

String lt[][]=new String[20][20]; int top3;

String pass1[][]=new String[20][20]; int top4;

String pass2[][]=new String[20][20];

int j,lc,reg,f1,f2,f3;

boolean flag;

Assembler()throws IOException

{

i=top=top1=top2=top3=top4=-1;

String temp=in.readLine();

while(temp!=null)

{

s[++i]=temp;

temp=in.readLine();

}

n=i;

for(j=0;j<=15;j++)

{

bt[j][0]="N";

bt[j][1]="-";

}

void initialize()

{

String psedo_char[]={ "START" , "USING" , "DROP" , "EQU" , "END" , "DS" , "DC" };

String mcop[]={ "A" , "L" , "ST" , "MVC" };

String dtype[]= { "DS" , "DC" };

compute(psedo_char,mcop,dtype);

display();

}

void compute(String psedo_char[],String mcop[],String dtype[])

{

int p1,p2,p3,p4;

String s1;

char c1;

f1=f2=f3=-1;

boolean f6=false;

lc=0;

flag=true;

for(i=0;i<=n;i++)

{

f1=s[i].indexOf("START");

f2=s[i].indexOf("USING");

f3=s[i].indexOf("L ");

findlc();

//MOT

for(j=0;j<4;j++)

{

p1=s[i].indexOf(mcop[j]);

if(p1!=-1)

{

p2=mcop[j].length();

c1=s[i].charAt(p1+p2);

if(c1==' ')

{

p3=s[i].lastIndexOf(",");

p4=s[i].indexOf("USING");

flag=check(mot,top,mcop[j]);

if(flag)

{

mot[++top][0]=mcop[j];

mot[top][1]=Integer.toHexString(45*(top+1));

mot[top][2]="4";

}

if((top3==-1) && i>1)

{

pass1[++top4][0]=Integer.toString(lc);

pass1[top4][1]=s[i].substring(p1,p3+1)+"_"+"(0,"+Integer.toString(reg)+")";

pass2[top4][0]=Integer.toString(lc);

pass2[top4][1]=s[i].substring(p1)+"(0,"+Integer.toString(reg)+")";

}

//POT

for(j=0;j<7;j++)

{

flag=true;

p1=s[i].indexOf(psedo_char[j]);

if(p1!=-1)

{

f6=psedo_char[j].equals("USING");

boolean f4=psedo_char[j].equals("DC");

boolean f5=psedo_char[j].equals("DS");

if(f6)

{

p2=s[i].indexOf(",");

reg=Integer.parseInt(s[i].substring(p2+1));

}

flag=check(pot,top1,psedo_char[j]);

if(flag)

{

pot[++top1][0]=psedo_char[j];

pot[top1][1]="P1"+psedo_char[j];

}

//LT

if(f4 || f5)

{

p3=s[i].lastIndexOf(" ");

p4=s[i].indexOf(" ");

lt[++top3][0]=s[i].substring(0,p4);

lt[top3][1]=s[i].substring(p3+1);

lt[top3][2]=Integer.toHexString(lc);

lt[top3][3]="1";

lt[top3][4]="R";

p3=lt[top3][1].indexOf("F'");

if(p3!=-1)

{

pass1[++top4][1]=lt[top3][1].substring(p3+2,lt[top3][1].length()-1);

pass2[top4][1]=Integer.toBinaryString(Integer.parseInt(pass1[top4][1]));

pass1[top4][0]=pass2[top4][0]=Integer.toString(lc);

}

if(f5)

{

pass1[++top4][1]=pass2[top4][1]="-";

pass1[top4][0]=pass2[top4][0]=Integer.toString(lc);

}

for(int k=0;k<=top4;k++)

pass2[k][1]=pass2[k][1].replace(lt[top3][0],Integer.toString(lc));

}

//ST

p1=s[i].charAt(0);

if(p1!=' ')

{

p2=s[i].indexOf(" ");

flag=check(st,top2,s[i].substring(0,p2));

if(flag)

{

st[++top2][0]=s[i].substring(0,p2);

st[top2][1]=Integer.toHexString(lc);

st[top2][2]="1";

st[top2][3]="R";

}

//BT

bt[reg][0]="Y";

bt[reg][1]="000";

}

void findlc()

{

if( (f1==-1 && f2==-1 && f3==-1) )

lc=lc+4;

}

boolean check(String ax[][],int ptr,String st)

{

boolean flag1=false;

if(ptr!=-1)

{

for(int l=0;l<=ptr;l++)

if(ax[l][0].equals(st))

{

flag1=true;

break;

}

if(flag1)

return false;

else

return true;

}

else

return true;

}

void display()

{

System.out.println("\nGiven Source Code:");

System.out.println();

for(i=0;i<=n;i++)

System.out.println(s[i]);

System.out.println("\nMOT:");

System.out.println("Machine-op\tBinary-op\tInstn length");

System.out.println();

for(i=0;i<=top;i++)

System.out.println(mot[i][0]+"\t\t"+mot[i][1]+"\t\t"+mot[i][2]);

System.out.println("\nPOT:");

System.out.println("Psedo-op\tRel. Address");

System.out.println();

for(i=0;i<=top1;i++)

System.out.println(pot[i][0]+"\t\t"+pot[i][1]);

System.out.println("\nST:");

System.out.println("Symbol\t\tValue\t\tLength\t\tRelocation");

System.out.println();

for(i=0;i<=top2;i++)

System.out.println(st[i][0]+"\t\t"+st[i][1]+"\t\t"+st[i][2]+"\t\t"+st[i][3]);

System.out.println("\nBT:");

System.out.println("Indicator\tAvailable"/*\tRelative addr"*/);

System.out.println();

for(i=0;i<=15;i++)

System.out.println(i+"\t\t "+bt[i][0]/*+"\t\t "+bt[i][1]*/);

System.out.println("\nLT:");

System.out.println("Literal\t\tValue\t\tLength\t\tRelocation");

System.out.println();

for(i=0;i<=top3;i++)

System.out.println(lt[i][1]+"\t\t"+lt[i][2]+"\t\t"+lt[i][3]+"\t\t"+lt[i][4]);

System.out.println("\nPass1:");

System.out.println("Rel. Addr\tMnemonic instn");

System.out.println();

for(i=0;i<=top4;i++)

System.out.println(pass1[i][0]+"\t\t"+pass1[i][1]);

System.out.println("\nPass2:");

System.out.println("Rel. Addr\tMnemonic instn");

System.out.println();

for(i=0;i<=top4;i++)

System.out.println(pass2[i][0]+"\t\t"+pass2[i][1]);

}

public static void main(String args[])throws IOException

{

Assembler as=new Assembler();

as.initialize();

}

/*
Output:

Given Source Code:

JOHN START 0

USING *,15

L 1,FIVE

A 1,FOUR

ST 1,TEMP

FOUR DC F'4'

FIVE DC F'5'

TEMP DS 1F

END

MOT:

Machine-op Binary-op Instn length

L 2d 4

A 5a 4

ST 87 4

POT:

Psedo-op Rel. Address

START P1START

USING P1USING

DC P1DC

DS P1DS

END P1END

ST:

Symbol Value Length Relocation

JOHN 0 1 R

FOUR c 1 R

FIVE 10 1 R

TEMP 14 1 R

BT:

Indicator Available

0 N

1 N

2 N

3 N

4 N

5 N

6 N

7 N

8 N

9 N

10 N

11 N

12 N

13 N

14 N

15 Y

LT:

Literal Value Length Relocation

F'4' c 1 R

F'5' 10 1 R

1F 14 1 R

Pass1:

Rel. Addr Mnemonic instn

0 L 1,_(0,15)

4 A 1,_(0,15)

8 ST 1,_(0,15)

12 4

16 5

20 -

Pass2:

Rel. Addr Mnemonic instn

0 L 1,16(0,15)

4 A 1,12(0,15)

8 ST 1,20(0,15)

12 100

16 101

20 -

Process completed.

.................................................................................................................................................

2. TWO PASS MACRO ASSEMBLER

import java.io.*;
import java.util.*;
class Macro
{
String src[]=new String[100]; int n,i;
String exp[]=new String[100]; int top2;
String mdt[]=new String[100]; int top1;
String mnt[]=new String[100]; int top;
String alt[][]=new String[100][100]; int top3,top4;
String altb[][]=new String[20][20]; int top5;
int cm[]=new int[100]; int noc;
int mdti[]=new int[100];
boolean flag;
String nom;
int j,k,x,y;

Scanner in=new Scanner(System.in);

public static void main(String args[])throws IOException
{
Macro m=new Macro();
m.expanssion();
}

Macro()throws IOException
{
i=-1;
flag=false;
top=top1=top2=top3=top5=noc=-1;
top4=1;

System.out.println("Enter the Initial source Code:");
System.out.println();
do
{
i++;
src[i]=in.nextLine();
}
while(src[i].equalsIgnoreCase("End")==false);
n=i;
for(j=0;j<20;j++)
altb[j][2]="0";
}

void expanssion()
{
for(i=0;i<=n;i++)
{
if(src[i].equalsIgnoreCase("Macro"))
{
i++;
if((src[i].indexOf(",")==-1) && (src[i].indexOf(" ")==-1))
{
mnt[++top]=src[i];
createmdt();
}
else
{
altb[++top5][1]=Integer.toString(top3+1);
parts(src[i]);
mnt[top]=nom;
altb[top5][0]=nom;
}
}
else
if(top!=-1)
{
if((src[i].indexOf(",")==-1) && (src[i].indexOf(" ")==-1))
{
nom=src[i];
check();
if(flag==true)
while(mdt[k].equalsIgnoreCase("Mend")==false)
{
exp[++top2]=mdt[k];
k++;
}
}
else
parts1(src[i]);
}
else
exp[++top2]=src[i];
}
System.out.println("\nPass-1 Output:");
pass1();
System.out.println("\nPass-2 Output:");
pass2();
}

void parts(String a)
{
int l;
noc=-1;
String na,noa;

x=a.indexOf(" ");
if((a.indexOf(",")==-1) && (a.indexOf(" ")>-1))
{
mnt[++top]=nom=a.substring(0,x);
createmdt();
na=alt[++top3][1]=a.substring(x+1,a.length());
noa=alt[top3][0]="#"+(Integer.toString(top3+1));
replacemdt(na,noa);
}
else
{
for(j=0;j<a.length();j++)
if(a.charAt(j)==',')
{
cm[++noc]=j;
}
mnt[++top]=nom=a.substring(0,x);
createmdt();
na=alt[++top3][1]=a.substring(x+1,cm[0]);
noa=alt[top3][0]="#"+(Integer.toString(top3+1));
replacemdt(na,noa);
j=0;
while(j!=noc)
{
na=alt[++top3][1]=a.substring(cm[j]+1,cm[j+1]);
noa=alt[top3][0]="#"+(Integer.toString(top3+1));
replacemdt(na,noa);
j++;
}
na=alt[++top3][1]=a.substring(cm[noc]+1,a.length());
noa=alt[top3][0]="#"+(Integer.toString(top3+1));
replacemdt(na,noa);
}
}

void parts1(String a)
{
noc=-1;
int l,p,q;

x=a.indexOf(" ");
if((a.indexOf(",")==-1) && (a.indexOf(" ")>-1))
{
nom=a.substring(0,x);
check();
if(flag==true)
{
l=checkalt(nom);
if(l!=-1)
{
q=Integer.parseInt(altb[l][2]);
q=q+1;
++q;
top4++;
p=Integer.parseInt(altb[l][1]);
alt[p++][q]=a.substring(x+1,a.length());
replaceexp(q);
altb[l][2]=Integer.toString(q-1);
}
}
}
else
{
for(j=0;j<a.length();j++)
if(a.charAt(j)==',')
{
cm[++noc]=j;
}
nom=a.substring(0,x);
check();
if(flag==true)
{
l=checkalt(nom);
if(l!=-1)
{
q=Integer.parseInt(altb[l][2]);
q=q+1;
++q;
top4++;
p=Integer.parseInt(altb[l][1]);
alt[p++][q]=a.substring(x+1,cm[0]);
j=0;
while(j!=noc)
{
alt[p++][q]=a.substring(cm[j]+1,cm[j+1]);
j++;
}
alt[p++][q]=a.substring(cm[noc]+1,a.length());
replaceexp(q);
altb[l][2]=Integer.toString(q-1);
}
}
}
}

void check()
{
flag=false;
for(j=0;j<=top;j++)
if(nom.equalsIgnoreCase(mnt[j]))
{
flag=true;
k=mdti[j];
break;
}
else
if(j<top)
continue;
else
{
exp[++top2]=src[i];
break;
}
}

void createmdt()
{
mdti[top]=top1+1;
do
{
mdt[++top1]=src[++i];
}
while(src[i].equalsIgnoreCase("Mend")==false);
}

void replacemdt(String na,String noa)
{
int l;
for(l=0;l<=top1;l++)
mdt[l]=mdt[l].replaceAll(na,noa);
}

void replaceexp(int q)
{
System.out.println("q= "+q);
while(mdt[k].equalsIgnoreCase("Mend")==false)
{
int d=0;
for(d=0;d<=top3;d++)
if((mdt[k].indexOf(alt[d][0]))!=-1)
exp[++top2]=mdt[k].replaceAll(alt[d][0],alt[d][q]);
k++;
}
}

int checkalt(String mn)
{
if(top5!=-1)
for(int l=0;l<=top5;l++)
if(altb[l][0].equalsIgnoreCase(mn))
return l;

return -1;
}

void pass1()
{
System.out.println("\nMNT:");
System.out.println();
System.out.println("index\tMacro name\tMDT index");
for(j=0;j<=top;j++)
System.out.println((j+1)+"\t"+mnt[j]+"\t\t"+mdti[j]);

System.out.println("\nMDT:");
System.out.println();
System.out.println("index\tCard");
for(j=0;j<=top1;j++)
System.out.println(j+"\t"+mdt[j]);

System.out.println("\nALA:");
System.out.println();
System.out.println("index\tArguments");
for(int l=0;l<=top3;l++)
{
System.out.print((l+1));
for(j=1;j<=top4;j++)
System.out.print("\t"+alt[l][j]);
System.out.println();
}
}

void pass2()
{
System.out.println("\nFinal expanded Code:");
System.out.println();
for(j=0;j<=top2;j++)
System.out.println(exp[j]);
}

}
/*

Output:
Enter Initial Source Code:

mov ax,15
mov dx,10
macro
addition &arg1
add ax,&arg1
add dx,&arg1
mend
macro
average &arg2,&arg3
division &arg2
division &arg3
mend
mov ax,dx
sum 8
average 5,2
average 6,2
end
q= 2
q= 2
q= 3

Pass-1 Output:

MNT:

index Macro name MDT index
1 addition 0
2 average 3

MDT:

index Card
0 add ax,#1
1 add dx,#1
2 mend
3 division #2
4 division #3
5 mend

ALA:

index Arguments
1 &arg1 8 null null
2 &arg2 5 6 null
3 &arg3 2 2 null

Pass-2 Output:

Final Expanded Code:

mov ax,15
mov dx,10
mov ax,dx
add ax,8
add dx,8
division 5
division 2
division 6
division 2
end
*/

..................................................................................................................................................

3. LEXICAL ANALYZER

import java.io.*;

class lexical_analysis {

public static void main(String[] args) throws Exception{

File input_file = new File ("input_file.txt");

if(!input_file.exists())
input_file.createNewFile();

Process p = Runtime.getRuntime().exec("notepad.exe input_file.txt");

p.waitFor();

fileScan(input_file);

display();

}

public static String[] word = { "include", "void","stdio.h","iostream.h","main","conio.h","cout","cin","clrscr","for","int","char","break","if","else","true","false","switch","return","while","getch"};
public static String[] found = new String[20], varArray = new String[50];
public static int kf = -1, sym = -1,v = -1;
public static Character[] symbol_array = new Character[100];

public static void fileScan(File f) throws IOException{

int i=0, c=0;

char[] word = new char[100];

FileInputStream fin = new FileInputStream(f);

while(i != -1)
{
i = fin.read();

if((char)i == '/')
{
int j=0;
i = fin.read();

if((char)i == '*')
{
boolean endC = false;

do {
i = fin.read();

while((char)i != '*')
i = fin.read();

if((char)i == '/')
endC = true;

}while(!endC);

}

else if(i == '/')
{
do {
i = fin.read();
}
while(i!=13);
}
}

if(!Character.isLetterOrDigit((char)i) && (char)i!='.' && !(i==13) && !(i==10) && (char)i !=' ' && i!=9)
{
if(!present(symbol_array,(char)i))
{
sym++;
symbol_array[sym] = (char)i;
}
}

if((char)i != ' ' && i != -1 && !(i==13) && !(i==10) && (char)i!=';' && (char)i!='(' && (char)i!=')')
{
word[c] = (char)i;
c++;
}

else {

c = 0;

wordScan(word,fin);

for(int x=0; x<word.length; x++)
word[x] = '\0';
}

}
}

public static void wordScan(char[] w,FileInputStream fin) throws IOException {

String word =new String(w);

word = word.replaceAll("\\t","");

word = word.trim();

if(word.length()>=1)
{

if(wordSearch(word))
{
int i=0;
String var = "";

if(word.equals("int") || word.equals("char"))
{

boolean comma = false;

do {
var = "";
comma = false;

do {
i = fin.read();
var= var +(char)i;
}while(Character.isLetter((char)i));

if(!present(varArray,var.substring(0,var.length()-1)))
{
v++;
varArray[v] = var.substring(0,var.length()-1);
}

if((char)i == ',')
{
var = "";
comma = true;

do {
i = fin.read();
}while(Character.isWhitespace((char)i));

do {
var = var +(char)i;
i = fin.read();
}while(Character.isLetter((char)i));

if(!present(varArray,var))
{
v++;
varArray[v] = var;
}
}

}while(comma);

}

if(!present(found,word))
{
kf++;
found[kf] = word;
}

}

}
}

public static boolean wordSearch(String s) {

for(int i=0; i<word.length; i++)
{
String st = word[i];

if(s.equals(st.trim()))
return true;
}

return false;
}

public static void display() {

if(kf != -1)
{
System.out.println("Words are: ");

for(int i=0; i<=kf; i++)
{
System.out.print(found[i] + " ");
}
}

if(sym != -1)
{
System.out.println("\n\nSymbols are: ");

for(int i=0; i<=sym-1; i++)
{
System.out.print(symbol_array[i] + " ");
}
}

if(v != -1)
{
System.out.println("\n\nVariables: ");

for(int i=0; i<=v-1; i++)
{
System.out.print(varArray[i] + " " );
}
}
}

public static boolean present(Object[] array, Object s) {

for(int i=0; i<array.length; i++)
{

if(array[i] != null && array[i].equals(s))
return true;
}

return false;
}

}

/*
Output:

Words are:
main while return

Symbols are:
@ $ % ^ * &
*/

------------------------------------------------------------------------------------------------------

4. CODE OPTIMIZATION

Program:

import java.io.*;

import java.util.*;

class Code_Optimization

{

Scanner in = new Scanner(System.in);

String s[]=new String[100]; int n,i;

String s1[]=new String[100];

String con[]=new String[10];

String var[][]=new String[20][20];

int j,k,top,top1;

boolean flag,flag1;

public static void main(String args[])throws IOException

{

Code_Optimization co=new Code_Optimization();

co.calc();

co.show();

}

Code_Optimization()throws IOException

{

i=top=top1=-1;

System.out.println("Enter Initial Source Code:");

System.out.println();

{

i++;

s[i]=in.nextLine();

}

while(s[i].equalsIgnoreCase("Finish")==false);

n=i;

for(i=0;i<10;i++)

con[i]=Integer.toString(i);

}

void calc()

{

int l=0;

boolean v=false;

flag1=true;

for(i=0;i<=n;i++)

{

v=false;

for(j=0;j<10;j++)

{

flag=false;

k=s[i].indexOf(con[j]);

if(k!=-1)

{

if(s[i].charAt(k-1)=='=')

if(top!=-1)

{

v=true;

for(int x=0;x<=top;x++)

if(var[x][0].equalsIgnoreCase(Character.toString(s[i].charAt(k-2))))

{

flag=true;

l=x;

break;

}

if(flag)

var[l][1]=Character.toString(s[i].charAt(k));

else

{

var[++top][0]=Character.toString(s[i].charAt(k-2));

var[top][1]=con[j];

}

else

{

v=true;

var[++top][0]=Character.toString(s[i].charAt(k-2));

var[top][1]=con[j];

}

if(v)

continue;

if(flag1)

s1[++top1]=s[i];

if(s[i].equals("{"))

flag1=false;

if(top!=-1 && i!=n)

change(s[i]);

}

void change(String st)

{

int t1=st.indexOf("int");

int t2=st.indexOf("float");

int t3=st.indexOf("double");

if( t1!=-1 || t2!=-1 || t3!=-1 )

{

int t4=st.indexOf(" ");

st=st.substring(t4+1);

}

for(int k=0;k<=top;k++)

st=st.replace(var[k][0],var[k][1]);

if(t1!=-1)

s1[++top1]="int "+st;

else

if(t2!=-1)

s1[++top1]="float "+st;

else

if(t3!=-1)

s1[++top1]="double "+st;

else

s1[++top1]=st;

}

void show()

{

System.out.println("\nFinal Optimized Code:");

System.out.println();

for(i=0;i<=top1;i++)

System.out.println(s1[i]);

}

Output:

Enter initial Source Code:

#include<iostream.h>

#include<conio.h>

void main()

{

int i=4,j=5;

float s;

s=i+6;

int t=j+3;

j=2

int z=j+5;

getch();

}

finish

Final Optimized Code:

#include<iostream.h>

#include<conio.h>

void main()

{

float s;

s=4+6;

int t=5+3;

int z=2+5;

getch();

}

-----------------------------------------------------------------------------------------------

5. SHIFT REDUCER PARSER

import java.io.*;
import java.util.*;

class Shift_Reduce_Parser
{
int i,n,top1,top2;
boolean flag1,flag2;
String stack1[]=new String[50];
String gr[][]=new String[50][50];
String stack2[][]=new String[50][50];
String input_string;

Scanner in= new Scanner(System.in);

public static void main(String args[])throws IOException
{
Shift_Reduce_Parser srp = new Shift_Reduce_Parser();
srp.compute();
srp.show();
}

Shift_Reduce_Parser()
{
top1=top2=i=-1; //Initialise
flag1=flag2=false;
System.out.println("Enter Grammar:");
System.out.println();
do
{
i++;
stack1[i]=in.nextLine();
int k=stack1[i].indexOf("=");
if(k!=-1)
{
gr[++top1][0]=stack1[i].substring(0,k);
gr[top1][1]="=";
gr[top1][2]=stack1[i].substring(k+1,stack1[i].length());
}
}
while(stack1[i].equalsIgnoreCase("finish")==false);

System.out.println("Enter input_string Production ending with '$':");
input_string=in.nextLine();
n=i;
}

void compute()
{
char d;
int j,len,l,r;
int k=-1;
String t,s1,s2,s3,st;
stack2[++top2][0]="$";
stack2[top2][1]=input_string;
stack2[top2][2]="No";

while(stack2[top2][1].equals("$")==false)
{
len=stack2[top2][0].length();

d=stack2[top2][1].charAt(0);

stack2[++top2][0]=stack2[top2-1][0]+Character.toString(d);
stack2[top2][1]=stack2[top2-1][1].substring(1,stack2[top2-1][1].length());
stack2[top2][2]="Shift";

st=check_string(Character.toString(d));
if(flag2)
{
stack2[++top2][0]=stack2[top2-2][0]+st;
stack2[top2][1]=stack2[top2-1][1];
stack2[top2][2]="Reduced";
}

l=stack2[top2][0].indexOf('(');
r=stack2[top2][0].indexOf(')');
if(l!=-1)
{
st=check_string(stack2[top2][0].substring(l+1));
if(flag2)
{
s1=stack2[top2][0].substring(0,l+1);
stack2[++top2][0]=s1+st;
stack2[top2][1]=stack2[top2-1][1];
stack2[top2][2]="Reduced";
}
}

if(r!=-1)
{
st=check_string(stack2[top2][0].substring(l+1,r));
if(flag2)
{
s1=stack2[top2][0].substring(0,l);
if(r!=len-1)
{
s2=stack2[top2][0].substring(r+1);
stack2[top2][0]=s1+st+s2;
}
else
stack2[top2][0]=s1+st;
}
}

st=check_string(stack2[top2][0].substring(1));
if(flag2)
{
stack2[++top2][0]="$"+st;
stack2[top2][1]=stack2[top2-1][1];
stack2[top2][2]="Reduced";
}
}

len=stack2[top2][0].length();
l=stack2[top2][0].indexOf('(');
r=stack2[top2][0].indexOf(')');
if(l!=-1 && r!=-1)
{
s1=stack2[top2][0].substring(0,l);
s2=stack2[top2][0].substring(l,r);
if(r!=len-1)
{
s3=stack2[top2][0].substring(r+1);
stack2[top2][0]=s1+s2+s3;
}
else
stack2[top2][0]=s1+s2;
}

st=check_string(stack2[top2][0].substring(1));
if(flag2)
{
stack2[++top2][0]="$"+st;
stack2[top2][1]=stack2[top2-1][1];
stack2[top2][2]="Reduced";
}

st="$"+gr[0][0];
if((st.equals(stack2[top2][0])) && (stack2[top2][1].equals("$")))
{
flag1=true;
stack2[++top2][0]=stack2[top2-1][0];
stack2[top2][1]=stack2[top2-1][1];
stack2[top2][2]="Accepted";
}
else
{
flag1=false;
stack2[++top2][0]=stack2[top2-1][0];
stack2[top2][1]=stack2[top2-1][1];
stack2[top2][2]="Rejected";
}
}

String check_string(String st)
{

int ind=0;
for(int l=0;l<=top1;l++)
{
flag2=false;
if(st.equalsIgnoreCase(gr[l][2]))
{
flag2=true;
ind=l;
break;
}
}

if(flag2)
return (gr[ind][0]);
else
return (st);
}

void show()
{
System.out.println("\nEntered Grammar:");
for(i=0;i<=top1;i++)
System.out.println(gr[i][0]+gr[i][1]+gr[i][2]);

System.out.println("\nO/p stack\t\ti/p stack\t\tTask Performed");
for(i=0;i<=top2;i++)
System.out.println(stack2[i][0]+"\t\t\t\t"+stack2[i][1]+"\t\t\t\t"+stack2[i][2]);

if(flag1)
System.out.println("\nEntered Production is Accepted");
else
System.out.println("\nEntered Production is Rejected");
}

}

/*Output
Enter Grammar:
e=e+e
e=e*e
e=e/e
e=d
finish
Enter input_string Production ending with '$':
d+d*d/d+d$

Entered Grammar:
e=e+e
e=e*e
e=e/e
e=d

O/p stack i/p stack Task Performed
$ d+d*d/d+d$ No
$d +d*d/d+d$ Shift
$e +d*d/d+d$ Reduced
$e+ d*d/d+d$ Shift
$e+d *d/d+d$ Shift
$e+e *d/d+d$ Reduced
$e *d/d+d$ Reduced
$e* d/d+d$ Shift
$e*d /d+d$ Shift
$e*e /d+d$ Reduced
$e /d+d$ Reduced
$e/ d+d$ Shift
$e/d +d$ Shift
$e/e +d$ Reduced
$e +d$ Reduced
$e+ d$ Shift
$e+d $ Shift
$e+e $ Reduced
$e $ Reduced
$e $ Accepted

Entered Production is Accepted

*/

----------------------------------------------------------------------------------------------------------------------

6. CODE GENERATION

import java.io.*;
import java.util.*;
class codeGen
{
public static String input=new String();
public static int r=0;
public static int[] R=new int[10];

public static void main(String args[]) throws IOException
{
System.out.println("Enter high level input: ");
Scanner in=new Scanner(System.in);
input=in.nextLine();
for(int x=0;x<=9;x++)
R[x]=-1;
scanBrackets(input);
}

public static void scanBrackets(String s)
{
int t=0,st=0,en=s.length();
String temp = "" ;
for(int i=0;i<s.length(); i++)
{
if(s.charAt(i)==')')
{
en=i;
for(int j=i;j>=0;j--)
{
if(s.charAt(j)=='(')
{
st=j+1;
break;
}
}
break;
}
}

temp=scan(s.substring(st,en),st);
if(st!=0&&en!=s.length())
{
s=s.substring(0,st-1)+temp+s.substring(en+1);
scanBrackets(s);
}
else if(st==0&&en!=s.length())
{
s=temp+s.substring(en+1);
}
else if(st!=0&&en==s.length())
{
s=s.substring(0,st-1)+temp;
}
else s=temp;
int v=0;
for(int j=0;j<s.length();j++)
{
if(!Character.isDigit(s.charAt(j)))
v=1;
}
if(v==0)
System.out.println("Ans: "+s);
}

public static String scan(String s,int st)
{
Character arr[]=new Character[10];
int c=0;
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='*'||s.charAt(i)=='/'||s.charAt(i)=='-'||s.charAt(i)=='+')
{
arr[c]=s.charAt(i);
c++;
}
}
return sortArr(arr,c,s,st);
}

public static String sortArr(Character arr[],int c,String s,int st)
{
for(int i=0;i<c;i++)
for(int j=1;j<c;j++)
{

if(prec(arr[i])<prec(arr[j]))
{
char a=arr[i];
arr[i]=arr[j];
arr[j]=a;
}
}
return calc(arr,c,s,st);
}

public static String calc(Character arr[],int c,String s,int st)
{
for(int i=0;i<c;i++)
{
switch(arr[i])
{
case '/':
{
int p=s.indexOf('/');
int pos1=inR(p-1+st);
if(pos1==-1)
System.out.println("Load AX"+s.charAt(p-1));
else
System.out.println("Load AX,R"+pos1);
int pos2=inR(p+1+st);
if(pos2==-1)
{
System.out.println("Load BX "+s.charAt(p+1));
System.out.println("DIV AX,BX");
}
else
System.out.println("DIV AX,R"+pos2);
int a =Character.getNumericValue(s.charAt(p-1));
int b=Character.getNumericValue(s.charAt(p+1));
int d=a/b;
++r;
if(c==1)
R[r]=st-1;
else R[r]=st;
System.out.println("Load R"+r+",AX");
s=s.substring(0,p-1)+d+s.substring(p+2);
break;

}

case '*':
{
int p=s.indexOf('*');
int pos1=inR(p-1+st);
if(pos1==-1)
System.out.println("Load AX"+s.charAt(p-1));
else
System.out.println("Load AX,R"+pos1);
int pos2=inR(p+1+st);
if(pos2==-1)
{
System.out.println("Load BX,"+s.charAt(p+1));

System.out.println("MUL AX,BX");
}
else System.out.println("MUL AX,R" + pos2);
int a=Character.getNumericValue(s.charAt(p-1));
int b=Character.getNumericValue(s.charAt(p+1));

int d=a*b;
++r;

if(c==1)
R[r]=st-1;
else R[r] =st;

System.out.println("Load R"+r+",AX");
s=s.substring(0,p-1)+ d + s.substring(p+2);

break;
}

case '+':
{
int p=s.indexOf('+');
int pos1 = inR(p-1+st);

if (pos1==-1)
System.out.println("Load AX," + s.charAt(p-1));
else
System.out.println("Load AX,R"+pos1);
int pos2 = inR(p+1+st);

if(pos2==-1)
{
System.out.println("Load BX," + s.charAt(p+1));
System.out.println("ADD AX,BX");

}
else
{
System.out.println("ADD AX,R"+pos2);
R[pos2] = -1;

}
int a=Character.getNumericValue(s.charAt(p-1));
int b =Character.getNumericValue(s.charAt(p+1));

int d=a+b;
++r;
if(c==1)
R[r]=st-1;
else R[r]=st;

System.out.println("Load R" + r + "AX");
s=s.substring(0,p-1) + d + s.substring(p+2);

break;
}

case '-':
{
int p=s.indexOf('-');
int pos1=inR(p-1+st);

if(pos1==-1)
System.out.println("Load AX," + s.charAt(p-1));
else
System.out.println("Load AX,R" + pos1);
int pos2=inR(p+1+st);

if(pos2==-1)
{
System.out.println("Load BX," + s.charAt(p+1));
System.out.println("SUB AX,R" + pos2);
}
else
System.out.println("SUB AX,R" + pos2);
int a=Character.getNumericValue(s.charAt(p-1));
int b=Character.getNumericValue(s.charAt(p+1));

int d=a-b;
++r;
if(c==1)
R[r]=st-1;
else
R[r]=st;

System.out.println("Load R" + r + ",AX");
s=s.substring(0,p-1)+ d + s.substring(p+2);

break;

}

}
}

return s;
}

public static int inR(int p)
{

for(int i =1;i<=9;i++)
{

if(R[i]==p)
return i;

}
return -1;
}

public static int prec(char a)
{
if(a=='+' || a== '-')
return 1;
if(a=='+')
return 2;
if(a=='/')
return 3;
return 0;
}

}

/*
Output:
Enter high level input:
8+(7-3)/9*3
Load AX,7
Load BX,3
SUB AX,R-1
Load R1,AX
Load AX,R1
LoadBX9
DIV AX,BX
Load R2,AX
Load AX,R1
Load BX,3
MUL AX,BX
Load R3,AX
Load AX,R2
ADD AX,R1
Load R4AX
Ans: 8
*/

SPCC (System Programming and Compiler Construction) practical programs

Related articles

3 comments :