K-means Clustering

Problem Definition: Write a program to implement K-means Clustering algorithm

Solution:

import java.io.*;
import java.util.*;
class Kmeans{
 public static void main(String args[])throws IOException{
 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 System.out.println("Enter the number of values to be evaluated(n):");
 int n=Integer.parseInt(br.readLine());
 int a[]=new int[n];
 System.out.println("Enter values in the same line:");
 String s[]=br.readLine().split(" ");
 for(int i=0;i<n;i++)
 a[i]=Integer.parseInt(s[i]);
 System.out.println("Enter the number of clusters(k):");
 ArrayList<ArrayList<Integer>> clusters=new ArrayList<ArrayList<Integer>>();
 int k=Integer.parseInt(br.readLine());
 float mean[][]=new float[k][2];
 for(int i=0;i<k;i++)
 mean[i][0]=a[i]; //it can be randomized as well
 int size,count=0,index=0;
 float temp,temp1=0,min=1000;
 do{
 clusters=new ArrayList<ArrayList<Integer>>();
 for(int i=0;i<k;i++)
 clusters.add(new ArrayList<Integer>());
 for(int i=0;i<n;i++,min=1000){
 for(int j=0;j<k;j++){
 temp=Math.abs(a[i]-mean[j][0]);
 if(temp<min){
 index=j;
 min=temp;
 }
 }
 clusters.get(index).add(a[i]);
 }
 for(int i=0;i<k;i++,temp1=0){
 size=clusters.get(i).size();
 for(int j=0;j<size;j++)
 temp1+=clusters.get(i).get(j);
 mean[i][1]=temp1/size;
 }
 System.out.println(clusters);
 count=0;
 for(int i=0;i<k;i++){
 if(mean[i][0]==mean[i][1])
 count++;
 mean[i][0]=mean[i][1];
 }
 }while(count!=k);
 }
}

 

Output:

Common Sub-Expression Elimination

Problem Definition: Write a program to implement code optimization technique(Elimination of common sub-expression).

Solution:

import java.io.*;
import java.util.*;
class subexp_opt
{
 public static void main(String args[])throws IOException
 {
 String s,temp;
 String arr[][]=new String[10][2]; //assuming 10 unique operations with LHS and RHS stored
 int flag=0,index=0;
 BufferedReader br=new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 File op = new File("output.txt");
 if (!op.exists())
 op.createNewFile();
 BufferedWriter output = new BufferedWriter(new FileWriter(op.getAbsoluteFile()));
 for(;(s=br.readLine())!=null;flag=0)
 {
 temp=s.substring(s.indexOf("=")+1);
 for(int i=0;i<index;i++)
 {
 if(temp.equals(arr[i][1])) 
 {
 flag=1;
 break;
 }
 else if(temp.contains(arr[i][1]))
 s=s.replaceAll(arr[i][1],arr[i][0]);
 } 
 if(flag==0)
 {
 arr[index][0]=s.substring(0,s.indexOf("="));
 arr[index][1]=temp;
 index++;
 output.write(s);
 output.newLine();
 }
 }
 output.close();
 }
}

 

input.txt

temp1=a-b
temp2=a-b+c
temp3=d-e
temp4=c
temp5=d-e

 

output.txt

temp1=a-b
temp2=temp1+c
temp3=d-e
temp4=c

Two Pass Macro Processor

Problem Statement: Write a program to implement 2 pass Macro Processor

Solution:

