Chapter 8: Program Development

This chapter is about constructing a mini programming language using specific UNIX toolsets, because UNIX is a program development environment. I wasn't expecting writing a compiler/interpreter in this book.

Writing a programming language is explained as a problem of converting inputs into actions and outputs. For this we'll need the following:

yacc: generates a parser from a grammatical description
make: control process to compile programs
lex: lexical analyzer

The process is divided into 6 steps.

1. A four-function calculator
2. Variables a-z
3. Long variables name, built-in functions
4. Refactoring
5. Control flow
6. Recursive functions and procedues with arguments

Stage 1:

We get introduced to yacc and a little bit with make automaticity.
Yacc is used to build a parse tree with related actions, while the makefile is used to not have to type the compilation command over and over again.

I didn't know that make was yacc file aware, it can automatically know how to build them.


Stage 2:

This step is about adding memory to hoc for 26 variables, a to z, single letter variable. Which is done by using a fixed size array.
Which is impressively simple to add.

We also see how error handling is done, here using long jump and signal. The signal reset doesn't need to be reset because it's going to jump back to a place which will set it again right after the label.


Stage 3:

This stage drops the fixed size array in favor of a linked list for arbitrary variable names an built-in functions.
Weirdly, the programming style also changes, the syntax isn't really the same.
There's a lot of heavy changes involved, and we definitely need a makefile to make the linking process simpler.

We see that make -n can be used to have a view of the full process:

The authors of the book also insist on a "pr" rule in the makefile, to print the file content. I'm not sure it's actually usefule these days.
The "clean" rule is definitely useful.

Lastly, in this section we get to know lex, the lexical analyzer. Instead of having to write yylex() yourself, you can rely on it to create the tokens for you. However, the book only uses it here and argues that they'll revert back to C for size related reasons. Using lex makes the binary a bit bigger, on my machine the lex version is 42KB while the one without is 24KB.

Stage 4:

In this section we stop interpreting the code right away and instead will generate and intermediate code (IR intermediate representation). This is then put on a stack machine and executed.
Compilation into a machine

Starting in this section, you are left alone to figure out which functions are missing and that you need to write yourself for the program to compile properly. For example you have to add sub,mul,power,negate yourself.

Stage 5:

In this section we continue the previous stage by adding control flow and relational operators. You're similarly left to write them yourself and figure it out.

The code is a bit fragile as it doesn't have statement separator other than surrounding them with braces. Now you can write stuff like:


Or on one line:

Stage 6:

In this section we add functions and procedure along with input/output. Though I couldn't really test the input/output as it wasn't explained well and integrated in the hoc final code.

To make functions work in our yacc parse tree we have to rely on embedded actions. These actions are used to delimit the start of the body of a function and the end of it.

The code is tedious and the authors go back to recommending again to rely on lex for lexical analysis instead of having the gigantic yylex() function we reached.

There's a lot of stack play here to make functions possible but which I couldn't really test in the end as I was not able to write the lexer for this.

Finally, we get to compare the speed of our implementation against bas, bc, and C for fib and ackermann's function.
By replacing calls to push and pop in action.c to macros we can actually speed up our hoc. So calling methods is pretty slow when writing a language.