The programming language LOGO (for example XLogo) is no longer one of the fashionable programming languages but one thing remains in use until today: turtle graphics.

This lab assignment asks you to create a compiler translating your own version of a turtle graphic command language to PostScript. A small program in your language might look like this (and you find more examples HERE):

// the recursive dragon curve PROCEDURE a(level,dist) { IF (level > 0) THEN { TURN -45; a(level-1,dist); TURN 90; b(level-1,dist); TURN -45; } ELSE GO dist; } PROCEDURE b(level,dist) { IF (level > 0) THEN { TURN 45; a(level-1,dist); TURN -90; b(level-1,dist); TURN 45; } ELSE GO dist; } UP; NORTH; GO 400; EAST; GO 150; DOWN; a(12, 5); |

This will be translated by your compiler into the quite unreadable PostScript code below. (Warning: This code was generated by the first version of my compiler and is really very ugly. Don't try to imitate it. I will teach you how to do a better job.)

%!PS-Adobe % generated by the simple turtle program compiler /sinphi 0.0 def /cosphi 1.0 def /state true def /pi 4 1 1 atan mul def newpath 0 0 moveto /turtlea { 20 dict begin /turtledist exch def /turtlelevel exch def turtlelevel 0 gt { 45 neg 180 div pi mul sinphi cosphi atan add dup sin /sinphi exch store cos /cosphi exch store turtlelevel 1 sub turtledist turtlea 90 180 div pi mul sinphi cosphi atan add dup sin /sinphi exch store cos /cosphi exch store turtlelevel 1 sub turtledist turtleb 45 neg 180 div pi mul sinphi cosphi atan add dup sin /sinphi exch store cos /cosphi exch store }{ turtledist dup cosphi mul exch sinphi mul state {rlineto} {rmoveto} ifelse } ifelse end } bind def /turtleb { 20 dict begin /turtledist exch def /turtlelevel exch def turtlelevel 0 gt { 45 180 div pi mul sinphi cosphi atan add dup sin /sinphi exch store cos /cosphi exch store turtlelevel 1 sub turtledist turtlea 90 neg 180 div pi mul sinphi cosphi atan add dup sin /sinphi exch store cos /cosphi exch store turtlelevel 1 sub turtledist turtleb 45 180 div pi mul sinphi cosphi atan add dup sin /sinphi exch store cos /cosphi exch store }{ turtledist dup cosphi mul exch sinphi mul state {rlineto} {rmoveto} ifelse } ifelse end } bind def /state false def /sinphi 1.0 store /cosphi 0.0 store 400 dup cosphi mul exch sinphi mul state {rlineto} {rmoveto} ifelse /sinphi 0.0 store /cosphi 1.0 store 150 dup cosphi mul exch sinphi mul state {rlineto} {rmoveto} ifelse /state true def 12 5 turtlea 2 setlinewidth stroke showpage |

The true beauty of it is visible only if you look at this code using a Postscript Viewer:

Learning Objectives:

- Know the important tools to build compilers.
- lex or flex to build a Lexical Analyzer
- yacc or bison to build a Parser

- Regular Expressions and EBNF to describe Syntax.

Assignment:

- Part 1

Analyze the above Program. Identify Tokens and write a syntactical analyzer using (f)lex. Test the analyzer with a simple main program. - Part 2

For the moment, we aim at a very simple language: no procedure, no functions, no variables no arithmetic, just commands. For example:`PEN UP`

,`PEN DOWN`

,`TURN LEFT`

,`TURN RIGHT`

,`GO FORWARD`

,`GO BACKWARD`

,`COLOR RED`

,`COLOR BLACK`

, - Part 3

We add numbers, variables, assignments, and expressions. - Part 4

We add controll structures for conditionals and loops. - Part 4

We add procedures.

More hints? Ask your Instructor!

- lex (flex) and yacc (bison)
- Basic turtle commands (go turn north south east west)
- Numbers
- Arithmetic expressions, associativity, and precedence (+ - * / ^ sin cos ... )
- Variables, symbol tables, and assignments
- Floating point numbers
- Boolean expressions ( and or not = < > )
- Control structures (if if-else while )
- Local variables and scope
- Procedures and functions
- Debugging, error handling, and error recovery