import java.util.*;
import java.io.*;
class twopassmacro
{
 static String mnt[][]=new String[5][3]; //assuming 5 macros in 1 program
 static String ala[][]=new String[10][2]; //assuming 2 arguments in each macro
 static String mdt[][]=new String[20][1]; //assuming 4 LOC for each macro
 static int mntc=0,mdtc=0,alac=0;
 public static void main(String args[])
 {
 pass1();
 System.out.println("Macro Name Table(MNT)");
 display(mnt,mntc,3);
 System.out.println("Argument List Array(ALA) for Pass1");
 display(ala,alac,2);
 System.out.println("Macro Definition Table(MDT)");
 display(mdt,mdtc,1);
 pass2();
 System.out.println("Argument List Array(ALA) for Pass2");
 display(ala,alac,2);
 System.out.println("Note:All tables are displayed here whereas intermediate pass1 output & expanded pass2 output is stored in files");
 }
 static void pass1()
 {
 int index=0,i;
 String s,prev="",substring;
 try
 {
 BufferedReader inp = new BufferedReader(new FileReader("input.txt"));
 File op = new File("pass1_output.txt");
 if (!op.exists())
 op.createNewFile();
 BufferedWriter output = new BufferedWriter(new FileWriter(op.getAbsoluteFile()));
 while((s=inp.readLine())!=null)
 {
 if(s.equalsIgnoreCase("MACRO"))
 {
 prev=s;
 for(;!(s=inp.readLine()).equalsIgnoreCase("MEND");mdtc++,prev=s)
 {
 if(prev.equalsIgnoreCase("MACRO"))
 {
 StringTokenizer st=new StringTokenizer(s);
 String str[]=new String[st.countTokens()];
 for(i=0;i<str.length;i++)
 str[i]=st.nextToken();
 mnt[mntc][0]=(mntc+1)+""; //mnt formation
 mnt[mntc][1]=str[0];
 mnt[mntc++][2]=(++mdtc)+"";
 st=new StringTokenizer(str[1],","); //tokenizing the arguments
 String string[]=new String[st.countTokens()];
 for(i=0;i<string.length;i++)
 {
 string[i]=st.nextToken();
 ala[alac][0]=alac+""; //ala table formation
 index=string[i].indexOf("=");
 if(index!=-1)
 ala[alac++][1]=string[i].substring(0,index);
 else
 ala[alac++][1]=string[i];
 }
 }
 else //automatically eliminates tagging of arguments in definition
 { //mdt formation
 index=s.indexOf("&");
 substring=s.substring(index);
 for(i=0;i<alac;i++)
 if(ala[i][1].equals(substring))
 s=s.replaceAll(substring,"#"+ala[i][0]);
 }
 mdt[mdtc-1][0]=s;
 }
 mdt[mdtc-1][0]=s;
 }
 else
 {
 output.write(s);
 output.newLine();
 }
 }
 output.close();
 }
 catch(FileNotFoundException ex)
 {
 System.out.println("Unable to find file ");
 }
 catch(IOException e)
 {
 e.printStackTrace(); 
 }
 }
 static void pass2()
 {
 int alap=0,index,mdtp,flag=0,i,j;
 String s,temp;
 try
 {
 BufferedReader inp = new BufferedReader(new FileReader("pass1_output.txt"));
 File op = new File("pass2_output.txt");
 if (!op.exists())
 op.createNewFile();
 BufferedWriter output = new BufferedWriter(new FileWriter(op.getAbsoluteFile()));
 for(;(s=inp.readLine())!=null;flag=0)
 {
 StringTokenizer st=new StringTokenizer(s);
 String str[]=new String[st.countTokens()];
 for(i=0;i<str.length;i++)
 str[i]=st.nextToken();
 for(j=0;j<mntc;j++)
 {
 if(str[0].equals(mnt[j][1]))
 {
 mdtp=Integer.parseInt(mnt[j][2]);
 st=new StringTokenizer(str[1],",");
 String arg[]=new String[st.countTokens()];
 for(i=0;i<arg.length;i++)
 {
 arg[i]=st.nextToken();
 ala[alap++][1]=arg[i];
 }
 for(i=mdtp;!(mdt[i][0].equalsIgnoreCase("MEND"));i++) //expand till MEND
 {
 index=mdt[i][0].indexOf("#");
 temp=mdt[i][0].substring(0,index);
 temp+=ala[Integer.parseInt(""+mdt[i][0].charAt(index+1))][1]; //converting char->string->integer & appending it
 output.write(temp);
 output.newLine();
 }
 flag=1;
 }
 }
 if(flag==0) //when it is not a macro
 {
 output.write(s);
 output.newLine();
 }
 }
 output.close();
 }
 catch(FileNotFoundException ex)
 {
 System.out.println("Unable to find file ");
 }
 catch(IOException e)
 {
 e.printStackTrace();
 } 
 }
 static void display(String a[][],int n,int m)
 {
 int i,j;
 for(i=0;i<n;i++)
 {
 for(j=0;j<m;j++)
 System.out.print(a[i][j]+" ");
 System.out.println();
 }
 }
}

 

Input:

MACRO
INCR1 &FIRST,&SECOND=DATA9
A 1,&FIRST
L 2,&SECOND
MEND
MACRO
INCR2 &ARG1,&ARG2=DATA5
L 3,&ARG1
ST 4,&ARG2
MEND
PRG2 START
 USING *,BASE
 INCR1 DATA1,DATA2
 INCR2 DATA3,DATA4
FOUR DC F'4'
FIVE DC F'5'
BASE EQU 8
TEMP DS 1F
 DROP 8
 END

 

Output:

Intermediate Pass 1 Output:

PRG2 START
 USING *,BASE
 INCR1 DATA1,DATA2
 INCR2 DATA3,DATA4
FOUR DC F'4'
FIVE DC F'5'
BASE EQU 8
TEMP DS 1F
 DROP 8
 END

 

Expanded Pass 2 Output:

PRG2 START
 USING *,BASE
A 1,DATA1
L 2,DATA2
L 3,DATA3
ST 4,DATA4
FOUR DC F'4'
FIVE DC F'5'
BASE EQU 8
TEMP DS 1F
 DROP 8
 END

Two Pass Assembler

Problem Statement: Write a program to implement Two Pass Assembler.

Solution:

import java.util.*;
import java.io.*;
class twopass
{
static int lc=0,index=0;
static String litrl[][]=new String[10][4]; //assumning 10 literals
static int base_table[][]=new int[10][2]; //assuming 10 entries
public static void main(String args[])
{
pass1();
pass2();
}
static void pass1()
{
try
{
int val=0,potflag=0,i;
String inpt,strng=null,mot;
String lit[]=new String[1];
BufferedReader inp = new BufferedReader(new FileReader(“input.txt”));
File syt = new File(“symbol_table.txt”);
if (!syt.exists())
syt.createNewFile();
BufferedWriter sy = new BufferedWriter(new FileWriter(syt.getAbsoluteFile()));
File ltt = new File(“literal_table.txt”);
if (!ltt.exists())
ltt.createNewFile();
BufferedWriter lt = new BufferedWriter(new FileWriter(ltt.getAbsoluteFile()));
File p1op = new File(“pass1output.txt”);
if (!p1op.exists())
p1op.createNewFile();
BufferedWriter op = new BufferedWriter(new FileWriter(p1op.getAbsoluteFile()));
for(;(inpt=inp.readLine())!=null;val=potflag=0)
{
StringTokenizer st=new StringTokenizer(inpt);
String str[]=new String[st.countTokens()];
for(i=0;i<str.length;i++)
str[i]=st.nextToken();
if(str.length==3)
val=1;
if(str.length!=1)
{
StringTokenizer stkn=new StringTokenizer(str[val+1],”,”); //delimiter is comma
lit=new String[stkn.countTokens()];
for(i=0;i<lit.length;i++)
lit[i]=stkn.nextToken();
}
if(str[val].equalsIgnoreCase(“DS”) || str[val].equalsIgnoreCase(“DC”)) //checking whether it is in pot
{
int l=0;
if (val==1)
strng=str[0]+” “+lc+” 4 R”;
if(lit[0].indexOf(“F”)!=0)
{
l=Integer.parseInt(lit[0].substring(0,lit[0].length()-1));
l*=4;
}
else
for(i=0;i<lit.length;i++)
l+=4;
lc+=l;
}
else
{
if(str[val].equalsIgnoreCase(“EQU”))
{
if(str[2].equals(“*”))
strng=str[0]+” “+lc+” 1 R”;
else
strng=str[0]+” “+str[2]+” 1 A”;
}
else
{
if(str[val].equalsIgnoreCase(“START”))
strng=str[0]+” “+str[2]+” 1 R”;
else
{
if(str[val].equalsIgnoreCase(“LTORG”))
ltorg(true);
else
{
if(str[val].equalsIgnoreCase(“END”))
ltorg(false);
else potflag=1;
}
}
}
}
if(potflag==1) //mot search
{
if(str.length!=1)
{
for(i=0;i<lit.length;i++)
if(lit[i].charAt(0)==’=’)
{
litrl[index][0]=lit[i].substring(1,lit[i].length());
litrl[index][1]=”-1″;
litrl[index][2]=”4″;
litrl[index++][3]=”R”;
}
}
BufferedReader mt = new BufferedReader(new FileReader(“mot.txt”));
while((mot=mt.readLine())!=null)
{
StringTokenizer stk=new StringTokenizer(mot);
String s[]=new String[stk.countTokens()];
for(i=0;i<s.length;i++)
s[i]=stk.nextToken();
if(str[val].equalsIgnoreCase(s[0]))
{
if(val==1)
strng=str[0]+” “+lc+” “+s[2]+” R”; //formation of symbol table
lc+=Integer.parseInt(s[2]);
break;
}
}
mt.close();
op.write(inpt); //input to pass 2
op.newLine();
}
if(val==1)
{
sy.write(strng);
sy.newLine();
}
}
for(i=0;i<index;i++)
{
lt.write(litrl[i][0]+” “+litrl[i][1]+” “+litrl[i][2]+” “+litrl[i][3]);
lt.newLine();
}
inp.close();
sy.close();
lt.close();
op.close();
}
catch(FileNotFoundException ex)
{
System.out.println(“Unable to find file “);
}
catch(IOException e)
{
e.printStackTrace();
}
}
static void pass2()
{
int first=0,val=0,i,temp,mask;
String s,s0=””,str[],output,mot;
int value[]=new int[2];
index=0;
try
{
BufferedReader p1o = new BufferedReader(new FileReader(“pass1output.txt”));
File p2 = new File(“pass2output.txt”);
if (!p2.exists())
p2.createNewFile();
BufferedWriter op = new BufferedWriter(new FileWriter(p2.getAbsoluteFile()));
for(;(s=p1o.readLine())!=null;s0=str[val],val=0)
{
StringTokenizer st=new StringTokenizer(s);
str=new String[st.countTokens()];
for(i=0;i<str.length;i++)
str[i]=st.nextToken();
if(str.length==3)
val=1;
st=new StringTokenizer(str[val+1],”,”); //delimiter is comma
String lit[]=new String[st.countTokens()];
for(i=0;i<lit.length;i++)
lit[i]=st.nextToken();
if(str[val].equalsIgnoreCase(“USING”)) //dealing with pot
{
if(lit[0].equals(“*”))
{
if(first==0)
value[0]=0;
else
value[0]=getValue(s0,0); //0=symbol table & 1=literal table value
value[1]=Integer.parseInt(lit[1]);
first=1;
}
else
{
for(i=0;i<lit.length;i++)
{
value[i]=getValue(lit[i],0);
if(value[i]==-1)
value[i]=Integer.parseInt(lit[i]);
}
}
base_table[index][0]=value[1];
base_table[index++][1]=value[0];
}
else //dealing with mot
{
if(str[val].equalsIgnoreCase(“BNE”))
output=”BC “+7;
else
if(str[val].equalsIgnoreCase(“BR”))
output=”BCR “+15+”,”;
else
output=str[val]+” “;
BufferedReader mt = new BufferedReader(new FileReader(“mot.txt”));
while((mot=mt.readLine())!=null)
{
st=new StringTokenizer(mot);
String mts[]=new String[st.countTokens()];
for(i=0;i<mts.length;i++)
mts[i]=st.nextToken();
if(str[val].equals(mts[0]))
{
if(mts[3].equals(“RR”))
{
for(i=0;i<lit.length;i++)
{
if(i!=0)
output+=”,”;
temp=getValue(lit[i],0);
if(temp!=-1)
output+=temp;
else
output+=lit[i];
}
}
else
{
if(lit.length==1)
output+=offset(lit[0]);
else
{
temp=getValue(lit[0],0);
if(temp!=-1)
output+=temp;
else
output+=lit[0];
output+=offset(lit[1]);
}
}
break;
}
}
op.write(output);
op.newLine();
}
}
op.close();
}
catch(FileNotFoundException ex)
{
System.out.println(“Unable to find file “);
}
catch(IOException e)
{
e.printStackTrace();
}
}
static void ltorg(boolean flag)
{
int i,l=0;
if(flag)
{
l=lc+8;
lc=l-(l%8);
}
for(i=0;i<index;i++)
if(litrl[i][1].equals(“-1”))
{
litrl[i][1]=””+lc;
lc+=4;
}
}
static String offset(String s)
{
int value,indx,i,ind=0,offst,new_offst,indx_reg=0;
String string=s;
if(s.charAt(0)==’=’)
value=getValue(s.substring(1,s.length()),1); //0=symbol table & 1=literal table value
else
{
indx=s.indexOf(“(“);
if(indx!=-1)
{
s=s.substring(0,indx);
indx_reg=getValue(string.substring(string.indexOf(“(“)+1,string.indexOf(“)”)),0);
}
value=getValue(s,0);
}
offst=Math.abs(value – base_table[ind][1]);
for(i=1 ; i<index ; i++)
{
new_offst = Math.abs(value – base_table[i][1]);
if(new_offst < offst)
{
offst = new_offst;
ind = i;
}
}
String result = “,”+offst + “(” + indx_reg + “, ” + base_table[ind][0] + “)”;
return result;
}
static int getValue(String s,int flag)
{
try
{
String sym,file_name;
if(flag==0)
file_name=”symbol_table.txt”;
else
file_name=”literal_table.txt”;
BufferedReader br = new BufferedReader(new FileReader(file_name));
while((sym=br.readLine())!=null)
{
StringTokenizer st=new StringTokenizer(sym);
String str[]=new String[st.countTokens()];
for(int i=0;i<str.length;i++)
str[i]=st.nextToken();
if(str[0].equalsIgnoreCase(s))
return Integer.parseInt(str[1]);
}
}
catch(FileNotFoundException ex)
{
System.out.println(“Unable to find file “);
}
catch(IOException e)
{
e.printStackTrace();
}
return -1;
}
}

Input:

PRGAM2   START 0
         USING *,15
         LA    15,SETUP
         SR    TOTAL,TOTAL
AC       EQU   2
INDEX    EQU   3
TOTAL    EQU   4
DATABASE EQU   13
SETUP    EQU   *
         USING SETUP,15
         L     DATABASE,=A(DATA1)
         USING DATAAREA,DATABASE
         SR    INDEX,INDEX
LOOP     L     AC,DATA1(INDEX)
         AR    TOTAL,AC
         A     AC,=F'5'
         ST    AC,SAVE(INDEX)
         A     INDEX,=F'4'
         C     INDEX,=F'8000'
         BNE   LOOP
         LR    1,TOTAL
         BR    14
         LTORG
SAVE     DS    3F
DATAAREA EQU   *
DATA1    DC    F'25,26,27'
         END

 

MOT:

LA 01h 4 RX
SR 02h 2 RR
L  03h 4 RX
AR 04h 2 RR
A  05h 4 RX
C  06h 4 RX
BNE 07h 4 RX
LR 08h 2 RR
ST 09h 4 RX
BR 15h 2 RR

 

OUTPUT:

Symbol Table:

PRGAM2 0 1 R
AC 2 1 A
INDEX 3 1 A
TOTAL 4 1 A
DATABASE 13 1 A
SETUP 6 1 R
LOOP 12 4 R
SAVE 64 4 R
DATAAREA 76 1 R
DATA1 76 4 R

 

Literal Table:

A(DATA1) 48 4 R
F'5' 52 4 R
F'4' 56 4 R
F'8000' 60 4 R

 

Pass 1 output(Pass 2 input):

