Compiler/Sample programs

Compute the GCD of two numbers

Input to lex

Output from lex, input to parse

Output from parse, input to gen

Output from gen, input to VM

<lang c> /* Compute the gcd of 1071, 1029: 21 */

a = 1071; b = 1029;

while (b != 0) {

   new_a = b;
   b     = a % b;
   a     = new_a;

} print(a); </lang>

3 1 Identifier a 3 3 Op_assign 3 5 Integer 1071 3 9 Semicolon 4 1 Identifier b 4 3 Op_assign 4 5 Integer 1029 4 9 Semicolon 6 1 Keyword_while 6 7 LeftParen 6 8 Identifier b 6 10 Op_notequal 6 13 Integer 0 6 14 RightParen 6 16 LeftBrace 7 5 Identifier new_a 7 11 Op_assign 7 13 Identifier b 7 14 Semicolon 8 5 Identifier b 8 11 Op_assign 8 13 Identifier a 8 15 Op_mod 8 17 Identifier b 8 18 Semicolon 9 5 Identifier a 9 11 Op_assign 9 13 Identifier new_a 9 18 Semicolon 10 1 RightBrace 11 1 Keyword_print 11 6 LeftParen 11 7 Identifier a 11 8 RightParen 11 9 Semicolon 12 1 End_of_input

Sequence Sequence Sequence Sequence ; Assign Identifier a Integer 1071 Assign Identifier b Integer 1029 While NotEqual Identifier b Integer 0 Sequence Sequence Sequence ; Assign Identifier new_a Identifier b Assign Identifier b Mod Identifier a Identifier b Assign Identifier a Identifier new_a Sequence ; Prti Identifier a ;

Datasize: 3 Strings: 0 0 push 1071 5 store [0] 10 push 1029 15 store [1] 20 fetch [1] 25 push 0 30 ne 31 jz (45) 77 36 fetch [1] 41 store [2] 46 fetch [0] 51 fetch [1] 56 mod 57 store [1] 62 fetch [2] 67 store [0] 72 jmp (-53) 20 77 fetch [0] 82 prti 83 halt

Factorial

Input to lex

Output from lex, input to parse

Output from parse

Output from gen, input to VM

<lang c> /* 12 factorial is 479001600 */

n = 12; result = 1; i = 1; while (i <= n) {

   result = result * i;
   i = i + 1;

} print(result); </lang>

3 1 Identifier n 3 3 Op_assign 3 5 Integer 12 3 7 Semicolon 4 1 Identifier result 4 8 Op_assign 4 10 Integer 1 4 11 Semicolon 5 1 Identifier i 5 3 Op_assign 5 5 Integer 1 5 6 Semicolon 6 1 Keyword_while 6 7 LeftParen 6 8 Identifier i 6 10 Op_lessequal 6 13 Identifier n 6 14 RightParen 6 16 LeftBrace 7 5 Identifier result 7 12 Op_assign 7 14 Identifier result 7 21 Op_multiply 7 23 Identifier i 7 24 Semicolon 8 5 Identifier i 8 7 Op_assign 8 9 Identifier i 8 11 Op_add 8 13 Integer 1 8 14 Semicolon 9 1 RightBrace 10 1 Keyword_print 10 6 LeftParen 10 7 Identifier result 10 13 RightParen 10 14 Semicolon 11 1 End_of_input

Sequence Sequence Sequence Sequence Sequence ; Assign Identifier n Integer 12 Assign Identifier result Integer 1 Assign Identifier i Integer 1 While LessEqual Identifier i Identifier n Sequence Sequence ; Assign Identifier result Multiply Identifier result Identifier i Assign Identifier i Add Identifier i Integer 1 Sequence ; Prti Identifier result ;

Datasize: 3 Strings: 0 0 push 12 5 store [0] 10 push 1 15 store [1] 20 push 1 25 store [2] 30 fetch [2] 35 fetch [0] 40 le 41 jz (41) 83 46 fetch [1] 51 fetch [2] 56 mul 57 store [1] 62 fetch [2] 67 push 1 72 add 73 store [2] 78 jmp (-49) 30 83 fetch [1] 88 prti 89 halt

Fibonacci

Input to lex

Output from lex, input to parse

Output from parse

Output from gen, input to VM

<lang c> /* fibonacci of 44 is 701408733 */

n = 44; i = 1; a = 0; b = 1; while (i < n) {

   w = a + b;
   a = b;
   b = w;
   i = i + 1;

} print(w, "\n"); </lang>

