Figure 1.6 (a)

Figure 1.6 (b)

Figure 1.6 (c)

Figure 1.6 (d)

Figure 1.7 (a)

Figure 1.7 (b)

Figure 1.9 (a)

Figure 1.9 (b)

Figure 1.9 (c)

Figure 1.9 (d)

Figure 1.9 (e)

Figure 1.9 (f)

Figure 1.16 (a)

Figure 1.16 (b)

Figure 1.17 (a)

Figure 1.8

Figure 1.23

Figure 1.24 (a)

Figure 1.24 (b)

Figure 1.24 (c)

Figure 1.24 (d)

Figure 1.24 (e)

Figure 1.24 (f)

Page 28

Random Tree

Random Tree

Random Tree

Random Tree

Random Tree

Random Tree

Random Tree

Introduction

The figures that follow on this page were generated using the descriptions in the online book The Algorithmic Beauty of Plants by Przemyslaw Pruskinkiewicz & Aristid Lindenmayer. This book explains how to generate the figures but does not give program listings that do. This web page reproduces some of the figures from the book and includes the source code, written in C++, that were used to create them. Translating from the notation used in the book to a working program was not trivial, therefore providing this code can save others from reinventing the wheel or make a concept in the book clearer when put in the context of computer code as opposed to descriptions in English.

The book describes a number of different types of figures. The algorithms to create these figures start out simple and become more complicated. I have written separate programs for some of the algorithms presented in the book. These programs start simple and then I add extra code to handle the more complicated algorithms.

Three programs are used to create the figures. The first performs the expansion of the initiator using the rules provided. The second converts the instructions in the expanded string to a file containing a number of line segments and the third takes this as input to create output in the SVG format. These programs can be connected using the Unix pipe mechanism to create a single program.

The generated figures are labelled with the same designations as those in the books. A large version of the figures appear on the right and a smaller version along with the input file that was used to generate it appear on the left inline with the text description.

Simple DOL Systems

An Input File Format

In order to generate a figure such as 1.6 (a) the L system must be specified as well as other details like the angle and the number of iterations to use. Here is the format that I came up with.

fig-1.6.a

Initiator -> F-F-F-F

Iterations -> 0

Angle -> 90.0

%%

F -> F-F+F+FF-F-F+F
In order to process this file it must be broken into tokens. The program flex can be used to build a tokenizer. The following is the file used by flex to create a tokenizer.

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

%x gen
%x rule

lhs                      [-+F]+

int                      0|[1-9]|[1-9][0-9]+

float                    [0-9]+"."[0-9]*

%%

"Initiator"              {
                           return INITIATOR;
                         }

"Angle"                  {
                           return ANGLE;
                         }

"Iterations"             {
                           return ITERATIONS;
                         }

"->"                     {
                           return ARROW;
                         }

{int}                    {
                           lxlval.n=atoi(yytext);
                           return INT;
                         }

{float}                  {
                           lxlval.d=atof(yytext);
                           return FLOAT;
                         }

[ ]+                     {}