     USING *,15
     LA    15,SETUP
     SR    TOTAL,TOTAL
     USING SETUP,15
     L     DATABASE,=A(DATA1)
     USING DATAAREA,DATABASE
     SR    INDEX,INDEX
LOOP L     AC,DATA1(INDEX)
     AR    TOTAL,AC
     A     AC,=F'5'
     ST    AC,SAVE(INDEX)
     A     INDEX,=F'4'
     C     INDEX,=F'8000'
     BNE   LOOP
     LR    1,TOTAL
     BR    14

 

Pass 2 output:

LA 15,6(0, 15)
SR 4,4
L 13,42(0, 15)
SR 3,3
L 2,0(3, 13)
AR 4,2
A 2,24(0, 13)
ST 2,12(3, 13)
A 3,20(0, 13)
C 3,16(0, 13)
BC 7,6(0, 15)
LR 1,4
BCR 15,14

First and Follow Set

Problem Statement: Write a program to find First and Follow set for LL(1) grammar.

Solution:

import java.util.*;
import java.io.*;
class fstnflw
{
static char ntermnl[],termnl[];
static int ntlen,tlen;
static String grmr[][],fst[],flw[];
public static void main(String args[]) throws IOException
{
String nt,t;
int i,j,n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter the non-terminals”);
nt=br.readLine();
ntlen=nt.length();
ntermnl=new char[ntlen];
ntermnl=nt.toCharArray();
System.out.println(“Enter the terminals”);
t=br.readLine();
tlen=t.length();
termnl=new char[tlen];
termnl=t.toCharArray();
System.out.println(“Specify the grammar(Enter 9 for epsilon production)”);
grmr=new String[ntlen][];
for(i=0;i<ntlen;i++)
{
System.out.println(“Enter the number of productions for “+ntermnl[i]);
n=Integer.parseInt(br.readLine());
grmr[i]=new String[n];
System.out.println(“Enter the productions”);
for(j=0;j<n;j++)
grmr[i][j]=br.readLine();
}
fst=new String[ntlen];
for(i=0;i<ntlen;i++)
fst[i]=first(i);
System.out.println(“First Set”);
for(i=0;i<ntlen;i++)
System.out.println(removeDuplicates(fst[i]));
flw=new String[ntlen];
for(i=0;i<ntlen;i++)
flw[i]=follow(i);
System.out.println(“Follow Set”);
for(i=0;i<ntlen;i++)
System.out.println(removeDuplicates(flw[i]));
}
static String first(int i)
{
int j,k,l=0,found=0;
String temp=””,str=””;
for(j=0;j<grmr[i].length;j++) //number of productions
{
for(k=0;k<grmr[i][j].length();k++,found=0) //when nonterminal has epsilon production
{
for(l=0;l<ntlen;l++) //finding nonterminal
{
if(grmr[i][j].charAt(k)==ntermnl[l]) //for nonterminal in first set
{
str=first(l);
if(!(str.length()==1 && str.charAt(0)==’9′)) //when epsilon production is the only nonterminal production
temp=temp+str;
found=1;
break;
}
}
if(found==1)
{
if(str.contains(“9″)) //here epsilon will lead to next nonterminal’s first set
continue;
}
else //if first set includes terminal
temp=temp+grmr[i][j].charAt(k);
break;
}
}
return temp;
}
static String follow(int i)
{
char pro[],chr[];
String temp=””;
int j,k,l,m,n,found=0;
if(i==0)
temp=”$”;
for(j=0;j<ntlen;j++)
{
for(k=0;k<grmr[j].length;k++) //entering grammar matrix
{
pro=new char[grmr[j][k].length()];
pro=grmr[j][k].toCharArray();
for(l=0;l<pro.length;l++) //entering each production
{
if(pro[l]==ntermnl[i]) //finding the nonterminal whose follow set is to be found
{
if(l==pro.length-1) //if it is the last terminal/non-terminal then follow of current non-terminal
{
if(j<i)
temp=temp+flw[j];
}
else
{
for(m=0;m<ntlen;m++)
{
if(pro[l+1]==ntermnl[m]) //first of next non-terminal otherwise (else later…)
{
chr=new char[fst[m].length()];
chr=fst[m].toCharArray();
for(n=0;n<chr.length;n++)
{
if(chr[n]==’9′) //if first includes epsilon
{
if(l+1==pro.length-1)
temp=temp+follow(j); //when non-terminal is second last
else
temp=temp+follow(m);
}
else
temp=temp+chr[n]; //include whole first set except epsilon
}
found=1;
}
}
if(found!=1)
temp=temp+pro[l+1]; //follow set will include terminal(else is here)
}
}
}
}
}
return temp;
}
static String removeDuplicates(String str)
{
int i;
char ch;
boolean seen[] = new boolean[256];
StringBuilder sb = new StringBuilder(seen.length);
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if (!seen[ch])
{
seen[ch] = true;
sb.append(ch);
}
}
return sb.toString();
}
}

 

