Building a compiler Part. 4 of 4 Turq

 "And all knowledge is vain save when there is work."

                                                                                                                   — Kahlil Gibran, The Prophet

Now we will be putting our knowledge of the last few blogs to create a compiler, this compiler will translate our program into assembly code in NASM syntax which can then be assembled and linked using GNU tools.

Note: The code was tested on a x86-64 Linux based system.

We will look into each instruction and how is it implemented in assembly, starting with the declarations. We assume the tape to be finite with 30000 cells; these will be our memory for the program. The rbx register will be the RW head.

For INC x:

    Increase the value of contents at rbx location/address by x. This translates to ADD byte [rbx], x in assembly

For DEC x:

    Decrease the value of contents at rbx location/address by x. This translates to SUB byte [rbx], x in assembly

For RIGHT:

   Increase the value of rbx. Most machines have a dedicated instruction INC in their ISA. This translates to INC rbx

For LEFT:

   Decrease the value of rbx. Most machines have a dedicated instruction DEC in their ISA. This translates to INC rbx

For PRINT:

    We use write syscall, for this the first argument is stored in rdi as 1 for stdout, second in rsi as rbx value, which points to the location of cell whose contents will be printed, and final argument in rdx as 1 to denote 1 byte. The rax has value of 1 to specify a write syscall.

For READ:

     We use read syscall, for this the first argument is stored in rdi as 0 for stdin, second in rsi as rbx value, which points to the location of cell in which the input will be read, and final argument in rdx as 1 to denote 1 byte. The rax has value of 0 to specify a write syscall.

For HALT:

    Exit the program by calling exit syscall with 0 exit code. Move 60 into rax and 0 into rdi.

For while and if blocks:

    jump statements are used to control flow and comparison can be made with the current cell value and an integer. jg, jl and its variants are used to support signed comparisons, this however limits the cell values to -128 to 127, hence limiting printable characters.

The yacc part is standard nested logic for while and if statements, for the other statements, they are directly derivable from terminals.

Now let's see how this language can be used to solve a classic problem of validating a parentheses string. The TM for a parentheses checker is

TM for paren_check

Here X and Y are the output tape symbols and B is treated to be '\n' in the code. S indicates that the RW head will be stationary. To convert this TM to code, we can treat each of the states to have a specific code snippet:

For state q0:

state q0

For state q1:

state q1

This can be shortened if we analyse that we just need to find if there exists a ')' and replace it with Y. We can run a loop till we don't reach a blank (here \'n') and if we encounter ')', write Y and move to state q2, but since in our language we don't have goto, labels or any break, we can modify it so that the move to state is outside the while loop

state q1 modified

state q1 code usable

Now for the last non-terminal state q2:

state q2

Now these 3 states follow a cycle and are sequential, hence can be put inside a loop, the compiler code for the compiler and the paren_check example can be found at git-hub: A bare bones compiler based on the Turing machine instructions written in LEX and YACC.