3 1 Identifier n 3 3 Op_assign 3 5 Integer 44 3 7 Semicolon 4 1 Identifier i 4 3 Op_assign 4 5 Integer 1 4 6 Semicolon 5 1 Identifier a 5 3 Op_assign 5 5 Integer 0 5 6 Semicolon 6 1 Identifier b 6 3 Op_assign 6 5 Integer 1 6 6 Semicolon 7 1 Keyword_while 7 7 LeftParen 7 8 Identifier i 7 10 Op_less 7 12 Identifier n 7 13 RightParen 7 15 LeftBrace 8 5 Identifier w 8 7 Op_assign 8 9 Identifier a 8 11 Op_add 8 13 Identifier b 8 14 Semicolon 9 5 Identifier a 9 7 Op_assign 9 9 Identifier b 9 10 Semicolon 10 5 Identifier b 10 7 Op_assign 10 9 Identifier w 10 10 Semicolon 11 5 Identifier i 11 7 Op_assign 11 9 Identifier i 11 11 Op_add 11 13 Integer 1 11 14 Semicolon 12 1 RightBrace 13 1 Keyword_print 13 6 LeftParen 13 7 Identifier w 13 8 Comma 13 10 String "\n" 13 14 RightParen 13 15 Semicolon 15 1 End_of_input

Sequence Sequence Sequence Sequence Sequence Sequence ; Assign Identifier n Integer 44 Assign Identifier i Integer 1 Assign Identifier a Integer 0 Assign Identifier b Integer 1 While Less Identifier i Identifier n Sequence Sequence Sequence Sequence ; Assign Identifier w Add Identifier a Identifier b Assign Identifier a Identifier b Assign Identifier b Identifier w Assign Identifier i Add Identifier i Integer 1 Sequence Sequence ; Prti Identifier w ; Prts String "\n" ;

Datasize: 5 Strings: 1 "\n" 0 push 44 5 store [0] 10 push 1 15 store [1] 20 push 0 25 store [2] 30 push 1 35 store [3] 40 fetch [1] 45 fetch [0] 50 lt 51 jz (61) 113 56 fetch [2] 61 fetch [3] 66 add 67 store [4] 72 fetch [3] 77 store [2] 82 fetch [4] 87 store [3] 92 fetch [1] 97 push 1 102 add 103 store [1] 108 jmp (-69) 40 113 fetch [4] 118 prti 119 push 0 124 prts 125 halt

FizzBuzz

Input to lex

Output from lex, input to parse

Output from parse

Output from gen, input to VM

<lang c> /* FizzBuzz */ i = 1; while (i <= 100) {

   if (!(i % 15))
       print("FizzBuzz");
   else if (!(i % 3))
       print("Fizz");
   else if (!(i % 5))
       print("Buzz");
   else
       print(i);

   print("\n");
   i = i + 1;

} </lang>

2 1 Identifier i 2 3 Op_assign 2 5 Integer 1 2 6 Semicolon 3 1 Keyword_while 3 7 LeftParen 3 8 Identifier i 3 10 Op_lessequal 3 13 Integer 100 3 16 RightParen 3 18 LeftBrace 4 5 Keyword_if 4 8 LeftParen 4 9 Op_not 4 10 LeftParen 4 11 Identifier i 4 13 Op_mod 4 15 Integer 15 4 17 RightParen 4 18 RightParen 5 9 Keyword_print 5 14 LeftParen 5 15 String "FizzBuzz" 5 25 RightParen 5 26 Semicolon 6 5 Keyword_else 6 10 Keyword_if 6 13 LeftParen 6 14 Op_not 6 15 LeftParen 6 16 Identifier i 6 18 Op_mod 6 20 Integer 3 6 21 RightParen 6 22 RightParen 7 9 Keyword_print 7 14 LeftParen 7 15 String "Fizz" 7 21 RightParen 7 22 Semicolon 8 5 Keyword_else 8 10 Keyword_if 8 13 LeftParen 8 14 Op_not 8 15 LeftParen 8 16 Identifier i 8 18 Op_mod 8 20 Integer 5 8 21 RightParen 8 22 RightParen 9 9 Keyword_print 9 14 LeftParen 9 15 String "Buzz" 9 21 RightParen 9 22 Semicolon 10 5 Keyword_else 11 9 Keyword_print 11 14 LeftParen 11 15 Identifier i 11 16 RightParen 11 17 Semicolon 13 5 Keyword_print 13 10 LeftParen 13 11 String "\n" 13 15 RightParen 13 16 Semicolon 14 5 Identifier i 14 7 Op_assign 14 9 Identifier i 14 11 Op_add 14 13 Integer 1 14 14 Semicolon 15 1 RightBrace 16 1 End_of_input

