Turtle Graphics
History
Many attempts have been made to create pro-
gramming languages which are intuitive and easy
to learn.
One of the best of these was LOGO which al-
lowed children as young as 3 to learn a computer
language.
A subset of this language involved a “turtle” which
could be driven around the screen using sim-
ple instructions. The turtle, when viewed from
above, was represented by a triangle.
An Example
{
FD 30
LT 45
FD 30
LT 45
FD 30
LT 45
FD 30
LT 45
FD 30
LT 45
FD 30
LT 45
FD 30
LT 45
FD 30
LT 45
}
Adding Loops
{
DOAFROM1TO8{
FD 30
LT 45
}
}The Formal Grammar
<MAIN> ::= "{" <INSTRCTLST>
<INSTRCTLST> ::= <INSTRUCTION><INSTRCTLST> |
"}"
<INSTRUCTION> ::= <FD> |
<LT> |
<RT> |
<DO> |
<SET>
<FD> ::= "FD" <VARNUM>
<LT> ::= "LT" <VARNUM>
<RT> ::= "RT" <VARNUM>
<DO> ::= "DO" <VAR> "FROM" <VARNUM> "TO"
<VARNUM> "{" <INSTRCTLST>
<VAR> ::= [A-Z]
<VARNUM> ::= number |
<VAR>
<SET> ::= "SET" <VAR> ":=" <POLISH>
<POLISH> ::= <OP> <POLISH> |
<VARNUM> <POLISH> |
";"
<OP> ::= "+" |
"-" |
"*" |
"/"
Using Variables
{
DO A FROM 1 TO 100 {
SET C := A 1.5 * ;
FD C
RT 62
}
}
Nested Loops
{
DOAFROM1TO50{
FD A
RT 30
DO B FROM 1 TO 8 {
SETC:=A5/;
FD C
RT 45
}
}
}
Hints
Don’t try to write the entire program in one go.
Try a cut down version of the grammar first, e.g.:
<MAIN> ::= "{" <INSTRCTLST>
<INSTRCTLST> ::= <INSTRUCTION><INSTRCTLST> |
"}"
<INSTRUCTION> ::= <FD> | <LT> | <RT>
<FD> ::= "FD" <VARNUM>
<LT> ::= "LT" <VARNUM>
<RT> ::= "RT" <VARNUM>
<VARNUM> ::= number
The language is simply a sequence of words (even
the semi-colons), so use scanf().
Some issues, such as what happens if you use
an undefined variable, or if you use a variable
before it is set, are not explained by the formal
grammar. Use your own common-sense, and
explain what you have done.Assessment
(25%) To implement a recursive descent parser
- this says whether or not a given turtle program
follows the formal grammar or not. The input file
is specified via argv[1].
(25%) To implement an interpreter, so that the
instructions are executed. Output is to the file
specified in argv[2]. The graphics could be
done using a .ppm file, as in the fractal work, or
directly to a postscript file. A simple postscript
file to draw a red box is shown here:
1 0 0 setrgbcolor
newpath
100 100 moveto
100 200 lineto
200 200 lineto
200 100 lineto
100 100 lineto
stroke
Postscript files can be used using ghostview
or xv.
(25%) To show a testing strategy on the above
- you should give details of white-box and black-
box testing done on your code. Describe any
test-harnesses used. Give examples of the out-
put of many different turtle programs. Convince
me that every line of your C code has been tested.
Assessment
(25%) To show an extension to the project in a
direction of your choice. It should demonstrate
your understanding of some aspect of program-
ming or S/W engineering. If you extend the for-
mal grammar make sure that you show the new,
full grammar.
Submit the program(s) and a Makefile so that I can:
Compile the parser by typing ‘make parse’.
Compile the interpreter by typing ‘make interp’.
Compile the extension by typing ‘make exten-
sion’.
In addition:
Submit a test strategy report called test.txt. This
will include sample outputs, any code written es-
pecially for testing etc.
Submit an extension report called ‘extend.txt’.
This is quite brief and explains the extension at-
tempted.
Assessment
Labs as normal weeks 11 and 12.
Please also fill out a hard-copy of the self-assessment
questionnaire on the web, so that you (and I!)
have an idea of what mark you expect. Leave
this in my room around deadline day. Don’t for-
get to fill out your name (you’d be surprised at
the number of people who do ....)