12.1 MiniC Language

The language we have selected has a syntax similar to C. It has been derived from the “higher order calculator”, especially HOC6 given by Kernighan and Pike in their pioneering book “Unix Programming Environment”.

12.1.1 What is HOC6?

HOC, “high-order calculator”, is a simple interpreted language for floating-point calculations. Its most common use is as a powerful and convenient calculator, interactively evaluating expressions such as 1 + 2 * sin(0.7). It also lets you assign values to variables, define your own functions, and use loops, conditionals and similar facilities you would expect in a programming language.

The HOC language was introduced and developed in the book The Unix Programming Environment, by Brian Kernighan and Rob Pike (Addison-Wesley, 1984). Countless people are indebted to this book, and its authors, for introducing them to Unix and its fantastic program development tools such as the shell, C and Yacc. Some of these people were strongly impressed by Kernighan and Pike's feat of building an interpreter so clearly, elegantly and easily, something which, before the advent of Yacc, was to be attempted only by experts.

In 1995, Kernighan and Pike released their version of HOC, under a BSD-like free software licence (http://netlib.bell-labs.comb/bwk/hoc.sh). This meant that modified versions of HOC could legally be released, and indeed several such modified versions were released. There are several other derivations from HOC6, for example:

Extended high-order calculator The HOC version 7. Last updated: Nov 4 06:13:29 2004. See http://www.math.utah.edu/pub/hoc/

HOC ver. 9.2 by Nadav Y. Har’El, Last updated version 9.2, September 10, 2008. See http://nadav.harel.org.il/homepage/hoc/.

12.1.2 Objectives of minic

The driving idea behind minic is to provide a teaching–learning vehicle to students and teachers. The complete source code is being made available through the publishers on the website.

• To provide the teachers and students a language, its grammar and an implementation of a compiled, C-like language.
• To suggest various exercises to be done by students for modifications and extensions of the language and thereby become more familiar with compiler technology.
• To provide the complete source code so that the above objectives can be met.

While HOC6 is designed as an interactive calculator, with its emphasis on numerical calculations and demonstration of program development facilities in Unix-like systems, our aim is to illustrate as much a compiler technology for a non-trivial programming language setting as possible within the space limitations of a text-book. Although we have adopted most of the grammar of the original Kernighan and Pike HOC6, there are significant differences also.

The main areas where minic differs from HOC6 are:

1. minic is meant to be compiled into a target language.
2. HOC6 handles only one type of data, viz., double, as the emphasis is on numerical calculation, minic has three data types – integers, floats and strings. This was necessary to demonstrate the type-checking concepts.
3. The Symbol Table used in HOC6 is a singly Linked List. In minic, we use a Binary Search Tree to form the main Symbol Table and Hash Table C library functions in the optimization analysis function in liveness.c. The use of BST ADT allows a student to experiment with more sophisticated tree structures like AVL or Red–Black trees. The functions to manipulate such advanced tree structures are already available in Tree-base.
4. HOC6 does not need declaration of a variable, but in minic each variable has to be declared before it is used. This helps us in demonstrating type checking and error generation.
5. Though HOC6 does generate a target code, the code is actually the call addresses for a library of C functions. In case of minic, the target code we have selected is assembly language of x86 (Section 12.4). It also generates two types of Intermediate representations – RPN and 4-tuples list. This will allow students to try various optimization techniques, beyond what we have demonstrated.
6. The function call conventions used in miniC are compatible with many popular C compilers. This makes functions written in miniC callable from a C program (and vice-versa, present with some limitations). This not only helps debugging the code generated by our miniC compiler, but also opens up a method of further development of a compiler for miniC.
7. We made a conscious decision not to use the standard C library with the compiled miniC programs, though it is perfectly possible to do so. We have given a small macro-based library for minimally required functions, such as read, print, square–root, etc., and expect the students to extend this library and use it with miniC programs.