Sequence Sequence ; Assign Identifier i Integer 1 While LessEqual Identifier i Integer 100 Sequence Sequence Sequence ; If Not Mod Identifier i Integer 15 ; If Sequence ; Prts String "FizzBuzz" ; If Not Mod Identifier i Integer 3 ; If Sequence ; Prts String "Fizz" ; If Not Mod Identifier i Integer 5 ; If Sequence ; Prts String "Buzz" ; Sequence ; Prti Identifier i ; Sequence ; Prts String "\n" ; Assign Identifier i Add Identifier i Integer 1

Datasize: 1 Strings: 4 "FizzBuzz" "Fizz" "Buzz" "\n" 0 push 1 5 store [0] 10 fetch [0] 15 push 100 20 le 21 jz (121) 143 26 fetch [0] 31 push 15 36 mod 37 not 38 jz (15) 54 43 push 0 48 prts 49 jmp (66) 116 54 fetch [0] 59 push 3 64 mod 65 not 66 jz (15) 82 71 push 1 76 prts 77 jmp (38) 116 82 fetch [0] 87 push 5 92 mod 93 not 94 jz (15) 110 99 push 2 104 prts 105 jmp (10) 116 110 fetch [0] 115 prti 116 push 3 121 prts 122 fetch [0] 127 push 1 132 add 133 store [0] 138 jmp (-129) 10 143 halt

99 Bottles

Input to lex

Output from lex, input to parse

Output from parse

Output from gen, input to VM

<lang c> /* 99 bottles */ bottles = 99; while (bottles >= 0) {

   print(bottles, " bottles of beer on the wall\n");
   print(bottles, " bottles of beer\n");
   print("Take one down, pass it around\n");
   print(bottles, " bottles of beer on the wall\n\n");
   bottles = bottles - 1;

} </lang>

2 1 Identifier bottles 2 9 Op_assign 2 11 Integer 99 2 13 Semicolon 3 1 Keyword_while 3 7 LeftParen 3 8 Identifier bottles 3 16 Op_greaterequal 3 19 Integer 0 3 20 RightParen 3 22 LeftBrace 4 5 Keyword_print 4 10 LeftParen 4 11 Identifier bottles 4 18 Comma 4 20 String " bottles of beer on the wall\n" 4 52 RightParen 4 53 Semicolon 5 5 Keyword_print 5 10 LeftParen 5 11 Identifier bottles 5 18 Comma 5 20 String " bottles of beer\n" 5 40 RightParen 5 41 Semicolon 6 5 Keyword_print 6 10 LeftParen 6 11 String "Take one down, pass it around\n" 6 44 RightParen 6 45 Semicolon 7 5 Keyword_print 7 10 LeftParen 7 11 Identifier bottles 7 18 Comma 7 20 String " bottles of beer on the wall\n\n" 7 54 RightParen 7 55 Semicolon 8 5 Identifier bottles 8 13 Op_assign 8 15 Identifier bottles 8 23 Op_subtract 8 25 Integer 1 8 26 Semicolon 9 1 RightBrace 10 1 End_of_input

Sequence Sequence ; Assign Identifier bottles Integer 99 While Greater Identifier bottles Integer 0 Sequence Sequence Sequence Sequence Sequence ; Sequence Sequence ; Prti Identifier bottles ; Prts String " bottles of beer on the wall\n" ; Sequence Sequence ; Prti Identifier bottles ; Prts String " bottles of beer\n" ; Sequence ; Prts String "Take one down, pass it around\n" ; Sequence Sequence ; Prti Identifier bottles ; Prts String " bottles of beer on the wall\n\n" ; Assign Identifier bottles Subtract Identifier bottles Integer 1

Datasize: 1 Strings: 4 " bottles of beer on the wall\n" " bottles of beer\n" "Take one down, pass it around\n" " bottles of beer on the wall\n\n" 0 push 99 5 store [0] 10 fetch [0] 15 push 0 20 gt 21 jz (67) 89 26 fetch [0] 31 prti 32 push 0 37 prts 38 fetch [0] 43 prti 44 push 1 49 prts 50 push 2 55 prts 56 fetch [0] 61 prti 62 push 3 67 prts 68 fetch [0] 73 push 1 78 sub 79 store [0] 84 jmp (-75) 10 89 halt

Ascii Mandlebrot

Input to lex

Output from lex, input to parse

Output from parse

Output from gen, input to VM

