Pigeon Compiler¶

In order to teach the basics of compilers and the compilation process there is a simple but very flexible and powerful meta-compiler built around a fascinating 1964 paper/project/artifact Meta-II.

Simple Polymorphic Compiler¶

Tiny engine that loads and runs compiler descriptions which then allow it to become several different compilers (including a compiler which can compile itself which is why it’s called a “meta-compiler”.)

A simple high-level description like this:

.SYNTAX OOOLALA

OOOLALA = HUH | 'jones' | foo | bar ;

HUH = gary 'smith' tuesday ;

tuesday = day ( night | .EMPTY ) | cake ;

.END

...gets compiled into this assembly code:

# Program OOOLALA
# (preamble)
set_switch()

label(OOOLALA) # subroutine ==========
call(HUH)
if_not_switch_jmp_to(L1)
label(L1)
if_switch_jmp_to(L2)
expect('jones')
if_not_switch_jmp_to(L3)
label(L3)
if_switch_jmp_to(L2)
call(foo)
if_not_switch_jmp_to(L4)
label(L4)
if_switch_jmp_to(L2)
call(bar)
if_not_switch_jmp_to(L5)
label(L5)
label(L2)
ret()

label(HUH) # subroutine ==========
call(gary)
if_not_switch_jmp_to(L6)
expect('smith')
if_not_switch_jmp_to(ERROR)
call(tuesday)
if_not_switch_jmp_to(ERROR)
label(L6)
label(L7)
ret()

label(tuesday) # subroutine ==========
call(day)
if_not_switch_jmp_to(L8)
call(night)
if_not_switch_jmp_to(L9)
label(L9)
if_switch_jmp_to(L10)
set_switch()
if_not_switch_jmp_to(L11)
label(L11)
label(L10)
if_not_switch_jmp_to(ERROR)
label(L8)
if_switch_jmp_to(L12)
call(cake)
if_not_switch_jmp_to(L13)
label(L13)
label(L12)
ret()

#END

The compiler takes care of figuring out the control flow logic for us and we supply the runtime implementation of the switching functions:

def set_switch():
  andi(reg, 1 << bit)

def call(addr):
  if abs(here() - addr) < RELATIVE_CALL_LIMIT:
    relative_call(addr)
  else:
    long_call(addr)

def if_not_switch_jmp_to(_):
  sbrs(reg, bit)
  jmp(_)

def if_switch_jmp_to(_):
  sbrc(reg, bit)
  jmp(_)

def expect(_):
  pass # This would examine some buffer and set reg[bit] accordingly.

This particular set of runtime macros uses a bit in a register (which ones are not defined here) as the switch to control program flow. We could use other definitions of “switch”, which opens up some interesting possibilities.

Val Shorre’s Meta-II Metacompiler¶

The Meta-II engine compiles the metaii.metaii description into an assembly source file (see metaii.asm) which is the same assembly source file that it uses to compile the assembly source file.

The assembly code regenerates itself. (Where do you get it the first time? You must emulate the engine in your mind and compile it by hand, or crib a copy from someone else.)

Here is the documentation on the Meta-II engine included in the Pigeon Computer project:

Meta II Meta-Compiler (Python Engine)¶

This is a Python implementation of Val Shorre’s Meta II metacompiler.

It is just the engine, the Meta-II machine, not a self-regenerating metacompiler. It does run the Meta-II assembly code and can scan the Meta-II compiler description and (re-)compile that assembly code.

This engine can be used to play with metacompilers and generate all sorts of cool and interesting things (see the Bayfront Technologies Metacompilers Tutorial.) We’re going to use it to target the Pigeon Assembler’s source format.

We can compile descriptions of high-level programming language constructs into assembly code and then use the assembler to generate HEX files to load on our chips, giving us a simple but powerful toolchain for developing code for our micro-controllers.

class pigeon.metacompiler.metaii.MetaII[source]¶

Bases: object

