Lab Assignment Turtle Graphic

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: 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.

Hints:

More hints? Ask your Instructor!

Learning Objectives:

• lex (flex) and yacc (bison)
• Basic turtle commands (go turn color width)
• 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