{lhs}                    {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

^"%%"[ ]*\n              {
                           line++;
                           BEGIN(gen);
                         }              

\n                       {
                           line++;
                           return EOL;
                         }

<gen>[F]                 {
                           lxlval.c=yytext[0];
                           return CHR;
                         }

<gen>[ ]+                {}

<gen>"->"                {
                           BEGIN(rule);
                           return ARROW;
                         }

<gen>\n                  {
                           line++;
                           return EOL;
                         }

<rule>[ ]+               {}

<rule>{lhs}              {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

<rule>\n                 {
                           line++;
                           BEGIN(gen);
                           return EOL;
                         }

<rule>.                  {
                           return UNK;
                         }

<gen>.                   {
                           return UNK;
                         }

.                        {
                           return UNK;
                         }

Each token is consumed by a parser which is implemented using the program bison. The parser dictates the order that the tokens read from the lexer can appear.

parse.y

%{
#include <iostream>
#include "system.h"

int lxlex(void);
void lxerror(char*);

extern unsigned int line;
extern System* sys;

%}

%union {
  char* s;
  char c;
  double d;
  unsigned int n;
}

%token EOL
%token ARROW
%token INITIATOR
%token UNK
%token ANGLE
%token ITERATIONS

%token <s> STR
%token <c> CHR
%token <d> FLOAT
%token <n> INT

%%

file:                 header generators

header:               initiator angle iterations
                    | initiator iterations angle
                    | iterations angle initiator
                    | iterations initiator angle
                    | angle iterations initiator
                    | angle initiator iterations

initiator:            INITIATOR ARROW STR eols
                      {
                        sys->setInitiator($3);
                      }

iterations:           ITERATIONS ARROW INT eols
                      {
                        sys->setIterations($3);
                      }

angle:                ANGLE ARROW INT eols
                      {
                        sys->setAngle($3);
                      }
                    | ANGLE ARROW FLOAT eols
                      {
                        sys->setAngle($3);
                      }

generators:           generator
                    | generators generator

generator:            CHR ARROW STR eols
                      {
                        sys->setGenerator($1,$3);
                      }

eols:                 EOL
                    | eols EOL 

%%

void lxerror(char* msg)
{
  std::cerr << "ERROR: " << line << " " << msg << std::endl;
}

As parts of the input file are recognized they are stored in a class called System through the instance variable sys.

system.h

#ifndef __SYSTEM_H__
#define __SYSTEM_H__

#include <map>

class System
{
  public:
    System(void);
    void setInitiator(const char*);
    void setAngle(double);
    void setIterations(unsigned int);
    void setGenerator(char,const char*);
    unsigned int getIterations(void);
    const char* getInitiator(void);
    const char* getGenerator(char);
    double getAngle(void);
    void write(const char*);
  private:
    bool in(char);
    const char* initiator;
    unsigned int n;
    double angle;
    std::map<char,const char*> m;
};

#endif

Expanding the Initiator Using Rules

Even though there is only one letter that gets replaced by a rule, the rules and the key letter are stored in a map. When the expansion is done it looks in the map to see if it is a key letter that should be expanded and if so it replaces the letter with the rule. If the letter is not in the map then no replacement is done. This allows the code that expands the string to be coded without using a switch statement and implicit key letters.

system.c

#include <iostream>
#include "system.h"

System::System(void)
{
}

void System::setInitiator(const char* i)
{
  initiator=i;
}

const char* System::getInitiator(void)
{
  return initiator;
}

void System::setGenerator(char c,const char* s)
{
  m[c]=s;
}

const char* System::getGenerator(char c)
{
  if (!in(c)) {
    return 0;
  }
  return m[c];
}

void System::setAngle(double a)
{
  angle=a;
}

double System::getAngle(void)
{
  return angle;
}

void System::setIterations(unsigned int n)
{
  this->n=n;
}

unsigned int System::getIterations(void)
{
  return n;
}

bool System::in(char c)
{
  std::map<char,const char*>::iterator pos=m.find(c);
  return (pos!=m.end());
}

void System::write(const char* s)
{
  std::cout << "Angle " << angle << std::endl;
  std::cout << s << std::endl;
}

The Grow class uses the map in the System class to replace each character in a string with the rules for expansion. In the main program this class will be called once for each iteration.

grow.h

#ifndef __GROW_H__
#define __GROW_H__

#include <string>
#include "system.h"

class Grow
{
  public:
    Grow(System*);
    std::string get(const std::string&);
  private:
    std::string generator[2];
    System* sys;
};

#endif

grow.c

#include <iostream>
#include <cstring>
#include "grow.h"

Grow::Grow(System* s) : sys(s)
{
}

std::string Grow::get(const std::string& a)
{
  std::string o="";
  const char* c=a.c_str();
  for (unsigned int i=0;i<strlen(c);i++) {
    if (sys->getGenerator(c[i])) {
      o+=sys->getGenerator(c[i]);
    } else {
      o+=c[i];
    }
  }
  return o;
}

The main program reads in the input file from standard input and stores it is an instance of the System class. Then the Grow class is used to build up the output in a standard string class. Finally the information needed by the generate program, just the angle and operations string, are written out to the standard output.

expand.c

#include <iostream>
#include <FlexLexer.h>
#include "system.h"
#include "grow.h"

extern int lxdebug;
extern int lx_flex_debug;

int lxparse(void);

System* sys;

int main(int argc,char* argv[])
{
  lxdebug=0; 
  lx_flex_debug=0;

  sys=new System;
 
  int ret=lxparse();
  if (ret!=0) {
    std::cerr << "Parser failed!" << std::endl;
    return 1;
  }

  Grow* g=new Grow(sys);

  std::string s=sys->getInitiator();
  for (unsigned int i=0;i<sys->getIterations();i++) {
    s=g->get(s);  
  }

  delete g;

  sys->write(s.c_str());

  delete sys;

  return ret;
}

The following Makefile builds the expand executable when the user types make.

Makefile

OBJS            =   lex.o\
                        parse.o\
                        system.o\
                        grow.o

all:                    expand

expand:                 expand.o $(OBJS)
                        g++ -o $@ expand.o $(OBJS) -lfl -lm

expand.o:               expand.c parse.h system.h grow.h
                        g++ -c expand.c

parse.o:                parse.c parse.h
                        g++ -c parse.c

lex.o:                  lex.c parse.h
                        g++ -c lex.c

parse.c parse.h:   parse.y
                        bison -v --debug -p lx -d -o parse.c parse.y

lex.c:                  lex.l
                        flex -d lex.l

system.o:               system.c system.h
                        g++ -c system.c

grow.o:                 grow.c grow.h
                        g++ -c grow.c

clean:                  
                        rm -f $(OBJS) parse.c parse.h lex.c
                        rm -f parse.output
                        rm -f expand expand.o

The command cat fig-1.6.a | expand now produces the following output.

Angle 90
F-F-F-F

Interpreting the Operation String

Once the initiator has been expanded for the number of iterations specified the operations need to be interpreted to get a drawing. This is done by another program called generate. The first step is to process the standard input stream using a lexer.

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

code                   [-+F]+

int                    [0-9]+

float                  [0-9]+"."[0-9]*

%%

"Angle"                {
                         return ANGLE;
                       }

{int}                  {
                         lxlval.n=atoi(yytext);
                         return INT;
                       }

{float}                {
                         lxlval.d=atof(yytext);
                         return FLOAT;
                       }

[ ]+                   {}

\n                     {
                         line++;
                         return EOL;
                       }

{code}                 {
                         lxlval.s=new char[strlen(yytext)+1];
                         strcpy(lxlval.s,yytext);
                         return STR;
                       }

.                      {
                         return UNK;
                       }

The tokens produced by the lexer are consumed by the parser and stored in a simpler System class than was used in the expand program.

parse.y

%{
#include <iostream>
#include "system.h"

int lxlex(void);
void lxerror(char*);

extern unsigned int line;
extern System* sys;

%}

%union {
  char* s;
  double d;
  unsigned int n;
}

%token EOL
%token UNK
%token ANGLE

%token <s> STR
%token <d> FLOAT
%token <n> INT

%%

file:                 angle generator

angle:                ANGLE INT eols
                      {
                        sys->setAngle($2);
                      }
                    | ANGLE FLOAT eols
                      {
                        sys->setAngle($2);
                      }

generator:            STR eols
                      {
                        sys->setGenerator($1);
                      }

eols:                 EOL
                    | eols EOL 

%%

void lxerror(char* msg)
{
  std::cerr << "ERROR: " << line << " " << msg << std::endl;
}

system.h

#ifndef __SYSTEM_H__
#define __SYSTEM_H__

#include <string>

class System
{
  public:
    System(void);
    void setAngle(double);
    void setGenerator(const char*);
    const char* getGenerator(void);
    double getAngle(void);
  private:
    double angle;
    std::string g;
};

#endif

system.c

#include <iostream>
#include "system.h"

System::System(void)
{
}

void System::setGenerator(const char* s)
{
  g=s;
}

const char* System::getGenerator(void)
{
  return g.c_str();
}

void System::setAngle(double a)
{
  angle=a;
}

double System::getAngle(void)
{
  return angle;
}

The Turtle class is used to interpret the operations specified by the input string. The Turtle class uses the State class to keep track of the turtle's state. The turtle has an angle that tells what direction it is heading and a two-dimensional point that specifies it's location.

state.h

#ifndef __STATE_H__
#define __STATE_H__

#include "point.h"

class State
{
  public:
    State(const Point&,double);
    State& operator=(const State&);
    const Point& getPoint(void) const;
    double getAngle(void) const;
    void setPoint(const Point&);
    void setAngle(double);
    void print(void);
  private:
    Point point;
    double angle;
};

#endif

state.c

#include <iostream>
#include "state.h"

State::State(const Point& p,double a)
{
  point=p;
  angle=a;
}

const Point& State::getPoint(void) const
{
  return point;
}

double State::getAngle(void) const
{
  return angle;
}

void State::setPoint(const Point& p)
{
  point=p;
}

void State::setAngle(double a)
{
  angle=a;
}

State& State::operator=(const State& s)
{
  this->point=s.getPoint();
  this->angle=s.getAngle();
}

The Point class used by the State class just implements a two-dimensional point.

point.h

#ifndef __POINT_H__
#define __POINT_H__

class Point
{
  public:
    Point(void);
    Point(double,double);
    double x(void) const;
    double y(void) const;
    Point& operator=(const Point&);
  private:
    double data[2];
};

#endif

point.c

#include <cmath>
#include "point.h"

Point::Point(void)
{
  data[0]=0.0;
  data[1]=0.0;
}

Point::Point(double a,double b)
{
  data[0]=a;
  data[1]=b;
}

Point& Point::operator=(const Point& p)
{
  data[0]=p.data[0];
  data[1]=p.data[1];
}

double Point::x(void) const
{
  return data[0];
}

double Point::y(void) const
{
  return data[1];
}

The Point class allows angles to be specified in degrees but then converted to radians so the standard math library calls to cosine and sin can be used.

angle.h

#ifndef __ANGLE_H__
#define __ANGLE_H__

double degrees2radians(double);
double radians2degrees(double);

#endif

angle.c

#include <cmath>
#include "angle.h"

// Convert an angle in degrees to radians 
// so it can be passed into C math trig functions 

double degrees2radians(double d)
{
  return d*M_PI/180.0;
}

double radians2degrees(double r)
{
  return r*180.0/M_PI;
}

The last class used by the Turtle class writes the lines generated by the turtle to the standard output.

write.h

#ifndef __WRITE_H__
#define __WRITE_H__

#include "point.h"

class Write
{
  public:
    static void line(const Point&,const Point&);
};

#endif 

write.c

#include <iostream>
#include "write.h"

void Write::line(const Point& from,const Point& to)
{
  std::cout << "line ";
  std::cout << from.x() << " " << from.y();
  std::cout << " ";
  std::cout << to.x() << " " << to.y();
  std::cout << std::endl;
}

The Turtle class only has three public functions. The only input needed by the constructor is the angle that the turtle should turn. The constructor initializes the state of the turtle which is located at 0,0 and facing up 90 degrees.

The process function takes in the operation string and processes it. For each character in the string the private function process is called. For the simplest diagrams there are only three operations F,+ and -.

The + and - operations are pretty simple, they just change the angle stored in the turtle's state. The changeAngle function changes the angle and keeps it between 0 and 360 degrees.

The F operation draws a line using the draw function. This function uses getNewPosition to compute a new position for the turtle using simple trigonometry. The draw function needs to save the current position before a new position is computed so that both endpoints of the line can be written out.

turtle.h

#ifndef __TURTLE_H__
#define __TURTLE_H__

#include "state.h"
#include "point.h"

class Turtle
{
  public:
    Turtle(double);
    ~Turtle(void);
    void process(const char*);
  private:
    void process(char);
    double changeAngle(double,double);
    const Point getNewPosition(const Point&,double);
    void draw(void);
    Point pos;
    const double reference;
    State* state;
};

#endif

turtle.c

#include <iostream>
#include <cstring>
#include <cmath>
#include "angle.h"
#include "turtle.h"
#include "write.h"

Turtle::Turtle(double t) : reference(t)
{
  state=new State(pos,90.0);
}

Turtle::~Turtle(void)
{
  delete state;
}

void Turtle::process(const char* s)
{
  for (unsigned int i=0;i<strlen(s);i++) {
    process(s[i]);
  }
}

void Turtle::process(char c)
{
  switch (c) {
    case 'F':
      draw();
      break;
    case '+':
      state->setAngle(changeAngle(state->getAngle(),reference));
      break;
    case '-':
      state->setAngle(changeAngle(state->getAngle(),-reference));
      break;
  }
}

void Turtle::draw(void)
{
  Point save=state->getPoint(); 
  state->setPoint(getNewPosition(state->getPoint(),state->getAngle()));
  Write::line(save,state->getPoint());
}

double Turtle::changeAngle(double a,double delta)
{
  double n=a+delta;
  if (n<0.0) {
    return 360.0+n;
  }
  if (n>=360.0) {
    return n-360.0;
  }
  return n;
}

const Point Turtle::getNewPosition(const Point& p,double angle)
{
  double x=p.x()+std::cos(degrees2radians(angle));
  double y=p.y()+std::sin(degrees2radians(angle));
  Point r(x,y);
  return r;
}

The main function is written in generate.c. It processes the input and then calls the process function on the Turtle class.

generate.c

#include <iostream>
#include <FlexLexer.h>
#include "system.h"
#include "turtle.h"

extern int lxdebug;
extern int lx_flex_debug;

int lxparse(void);

System* sys;

int main(int argc,char* argv[])
{
  lxdebug=0; 
  lx_flex_debug=0;

  sys=new System;
 
  int ret=lxparse();
  if (ret!=0) {
    std::cerr << "Parser failed!" << std::endl;
    return 1;
  }

  Turtle* t=new Turtle(sys->getAngle());

  t->process(sys->getGenerator());

  delete t;

  delete sys;

  return ret;
}

Here is the Makefile for the generate program.

Makefile

OBJS            =   lex.o\
                        parse.o\
                        system.o\
                        turtle.o\
                        point.o\
                        write.o\
                        angle.o\
                        state.o

all:                    generate

generate:               generate.o $(OBJS)
                        g++ -o $@ generate.o $(OBJS) -lfl -lm

generate.o:             generate.c parse.h system.h turtle.h point.h
                        g++ -c generate.c

parse.o:                parse.c parse.h
                        g++ -c parse.c

lex.o:                  lex.c parse.h
                        g++ -c lex.c

parse.c parse.h:   parse.y
                        bison -v --debug -p lx -d -o parse.c parse.y

lex.c:                  lex.l
                        flex -d lex.l

system.o:               system.c system.h
                        g++ -c system.c

turtle.o:               turtle.c turtle.h write.h
                        g++ -c turtle.c

point.o:                point.c point.h
                        g++ -c point.c

write.o:                write.c write.h point.h
                        g++ -c write.c

angle.o:                angle.c angle.h
                        g++ -c angle.c

state.o:                state.c state.h point.h
                        g++ -c state.c

clean:                  
                        rm -f $(OBJS) parse.c parse.h lex.c
                        rm -f parse.output
                        rm -f generate generate.o

Converting to an SVG image

When creating an SVG (Scaled Vector Graphics) from the line segments output by the generate program, the main difficulty is that the final size of the image is unknown. The size will depend on the number of iterations used to create an image. To handle this all the points in the lines are collected to find the bounds of the image. These bounds are used to scale the image so that it fits in a unit square and then it is again scaled to fill the size that is used to construct the SVG class.

The lexer returns tokens to the parser.

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

int                   [-]?0|[-]?[1-9]|[-]?[1-9][0-9]+

float                 [-]?[0-9]+"."[0-9]*(e{int})?

%%

"line"                {
                        return LINETO;
                      }

{int}                 {
                        lxlval.d=atof(yytext);
                        return NUM;
                      }

{float}               {
                        lxlval.d=atof(yytext);
                        return NUM;
                      }

[ ]+                  {}

\n                    {
                        line++;
                        return EOL;
                      }

.                     {
                        return UNK;
                      }

The parser is set up to recognize a set of line segments. For each line, two points are instantiated from the Point class. These two variables are used to instantiate a variable of the Line class.

The class Ln is used to collect bounding information from all the lines to be plotted. All of the instances of Ln are collected in a variable of class Lns.

parse.y

%{
#include <iostream>
#include "bounds.h"
#include "point.h"
#include "lns.h"
#include "ln.h"

int lxlex(void);
void lxerror(char*);

extern unsigned int line;
extern Lns* lns;

%}

%union {
  double d;
}

%token LINETO
%token EOL
%token UNK

%token <d> NUM

%%

file:                 lines

lines:                line
                    | lines line

line:                 LINETO NUM NUM NUM NUM eols
                      {
                        Point from($2,$3);
                        Point to($4,$5);
                        Line line(from,to);
                        Ln* ln=new Ln(line);
                        lns->add(ln);
                      }

eols:                 EOL
                    | eols EOL 

%%

void lxerror(char* msg)
{
  std::cerr << "ERROR: " << line << " " << msg << std::endl;
}

The Bounds class processes all the line segments and gathers the minimum and maximum values for the x and y coordinates.

bounds.h

#ifndef __BOUNDS_H__
#define __BOUNDS_H__

#include "point.h"

class Bounds
{
  public:
    static void init(void);
    static void set(const Point&);
    static const Point& min(void);
    static const Point& max(void);
  private:
    static bool first;
    static Point mn;
    static Point mx;
};

#endif
     

bounds.c

#include <iostream>
#include <algorithm>
#include "bounds.h"

Point Bounds::mn;
Point Bounds::mx;

bool Bounds::first=true;

void Bounds::init(void)
{
  first=true;
}

void Bounds::set(const Point& p)
{
  if (first) {
    mn.set(p.x(),p.y());
    mx.set(p.x(),p.y());
    first=false;
  } else {
    double xmin=std::min(mn.x(),p.x());
    double xmax=std::max(mx.x(),p.x());
    double ymin=std::min(mn.y(),p.y());
    double ymax=std::max(mx.y(),p.y());
    mn.set(xmin,ymin);
    mx.set(xmax,ymax);
  }
}

const Point& Bounds::min(void)
{
  return mn;
}

const Point& Bounds::max(void)
{
  return mx;
}

The Point class basically just stores a two dimensional point but it also includes a number of operations that will allow scaling and translation.

point.h

#ifndef __POINT_H__
#define __POINT_H__

class Point
{
  public:
    Point(void);
    Point(double,double);
    void set(double,double);
    double x(void) const;
    double y(void) const;
    void operator+=(const Point&);
    void operator/=(double);
  private:
    double data[2];
};

#endif

point.c

#include <iostream>
#include <cmath>
#include "point.h"

Point::Point(void)
{
  data[0]=0.0;
  data[1]=0.0;
}

Point::Point(double a,double b)
{
  data[0]=a;
  data[1]=b;
}

void Point::operator+=(const Point& d)
{
  data[0]+=d.data[0];
  data[1]+=d.data[1];
}

void Point::operator/=(double s)
{
  data[0]/=s;
  data[1]/=s;
}

void Point::set(double x,double y)
{
  data[0]=x;
  data[1]=y;
}

double Point::x(void) const
{
  return data[0];
}

double Point::y(void) const
{
  return data[1];
}

The Ln class just holds the instance of a Line but the constructor is used to get bounds information.

ln.h

#ifndef __LN_H__
#define __LN_H__

#include "line.h"
#include "svg.h"

class Ln
{
  public:
    Ln(const Line&);
    void process(SVG*);
  private:
    Line ln;
};

#endif

ln.c

#include <iostream>
#include "ln.h"
#include "bounds.h"

Ln::Ln(const Line& l) : ln(l)
{
  Bounds::set(ln.p1());
  Bounds::set(ln.p2());
}

void Ln::process(SVG* svg)
{
  svg->line(ln);
}

The Lns class just holds all the Lns. I also has the process method that will copy the Lines to the SVG class.

lns.h

#ifndef __LNS_H__
#define __LNS_H__

#include <vector>
#include "ln.h"
#include "svg.h"

class Lns
{
  public:
    Lns(void);
    void add(Ln*);
    void process(SVG*);
  private:
    std::vector<Ln*> ops;
};

#endif

lns.c

#include "lns.h"

Lns::Lns(void)
{
}

void Lns::add(Ln* o)
{
  ops.push_back(o);
}

void Lns::process(SVG* svg)
{
  for (unsigned int i=0;i<ops.size();i++)
    ops[i]->process(svg);
}

The Line class basically just stores the two endpoints of a line segment but it also includes a number of operations that will allow scaling and translation.

line.h

#ifndef __LINE_H__
#define __LINE_H__

#include "point.h"

class Line
{
  public:
    Line(const Point&,const Point&);
    void set(const Point&,const Point&);
    void translate(double,double);
    void scale(double);
    void verticalflip(double);
    const Point& p1(void) const;
    const Point& p2(void) const;
  private:
    Point p[2];
};

#endif    
    

line.c

#include <iostream>
#include <algorithm>
#include "line.h"

Line::Line(const Point& p1,const Point& p2)
{
  p[0]=p1;
  p[1]=p2;
}

void Line::translate(double x,double y)
{
  Point t(x,y);
  p[0]+=t;
  p[1]+=t;
}

void Line::scale(double s)
{
  p[0]/=s;
  p[1]/=s;
}

void Line::verticalflip(double m)
{
  p[0].set(p[0].x(),m-p[0].y());
  p[1].set(p[1].x(),m-p[1].y());
}

const Point& Line::p1(void) const
{
  return p[0];
}

const Point& Line::p2(void) const
{
  return p[1];
}

The Lines class holds all the lines that will be in the figure. Using bounding information from the Bounds class it can scale and translate all the lines to fit the desired size.

lines.h

#ifndef __LINES_H__
#define __LINES_H__

#include <vector>
#include "line.h"

class Lines
{
  public:
    void add(const Line&);
    void normalize(void);
    Line* get(unsigned int);
    unsigned int count(void);
  private:
    double absdiff(double,double);
    std::vector<Line*> lines;
};

#endif    
    

lines.c

#include <iostream>
#include <algorithm>
#include <cmath>
#include "lines.h"
#include "bounds.h"

void Lines::add(const Line& l)
{
  Line* ln=new Line(l);
  lines.push_back(ln);
}

void Lines::normalize(void)
{
  double xmax=Bounds::max().x();
  double xmin=Bounds::min().x();
  double ymax=Bounds::max().y();
  double ymin=Bounds::min().y();

  double x=absdiff(xmin,xmax);
  double y=absdiff(ymin,ymax);

  double dim=std::max(x,y);

  for (unsigned int i=0;i<lines.size();i++) {
    lines[i]->translate(-xmin,-ymin);
    lines[i]->verticalflip(ymax-ymin);
    lines[i]->scale(dim);
  }
}

double Lines::absdiff(double mn,double mx)
{
  if (mn>=0.0 && mx>=0.0)
    return mx-mn;
  if (mn<0.0 && mx<0.0)
    return -(mx-mn);
  return mx-mn;
}

Line* Lines::get(unsigned int i)
{
  return lines[i];
}

unsigned int Lines::count(void)
{
  return lines.size();
}

The SVG class holds all the lines that will be in the figure. It uses the Lines class to normalize all the line end points. The class can then write out the SVG image with the correct header and trailer.

svg.h

#ifndef __SVG_H__
#define __SVG_H__

#include "lines.h"

class SVG
{
  public:
    SVG(double);
    ~SVG(void);
    void header(void);
    void trailer(void);
    void line(double,double,double,double);
    void line(const Line&);
    void writelines(void);
    void writeline(double,double,double,double);
    void writeline(const Line*);
    void normalize(void);
  private:
    double size;
    Lines* lines;    
};

#endif

svg.c

#include <iostream>
#include "lines.h"
#include "svg.h"

SVG::SVG(double sz) : size(sz)
{
  lines=new Lines;
}

SVG::~SVG(void)
{
  delete lines;
}

void SVG::header(void)
{
  std::cout << "<?xml version=\"1.0\" encoding=\"iso-8859-1\" standalone=\"no\"?>" << std::endl;
  std::cout << "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.0//EN\" \"http://www.w3.org/TR/SVG/DTD/svg10.dtd\">" << std::endl;
  std::cout << "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" xml:space=\"preserve\">" << std::endl;

  std::cout << "  <g>" << std::endl;
}

void SVG::trailer(void)
{
  std::cout << "  </g>" << std::endl;
  std::cout << "</svg>" << std::endl;
}

void SVG::line(const Line& ln)
{
  lines->add(ln);
}

void SVG::writelines(void)
{
  for (unsigned int i=0;i<lines->count();i++) {
    Line* ln=lines->get(i);
    writeline(ln);
  }
}

void SVG::writeline(const Line* ln)
{
  Point p1=ln->p1();
  Point p2=ln->p2();

  std::cout << "    <line";
  std::cout << " x1=\"";
  std::cout << p1.x()*size;
  std::cout << "\"";
  std::cout << " y1=\"";
  std::cout << p1.y()*size;
  std::cout << "\"";
  std::cout << " x2=\"";
  std::cout << p2.x()*size;
  std::cout << "\"";
  std::cout << " y2=\"";
  std::cout << p2.y()*size;
  std::cout << "\"";
  std::cout << " style=\"stroke:black; stroke-width:1px\"/>" << std::endl;
}

void SVG::normalize(void)
{
  lines->normalize();
}

The main function reads in the input file and fills an instance of the Lns class. This instance is processed which just fills up an instance of the SVG class which normalizes the lines and then writes out the SVG drawing.

display.c

#include <iostream>
#include <unistd.h>
#include <FlexLexer.h>
#include "svg.h"
#include "lines.h"
#include "lns.h"
#include "parse.h"

#include "bounds.h"

extern int lxdebug;
extern int lx_flex_debug;

int lxparse(void);

Lns* lns=0;

int main(int argc,char* argv[])
{
  lxdebug=0; 
  lx_flex_debug=0;

  unsigned int size=1;

  int c;
  while ((c=getopt(argc,argv,"s:"))!=-1)
    switch (c) {
      case 's':
        size=atoi(optarg);
        break;
    }

  lns=new Lns;
  SVG* svg=new SVG(size);
 
  int ret=lxparse();
  if (ret!=0) {
    std::cerr << "Parser failed!" << std::endl;
  }

  lns->process(svg);

  svg->header();

  svg->normalize();

  svg->writelines();

  svg->trailer();

  delete lns;

  return ret;
}

Makefile

OBJS            =   lex.o\
                        parse.o\
                        point.o\
                        svg.o\
                        line.o\
                        lines.o\
                        lns.o\
                        ln.o\
                        bounds.o

all:                    display

display:                display.o $(OBJS)
                        g++ -o $@ display.o $(OBJS) -L/mcr/rsa/lib -lg -lfl -lm

display.o:              display.c parse.h
                        g++ -c display.c

parse.o:                parse.c parse.h
                        g++ -c parse.c

lex.o:                  lex.c parse.h
                        g++ -c lex.c

parse.c parse.h:   parse.y
                        bison -v --debug -p lx -d -o parse.c parse.y

lex.c:                  lex.l
                        flex -d lex.l

system.o:               system.c system.h
                        g++ -c system.c

point.o:                point.c point.h
                        g++ -c point.c

line.o:                 line.c line.h point.h
                        g++ -c line.c

grow.o:                 grow.c grow.h
                        g++ -c grow.c

svg.o:                  svg.c svg.h
                        g++ -c svg.c

lines.o:                lines.c lines.h
                        g++ -c lines.c

lns.o:                  lns.c lns.h
                        g++ -c lns.c

ln.o:                   ln.c ln.h line.h point.h
                        g++ -c ln.c

bounds.o:               bounds.c bounds.h point.h
                        g++ -c bounds.c

clean:                  
                        rm -f $(OBJS) parse.c parse.h lex.c
                        rm -f parse.output
                        rm -f display display.o

The Whole Process

Now that all three programs have been written they can be combined to take the simple specification file and create an SVG image.

cat fig-1.6.a | expand | generate | display -s 200 > fig-1-6-a.svg

fig-1.6.a

Initiator -> F-F-F-F

Iterations -> 0

Angle -> 90.0

%%

F -> F-F+F+FF-F-F+F

fig-1-6-a.svg

fig-1.6.b

Initiator -> F-F-F-F

Iterations -> 1

Angle -> 90.0

%%

F -> F-F+F+FF-F-F+F

fig-1-6-b.svg

fig-1.6.c

Initiator -> F-F-F-F

Iterations -> 2

Angle -> 90.0

%%

F -> F-F+F+FF-F-F+F

fig-1-6-c.svg

fig-1.6.d

Initiator -> F-F-F-F

Iterations -> 3

Angle -> 90.0

%%

F -> F-F+F+FF-F-F+F

fig-1-6-d.svg

Multiple Generators

It is possible to have multiple generators such as those in the input file for Figure 1.16 (a). To allow this type of input only the expand and generate programs need to be modified. The turtle in the generate program will only recognize the Fs that end up in the final string to draw lines. The L and R characters are ignored.

fig-1.16.a

Initiator -> -L

Iterations -> 3

Angle -> 90

%%

L -> LF+RFR+FL-F-LFLFL-FRFR+ 
R -> -LFLF+RFRFR+F+RF-LFL-FR

fig-1-16-a.svg

fig-1.17.a

Initiator -> L

Iterations -> 2

Angle -> 90

%%

L -> LFRFL-F-RFLFR+F+LFRFL
R -> RFLFR+F+LFRFL-F-RFLFR

fig-1-17-a.svg

The lex.l file needs to be changed so that instead of F the letters L and R need to be recognized. To make the program more flexible, any capital letter was allowed by specifying a range A-Z.

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

%x gen
%x rule

lhs                      [-+A-Z]+

int                      0|[1-9]|[1-9][0-9]+

float                    [0-9]+"."[0-9]*

%%

"Initiator"              {
                           return INITIATOR;
                         }

"Angle"                  {
                           return ANGLE;
                         }

"Iterations"             {
                           return ITERATIONS;
                         }

"->"                     {
                           return ARROW;
                         }

{int}                    {
                           lxlval.n=atoi(yytext);
                           return INT;
                         }

{float}                  {
                           lxlval.d=atof(yytext);
                           return FLOAT;
                         }

[ ]+                     {}

{lhs}                    {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

^"%%"[ ]*\n              {
                           line++;
                           BEGIN(gen);
                         }              

\n                       {
                           line++;
                           return EOL;
                         }

<gen>[A-Z]               {
                           lxlval.c=yytext[0];
                           return CHR;
                         }

<gen>[ ]+                {}

<gen>"->"                {
                           BEGIN(rule);
                           return ARROW;
                         }

<gen>\n                  {
                           line++;
                           return EOL;
                         }

<rule>[ ]+               {}

<rule>{lhs}              {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

<rule>\n                 {
                           line++;
                           BEGIN(gen);
                           return EOL;
                         }

<rule>.                  {
                           return UNK;
                         }

<gen>.                   {
                           return UNK;
                         }

.                        {
                           return UNK;
                         }

The lex.l file in the generate program also needs to allow more letters than F.

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

code                   [-+A-Z]+

int                    [0-9]+

float                  [0-9]+"."[0-9]*

%%

"Angle"                {
                         return ANGLE;
                       }

{int}                  {
                         lxlval.n=atoi(yytext);
                         return INT;
                       }

{float}                {
                         lxlval.d=atof(yytext);
                         return FLOAT;
                       }

[ ]+                   {}

\n                     {
                         line++;
                         return EOL;
                       }

{code}                 {
                         lxlval.s=new char[strlen(yytext)+1];
                         strcpy(lxlval.s,yytext);
                         return STR;
                       }

.                      {
                         return UNK;
                       }

Disconnected Drawings

It is possible to have pick up the pen and create disconnected drawings such as Figure 1.8. To allow this type of input only the expand and generate programs need to be modified. A move operation is added to the turtle in the generate program. When an f is seen in the operation string then a move instead of a draw takes place.

fig-1.8

Initiator -> F+F+F+F

Iterations -> 2

Angle -> 90.0

%%

F -> F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF
f -> ffffff

fig-1-8.svg

In the lexers for both the expand and generate executables the accepted character set has to be expanded to have lower case characters.

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

%x gen
%x rule

lhs                      [-+A-Za-z]+

int                      0|[1-9]|[1-9][0-9]+

float                    [0-9]+"."[0-9]*

%%

"Initiator"              {
                           return INITIATOR;
                         }

"Angle"                  {
                           return ANGLE;
                         }

"Iterations"             {
                           return ITERATIONS;
                         }

"->"                     {
                           return ARROW;
                         }

{int}                    {
                           lxlval.n=atoi(yytext);
                           return INT;
                         }

{float}                  {
                           lxlval.d=atof(yytext);
                           return FLOAT;
                         }

[ ]+                     {}

{lhs}                    {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

^"%%"[ ]*\n              {
                           line++;
                           BEGIN(gen);
                         }              

\n                       {
                           line++;
                           return EOL;
                         }

<gen>[A-Za-z]            {
                           lxlval.c=yytext[0];
                           return CHR;
                         }

<gen>[ ]+                {}

<gen>"->"                {
                           BEGIN(rule);
                           return ARROW;
                         }

<gen>\n                  {
                           line++;
                           return EOL;
                         }

<rule>[ ]+               {}

<rule>{lhs}              {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

<rule>\n                 {
                           line++;
                           BEGIN(gen);
                           return EOL;
                         }

<rule>.                  {
                           return UNK;
                         }

<gen>.                   {
                           return UNK;
                         }

.                        {
                           return UNK;
                         }

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

code                   [-+A-Za-z]+

int                    [0-9]+

float                  [0-9]+"."[0-9]*

%%

"Angle"                {
                         return ANGLE;
                       }

{int}                  {
                         lxlval.n=atoi(yytext);
                         return INT;
                       }

{float}                {
                         lxlval.d=atof(yytext);
                         return FLOAT;
                       }

[ ]+                   {}

\n                     {
                         line++;
                         return EOL;
                       }

{code}                 {
                         lxlval.s=new char[strlen(yytext)+1];
                         strcpy(lxlval.s,yytext);
                         return STR;
                       }

.                      {
                         return UNK;
                       }

The turtle has to be modified so that it can move as well as draw.

turtle.h

#ifndef __TURTLE_H__
#define __TURTLE_H__

#include "state.h"
#include "point.h"

class Turtle
{
  public:
    Turtle(double);
    ~Turtle(void);
    void process(const char*);
  private:
    void process(char);
    double changeAngle(double,double);
    const Point getNewPosition(const Point&,double);
    void draw(void);
    void move(void);
    Point pos;
    const double reference;
    State* state;
};

#endif

turtle.c

#include <iostream>
#include <cstring>
#include <cmath>
#include "angle.h"
#include "turtle.h"
#include "write.h"

Turtle::Turtle(double t) : reference(t)
{
  state=new State(pos,90.0);
}

Turtle::~Turtle(void)
{
  delete state;
}

void Turtle::process(const char* s)
{
  for (unsigned int i=0;i<strlen(s);i++) {
    process(s[i]);
  }
}

void Turtle::process(char c)
{
  switch (c) {
    case 'F':
      draw();
      break;
    case 'f':
      move();
      break;
    case '+':
      state->setAngle(changeAngle(state->getAngle(),reference));
      break;
    case '-':
      state->setAngle(changeAngle(state->getAngle(),-reference));
      break;
  }
}

void Turtle::draw(void)
{
  Point save=state->getPoint(); 
  state->setPoint(getNewPosition(state->getPoint(),state->getAngle()));
  Write::line(save,state->getPoint());
}

void Turtle::move(void)
{
  state->setPoint(getNewPosition(state->getPoint(),state->getAngle()));
}
double Turtle::changeAngle(double a,double delta)
{
  double n=a+delta;
  if (n<0.0) {
    return 360.0+n;
  }
  if (n>=360.0) {
    return n-360.0;
  }
  return n;
}

const Point Turtle::getNewPosition(const Point& p,double angle)
{
  double x=p.x()+std::cos(degrees2radians(angle));
  double y=p.y()+std::sin(degrees2radians(angle));
  Point r(x,y);
  return r;
}

Trees

In order to implement trees a stack has to be added to the Turtle. The lexical analyzer also needs to have the square brackets [] added. These brackets control when the turtle's state is pushed on and popped off the stack.

fig-1.23

Initiator -> F[+F][-F[-F]F]F[+F][-F]

Iterations -> 0

Angle -> 45.0

fig-1-23.svg

fig-1.24.a

Initiator -> F

Iterations -> 5 

Angle -> 25.7

%%

F -> F[+F]F[-F]F

fig-1-24-a.svg

fig-1.24.b

Initiator -> F

Iterations -> 5 

Angle -> 20

%%

F -> F[+F]F[-F][F]

fig-1-24-b.svg

fig-1.24.c

Initiator -> F

Iterations -> 4

Angle -> 22.5

%%

F -> FF-[-F+F+F]+[+F-F-F]

fig-1-24-c.svg

fig-1.24.d

Initiator -> X

Iterations -> 7

Angle -> 20

%%

X -> F[+X]F[-X]+X
F -> FF

fig-1-24-d.svg

fig-1.24.e

Initiator -> X

Iterations -> 7

Angle -> 25.7

%%

X -> F[+X][-X]FX
F -> FF

fig-1-24-e.svg

fig-1.24.f

Initiator -> X

Iterations -> 5 

Angle -> 22.5

%%

X -> F-[[X]+X]+F[+FX]-X
F -> FF

fig-1-24-f.svg

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

%x gen
%x rule

lhs                      [-+A-Za-z\[\]]+

int                      0|[1-9]|[1-9][0-9]+

float                    [0-9]+"."[0-9]*

%%

"Initiator"              {
                           return INITIATOR;
                         }

"Angle"                  {
                           return ANGLE;
                         }

"Iterations"             {
                           return ITERATIONS;
                         }

"->"                     {
                           return ARROW;
                         }

{int}                    {
                           lxlval.n=atoi(yytext);
                           return INT;
                         }

{float}                  {
                           lxlval.d=atof(yytext);
                           return FLOAT;
                         }

[ ]+                     {}

{lhs}                    {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

^"%%"[ ]*\n              {
                           line++;
                           BEGIN(gen);
                         }              

\n                       {
                           line++;
                           return EOL;
                         }

<gen>[A-Za-z]            {
                           lxlval.c=yytext[0];
                           return CHR;
                         }

<gen>[ ]+                {}

<gen>"->"                {
                           BEGIN(rule);
                           return ARROW;
                         }

<gen>\n                  {
                           line++;
                           return EOL;
                         }

<rule>[ ]+               {}

<rule>{lhs}              {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

<rule>\n                 {
                           line++;
                           BEGIN(gen);
                           return EOL;
                         }

<rule>.                  {
                           return UNK;
                         }

<gen>.                   {
                           return UNK;
                         }

.                        {
                           return UNK;
                         }

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

code                   [-+A-Za-z\[\]]+

int                    [0-9]+

float                  [0-9]+"."[0-9]*

%%

"Angle"                {
                         return ANGLE;
                       }

{int}                  {
                         lxlval.n=atoi(yytext);
                         return INT;
                       }

{float}                {
                         lxlval.d=atof(yytext);
                         return FLOAT;
                       }

[ ]+                   {}

\n                     {
                         line++;
                         return EOL;
                       }

{code}                 {
                         lxlval.s=new char[strlen(yytext)+1];
                         strcpy(lxlval.s,yytext);
                         return STR;
                       }

.                      {
                         return UNK;
                       }

turtle.h

#ifndef __TURTLE_H__
#define __TURTLE_H__

#include <stack>
 #include "state.h"
#include "point.h"

class Turtle
{
  public:
    Turtle(double);
    ~Turtle(void);
    void process(const char*);
  private:
    void process(char);
    double changeAngle(double,double);
    const Point getNewPosition(const Point&,double);
    void draw(void);
    void move(void);
    Point pos;
    const double reference;
    State* state;
    std::stack<State> stck;
 };

#endif

turtle.c

#include <iostream>
#include <cstring>
#include <cmath>
#include "angle.h"
#include "turtle.h"
#include "write.h"

Turtle::Turtle(double t) : reference(t)
{
  state=new State(pos,90.0);
}

Turtle::~Turtle(void)
{
  delete state;
}

void Turtle::process(const char* s)
{
  for (unsigned int i=0;i<strlen(s);i++) {
    process(s[i]);
  }
}

void Turtle::process(char c)
{
  switch (c) {
    case 'F':
      draw();
      break;
    case 'f':
      move();
      break;
    case '+':
      state->setAngle(changeAngle(state->getAngle(),reference));
      break;
    case '-':
      state->setAngle(changeAngle(state->getAngle(),-reference));
      break;
   case '[':
       stck.push(*state);
       break;
    case ']':
       *state=stck.top();
       stck.pop();
       break;
   }
}

void Turtle::draw(void)
{
  Point save=state->getPoint(); 
  state->setPoint(getNewPosition(state->getPoint(),state->getAngle()));
  Write::line(save,state->getPoint());
}

void Turtle::move(void)
{
  state->setPoint(getNewPosition(state->getPoint(),state->getAngle()));
}

double Turtle::changeAngle(double a,double delta)
{
  double n=a+delta;
  if (n<0.0) {
    return 360.0+n;
  }
  if (n>=360.0) {
    return n-360.0;
  }
  return n;
}

const Point Turtle::getNewPosition(const Point& p,double angle)
{
  double x=p.x()+std::cos(degrees2radians(angle));
  double y=p.y()+std::sin(degrees2radians(angle));
  Point r(x,y);
  return r;
}

Natural Looking Trees

In order to create a forest of trees they need to look different from each other. To solve this the expansion is done randomly. To implement this only the expand program needs to be changed.

page-28

Initiator -> F

Iterations -> 5

Angle -> 35

%%

F (0.33) -> F[+F]F[-F]F
F (0.33) -> F[+F]F
F (0.34) -> F[-F]F

page-28.svg

lex.l

%{
#include <cstring>
#include <cstdlib>
#include "parse.h"

unsigned int line=1;

%}

%option noyywrap
%option prefix="lx"
%option outfile="lex.c"

%x gen
%x rule

lhs                      [-+A-Za-z\[\]]+

int                      0|[1-9]|[1-9][0-9]+

float                    [0-9]+"."[0-9]*

%%

"Initiator"              {
                           return INITIATOR;
                         }

"Angle"                  {
                           return ANGLE;
                         }

"Iterations"             {
                           return ITERATIONS;
                         }

"->"                     {
                           return ARROW;
                         }

{int}                    {
                           lxlval.n=atoi(yytext);
                           return INT;
                         }

{float}                  {
                           lxlval.d=atof(yytext);
                           return FLOAT;
                         }

[ ]+                     {}

{lhs}                    {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

^"%%"[ ]*\n              {
                           line++;
                           BEGIN(gen);
                         }              

\n                       {
                           line++;
                           return EOL;
                         }

<gen>[A-Za-z]            {
                           lxlval.c=yytext[0];
                           return CHR;
                         }

<gen>[ ]+                {}

<gen>"->"                {
                           BEGIN(rule);
                           return ARROW;
                         }

<gen>\(                  {
                            return '(';
                          }
<gen>\)                  {
                            return ')';
                          }
<gen>{float}             {
                            lxlval.d=atof(yytext);
                            return FLOAT;
                          }
<gen>\n                  {
                           line++;
                           return EOL;
                         }

<rule>[ ]+               {}

<rule>{lhs}              {
                           lxlval.s=new char[strlen(yytext)+1];
                           strcpy(lxlval.s,yytext);
                           return STR;
                         }

<rule>\n                 {
                           line++;
                           BEGIN(gen);
                           return EOL;
                         }

<rule>.                  {
                           return UNK;
                         }

<gen>.                   {
                           return UNK;
                         }

.                        {
                           return UNK;
                         }

parse.y

%{
#include <iostream>
#include "system.h"

int lxlex(void);
void lxerror(char*);

extern unsigned int line;
extern System* sys;

%}

%union {
  char* s;
  char c;
  double d;
  unsigned int n;
}

%token EOL
%token ARROW
%token INITIATOR
%token UNK
%token ANGLE
%token ITERATIONS

%token <s> STR
%token <c> CHR
%token <d> FLOAT
%token <n> INT

%%

file:                 header generators
                    | header

header:               initiator angle iterations
                    | initiator iterations angle
                    | iterations angle initiator
                    | iterations initiator angle
                    | angle iterations initiator
                    | angle initiator iterations

initiator:            INITIATOR ARROW STR eols
                      {
                        sys->setInitiator($3);
                      }

iterations:           ITERATIONS ARROW INT eols
                      {
                        sys->setIterations($3);
                      }

angle:                ANGLE ARROW INT eols
                      {
                        sys->setAngle($3);
                      }
                    | ANGLE ARROW FLOAT eols
                      {
                        sys->setAngle($3);
                      }

generators:           generator
                    | generators generator

generator:            CHR '(' FLOAT ')' ARROW STR eols
                       {
                        sys->setGenerator($1,$3,$6);
                       }

eols:                 EOL
                    | eols EOL 

%%

void lxerror(char* msg)
{
  std::cerr << "ERROR: " << line << " " << msg << std::endl;
}

choice.h

#ifndef __CHOICE_H__
#define __CHOICE_H__

#include <vector>
#include <string>

class Choice
{
  public:
    Choice(char);
    void add(double,const char*);
    const char* get(void);
  private:
    double getRunningTotal(void);
    char c;
    std::vector<std::pair<double,const char*> > p;
};

#endif

choice.c

#include <iostream>
#include <cstdlib>
#include <time.h>
#include "choice.h"

Choice::Choice(char)
{
  srand(time(NULL));
}

void Choice::add(double d,const char* s)
{
  p.push_back(std::make_pair(getRunningTotal()+d,s));
}

const char* Choice::get(void)
{
  double random=rand();
  double max=RAND_MAX;
  double r=random/max;
  unsigned int i=0;
  for (i=0;i<p.size();i++) {
    if (r<p[i].first)
      return p[i].second;
  }
  return p[i].second;
}

double Choice::getRunningTotal(void)
{
  return (p.size()==0) ? 0.0:p[p.size()-1].first;
} 

system.h

#ifndef __SYSTEM_H__
#define __SYSTEM_H__

#include <map>
#include "choice.h"

class System
{
  public:
    System(void);
    void setInitiator(const char*);
    void setAngle(double);
    void setIterations(unsigned int);
    void setGenerator(char,double,const char*);
     unsigned int getIterations(void);
    const char* getInitiator(void);
    const char* getGenerator(char);
    double getAngle(void);
    void write(const char*);
  private:
    bool in(char);
    const char* initiator;
    unsigned int n;
    double angle;
    std::map<char,Choice*> m;
 };

#endif

system.c

#include <iostream>
#include "system.h"

System::System(void)
{
}

void System::setInitiator(const char* i)
{
  initiator=i;
}

const char* System::getInitiator(void)
{
  return initiator;
}

void System::setGenerator(char c,double p,const char* s)
{
  if (in(c)) {
    m[c]->add(p,s);
  } else {
    m[c]=new Choice(c);
    m[c]->add(p,s);
  }
}

const char* System::getGenerator(char c)
{
  if (!in(c)) {
    return 0;
  }
  return m[c]->get();
}

void System::setAngle(double a)
{
  angle=a;
}

double System::getAngle(void)
{
  return angle;
}

void System::setIterations(unsigned int n)
{
  this->n=n;
}

unsigned int System::getIterations(void)
{
  return n;
}

bool System::in(char c)
{
  std::map<char,Choice*>::iterator pos=m.find(c);
  return (pos!=m.end());
}

void System::write(const char* s)
{
  std::cout << "Angle " << angle << std::endl;
  std::cout << s << std::endl;
}

Makefile

OBJS            =   lex.o\
                        parse.o\
                        system.o\
                        grow.o\
                        choice.o

all:                    expand

expand:                 expand.o $(OBJS)
                        g++ -o $@ expand.o $(OBJS) -lfl -lm

expand.o:               expand.c parse.h system.h grow.h
                        g++ -c expand.c

parse.o:                parse.c parse.h
                        g++ -c parse.c

lex.o:                  lex.c parse.h
                        g++ -c lex.c

parse.c parse.h:   parse.y
                        bison -v --debug -p lx -d -o parse.c parse.y

lex.c:                  lex.l
                        flex -d lex.l

system.o:               system.c system.h
                        g++ -c system.c

grow.o:                 grow.c grow.h
                        g++ -c grow.c

choice.o:               choice.c choice.h
                         g++ -c choice.c
clean:                  
                        rm -f $(OBJS) parse.c parse.h lex.c
                        rm -f parse.output
                        rm -f expand expand.o