Program #2: eulcid.mns
/***
A program to perform Euclid's Algorithm to compute gcd.
***/
int gcd (int u, int v)
{
if (v == 0)
return u ;
else
return gcd(v,u-u/v*v);
/* u-u/v*v == u mod v */
}
void main(void)
{ int x; int y;
x = input(); y = input();
output(gcd(x,y));
}
Example #2 Ouput
CMINUS COMPILATION: euclid.mns
Running Semantic Analyzer...
Type DeclarName DType Loc Block ScopeName Line Numbers
---- ---------- ----- --- ----- --------- ------------
void main func 3 0 global 16
int input var -1 0 global -1 18 18
int u var 1 1 gcd 7 10 12 12
void output var -2 0 global -2 19
int v var 2 1 gcd 7 9 12 12 12
int x var 4 1 main 17 18 19
int y var 5 1 main 17 18 19
int gcd func 0 0 global 7 12 19
Type Checking Finished
Annotated Syntax tree:
INT Func: gcd
INT PARAM: u
INT PARAM: v
Compound Block
If
Op: ==
Id: v
Const: 0
Then
Return
Id: u
else
Return
CALL: gcd
Id: v
Op: -
Id: u
Op: *
Op: /
Id: u
Id: v
Id: v
endif
VOID Func: main
VOID PARAM: (null)
Compound Block
INT VAR: x
INT VAR: y
Assign:
Id: x
Input()
Assign:
Id: y
Input()
Output:
CALL: gcd
Id: x
Id: y
Program #3: quicksort.mns
/* This is the first example of incorrect
typing
*/
void swap( int arr[], int i, int j )
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return;
}
int partition( int arr[], int lo, int hi )
{ /* hi is the highest index to use, lo is the lowest index to use */
int sz;
int mid;
int median;
int temp;
sz = hi - lo;
mid = lo + (hi - lo)/2;
/* median of three partitioning */
if( arr[lo] > arr[mid] )
{
swap( arr, lo, mid );
}
if( arr[lo] > arr[hi] )
{
swap( arr, lo, hi );
}
if( arr[mid] > arr[hi] )
{
swap( arr, mid, hi );
}
swap(arr,mid, hi-1);
return ( arr[hi-1] );
}
void quicksort( int arr[], int lo, int hi )
{
int part;
int lb;
int hb;
if(lo + 2 < hi)
{
int pivot;
int flag;
int i;
int j;
flag = 0;
pivot = partition(arr, lo, hi );
i = lo;
j = hi - 1;
while( flag == 0 )
{
i = i + 1;
while ( arr[i] < pivot )
{
i = i + 1;
}
j = j - 1;
while( arr[j] > pivot )
{
j = j - 1;
}
if ( i < j )
{
swap( arr, i, j );
}
else
{
flag = 1;
}
}
swap( arr, i, hi - 1 );
quicksort(arr, lo, i-1 );
quicksort(arr, i+1, hi );
}
else
{
/* replace insertion sort*/
int mid;
mid = (lo + hi) /2;
if( arr[lo] > arr[mid] )
{
swap( arr, lo, mid );
}
if( arr[lo] > arr[hi] )
{
swap( arr, lo, hi );
}
if( arr[mid] > arr[hi] )
{
swap( arr, mid, hi );
}
}
return;
}
Example #3 Ouput: quicksort.mns
CMINUS COMPILATION: quicksort.mns
Running Semantic Analyzer...
Type DeclarName DType Loc Block ScopeName Line Numbers
---- ---------- ----- --- ----- --------- ------------
int part var 17 1 quicksort 47
int partition func 5 0 global 14 59
void main func 25 0 global 116
int temp var 12 1 partition 19
int temp var 4 1 swap 6 7 9
int array var 26 1 main 118 128 133 138
int median var 11 1 partition 18
int sz var 9 1 partition 16 21
int pivot var 20 2 quicksort 53 59 67 73
int hb var 19 1 quicksort 49
int input var -1 0 global -1
int hi var 16 1 quicksort 45 51 59 61 88 92 98
106 110
int hi var 8 1 partition 14 21 22 32 36 40
void quicksort func 13 0 global 45 90 92 133
int i var 27 1 main 119 121 126 129 129 135 136
139 139
int i var 22 2 quicksort 55 60 66 66 69 69 78
80 88 90 92
int i var 2 1 swap 4
int j var 28 1 main 120 123 128 130 130
int j var 23 2 quicksort 56 61 72 72 75 75 78
80
int j var 3 1 swap 4
void output var -2 0 global -2 138
int lb var 18 1 quicksort 48
int mid var 24 8 quicksort 97 98 102 110
int mid var 10 1 partition 17 22 27 36 40
void swap func 0 0 global 4 27 32 36 40 80 88
102 106 110
int lo var 15 1 quicksort 45 51 59 60 90 98 102
106
int lo var 7 1 partition 14 21 22 22 27 32
int arr var 14 1 quicksort 45 59 67 73 80 88 90
92 100 100 102 104 104 106 108 108 110
int arr var 6 1 partition 14 25 25 27 30 30 32
34 34 36 40 41
int arr var 1 1 swap 4 7 8 8 9
int flag var 21 2 quicksort 54 58 63 84
Type Checking Finished
Annotated Syntax tree:
VOID Func: swap
INT PARAM: arr
Param Array
INT PARAM: i
INT PARAM: j
Compound Block
INT VAR: temp
Assign:
Id: temp
Id: arr
Id: i
Assign:
Id: arr
Id: i
Id: arr
Id: j
Assign:
Id: arr
Id: j
Id: temp
Return
INT Func: partition
INT PARAM: arr
Param Array
INT PARAM: lo
INT PARAM: hi
Compound Block
INT VAR: sz
INT VAR: mid
INT VAR: median
INT VAR: temp
Assign:
Id: sz
Op: -
Id: hi
Id: lo
Assign:
Id: mid
Op: +
Id: lo
Op: /
Op: -
Id: hi
Id: lo
Const: 2
If
Op: >
Id: arr
Id: lo
Id: arr
Id: mid
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: lo
Id: mid
endif
If
Op: >
Id: arr
Id: lo
Id: arr
Id: hi
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: lo
Id: hi
endif
If
Op: >
Id: arr
Id: mid
Id: arr
Id: hi
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: mid
Id: hi
endif
CALL: swap
Id: arr
CALL: (null)
Id: mid
Op: -
Id: hi
Const: 1
Return
Id: arr
Op: -
Id: hi
Const: 1
VOID Func: quicksort
INT PARAM: arr
Param Array
INT PARAM: lo
INT PARAM: hi
Compound Block
INT VAR: part
INT VAR: lb
INT VAR: hb
If
Op: <
Op: +
Id: lo
Const: 2
Id: hi
Then
Compound Block
INT VAR: pivot
INT VAR: flag
INT VAR: i
INT VAR: j
Assign:
Id: flag
Const: 0
Assign:
Id: pivot
CALL: partition
Id: arr
CALL: (null)
Id: lo
Id: hi
Assign:
Id: i
Id: lo
Assign:
Id: j
Op: -
Id: hi
Const: 1
While:
Op: ==
Id: flag
Const: 0
Compound Block
Assign:
Id: i
Op: +
Id: i
Const: 1
While:
Op: <
Id: arr
Id: i
Id: pivot
Compound Block
Assign:
Id: i
Op: +
Id: i
Const: 1
Assign:
Id: j
Op: -
Id: j
Const: 1
While:
Op: >
Id: arr
Id: j
Id: pivot
Compound Block
Assign:
Id: j
Op: -
Id: j
Const: 1
If
Op: <
Id: i
Id: j
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: i
Id: j
else
Compound Block
Assign:
Id: flag
Const: 1
endif
CALL: swap
Id: arr
CALL: (null)
Id: i
Op: -
Id: hi
Const: 1
CALL: quicksort
Id: arr
CALL: (null)
Id: lo
Op: -
Id: i
Const: 1
CALL: quicksort
Id: arr
CALL: (null)
Op: +
Id: i
Const: 1
Id: hi
else
Compound Block
INT VAR: mid
Assign:
Id: mid
Op: /
Op: +
Id: lo
Id: hi
Const: 2
If
Op: >
Id: arr
Id: lo
Id: arr
Id: mid
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: lo
Id: mid
endif
If
Op: >
Id: arr
Id: lo
Id: arr
Id: hi
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: lo
Id: hi
endif
If
Op: >
Id: arr
Id: mid
Id: arr
Id: hi
Then
Compound Block
CALL: swap
Id: arr
CALL: (null)
Id: mid
Id: hi
endif
endif
Return
VOID Func: main
VOID PARAM: (null)
Compound Block
INT VAR: array
Const: 100
INT VAR: i
INT VAR: j
Assign:
Id: i
Const: 0
Assign:
Id: j
Const: 100
While:
Op: <
Id: i
Const: 100
Compound Block
Assign:
Id: array
Id: i
Id: j
Assign:
Id: i
Op: +
Id: i
Const: 1
Assign:
Id: j
Op: -
Id: j
Const: 1
CALL: quicksort
Id: array
CALL: (null)
Const: 0
Const: 99
Assign:
Id: i
Const: 0
While:
Op: <
Id: i
Const: 100
Compound Block
Output:
Id: array
Id: i
Assign:
Id: i
Op: +
Id: i
Const: 1