<lang c> { /*

This is an integer ascii Mandelbrot generator
*/
   left_edge   = -420;
   right_edge  =  300;
   top_edge    =  300;
   bottom_edge = -300;
   x_step      =    7;
   y_step      =   15;

   max_iter    =  200;

   y0 = top_edge;
   while (y0 > bottom_edge) {
       x0 = left_edge;
       while (x0 < right_edge) {
           y = 0;
           x = 0;
           the_char = ' ';
           i = 0;
           while (i < max_iter) {
               x_x = (x * x) / 200;
               y_y = (y * y) / 200;
               if (x_x + y_y > 800 ) {
                   the_char = '0' + i;
                   if (i > 9) {
                       the_char = '@';
                   }
                   i = max_iter;
               }
               y = x * y / 100 + y0;
               x = x_x - y_y + x0;
               i = i + 1;
           }
           putc(the_char);
           x0 = x0 + x_step;
       }
       putc('\n');
       y0 = y0 - y_step;
   }

} </lang>

1 1 LeftBrace 5 5 Identifier left_edge 5 17 Op_assign 5 19 Op_subtract 5 20 Integer 420 5 23 Semicolon 6 5 Identifier right_edge 6 17 Op_assign 6 20 Integer 300 6 23 Semicolon 7 5 Identifier top_edge 7 17 Op_assign 7 20 Integer 300 7 23 Semicolon 8 5 Identifier bottom_edge 8 17 Op_assign 8 19 Op_subtract 8 20 Integer 300 8 23 Semicolon 9 5 Identifier x_step 9 17 Op_assign 9 22 Integer 7 9 23 Semicolon 10 5 Identifier y_step 10 17 Op_assign 10 21 Integer 15 10 23 Semicolon 12 5 Identifier max_iter 12 17 Op_assign 12 20 Integer 200 12 23 Semicolon 14 5 Identifier y0 14 8 Op_assign 14 10 Identifier top_edge 14 18 Semicolon 15 5 Keyword_while 15 11 LeftParen 15 12 Identifier y0 15 15 Op_greater 15 17 Identifier bottom_edge 15 28 RightParen 15 30 LeftBrace 16 9 Identifier x0 16 12 Op_assign 16 14 Identifier left_edge 16 23 Semicolon 17 9 Keyword_while 17 15 LeftParen 17 16 Identifier x0 17 19 Op_less 17 21 Identifier right_edge 17 31 RightParen 17 33 LeftBrace 18 13 Identifier y 18 15 Op_assign 18 17 Integer 0 18 18 Semicolon 19 13 Identifier x 19 15 Op_assign 19 17 Integer 0 19 18 Semicolon 20 13 Identifier the_char 20 22 Op_assign 20 24 Integer 32 20 27 Semicolon 21 13 Identifier i 21 15 Op_assign 21 17 Integer 0 21 18 Semicolon 22 13 Keyword_while 22 19 LeftParen 22 20 Identifier i 22 22 Op_less 22 24 Identifier max_iter 22 32 RightParen 22 34 LeftBrace 23 17 Identifier x_x 23 21 Op_assign 23 23 LeftParen 23 24 Identifier x 23 26 Op_multiply 23 28 Identifier x 23 29 RightParen 23 31 Op_divide 23 33 Integer 200 23 36 Semicolon 24 17 Identifier y_y 24 21 Op_assign 24 23 LeftParen 24 24 Identifier y 24 26 Op_multiply 24 28 Identifier y 24 29 RightParen 24 31 Op_divide 24 33 Integer 200 24 36 Semicolon 25 17 Keyword_if 25 20 LeftParen 25 21 Identifier x_x 25 25 Op_add 25 27 Identifier y_y 25 31 Op_greater 25 33 Integer 800 25 37 RightParen 25 39 LeftBrace 26 21 Identifier the_char 26 30 Op_assign 26 32 Integer 48 26 36 Op_add 26 38 Identifier i 26 39 Semicolon 27 21 Keyword_if 27 24 LeftParen 27 25 Identifier i 27 27 Op_greater 27 29 Integer 9 27 30 RightParen 27 32 LeftBrace 28 25 Identifier the_char 28 34 Op_assign 28 36 Integer 64 28 39 Semicolon 29 21 RightBrace 30 21 Identifier i 30 23 Op_assign 30 25 Identifier max_iter 30 33 Semicolon 31 17 RightBrace 32 17 Identifier y 32 19 Op_assign 32 21 Identifier x 32 23 Op_multiply 32 25 Identifier y 32 27 Op_divide 32 29 Integer 100 32 33 Op_add 32 35 Identifier y0 32 37 Semicolon 33 17 Identifier x 33 19 Op_assign 33 21 Identifier x_x 33 25 Op_subtract 33 27 Identifier y_y 33 31 Op_add 33 33 Identifier x0 33 35 Semicolon 34 17 Identifier i 34 19 Op_assign 34 21 Identifier i 34 23 Op_add 34 25 Integer 1 34 26 Semicolon 35 13 RightBrace 36 13 Keyword_putc 36 17 LeftParen 36 18 Identifier the_char 36 26 RightParen 36 27 Semicolon 37 13 Identifier x0 37 16 Op_assign 37 18 Identifier x0 37 21 Op_add 37 23 Identifier x_step 37 29 Semicolon 38 9 RightBrace 39 9 Keyword_putc 39 13 LeftParen 39 14 Integer 10 39 18 RightParen 39 19 Semicolon 40 9 Identifier y0 40 12 Op_assign 40 14 Identifier y0 40 17 Op_subtract 40 19 Identifier y_step 40 25 Semicolon 41 5 RightBrace 42 1 RightBrace 43 1 End_of_input