OUTPUT:

Tested for the following Grammars:

1.

S->aABC

A->a|bb

B->a|epsilon

C->b|epsilon

2.

S->aBDh

B->cC

C->bC|epsilon

D->EF

E->g|epsilon

F->f|epsilon

3.

E->TA

A->+TA|epsilon

T->FB

B->*FB|epsilon

F->i|(E)

4.

S->AaAb|BbBa

A->epsilon

B->epsilon

5.

S->A

A->aBZ

Z->dZ|epsilon

B->bBC|f

C->g

6.

S->A

A->aBZ|aCZ

Z->dZ|eZ|epsilon

B->bBC|f

C->g

 

Note:

The above program might not work for complex grammars which require additional coding support (thereby, increasing the length of the code than it already is).

Recursive Descent Parser

Problem Definition: Write a program to implement recursive descent parser for the following grammar:

E->x+T

T->(E)

T->x

Solution:

import java.util.*;
import java.io.*;
class rdp
{
static char inp[]=new char[10]; //static method can call static data
static int index=0;
public static void main(String args[]) throws IOException
{
String input;
int valid;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter input string”);
input=br.readLine();
inp=input.toCharArray();
try
{
valid=E();
if(valid==1)
System.out.println(“Input String is valid”);
else
System.out.println(“Input String is invalid”);
}
catch(ArrayIndexOutOfBoundsException e)
{
System.out.println(“Input String is invalid”);
}
}
static int E()
{
if(inp[index++]!=’x’)
return 0;
if(inp[index++]!=’+’)
return 0;
if(T()==1)
return 1;
else
return 0;
}
static int T()
{
if(inp[index]==’x’ || inp[index]=='(‘)
{
if(inp[index++]==’x’)
return 1;
if(inp[index-1]=='(‘)
{
if(E()==1)
{
if(inp[index++]!=’)’)
return 0;
else
return 1;
}
else
return 0;
}
else
return 0;
}
else
return 0;
}
}

Output:

Income Tax Calculator(J2ME)

Problem Definition: Write a J2ME program to find Income Tax.Take Age,Sex and 1.5 lakhs exemption under investment 80C into consideration.

Note:Super senior citizen age(Above 80 years) is also taken into consideration.

Solution:

import javax.microedition.lcdui.*;
import javax.microedition.midlet.MIDlet;

