PPPPPPPPP
pp
BINARY SEARCH:
#include<iostream>
using namespace std;
class bin_search
{
private:
int i,j,first,last,key,size,temp,middle,*array;
public:
bin_search()
{
i=j=key=middle=first=last=size=temp=middle=0;
}
void input()
{
cout<<"enter the no of elements: \n";
cin>>size;
array = new int[size];
cout<<"enter the "<<size<<" elements: \n";
for(i=0;i<size;i++)
cin>>array[i];
display();
}
void display()
{
cout<<"The elments are: \n";
cout<<"[";
for(i=0;i<size;i++)
{
cout<<array[i];
cout<<",";
}
cout<<"]\n";
}
void sorting()
{
cout<<" sorting elemenmts:";
for(i=0;i<(size-1);i++)
{for(j=0;j<(size-i-1);j++)
{
if(array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
display();
}
void search()
{
cout<<"Element to be searched";
cin>>key;
first=0;
last=size-1;
middle=(first+last)/2;
while(first<=last)
{
if(array[middle]==key)
{
cout<<"Element found at: "<<middle+1<<endl;
break;
}
else if(array[middle]<key)
first=middle+1;
else
last=middle-1;
middle=(first+last)/2;
}
if (first>last)
cout<<"not present";
}
};
int main()
{
bin_search obj;
obj.input();
obj.sorting();
obj.search();
return 0;
}
#Eight Queens Problem in Python
def displayBoard(mat, n):
print ("\n")
for i in range(0,n):
for j in range(0,n):
if mat[i][j] == 1:
print " Q " ,
else :
print " - " ,
print("\n")
def isSafe(mat,n,row,col):
#check LHS of this row
i =0
while i <=col:
if mat[row][i] == 1:
return False
i+=1
#check upper diagonal
i =row
j = col
while i>=0 and j >=0:
if mat[i][j] == 1:
return False
i-=1
j-=1
#check lower diagonal
i= row
j = col
while i < n and j >=0:
if mat[i][j] == 1:
return False
i+=1
j-=1
#otherwise
return True
def solve(mat,n, col):
if col >= n: #base case to stop recursion
return True;
for i in range(0,n): #consider col and try placing the queen in all rows
if isSafe(mat,n, i, col):
mat[i][col] = 1 #place the queen at mat[i][col]
if solve(mat, n, col+1) == True: #recur to place rest of the queens
return True
mat[i][col] = 0 #backtrack
#queen cannot be placed in any row corresponding to this col
return False;
def main(n):
mat=[ [0 for i in range(n)] for j in range(n)]
if solve(mat, n, 0) == False:
print("SOLUTION DOESNT EXIST")
else:
displayBoard(mat,n)
if __name__ == "__main__":
main(8)
"""
rax@ubuntu:~$ cd Desktop
rax@ubuntu:~/Desktop$ python EightQueens.py
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
rax@ubuntu:~/Desktop$
"""
:::KNAPSACK:::
#include<stdio.h>
#include<iostream>
#define MAX 20
using namespace std;
float p[MAX]={0},w[MAX]={0},m;
int no;
struct node
{
float lb,ub;
int tag,objno;
};
void accept()
{
int i;
cout<<"\nEnter no. of objects:";
cin>>no;
for(i = 1;i<=no;i++)
{
cout<<"\nWeight->";
cin>>w[i];
cout<<"\nProfit->";
cin>>p[i];
}
cout<<"\nEnter knapsack capacity:";
cin>>m;
}
float ubound(float cp,float cw,int k,float m)
{
int i;
float b,c;
b = cp;
c = cw;
for(i = k+1;i<=no;i++)
{
if(c+w[i]<=m)
{
c= c + w[i];
b= b - p[i];
}
}
return b;
}
float bound(float cp,float cw,int k)
{
int i;
float b,c;
b = cp;
c = cw;
for(i = k+1;i<=no;i++)
{
c+=w[i];
if(c<m)b-=p[i];
else return (b-(1-(c-m)/w[i])*p[i]);
}
return b;
}
void LCsearch()
{
int i,k,vector[10]={0};
float wt = 0,pr = 0,upper = 999;
struct node lc,rc,e;
e.ub = ubound(0,0,0,m);
e.lb = bound(0,0,0);
e.tag = -1;
e.objno = 0;
upper = e.ub;
i = 1;
while(1)
{
k=e.objno+1;
rc.ub = ubound(pr,wt,k,m);
rc.lb = bound(pr,wt,k);
rc.tag = 0;
rc.objno = k;
if(rc.ub<upper)
upper = rc.ub;
lc.tag = 1;
lc.objno = k;
if(wt+w[k]<=m)
{
lc.ub = ubound(pr-p[k],wt+w[k],k,m);
lc.lb = bound(pr-p[k],wt+w[k],k);
}
else
{
e.ub=pr;
lc.lb =pr;
}
if(lc.lb<=rc.lb && lc.ub<=rc.ub)
e = lc;
else
e = rc;
vector[i] = e.tag;
i++;
if(e.tag==1 )
{
pr = pr - p[(e.objno)];
wt = wt + w[(e.objno)];
}
if(e.objno == no)
break;
}
cout<<"\nSolution vector=";
for(i = 1;i<=no;i++)
cout<<"\t" <<vector[i];
cout<<"\nProfit is: " <<-(e.lb)<<"\n";
}
int main()
{
accept();
LCsearch();
return 0;
}
/*
::::OUTPUT::::
rax@ubuntu:~$ cd Desktop/g
rax@ubuntu:~/Desktop/g$ g++ knap.cpp
rax@ubuntu:~/Desktop/g$ ./a.out
Enter no. of objects:5
Weight->10
Profit->8
Weight->21
Profit->14
Weight->16
Profit->11
Weight->15
Profit->10
Weight->11
Profit->8
Enter knapsack capacity:50
Solution vector= 1 0 1 1 1
Profit is: 29
*/
QUICKSORT
#include<iostream>
#include<omp.h>
using namespace std;
int k=0;
class array
{
public:
int partition(int arr[], int low_index, int high_index)
{
int i, j, temp, key;
key = arr[low_index];
i= low_index + 1;
j= high_index;
while(1)
{
while(i < high_index && key >= arr[i])
i++;
while(key < arr[j])
j--;
if(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
temp= arr[low_index];
arr[low_index] = arr[j];
arr[j]= temp;
return(j);
}
}
}
void quicksort(int arr[], int low_index, int high_index)
{
int j;
if(low_index < high_index)
{
j = partition(arr, low_index, high_index);
cout<<"Pivot element with index "<<j<<" has been found out by thread "<<k<<"\n";
#pragma omp parallel sections
{
#pragma omp section
{
k=k+1;
quicksort(arr, low_index, j - 1);
}
#pragma omp section
{
k=k+1;
quicksort(arr, j + 1, high_index);
}
}
}
}
};
int main()
{
array a;
int arr[100];
int n,i;
cout<<"Enter the value of n\n";
cin>>n;
cout<<"Enter the "<<n<<" number of elements \n";
for(i=0;i<n;i++)
{
cin>>arr[i];
}
a.quicksort(arr, 0, n - 1);
cout<<"Elements of array after sorting \n";
for(i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
cout<<"\n";
}
/*
::::::OUTPUT::::::
rax@ubuntu:~$ cd Desktop
rax@ubuntu:~/Desktop$ g++ quick.cpp
rax@ubuntu:~/Desktop$ ./a.out
Enter the value of n
7
Enter the 7 number of elements
2
31
45
3
87
109
45
Pivot element with index 0 has been found out by thread 0
Pivot element with index 2 has been found out by thread 2
Pivot element with index 4 has been found out by thread 4
Pivot element with index 6 has been found out by thread 6
Elements of array after sorting
2 3 31 45 45 87 109
rax@ubuntu:~/Desktop$
*/
TSP
import java.util.*;
public class travel implements Runnable
{
int size;
int routes[][];//edges
String cities[];//vertices
Thread runners[];
int threadCompleteCount;
String solution;
int totDistance;
travel()
{
try
{
int i, j;
String choice;
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of cities ");
size = scan.nextInt();
scan.skip("\n");
cities = new String[size];
routes = new int[size][size];
System.out.println("Set city names : ");
for(i=0; i< size; i++)
{
System.out.println("City " + (i+1) );
cities[i] = scan.next();
}
System.out.println("Set interconnecting routes ");
for(i =0; i< size; i++)
{
for(j =i+1; j<size; j++ )
{
System.out.println("Is there a route between " + cities[i] + " and " + cities[j] + "(y/n) : " );
choice = scan.next();
if(choice.equalsIgnoreCase("y"))
{
System.out.println("Enter distance : ");
routes[i][j] = routes[j][i]=scan.nextInt();
scan.skip("\n");
}
else
{//no route
routes[i][j] = routes[j][i] = 999;
}
}
}
threadCompleteCount = 0;
solution = "Nearest Neighbour Algorithm couldnt form a tour to visit all cities";
totDistance = 999;
runners = new Thread[size];
for(i =0 ; i< size; i++)
{
runners[i]= new Thread(this, String.valueOf(i));
runners[i].start();
}
}
catch(Exception ex)
{
System.out.println("Err : "+ ex);
}
}//TSP()
void display()
{
int i, j;
for(i = 0; i< size; i++)
{
System.out.println();
System.out.print(cities[i] + " : ");
for(j =0; j< size; j++)
{
System.out.print( cities[j] + "(" + routes[i][j] + ") ");
}
}//for(i ...
System.out.println();
}
public void run()
{
int sPos=Integer.parseInt(Thread.currentThread().getName());
solveTSPUsingNearestNeighbour(sPos);
threadCompleteCount++;
}
boolean solveTSPUsingNearestNeighbour(int startPos)
{
boolean isTourComplete = false;
try
{
String solution = "";
int i, j, min, currentPos, nextPos, totDistance;
int visitedCities[];
int vi;
//initializations and allocations
visitedCities = new int[size];
vi =0 ;
totDistance = 0;
//mark startPos as visited
visitedCities[vi] = startPos;
vi++;
solution = cities[startPos];
currentPos = startPos;
//tour
while(! isTourComplete)
{
nextPos = -1;
min = 999;
for(i =0; i < size; i++)
{
if(routes[currentPos][i] != 999 && currentPos != i)
{
int flag = 0;
//check for being unvisited
for(j =0; j < vi; j++)
{
if(visitedCities[j] == i)
{
flag = 1;
break;
}
}//for(j ...
if(flag == 0)
{//unvisited
if(routes[currentPos][i] < min)
{
min = routes[currentPos][i];
nextPos = i;
}
}
}//if(routes...
}//for(i ...
if(nextPos != -1)
{//move to next city
totDistance += min;
visitedCities[vi] = nextPos;
vi++;
solution = solution + " " + cities[nextPos];
currentPos = nextPos;
}
else
{
break;
}
if(vi == size)
{
//tour back to start city
if(routes[currentPos][startPos] != 999)
{
solution = solution + " " + cities[startPos];
totDistance += routes[currentPos][startPos];
isTourComplete = true;
if(totDistance < this.totDistance)
{
this.totDistance = totDistance;
this.solution = solution + "\nTotal Distance : " + totDistance;
}
}
else
{
isTourComplete = false;
break;
}
}
}//while
}
catch(Exception ex)
{
solution = "Err : " + ex.getMessage();
}
return isTourComplete;
}
void displaySolution()
{
while(threadCompleteCount < size)
{
try
{
Thread.sleep(1000);
}
catch(Exception ex)
{}
}
System.out.println("Solution : " + solution);
}
public static void main(String[] args)
{
travel tsp = new travel();
tsp.display();
tsp.displaySolution();
}
}
/*
::::OUTPUT:::
rax@ubuntu:~$ cd Desktop/g
rax@ubuntu:~/Desktop/g$ javac travel.java
rax@ubuntu:~/Desktop/g$ java travel
Enter the number of cities
4
Set city names :
City 1
A
City 2
B
City 3
C
City 4
D
Set interconnecting routes
Is there a route between A and B(y/n) :
y
Enter distance :
12
Is there a route between A and C(y/n) :
y
Enter distance :
43
Is there a route between A and D(y/n) :
n
Is there a route between B and C(y/n) :
y
Enter distance :
32
Is there a route between B and D(y/n) :
y
Enter distance :
87
Is there a route between C and D(y/n) :
y
Enter distance :
45
A : A(0) B(12) C(43) D(999)
B : A(12) B(0) C(32) D(87)
C : A(43) B(32) C(0) D(45)
D : A(999) B(87) C(45) D(0)
Solution : B A C D B
Total Distance : 187
*/
KMEANS
#include<iostream>
using namespace std;
int main()
{
int i1,i2,i3,t1,t2;
int k0[10];
int k1[10];
int k2[10];
cout<<"\nEnter 10 numbers:\n";
for(i1=0;i1<10;i1++)
{
cin>>k0[i1];
}
//initial means
int m1;
int m2;
cout<<"\n Enter initial mean 1:";
cin>>m1;
cout<<"\n Enter initial mean 2:";
cin>>m2;
int om1,om2; //old means
do
{
//saving old means
om1=m1;
om2=m2;
//creating clusters
i1=i2=i3=0;
for(i1=0;i1<10;i1++)
{
//calculating distance to means
t1=k0[i1]-m1;
if(t1<0){t1=-t1;}
t2=k0[i1]-m2;
if(t2<0){t2=-t2;}
if(t1<t2)
{
//near to first mean
k1[i2]=k0[i1];
i2++;
}
else
{
//near to second mean
k2[i3]=k0[i1];
i3++;
}
}
t2=0;
//calculating new mean
for(t1=0;t1<i2;t1++)
{
t2=t2+k1[t1];
}
m1=t2/i2;
t2=0;
for(t1=0;t1<i3;t1++)
{
t2=t2+k2[t1];
}
m2=t2/i3;
//printing clusters
cout<<"\nCluster 1:";
for(t1=0;t1<i2;t1++)
{
cout<<k1[t1]<<" ";
}
cout<<"\nm1="<<m1;
cout<<"\nCluster 2:";
for(t1=0;t1<i3;t1++)
{
cout<<k2[t1]<<" ";
}
cout<<"\nm2="<<m2;
cout<<"\n ----";
}while(m1!=om1&&m2!=om2);
cout<<"\n Clusters created\n";
return 0;
}
/*
:::::::OUTPUT::::::
rax@ubuntu:~$ cd Desktop
rax@ubuntu:~/Desktop$ g++ km.cpp
rax@ubuntu:~/Desktop$ ./a.out
Enter 10 numbers:
3
45
23
109
4
9
034
0
67
34
Enter initial mean 1:9
Enter initial mean 2:34
Cluster 1:3 4 9 0
m1=4
Cluster 2:45 23 109 34 67 34
m2=52
----
Cluster 1:3 23 4 9 0
m1=7
Cluster 2:45 109 34 67 34
m2=57
----
Cluster 1:3 23 4 9 0
m1=7
Cluster 2:45 109 34 67 34
m2=57
----
Clusters created
*/
KNN
//knn program to classify person as young, middle-aged or old
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
int main()
{
int age[12]={10,29,30,45,2,70,8,9,65,57,80,35};
char cl[12]={'y','m','m','m','y','o','y','y','o','o','o','m'};
cout<<"\n Initial Set:";
cout<<"\nAge\tAge Class\n";
for(int i=0;i<12;i++)
{
cout<<"\n"<<age[i]<<"\t"<<cl[i]<<"\n";
}
int a;
cout<<"\n Enter age :";
cin>>a;
int k;
cout<<"\n Enter value of k:";
cin>>k;
int d[12][2]; int diff;
//calculating (Manhattan) distance to each value in training set
for(int i=0;i<12;i++)
{
d[i][0]=i;
diff=a-age[i];
diff= abs(diff);
d[i][1]=diff;
}
//Sorting
for(int i=0;i<11;i++)
{
for(int j=0;j<11;j++)
{
if(d[j][1]>d[j+1][1])
{ //swapping height
int temp=d[j][1];
d[j][1]=d[j+1][1];
d[j+1][1]=temp;
temp=d[j][0]; //swapping index
d[j][0]=d[j+1][0];
d[j+1][0]=temp;
}
}
}
int noy=0; //no of young
int nom=0; //no of mid-aged
int noo =0; //no of old
cout<<"\nGender\tHeight\tOutput\n";
for(int i=0;i<k;i++)
{
int l=d[i][0];
cout<<age[l]<<"\t"<<cl[l]<<"\t"<<"\n";
if(cl[l]=='y')
{noy++;}
if(cl[l]=='m')
{nom++;}
if(cl[l]=='o')
{noo++;}
}
cout<<"\n Young:"<<noy;
cout<<"\n Middle-aged:"<<nom;
cout<<"\n Old:"<<noo;
if(noy>nom&&noy>noo)
{
cout<<"\n New Tuple is classified as Young \n";
}
if(nom>noy&&nom>noo)
{
cout<<"\n New Tuple is classified as Middle-aged \n";
}
if(noo>nom&&noo>noy)
{
cout<<"\n New Tuple is classified as Old \n";
}
return 0;
}
/*
akshata@ubuntu:~/Desktop$ g++ knn1.cpp
akshata@ubuntu:~/Desktop$ ./a.out
Initial Set:
Age Age Class
10 y
29 m
30 m
45 m
2 y
70 o
8 y
9 y
65 o
57 o
80 o
35 m
Enter age :21
Enter value of k:5
Gender Height Output
29 m
30 m
10 y
9 y
8 y
Young:3
Middle-aged:2
Old:0
New Tuple is classified as Young
vikas@ubuntu:~/Desktop$
*/
"""
APRIORI
$python apriori.py -f DATASET.csv -s 0.15 -c 0.6
"""
import sys
from itertools import chain, combinations
from collections import defaultdict
from optparse import OptionParser
def subsets(arr):
""" Returns non empty subsets of arr"""
return chain(*[combinations(arr, i + 1) for i, a in enumerate(arr)])
def returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet):
"""calculates the support for items in the itemSet and returns a subset
of the itemSet each of whose elements satisfies the minimum support"""
_itemSet = set()
localSet = defaultdict(int)
for item in itemSet:
for transaction in transactionList:
if item.issubset(transaction):
freqSet[item] += 1
localSet[item] += 1
for item, count in localSet.items():
support = float(count)/len(transactionList)
if support >= minSupport:
_itemSet.add(item)
return _itemSet
def joinSet(itemSet, length):
"""Join a set with itself and returns the n-element itemsets"""
return set([i.union(j) for i in itemSet for j in itemSet if len(i.union(j)) == length])
def getItemSetTransactionList(data_iterator):
transactionList = list()
itemSet = set()
for record in data_iterator:
transaction = frozenset(record)
transactionList.append(transaction)
for item in transaction:
itemSet.add(frozenset([item])) # Generate 1-itemSets
return itemSet, transactionList
def runApriori(data_iter, minSupport, minConfidence):
"""
run the apriori algorithm. data_iter is a record iterator
Return both:
- items (tuple, support)
- rules ((pretuple, posttuple), confidence)
"""
itemSet, transactionList = getItemSetTransactionList(data_iter)
freqSet = defaultdict(int)
largeSet = dict()
# Global dictionary which stores (key=n-itemSets,value=support)
# which satisfy minSupport
assocRules = dict()
# Dictionary which stores Association Rules
oneCSet = returnItemsWithMinSupport(itemSet,
transactionList,
minSupport,
freqSet)
currentLSet = oneCSet
k = 2
while(currentLSet != set([])):
largeSet[k-1] = currentLSet
currentLSet = joinSet(currentLSet, k)
currentCSet = returnItemsWithMinSupport(currentLSet,
transactionList,
minSupport,
freqSet)
currentLSet = currentCSet
k = k + 1
def getSupport(item):
"""local function which Returns the support of an item"""
return float(freqSet[item])/len(transactionList)
toRetItems = []
for key, value in largeSet.items():
toRetItems.extend([(tuple(item), getSupport(item))
for item in value])
toRetRules = []
for key, value in largeSet.items()[1:]:
for item in value:
_subsets = map(frozenset, [x for x in subsets(item)])
for element in _subsets:
remain = item.difference(element)
if len(remain) > 0:
confidence = getSupport(item)/getSupport(element)
if confidence >= minConfidence:
toRetRules.append(((tuple(element), tuple(remain)),
confidence))
return toRetItems, toRetRules
def printResults(items, rules):
"""prints the generated itemsets sorted by support and the confidence rules sorted by confidence"""
for item, support in sorted(items, key=lambda (item, support): support):
print "item: %s , %.3f" % (str(item), support)
print "\n------------------------ RULES:"
for rule, confidence in sorted(rules, key=lambda (rule, confidence): confidence):
pre, post = rule
print "Rule: %s ==> %s , %.3f" % (str(pre), str(post), confidence)
def dataFromFile(fname):
"""Function which reads from the file and yields a generator"""
file_iter = open(fname, 'rU')
for line in file_iter:
line = line.strip().rstrip(',') # Remove trailing comma
record = frozenset(line.split(','))
yield record
if __name__ == "__main__":
optparser = OptionParser()
optparser.add_option('-f', '--inputFile',
dest='input',
help='filename containing csv',
default=None)
optparser.add_option('-s', '--minSupport',
dest='minS',
help='minimum support value',
default=0.15,
type='float')
optparser.add_option('-c', '--minConfidence',
dest='minC',
help='minimum confidence value',
default=0.6,
type='float')
(options, args) = optparser.parse_args()
inFile = None
if options.input is None:
inFile = sys.stdin
elif options.input is not None:
inFile = dataFromFile(options.input)
else:
print 'No dataset filename specified, system with exit\n'
sys.exit('System will exit')
minSupport = options.minS
minConfidence = options.minC
items, rules = runApriori(inFile, minSupport, minConfidence)
printResults(items, rules)
"""
T1 Mango Onion Jar Key-chain Eggs Chocolates
T2 Nuts Onion Jar Key-chain Eggs Chocolates
T3 Mango Apple Key-chain Eggs
T4 Mango Toothbrush Corn Key-chain Chocolates
T5 Corn Onion Onion Key-chain Knife Eggs
python apriori.py -f DATASET.csv -s 0.4 -c 0.5
OUTPUT:
student@student-OptiPlex-3020:~$ cd Desktop
student@student-OptiPlex-3020:~/Desktop$ python apriori.py -f DATASET.csv -s 0.4 -c 0.5
item: ('Onion',) , 0.500
item: ('Chocolates',) , 0.500
item: ('Mango',) , 0.500
item: ('Key-chain', 'Onion') , 0.500
item: ('Eggs', 'Onion') , 0.500
item: ('Key-chain', 'Mango') , 0.500
item: ('Key-chain', 'Chocolates') , 0.500
item: ('Key-chain', 'Eggs', 'Onion') , 0.500
item: ('Eggs',) , 0.667
item: ('Key-chain', 'Eggs') , 0.667
item: ('Key-chain',) , 0.833
------------------------ RULES:
Rule: ('Key-chain',) ==> ('Onion',) , 0.600
Rule: ('Key-chain',) ==> ('Mango',) , 0.600
Rule: ('Key-chain',) ==> ('Chocolates',) , 0.600
Rule: ('Key-chain',) ==> ('Eggs', 'Onion') , 0.600
Rule: ('Eggs',) ==> ('Onion',) , 0.750
Rule: ('Eggs',) ==> ('Key-chain', 'Onion') , 0.750
Rule: ('Key-chain', 'Eggs') ==> ('Onion',) , 0.750
Rule: ('Key-chain',) ==> ('Eggs',) , 0.800
Rule: ('Onion',) ==> ('Key-chain',) , 1.000
Rule: ('Onion',) ==> ('Eggs',) , 1.000
Rule: ('Eggs',) ==> ('Key-chain',) , 1.000
Rule: ('Mango',) ==> ('Key-chain',) , 1.000
Rule: ('Chocolates',) ==> ('Key-chain',) , 1.000
Rule: ('Onion',) ==> ('Key-chain', 'Eggs') , 1.000
Rule: ('Key-chain', 'Onion') ==> ('Eggs',) , 1.000
Rule: ('Eggs', 'Onion') ==> ('Key-chain',) , 1.000
student@student-OptiPlex-3020:~/Desktop$
"""
1st LEX
%{
#include<stdio.h>
#include<string.h>
struct ST
{
char lexeme[20];
char type[20];
int count;
}ST[100];
int cnt=0;
//int cnt1=1;
%}
ID [a-zA-Z][a-zA-Z0-9]*
digit [0-9]
%%
{digit}+ {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Integer");ST[cnt++].count=cnt;}
{digit}*\.{digit}+ {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Float");ST[cnt++].count=cnt;}
void|int|struct|char|double|string {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Datatype");ST[cnt++].count=cnt;}
typedef|struct|if|else|do|while|for|switch|main|continue|return {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Keyword");ST[cnt++].count=cnt;}
"+"|"-"|"*"|"/"|"<"|">"|"="|"=="|"<="|">=" {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Operator");ST[cnt++].count=cnt;}
"#include" {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Preproc. Directive");ST[cnt++].count=cnt;}
{ID}+".h" {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Header");ST[cnt++].count=cnt;}
{ID}+ {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Identifier");ST[cnt++].count=cnt;}
"%d" | "%c" {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"String Constant");ST[cnt++].count=cnt;}
. {strcpy(ST[cnt].lexeme,yytext);strcpy(ST[cnt].type,"Terminal");ST[cnt++].count=cnt;}
%%
main(int argc,char *argv[])
{
char filename[30];
int i=0;
yyin=fopen(argv[1],"r");
yylex();
printf("\t\tTOKEN TABLE:\n");
printf("----------------------------------------------------------\n");
printf("SR| LEXEME\t|\tTYPE\n");
printf("----------------------------------------------------------\n");
for(i=0;i<cnt;i++)
{
printf("%2d|%10s|\t%s\n",ST[i].count,ST[i].lexeme,ST[i].type);
}
}
int yywrap()
{
return 1;
}
/*
::::::OUTPUT:::::
rax@ubuntu:~$ cd Desktop
rax@ubuntu:~/Desktop$ lex assign1.l
rax@ubuntu:~/Desktop$ cc lex.yy.c
rax@ubuntu:~/Desktop$ ./a.out h.c
*/
2nd YACC
%{
#include "y.tab.h"
%}
%%
[\t\n]
int|float|char|long|double {return DATATYPE;}
\# {return HASH;}
include {return INCLUDE;}
define {return DEFINE;}
printf\(.*\)\; {return STATEMENT;}
\< {return LT;}
\> {return GT;}
\( {return LB;}
\) {return RB;}
\, {return COMMA;}
\{ {return OCB;}
\} {return CCB;}
\; {return EOL;}
[a-zA-Z_]+[a-zA-A0-9_]*\.h {return HEADER_FILE;}
[a-zA-Z_]+[a-zA-Z0-9_]* {return IDENTIFIER;}
[0-9]+ {return NUMBER;}
[0-9]+\.[0-9]+ {return NUMBER;}
%%
%{
#include<stdio.h>
%}
%token DATATYPE,IDENTIFIER,NUMBER,EOL,LB,RB,COMMA,HASH,LT,GT,INCLUDE,HEADER_FILE,DEFINE,OCB,CCB,STATEMENT, BLOCK
%%
pgm:header other {printf("Valid Expression\n");}
header: HASH INCLUDE LT HEADER_FILE GT header| HASH DEFINE IDENTIFIER NUMBER header|;
other:fun_name part other|;
fun_name:declaration LB parameters RB;
part:block|EOL;
block: OCB stmt CCB;
stmt:STATEMENT stmt|block stmt|;
parameters:declaration t|;
t:COMMA declaration t|;
declaration:DATATYPE IDENTIFIER;
%%
extern FILE *yyin;
extern char *yytext;
main()
{
char fname[25];
printf("\nEnter file name:");
scanf("%s", fname);
yyin=fopen(fname, "r");
while(!feof(yyin))
yyparse();
fclose(yyin);
printf("\nString parsed successfully.\n");
}
yyerror(char *s)
{
printf("\nError occured:%s:%s\nCannot Parse\n",s,yytext);
}
int yywrap()
{
return 1;
}
#include<stdio.h>
#define max 50
#define x 100
int fun();
float fun1(int a);
char fun2(int a, float b);
int main()
{
printf("Insisde main.");
printf("Again inside main.");
{
printf("Inside Block 1");
}
printf("Between Bloack");
{
printf("Inside Block 2");
}
}
int fun(){
printf("Inside fun.");
}
float fun1(int a)
{
printf("Inside fun1.");
}
char fun2(int a, float b)
{
printf("Inside fun2.");
}
student@student-Veriton-Series:~/Desktop$ lex ass2.l
student@student-Veriton-Series:~/Desktop$ yacc -d ass2.y
student@student-Veriton-Series:~/Desktop$ cc lex.yy.c y.tab.c -ll -lm
student@student-Veriton-Series:~/Desktop$ ./a.out
Enter file name:ip1.c
Error occured:syntax error:int
Cannot Parse
String parsed successfully.
student@student-Veriton-Series:~/Desktop$
3rd Intermediate code generation Arithemetic Expression
%{
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void ThreeAddressCode();
void qudraple();
char AddToTable(char ,char, char);
int ind=0;
char temp='A';
struct incod
{
char opd1;
char opd2;
char opr;
};
%}
%union
{
char sym;
}
%token <sym> LETTER NUMBER
%type <sym> expr
%left '-''+'
%right '*''/'
%%
statement: LETTER '=' expr ';' {AddToTable((char)$1,(char)$3,'=');}
| expr ';'
;
expr: expr '+' expr {$$ = AddToTable((char)$1,(char)$3,'+');}
| expr '-' expr {$$ = AddToTable((char)$1,(char)$3,'-');}
| expr '*' expr {$$ = AddToTable((char)$1,(char)$3,'*');}
| expr '/' expr {$$ = AddToTable((char)$1,(char)$3,'/');}
| '(' expr ')' {$$ = (char)$2;}
| NUMBER {$$ = (char)$1;}
| LETTER {$$ = (char)$1;}
;
%%
yyerror(char *s)
{
printf("%s",s);
exit(0);
}
struct incod code[20];
int id=0;
char AddToTable(char opd1,char opd2,char opr)
{
code[ind].opd1=opd1;
code[ind].opd2=opd2;
code[ind].opr=opr;
ind++;
temp++;
return temp;
}
void ThreeAddressCode()
{
int cnt=0;
temp++;
printf("\n\n\t THREE ADDRESS CODE\n\n");
while(cnt<ind)
{
printf("%c : = \t",temp);
if(isalpha(code[cnt].opd1))
printf("%c\t",code[cnt].opd1);
else
{printf("%c\t",temp);}
printf("%c\t",code[cnt].opr);
if(isalpha(code[cnt].opd2))
printf("%c\t",code[cnt].opd2);
else
{printf("%c\t",temp);}
printf("\n");
cnt++;
temp++;
}
}
void quadraple()
{
int cnt=0;
char temp='A';
temp++;
printf("\n\n\t QUADRAPLE CODE\n\n");
while(cnt<ind)
{
//printf("%c : = \t",temp);
printf("%d",id);
printf("\t");
printf("%c",code[cnt].opr);
printf("\t");
if(isalpha(code[cnt].opd1))
printf("%c\t",code[cnt].opd1);
else
{printf("%c\t",temp);}
//printf("%c\t",code[cnt].opr);
if(isalpha(code[cnt].opd2))
printf("%c\t",code[cnt].opd2);
else
{printf("%c\t",temp);}
printf("%c",temp);
printf("\n");
cnt++;
temp++;
id++;
}
}
main()
{
printf("\nEnter the Expression: ");
yyparse();
temp='A';
ThreeAddressCode();
quadraple();
}
yywrap()
{
return 1;
}
%{
#include "y.tab.h"
extern char yyval;
%}
NUMBER [0-9]+
LETTER [a-zA-Z]+
%%
{NUMBER} {yylval.sym=(char)yytext[0]; return NUMBER;}
{LETTER} {yylval.sym=(char)yytext[0];return LETTER;}
\n {return 0;}
. {return yytext[0];}
%%
student@icemcompproj1:~/cl1/a3$ gedit ic1.y
student@icemcompproj1:~/cl1/a3$ lex ic1.l
student@icemcompproj1:~/cl1/a3$ yacc -d ic1.y
student@icemcompproj1:~/cl1/a3$ gcc lex.yy.c y.tab.c -ll
student@icemcompproj1:~/cl1/a3$ ./a.out
Enter the Expression: (a-b)*(c-d);
THREE ADDRESS CODE
B : = a - b
C : = c - d
D : = B * C
QUADRAPLE CODE
0 - a b B
1 - c d C
2 * B C D
4th - Intermediate Code Generator of If Else Statement
ALPHA [A-Za-z]
DIGIT [0-9]
%%
if return IF;
then return THEN;
else return ELSE;
{ALPHA}({ALPHA}|{DIGIT})* return ID;
{DIGIT}+ {yylval=atoi(yytext); return NUM;}
">=" return GE;
"<=" return LE;
[ \t] ;
\n yyterminate();
. return yytext[0];
%%
%{
#include<string.h>
%}
%token ID NUM IF THEN ELSE
%right '='
%left '+' '-'
%left '*' '/'
%left GE LE '<' '>'
%left UMINUS
%%
S : IF '(' E ')'{lab1();} THEN E ';'{lab2();} ELSE E ';'{lab3();}
;
E :V '='{push();} E{codegen_assign();}
| E '+'{push();} E{codegen();}
| E '-'{push();} E{codegen();}
| E '*'{push();} E{codegen();}
| E '/'{push();} E{codegen();}
| E '>'{push();} E{codegen();}
| E '<'{push();} E{codegen();}
| E GE {push();} E{codegen();}
| E LE {push();} E{codegen();}
| '(' E ')'
| '-'{push();} E{codegen_umin();} %prec UMINUS
| V
| NUM{push();}
;
V : ID {push();}
;
%%
#include "lex.yy.c"
#include<ctype.h>
char st[100][10];
int top=0;
char i_[2]="0";
char temp[2]="t";
int label[20];
int lnum=0;
int ltop=0;
main()
{
printf("Enter the expression : ");
yyparse();
}
push()
{
strcpy(st[++top],yytext);
}
codegen()
{
strcpy(temp,"t");
strcat(temp,i_);
printf("%s = %s %s %s\n",temp,st[top-2],st[top-1],st[top]);
top-=2;
strcpy(st[top],temp);
i_[0]++;
}
codegen_umin()
{
strcpy(temp,"t");
strcat(temp,i_);
printf("%s = -%s\n",temp,st[top]);
top--;
strcpy(st[top],temp);
i_[0]++;
}
codegen_assign()
{
printf("%s = %s\n",st[top-2],st[top]);
top-=2;
}
lab1()
{
lnum++;
strcpy(temp,"t");
strcat(temp,i_);
printf("%s = not %s\n",temp,st[top]);
printf("if %s goto L%d\n",temp,lnum);
i_[0]++;
label[++ltop]=lnum;
}
lab2()
{
int x;
lnum++;
x=label[ltop--];
printf("goto L%d\n",lnum);
printf("L%d: \n",x);
label[++ltop]=lnum;
}
lab3()
{
int y;
y=label[ltop--];
printf("L%d: \n",y);
}
int yyerror(char *s)
{
printf("%s\n", s);
}
Intermediate Code Generator for While Statement
ALPHA [A-Za-z]
DIGIT [0-9]
%%
while return WHILE;
{ALPHA}({ALPHA}|{DIGIT})* return ID;
{DIGIT}+ {yylval=atoi(yytext); return NUM;}
">=" return GE;
"<=" return LE;
[ \t] ;
\n yyterminate();
. return yytext[0];
%%
%{
#include<string.h>
%}
%token ID NUM WHILE
%right '='
%left '+' '-'
%left '*' '/'
%left GE LE '<' '>'
%left UMINUS
%%
S : WHILE{lab1();} '(' E ')'{lab2();} E ';'{lab3();}
;
E :V '='{push();} E{codegen_assign();}
| E '+'{push();} E{codegen();}
| E '-'{push();} E{codegen();}
| E '*'{push();} E{codegen();}
| E '/'{push();} E{codegen();}
| E '>'{push();} E{codegen();}
| E '<'{push();} E{codegen();}
| E GE {push();} E{codegen();}
| E LE {push();} E{codegen();}
| '(' E ')'
| '-'{push();} E{codegen_umin();} %prec UMINUS
| V
| NUM{push();}
;
V : ID {push();}
;
%%
#include "lex.yy.c"
#include<ctype.h>
char st[100][10];
int top=0;
char i_[2]="0";
char temp[2]="t";
int lnum=0;
int start=0;
main()
{
printf("Enter the expression : ");
yyparse();
}
push()
{
strcpy(st[++top],yytext);
}
codegen()
{
strcpy(temp,"t");
strcat(temp,i_);
printf("%s = %s %s %s\n",temp,st[top-2],st[top-1],st[top]);
top-=2;
strcpy(st[top],temp);
i_[0]++;
}
codegen_umin()
{
strcpy(temp,"t");
strcat(temp,i_);
printf("%s = -%s\n",temp,st[top]);
top--;
strcpy(st[top],temp);
i_[0]++;
}
codegen_assign()
{
printf("%s = %s\n",st[top-2],st[top]);
top-=2;
}
lab1()
{
printf("L%d: \n",lnum++);
}
lab2()
{
strcpy(temp,"t");
strcat(temp,i_);
printf("%s = not %s\n",temp,st[top]);
printf("if %s goto L%d\n",temp,lnum);
i_[0]++;
}
lab3()
{
printf("goto L%d \n",start);
printf("L%d: \n",lnum);
}
int yyerror(char *s)
{
printf("%s\n", s);
}
5th
Code Optimization using DAG
include<stdio.h>
#include<string.h>
#include<ctype.h>
void input();
void output();
void change(int p,int q,char *res);
void constant();
void expression();
struct expr
{
char op[2],op1[5],op2[5],res[5];
int flag;
}arr[10];
int n;
int main()
{
int ch=0;
input();
constant();
expression();
output();
}
void input()
{
int i;
printf("\n\nEnter the maximum number of expressions : ");
scanf("%d",&n);
printf("\nEnter the input : \n");
for(i=0;i<n;i++)
{
scanf("%s:",arr[i].op);
scanf("%s",arr[i].op1);
scanf("%s",arr[i].op2);
scanf("%s",arr[i].res);
arr[i].flag=0;
}
}
void constant()
{
int i;
int op1,op2,res;
char op,res1[5];
for(i=0;i<n;i++)
{
if(isdigit(arr[i].op1[0]) && isdigit(arr[i].op2[0]))
//if both digits, store them in variables
{
op1=atoi(arr[i].op1);
op2=atoi(arr[i].op2);
op=arr[i].op[0];
switch(op)
{
case '+':
res=op1+op2;
break;
case '-':
res=op1-op2;
break;
case '*':
res=op1*op2;
break;
case '/':
res=op1/op2;
break;
}
sprintf(res1,"%d",res);
arr[i].flag=1; //eliminate expr and replace any operand below that uses result of this expr
change(i,i,res1);
}
}
}
void expression()
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(strcmp(arr[i].op,arr[j].op)==0) //if operators are same
{
if(strcmp(arr[i].op,"+")==0||strcmp(arr[i].op,"*")==0) //order doesn't matter if operators are + or *
{
if(strcmp(arr[i].op1,arr[j].op1)==&&strcmp(arr[i].op2,arr[j].op2)==0 || strcmp(arr[i].op1,arr[j].op2)==0&&strcmp(arr[i].op2,arr[j].op1)==0)
{
arr[j].flag=1; //does't print
change(i,j,NULL); //change any operand below that uses result of this expression
}
}
else
{
if(strcmp(arr[i].op1,arr[j].op1)==&&strcmp(arr[i].op2,arr[j].op2)==0)
{
arr[j].flag=1;
change(i,j,NULL);
}
}
}
}
}
}
void output()
{
int i=0;
printf("\nOptimized code is : ");
for(i=0;i<n;i++)
{
if(!arr[i].flag)
{
printf("\n%s %s %s %s", arr[i].op, arr[i].op1, arr[i].op2, arr[i].res);
}
}
}
void change(int p,int q,char *res)
{
int i;
for(i=q+1;i<n;i++)
{
if(strcmp(arr[q].res,arr[i].op1)==0)
if(res == NULL) //for csub
strcpy(arr[i].op1,arr[p].res);
else //for ceval
strcpy(arr[i].op1,res);
else if(strcmp(arr[q].res,arr[i].op2)==0)
if(res == NULL) //for csub
strcpy(arr[i].op2,arr[p].res);
else //for ceval
strcpy(arr[i].op2,res);
}
}
/*
:::::OUTPUT::::
rax@ubuntu:~$ cd Desktop
rax@ubuntu:~/Desktop$ cd B4
rax@ubuntu:~/Desktop/B4$ gcc opt.c
rax@ubuntu:~/Desktop/B4$ ./a.out
Enter the maximum number of expressions : 4
Enter the input :
* 5 2 a1
+ a1 6 t1
* b a t2
+ t1 t2 z1
Optimized code is :
* b a t2
+ 16 t2 z1
*/
6th
DAG LABELLED TREE
#include<stdlib.h>
#include<stdio.h>
struct bin_tree
{
char data;
int label;
struct bin_tree *right, *left;
};typedef struct bin_tree node;
int R[]={1,0};
int top=1;
char *op;
void insertnode(node **tree,char val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
temp->label=-1;
*tree = temp;
}
}
void insert(node **tree,char val)
{
char l,r;
int numofchildren;
insertnode(tree, val);
printf("\nEnter number of children of %c:",val);
scanf("%d",&numofchildren);
if(numofchildren==2)
{
printf("\nEnter Left Child of %c:",val);
scanf("%s",&l);
insertnode(&(*tree)->left,l);
printf("\nEnter Right Child of %c:",val);
scanf("%s",&r);
insertnode(&(*tree)->right,r);
insert(&(*tree)->left,l);
insert(&(*tree)->right,r);
}
}
void findleafnodelabel(node *tree,int val)
{
if(tree->left != NULL && tree->right !=NULL)
{
findleafnodelabel(tree->left,1);
findleafnodelabel(tree->right,0);
}
else
{tree->label=val;}
}
void findinteriornodelabel(node *tree)
{
if(tree->left->label==-1)
{findinteriornodelabel(tree->left);}
else if(tree->right->label==-1)
{findinteriornodelabel(tree->right);}
else
{
if(tree->left != NULL && tree->right !=NULL)
{
if(tree->left->label == tree->right->label)
{
tree->label=(tree->left->label)+1;
}
else
{
if(tree->left->label > tree->right->label)
{
tree->label=tree->left->label;
}
else
{
tree->label=tree->right->label;
}
}
}
}
}
void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
printf("%c with Label %d\n",tree->data,tree->label);
print_inorder(tree->right);
}
}
void swap()
{
int temp;
temp=R[0];
R[0]=R[1];
R[1]=temp;
}
int pop()
{
int temp=R[top];
top--;
return temp;
}
void push(int temp)
{
top++;
R[top]=temp;
}
char* nameofoperation(char temp)
{
switch(temp)
{
case '+': return "ADD"; break;
case '-': return "SUB"; break;
case '*': return "MUL"; break;
case '/': return "DIV"; break;
}
}
void gencode(node * tree)
{
if(tree->left != NULL && tree->right != NULL)
{
if(tree->left->label== 1 && tree->right->label ==0)
{
printf("MOV %c,R[%d]\n",tree->left->data,R[top]);
op=nameofoperation(tree->data);
printf("%s %c,R[%d]\n",op,tree->right->data,R[top]);
}
else if(tree->left->label < tree->right->label)
{
int temp;
swap();
gencode(tree->right);
temp=pop();
gencode(tree->left);
push(temp);
swap();
op=nameofoperation(tree->data);
printf("%s R[%d],R[%d]\n",op,R[top-1],R[top]);
}
else if(tree->left->label >= tree->right->label)
{
int temp;
gencode(tree->left);
temp=pop();
gencode(tree->right);
push(temp);
op=nameofoperation(tree->data);
printf("%s R[%d],R[%d]\n",op,R[top-1],R[top]);
}
}
else if(tree->left == NULL && tree->right == NULL && tree->label == 1)
{
printf("MOV %c,R[%d]\n",tree->data,R[top]);
}
}
void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}
void main()
{
node *root;
node *tmp;
char val;
root = NULL;
/* Inserting nodes into tree */
printf("\nEnter root of tree:");
scanf("%c",&val);
insert(&root,val);
/* Finding Labels of Leaf nodes */
findleafnodelabel(root,1);
/* Finding Labels of Interior nodes */
while(root->label== -1)
findinteriornodelabel(root);
/* Printing nodes of tree */
printf("In Order Display\n");
print_inorder(root);
/* Printing nodes of tree */
printf("Assembly Code:\n");
gencode(root);
/* Deleting all nodes of tree */
deltree(root);
}
Output:
rax@ubuntu:~$ cd Desktop
rax@ubuntu:~/Desktop$ gcc gencode.c
rax@ubuntu:~/Desktop$ ./a.out
Enter root of tree:+
Enter number of children of +:2
Enter Left Child of +:-
Enter Right Child of +:-
Enter number of children of -:2
Enter Left Child of -:a
Enter Right Child of -:/
Enter number of children of a:0
Enter number of children of /:2
Enter Left Child of /:b
Enter Right Child of /:c
Enter number of children of b:0
Enter number of children of c:0
Enter number of children of -:2
Enter Left Child of -:c
Enter Right Child of -:/
Enter number of children of c:0
Enter number of children of /:2
Enter Left Child of /:d
Enter Right Child of /:e
Enter number of children of d:0
Enter number of children of e:0
In Order Display
a with Label 1
- with Label 2
b with Label 1
/ with Label 1
c with Label 0
+ with Label 3
c with Label 1
- with Label 2
d with Label 1
/ with Label 1
e with Label 0
Assembly Code:
MOV a,R[0]
MOV b,R[1]
DIV c,R[1]
SUB R[1],R[0]
MOV c,R[1]
MOV d,R[0]
DIV e,R[0]
SUB R[0],R[1]
ADD R[1],R[0]
7th
Abstract Syntax Tree
%{
#include "y.tab.h"
%}
%%
[0-9]+ {yylval = (int)yytext; return NUMBER;}
/* cast pointer to int for compiler warning */
[ \t\n] ;
"+" return(PLUS);
"-" return(MINUS);
"*" return(TIMES);
"/" return(DIVIDE);
"^" return(POWER);
"(" return(LEFT_PARENTHESIS);
")" return(RIGHT_PARENTHESIS);
";" return(END);
%%
int yywrap (void) {return 1;}
%{
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node
{
struct node *left;
struct node *right;
char *token;
} node;
node *mknode(node *left, node *right, char *token);
void printtree(node *tree);
#define YYSTYPE struct node *
%}
%start lines
%token NUMBER
%token PLUS MINUS TIMES DIVIDE POWER
%token LEFT_PARENTHESIS RIGHT_PARENTHESIS
%token END
%left PLUS MINUS
%left TIMES DIVIDE
%right POWER
%%
lines: /* empty */
| lines line /* do nothing */
line: exp END { printtree($1); printf("\n");}
;
exp : term {$$ = $1;}
| exp PLUS term {$$ = mknode($1, $3, "+");}
| exp MINUS term {$$ = mknode($1, $3, "-");}
;
term : factor {$$ = $1;}
| term TIMES factor {$$ = mknode($1, $3, "*");}
;
factor : NUMBER {$$ = mknode(0,0,(char *)yylval);}
| LEFT_PARENTHESIS exp RIGHT_PARENTHESIS {$$ = $2;}
;
%%
int main (void) {return yyparse ( );}
node *mknode(node *left, node *right, char *token)
{
/* malloc the node */
node *newnode = (node *)malloc(sizeof(node));
char *newstr = (char *)malloc(strlen(token)+1);
strcpy(newstr, token);
newnode->left = left;
newnode->right = right;
newnode->token = newstr;
return(newnode);
}
void printtree(node *tree)
{
int i;
if (tree->left || tree->right)
printf("(");
printf(" %s ", tree->token);
if (tree->left)
printtree(tree->left);
if (tree->right)
printtree(tree->right);
if (tree->left || tree->right)
printf(")");
}
int yyerror (char *s) {fprintf (stderr, "%s\n", s);}
student@icemcompproj1:~/cl1/b3$ bison -d ab.y
student@icemcompproj1:~/cl1/b3$ mv ab.tab.h ab.h
student@icemcompproj1:~/cl1/b3$ mv ab.tab.c ab.y.c
student@icemcompproj1:~/cl1/b3$ flex -o ab.lex.c ab.l
student@icemcompproj1:~/cl1/b3$ cc -g -o ab ab.lex.c ab.y.c -lm
student@icemcompproj1:~/cl1/b3$ ./ab < ab.txt
( + 6 ( * 8 4 ))
No comments:
Post a Comment