Sequence ; Sequence Sequence Sequence Sequence Sequence Sequence Sequence Sequence Sequence ; Assign Identifier left_edge Negate Integer 420 ; Assign Identifier right_edge Integer 300 Assign Identifier top_edge Integer 300 Assign Identifier bottom_edge Negate Integer 300 ; Assign Identifier x_step Integer 7 Assign Identifier y_step Integer 15 Assign Identifier max_iter Integer 200 Assign Identifier y0 Identifier top_edge While Greater Identifier y0 Identifier bottom_edge Sequence Sequence Sequence Sequence ; Assign Identifier x0 Identifier left_edge While Less Identifier x0 Identifier right_edge Sequence Sequence Sequence Sequence Sequence Sequence Sequence ; Assign Identifier y Integer 0 Assign Identifier x Integer 0 Assign Identifier the_char Integer 32 Assign Identifier i Integer 0 While Less Identifier i Identifier max_iter Sequence Sequence Sequence Sequence Sequence Sequence ; Assign Identifier x_x Divide Multiply Identifier x Identifier x Integer 200 Assign Identifier y_y Divide Multiply Identifier y Identifier y Integer 200 If Greater Add Identifier x_x Identifier y_y Integer 800 If Sequence Sequence Sequence ; Assign Identifier the_char Add Integer 48 Identifier i If Greater Identifier i Integer 9 If Sequence ; Assign Identifier the_char Integer 64 ; Assign Identifier i Identifier max_iter ; Assign Identifier y Add Divide Multiply Identifier x Identifier y Integer 100 Identifier y0 Assign Identifier x Add Subtract Identifier x_x Identifier y_y Identifier x0 Assign Identifier i Add Identifier i Integer 1 Prtc Identifier the_char ; Assign Identifier x0 Add Identifier x0 Identifier x_step Prtc Integer 10 ; Assign Identifier y0 Subtract Identifier y0 Identifier y_step

Datasize: 15 Strings: 0 0 push 420 5 neg 6 store [0] 11 push 300 16 store [1] 21 push 300 26 store [2] 31 push 300 36 neg 37 store [3] 42 push 7 47 store [4] 52 push 15 57 store [5] 62 push 200 67 store [6] 72 fetch [2] 77 store [7] 82 fetch [7] 87 fetch [3] 92 gt 93 jz (329) 423 98 fetch [0] 103 store [8] 108 fetch [8] 113 fetch [1] 118 lt 119 jz (276) 396 124 push 0 129 store [9] 134 push 0 139 store [10] 144 push 32 149 store [11] 154 push 0 159 store [12] 164 fetch [12] 169 fetch [6] 174 lt 175 jz (193) 369 180 fetch [10] 185 fetch [10] 190 mul 191 push 200 196 div 197 store [13] 202 fetch [9] 207 fetch [9] 212 mul 213 push 200 218 div 219 store [14] 224 fetch [13] 229 fetch [14] 234 add 235 push 800 240 gt 241 jz (56) 298 246 push 48 251 fetch [12] 256 add 257 store [11] 262 fetch [12] 267 push 9 272 gt 273 jz (14) 288 278 push 64 283 store [11] 288 fetch [6] 293 store [12] 298 fetch [10] 303 fetch [9] 308 mul 309 push 100 314 div 315 fetch [7] 320 add 321 store [9] 326 fetch [13] 331 fetch [14] 336 sub 337 fetch [8] 342 add 343 store [10] 348 fetch [12] 353 push 1 358 add 359 store [12] 364 jmp (-201) 164 369 fetch [11] 374 prtc 375 fetch [8] 380 fetch [4] 385 add 386 store [8] 391 jmp (-284) 108 396 push 10 401 prtc 402 fetch [7] 407 fetch [5] 412 sub 413 store [7] 418 jmp (-337) 82 423 halt