public final class ItMIDlet extends MIDlet implements CommandListener
{
private static final int NUM_SIZE = 20;

private final Command exitCmd = new Command(“Exit”, Command.EXIT, 2);

private final Command calcCmd = new Command(“Calc”, Command.SCREEN, 1);

private final TextField t1 = new TextField(“Age”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t2 = new TextField(“Monthly Income”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t3 = new TextField(“Investment under 80C”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t4 = new TextField(“Hometown Int/Rent”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t5 = new TextField(“MediClaim Premiums”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t6 = new TextField(“Donations”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField ti = new TextField(“Taxable Income”, “”, NUM_SIZE, TextField.UNEDITABLE);

private final TextField tt = new TextField(“Payable Tax”, “”, NUM_SIZE, TextField.UNEDITABLE);

private final ChoiceGroup cg =
new ChoiceGroup(“Sex”, ChoiceGroup.POPUP,
new String[] { “Male”, “Female” }, null);

private final Alert alert = new Alert(“Error”, “”, null, AlertType.ERROR);

private boolean isInitialized = false;

protected void startApp()
{
if (isInitialized)
return;

Form f = new Form(“Income Tax Calculator”);
f.append(t1);
f.append(cg);
f.append(t2);
f.append(t3);
f.append(t4);
f.append(t5);
f.append(t6);
f.append(ti);
f.append(tt);
f.addCommand(exitCmd);
f.addCommand(calcCmd);
f.setCommandListener(this);
Display.getDisplay(this).setCurrent(f);
alert.addCommand(new Command(“Back”, Command.SCREEN, 1));
isInitialized = true;
}

protected void destroyApp(boolean unconditional)
{
}

protected void pauseApp()
{
}

public void commandAction(Command c, Displayable d)
{
if (c == exitCmd)
{
destroyApp(false);
notifyDestroyed();
return;
}

double res = 0.0;
double pt = 0.0;

try {
double age=getNumber(t1, “First”);
double income = getNumber(t2, “Second”);
double invst = getNumber(t3, “Third”);
double hometown = getNumber(t4, “Fourth”);
double mediclaim = getNumber(t5, “Fifth”);
double donation = getNumber(t6, “Sixth”);

if(invst<=150000) //exemption of 1.5 lakhs under investment 80C
res=(income*12)-invst-hometown-mediclaim-donation;
else
res=(income*12)+invst-150000-hometown-mediclaim-donation;
if(age<=60)
{
switch (cg.getSelectedIndex())
{
case 0:if(res<=200000) //for males
pt=0.0;
if(res>200000 && res<=300000)
pt=(res*10)/100;
if (res>300000 && res<=500000)
pt=(res*20)/100;
if (res>500000)
pt=(res*30)/100;
break;
case 1:if(res<=250000) //for females
pt=0.0;
if(res>250000 && res<=350000)
pt=(res*10)/100;
if (res>350000 && res<=500000)
pt=(res*20)/100;
if (res>500000)
pt=(res*30)/100;
break;
default:
}
}
else
{
if(age<=80) //senior citizen
{
if(res<=300000)
pt=0.0;
if(res>300000 && res<=400000)
pt=(res*10)/100;
if (res>400000 && res<=500000)
pt=(res*20)/100;
if (res>500000)
pt=(res*30)/100;
}
else //super senior citizen
{
if(res<=400000)
pt=0.0;
if (res>400000 && res<=500000)
pt=(res*20)/100;
if (res>500000)
pt=(res*30)/100;
}
}
} catch (NumberFormatException e)
{
return;
}
catch (ArithmeticException e)
{
alert.setString(“Divide by zero.”);
Display.getDisplay(this).setCurrent(alert);
return;
}

String res_str = Double.toString(res); //Taxable Income

if (res_str.length() > ti.getMaxSize()) {
ti.setMaxSize(res_str.length());
}

ti.setString(res_str);

String pt_str; //Payable Tax

if(pt==0.0)
pt_str = “Tax not applicable”;
else
pt_str = Double.toString(pt);

if (pt_str.length() > tt.getMaxSize()) {
tt.setMaxSize(pt_str.length());
}

tt.setString(pt_str);
}

private double getNumber(TextField t, String type)throws NumberFormatException
{
String s = t.getString();

if (s.length() == 0)
{
alert.setString(“No ” + type + ” Argument”);
Display.getDisplay(this).setCurrent(alert);
throw new NumberFormatException();
}

double n;

try
{
n = Double.parseDouble(s);
}
catch (NumberFormatException e)
{
alert.setString(type + ” argument is out of range.”);
Display.getDisplay(this).setCurrent(alert);
throw e;
}

return n;
}
} // end of class ‘ItMIDlet’ definition

Output:

                        

EMI Calculator(J2ME)

import javax.microedition.lcdui.*;
import javax.microedition.midlet.MIDlet;
public final class EmiMIDlet extends MIDlet implements CommandListener {

private static final int NUM_SIZE = 20;

private final Command exitCmd = new Command(“Exit”, Command.EXIT, 2);

private final Command calcCmd = new Command(“Calc”, Command.SCREEN, 1);

private final TextField t1 = new TextField(“Principle Amount”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t2 = new TextField(“Rate of Interest(pcpa)”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t3 = new TextField(“Tenure(in months)”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField tr = new TextField(“EMI”, “”, NUM_SIZE, TextField.UNEDITABLE);

private final Alert alert = new Alert(“Error”, “”, null, AlertType.ERROR); // An alert to be reused for different errors.

private boolean isInitialized = false;

protected void startApp()
{
if (isInitialized)
{
return;
}

Form f = new Form(“EMI Calculator”);
f.append(t1);
f.append(t2);
f.append(t3);
f.append(tr);
f.addCommand(exitCmd);
f.addCommand(calcCmd);
f.setCommandListener(this);
Display.getDisplay(this).setCurrent(f);
alert.addCommand(new Command(“Back”, Command.SCREEN, 1));
isInitialized = true;
}

protected void destroyApp(boolean unconditional)
{
}

protected void pauseApp()
{
}

public double power(double a,double b)
{
double ans=1.0;
int i;
for(i=0;i<b;i++)
ans=ans*a;
return ans;
}

public void commandAction(Command c, Displayable d)
{
if (c == exitCmd)
{
destroyApp(false);
notifyDestroyed();

return;
}

double res = 0.0;
double temp = 0.0;

try
{
double principle = getNumber(t1, “First”);
double roi = getNumber(t2, “Second”);
double tenure = getNumber(t3,”Third”);
roi=roi/1200; //roi is taken annually, converting it to monthly
temp=power((1+roi),tenure); //Math.power doesn’t work
res=(principle*roi*temp)/(temp-1);
}
catch (NumberFormatException e)
{
return;
}
catch (ArithmeticException e)
{
alert.setString(“Divide by zero.”);
Display.getDisplay(this).setCurrent(alert);
return;
}

String res_str = Double.toString(res); //The resulted string may exceed the text max size.

if (res_str.length() > tr.getMaxSize())
{
tr.setMaxSize(res_str.length());
}

tr.setString(res_str);
}

private double getNumber(TextField t, String type) throws NumberFormatException //Extracts the double number from text field.
{
String s = t.getString();

if (s.length() == 0)
{
alert.setString(“No ” + type + ” Argument”);
Display.getDisplay(this).setCurrent(alert);
throw new NumberFormatException();
}

double n;

try
{
n = Double.parseDouble(s);
}
catch (NumberFormatException e)
{
alert.setString(type + ” argument is out of range.”);
Display.getDisplay(this).setCurrent(alert);
throw e;
}

return n;
}
} // end of class ‘EmiMIDlet’ definition

 

Output:

Calculator(J2ME)

Problem Definition: Write a J2ME program to implement a Calculator with add,subtract,multiply and division functions(Use buttons).

import javax.microedition.lcdui.*;
import javax.microedition.midlet.MIDlet;
public final class CalcMIDlet extends MIDlet implements CommandListener,ItemCommandListener
{

private static final int NUM_SIZE = 20;

private final Command exitCmd = new Command(“Exit”, Command.EXIT, 2);

private final Command add = new Command(“Add”, Command.ITEM, 1);
private final Command sub = new Command(“Sub”, Command.ITEM, 1);
private final Command mul = new Command(“Mul”, Command.ITEM, 1);
private final Command div = new Command(“Div”, Command.ITEM, 1);

private final TextField t1 = new TextField(“A”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField t2 = new TextField(“B”, “”, NUM_SIZE, TextField.DECIMAL);

private final TextField tr = new TextField(“Result”, “”, NUM_SIZE, TextField.UNEDITABLE);

private final Alert alert = new Alert(“Error”, “”, null, AlertType.ERROR);

private boolean isInitialized = false;

protected void startApp()
{
if (isInitialized)
{
return;
}

Form f = new Form(“Calculator”);
f.append(t1);
f.append(t2);
StringItem itema = new StringItem(“Add”, “”, Item.BUTTON);
itema.setDefaultCommand(add);
itema.setItemCommandListener(this);
f.append(itema);
StringItem items = new StringItem(“Sub”, “”, Item.BUTTON);
items.setDefaultCommand(sub);
items.setItemCommandListener(this);
f.append(items);
StringItem itemm = new StringItem(“Mul”, “”, Item.BUTTON);
itemm.setDefaultCommand(mul);
itemm.setItemCommandListener(this);
f.append(itemm);
StringItem itemd = new StringItem(“Div”, “”, Item.BUTTON);
itemd.setDefaultCommand(div);
itemd.setItemCommandListener(this);
f.append(itemd);
f.append(tr);
f.addCommand(exitCmd);
f.setCommandListener(this);
Display.getDisplay(this).setCurrent(f);
isInitialized = true;
}

protected void destroyApp(boolean unconditional)
{
}

protected void pauseApp()
{
}

public void commandAction(Command c, Item item)
{

//do not declare variables inside try…it will give you an error
double res = 0.0;
double n1 = getNumber(t1, “First”);
double n2 = getNumber(t2, “Second”);
try
{
if (c==add)
res=n1+n2;
if (c==sub)
res=n1-n2;
if (c==mul)
res=n1*n2;
if (c==div)
res=n1/n2;
}
catch (NumberFormatException e)
{
return;
}
catch (ArithmeticException e)
{
alert.setString(“Divide by zero.”);
Display.getDisplay(this).setCurrent(alert);
return;
}

String res_str = Double.toString(res);

if (res_str.length() > tr.getMaxSize())
{
tr.setMaxSize(res_str.length());
}

tr.setString(res_str);
}

public void commandAction(Command c, Displayable d) //this method must be written otherwise it will give an error “CalcMIDlet is not abstract and does not override abstract method commandAction(javax.microedition.lcdui.Command,javax.microedition.lcdui.Displayable) in javax.microedition.lcdui.CommandListener”
{
if (c == exitCmd)
{
destroyApp(false);
notifyDestroyed();
return;
}
}

private double getNumber(TextField t, String type) throws NumberFormatException
{
String s = t.getString();

if (s.length() == 0)
{
alert.setString(“No ” + type + ” Argument”);
Display.getDisplay(this).setCurrent(alert);
throw new NumberFormatException();
}

double n;

try
{
n = Double.parseDouble(s);
}
catch (NumberFormatException e)
{
alert.setString(type + ” argument is out of range.”);
Display.getDisplay(this).setCurrent(alert);
throw e;
}

return n;
}
} // end of class ‘CalcMIDlet’ definition

 

Output:

Lexical Analyzer

Note:

All files lexanly.java , input.txt , func.txt (function table) , op.txt (operator table) , spsy.txt (special symbol table) , ky.txt (keyword table) must be in the same folder.

Output file will be saved in the same folder on execution of the program.

Identifier Table will be printed on the console.

Solution:

import java.util.*;
import java.io.*;
class lexanly
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println(“Enter file name for input”);
String filename=sc.nextLine();
String line=null;
String function_table=”func.txt”;
String linef=null;
String keyword_table=”ky.txt”;
String linek=null;
char s[]=new char[100]; //assuming line of code has maximum of 100 charcters
int i,j,k,found,id=0,match=0;
int var[]=new int[2];
String idf[]=new String[50]; //assuming 50 identifiers in the program
try
{
FileReader fr=new FileReader(filename);
BufferedReader br=new BufferedReader(fr);
File file = new File(“output.txt”);
if (!file.exists())
file.createNewFile();
FileWriter fw = new FileWriter(file.getAbsoluteFile());
BufferedWriter bw = new BufferedWriter(fw);
while((line=br.readLine())!=null)
{
s=line.toCharArray();
for(i=0,j=0;i<line.length();i++)
{
found=0;
var=spopsy(s[i]);
if(var[0]!=0 || s[i]==’ ‘) //special symbol,operator and space are separators
{
FileReader frf=new FileReader(function_table); //opening all files during every traversal
BufferedReader brf=new BufferedReader(frf);
FileReader frk=new FileReader(keyword_table);
BufferedReader brk=new BufferedReader(frk);
for(k=0;(linef=brf.readLine())!=null && found==0;k++) //search for functions
if(linef.equals(line.substring(j,i)))
{
bw.write(“Func#”+(k+1)+” “);
found=1;
}
for(k=0;(linek=brk.readLine())!=null && found==0;k++) //search for keywords
if(linek.equals(line.substring(j,i)))
{
bw.write(“Keyword#”+(k+1)+” “);
found=1;
}
if(found==0 && id==0 && s[i]!=’ ‘) //space is not an identifier
{
idf[0]=line.substring(j,i); //creating identifier table
id++;
}
for(k=0;k<id && found==0 && s[i]!=’ ‘;k++) //search for identifier history
{
if(idf[k].equals(line.substring(j,i)))
{
match=1;
break;
}
else
match=0;
}
if(match==0 && found==0 && s[i]!=’ ‘ && j!=i) //j!=i inorder to avoid null substring
{
idf[id]=line.substring(j,i); //add identifier only if it does not exist
id++;
}
if(found==0 && s[i]!=’ ‘ && j!=i)
{
bw.write(“Identifier#”+(k+1)+” “); //adding identifiers in identifier table
found=1;
}
if(var[0]==1)
bw.write(“SpecialSymbol#”+var[1]+” “);
if(var[0]==2)
bw.write(“Operator#”+var[1]+” “);
j=i+1; //marks the beginning of a function,keyword or identifier
brf.close();
brk.close();
}
}
bw.newLine(); //writing on the next line of the file
}
br.close();
bw.close();
}
catch(FileNotFoundException ex)
{
System.out.println(“Unable to find file “);
}
catch(IOException e)
{
e.printStackTrace();
}
System.out.println(“Identifier table”);
for(k=0;k<id;k++)
System.out.println(idf[k]);
System.out.println(“Output printed in the file named output.txt”);
}
static int[] spopsy(char c)
{
String sp_symbol_table=”spsy.txt”;
String linessy=null;
String operator_table=”op.txt”;
String lineo=null;
int found=0,i,k;
int var[]=new int[2];
try
{
FileReader frs=new FileReader(sp_symbol_table);
BufferedReader brs=new BufferedReader(frs);
FileReader fro=new FileReader(operator_table);
BufferedReader bro=new BufferedReader(fro);
for(k=0;(linessy=brs.readLine())!=null && found==0;k++)
{
if(linessy.equals(Character.toString(c)))
{
var[0]=1;
var[1]=k+1;
found=1;
}
}
brs.close();
for(k=0;(lineo=bro.readLine())!=null && found==0;k++)
if(lineo.equals(Character.toString(c)))
{
var[0]=2;
var[1]=k+1;
found=1;
}
bro.close();
}
catch(FileNotFoundException ex)
{
System.out.println(“Unable to find file “);
}
catch(IOException ex)
{
System.out.println(“Error reading file “);
}
return var;
}
}

 

op.txt

+
–
/
%
=

spsy.txt

{
}
;
,

func.txt

main()
clrscr()
getch()

ky.txt

void
for
while
do
int
static
float
if
else

input.txt

void main(){
int a,b,sum,diff;
clrscr();
sum=a+b;
diff=a-b;
getch();
}

Console

output.txt

Keyword#1 Func#1 SpecialSymbol#1
Keyword#5 Identifier#1 SpecialSymbol#4 Identifier#2 SpecialSymbol#4 Identifier#3 SpecialSymbol#4 Identifier#4 SpecialSymbol#3
Func#2 SpecialSymbol#3
Identifier#3 Operator#5 Identifier#1 Operator#1 Identifier#2 SpecialSymbol#3
Identifier#4 Operator#5 Identifier#1 Operator#2 Identifier#2 SpecialSymbol#3
Func#3 SpecialSymbol#3
SpecialSymbol#2