flipCode - Tech File - Alex Champandard [an error occurred while processing this directive]
Alex Champandard
Click the name for some bio info

E-Mail: alex@base-sixteen.com



   06/13/2000, Revision Week Indeed




Nice And Fluffy


The start of my summer term picked up where the spring term left off, with another huge assessment. The difference was however that it was a Team System Project. It was a very interesting week where we all had to learn pretty much all of our System Specification And Design course, and then apply all that to create an Online Banking Interface. My team got along very well as we did very little arguing, probably because for the first few days we had no clue what we were doing, and during the last few days we concentrated on getting as much done as possible, as we realised how much we had to do. We stayed up the last night until 7 AM writing the report, in which we explained what we would have done, had we known what we were doing right from the start. Apart from laughing at each other's 4 o'clock in the morning humour, we managed to get a pretty consistent report done, but the design was still quite a bit vague in my opinion. Quite a few other projects impressed me. It turns out we got an A, probably because it was vague enough to be classed as design. So luckily we were unorganised enough to not get the full implementation done, like some other (really impressive) projects. I feel a bit bitter about the whole thing, since getting an A for something that fluffy is not satisfying at all. However, the design methodology we used was very elegant and got me interested. Since then, I've been trying to apply this to Escape, and found it extremely satisfying to actually implement something once it had been designed correctly. I'll talk about this process a bit more in the next week or so.

The rest of the term flew by... beer, girl, beer, no girl, birthday beer, programming, beer, programming, programming. Most of my attention has been focused on Escape, as I am extremely confident of the potential of this engine. Unfortunately, I'll probably run out of time before I start my summer job in two weeks. Keep an eye on the web page for more info.



Implementation Of Programming Languages


Lectures have slowly come to a halt, and surely enough exams are looming. There's nothing quite like revision week. I seem to get so many things get done: emailing most people in my address book twice, updating tech files, listening to my entire MP3 collection over and over, checking the content of flipcode on an hourly basis, and the occasional pint.... Basically, anything to avoid revision :P Anyway the first exam is tomorrow (IPL), so I've had to sit down and revise properly. It turns out most of it is actually just about remembering definitions. The interesting part being the use of Flex and Bison.

Given a specification of a language, Lex (and Flex) is capable of generating an appropriate scanner that will analyse any source code written in that language, and return a series of tokens. For example, take the following Flex specification:

 
%{

#include <stdio.h>

#define WORD		1001
#define NUMBER		1002
#define ASSIGN		1003
#define COMMA		1004
#define PLUS		1005


%}


letter			[a-zA-Z]
digit			[0-9]
ignored			[ \t\n]


%

{letter}+		{
				yylval = yytext;
				printf( "Word (%s)\n", yytext );
				return WORD;
			}


{number}+		{
				yylval = atoi( yytext );
				printf( "Number (%i)\n", yylval );
				return NUMBER;
			}


":="			return ASSIGN;
","			return COMMA;
"+"			return PLUS;


 

Running Flex on this will create a scanner for you. You can then pass it the following file, and it will output:

 
2 camels have 8 legs

Number (2)
Word (camels)
Word (have)
Number (8)
Word (legs) 

The advantage of using Flex is that development time is massively reduced, the time required to change the language's specification is proportionally very small. However, if you have time to space and wish to gain an intricate knowledge of scanners, you could hand code a scanner yourself. This would probably be slightly more efficient, as you will be able to fine tune your scanner, as opposed to Flex which uses an automated algorithm to do so. A fairly good book to read if you want to get started in that area is Compiler Construction: Principles And Practice - Kenneth C. Louden.

Yacc (younger brother of Bison) on the other hand is a parser, which can pretty much parse any language given it's specification. To get a fully working compiler, you have to implement semantic checking, build up the syntax tree, and convert that to code. You also have the option of creating a simple interpreter, which will for example compute simple arithmetic. Another application you could use Bison for is to parse Q3's .shader files, and build up appropriate data structures for each shader. Here is a sample of what Yacc can do, together with Lex:

 %{

#include <stdio.h>
#include "lex.yy.cc"

%}

%token 	WORD
%token 	NUMBER
%token 	ASSIGN
%token 	COMMA
%token 	PLUS

%%

program 	:	statement COMMA program
		|	statement

statement	:	WORD ASSIGN expression
			{
 			  /* just display the result */
			     printf( "%s = %i\n", $1, $3 );
			}

expression	:	NUMBER
			{
			     /* return the value of the first parameter */
				$$ = $1;
			}
		|	NUMBER PLUS expression
			{
                             /* return the sum of the two concerned parameters */
				$$ = $1 + $3
			}	

%% 

That's pretty much all you need for a simple interpreter. If you're interested in these tools, a good place to start is to read the appropriate manuals for Bison, and Flex.

I'll probably write another tech update tomorrow, as I will no doubt have a few minutes to spare during my revision ;)

Enjoy,

Alex





  • 01/05/2002 - A.I., Websites and Voxels
  • 03/05/2001 - State Of The Art Character Animation
  • 01/24/2001 - Alternate Programming Languages
  • 01/11/2001 - The Sound Of Silence
  • 09/20/2000 - Engine prototypes, yet more landscape LOD and hard body physics
  • 07/13/2000 - Good Practice (TM)
  • 06/13/2000 - Revision Week Indeed
  • 04/11/2000 - Escape From Inactivity ;)
  • 01/05/2000 - Generic Shaders
  • 12/03/1999 - Start Of Term: Lots Of Good Intensions :)
  • 10/06/1999 - Dynamic LOD, Landscape Generation and much more...
  • 09/22/1999 - Water Contest Entry: Rendering Raytraced Refraction with 3D Hardware
  • 09/16/1999 - More About Bezier Patches And Fractals
  • 08/11/1999 - The Right Landscape Engine For You!
  • 07/12/1999 - Leftovers From The Contest: Fixing TP7's Runtime Error 200 bug
  • 07/01/1999 - Introduction

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]