Implementation of Val Shorre’s Meta II metacompiler. (see http://en.wikipedia.org/wiki/META_II)

usage: metaii.py [-h] [-p PROGRAM] source

positional arguments:

source Source code file to compile.

optional arguments:

`-h, --help`	show this help message and exit
`-p PROGRAM, --program PROGRAM`
	Assembly file to use for compiler (default: metaii.asm).

ADR(ident)[source]¶: Set PC to the given label/address.

B(addr)[source]¶: Unconditional branch to addr.

BE()[source]¶: Branch to error. Terminates compilation and (by default) prints a bit of debugging information.

BF(addr)[source]¶: Branch to addr if switch is clear.

BT(addr)[source]¶: Branch to addr if switch is set.

CI()[source]¶: Copy last buffer contents to output buffer.

CL(string)[source]¶: Copy literal to output buffer.

CLL(addr)[source]¶: Call the subroutine at addr.

END()[source]¶: Terminate compilation normally.

GN1()[source]¶: Generate and output label for current subroutine cell 1.

GN2()[source]¶: Generate and output label for current subroutine cell 2.

ID()[source]¶: Strip all leading whitespace and scan for an identifier. If found consume it, store it in the last buffer and set switch, otherwise reset the switch.

LB()[source]¶: Set up output buffer for a label (as opposed to an instruction.)

NUM()[source]¶: Strip all leading whitespace and scan for a number. If found consume it, store it in the last buffer and set switch, otherwise reset the switch.

OUT()[source]¶: Copy output buffer to output stream, appending a newline character, then reset output buffer for next line.

R()[source]¶: Return from a subroutine.

SET()[source]¶: Set switch.

SR()[source]¶: Strip all leading whitespace and scan for a string (enclosed in single quotes.) If found consume it, store it in the last buffer and set switch, otherwise reset the switch.

TST(string)[source]¶: Look for and consume the string in the input text, setting switch if found, otherwise consume nothing (but leading whitespace) and reset switch. Strips all leading whitespace.

assemble(program_source)[source]¶: Assemble the provided Meta II assembly source text and become the machine (compiler) defined by that program.

assemble_line(op, arg=None)[source]¶: Used by the assemble() method to process each non-label input line in the assembly source text.

compile(input_text)[source]¶

Once a compiler assembly source text has been assembled (using the assemble() method) you can pass source code in the compiler’s language to this method to compile it.

Parameters:	input_text (`str`) – Source code in the language recognized by the machine passed to the `assemble()` method.
Return type:	`str`

info()[source]¶: Print out some useful information about the current state of the assembler/compiler. Used for debugging and after errors to report, uh, errors.

print_program()[source]¶: Print out a dump of the assembled compiler machine’s program. Used for debugging.

pigeon.metacompiler.metaii.label_generator()[source]¶: Generator of string labels: ‘L1’, ‘L2’, ‘L3’, ‘L4’, ‘L5’, ...

Language Design and Compiler Extentions¶

TODO: Write up a bit about all the myriad ways to go from here (basically ALL THE REST OF COMPUTER PROGRAMMING!!) Lol.

For example, here is the Meta-II compiler description that compiles the above high-level source to target the Pigeon Assembler:

.SYNTAX PROGRAM

EX3 = .ID .OUT('call(' * ')') |
      .STRING .OUT('expect(' * ')') |
      '(' EX1 ')' |
      '.EMPTY' .OUT('set_switch()') |

      '$' .OUT('label(' *1 ')')
      EX3 .OUT('if_switch_jmp_to(' *1 ')')
          .OUT('set_switch()') ;

EX2 = (EX3 .OUT('if_not_switch_jmp_to(' *1 ')'))
      $ (EX3 .OUT('if_not_switch_jmp_to(ERROR)'))
      .OUT('label(' *1 ')') ;

EX1 = EX2 $ ( '|' .OUT('if_switch_jmp_to(' *1 ')') EX2)
      .OUT('label(' *1 ')') ;

ST = .ID .OUT('label(' * ') # subroutine ==========')
     '='
     EX1
     ';' .OUT('ret()') .OUT('') ;

PROGRAM = '.SYNTAX'
          .ID .OUT('# Program ' * )
              .OUT('# (preamble)')
              .OUT('set_switch()')
              .OUT('')
          $ ST
          '.END' .OUT('#END') ;

.END

Pigeon Computer 0.1 documentation

Pigeon Compiler

Pigeon Compiler¶

Simple Polymorphic Compiler¶

Val Shorre’s Meta-II Metacompiler¶

Meta II Meta-Compiler (Python Engine)¶

Language Design and Compiler Extentions¶