www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com
Free Guestbook
My Guestbook

So what do we want to make?

Our aim is to turn the high-level format into a language that we shall call AdvLang. Then we shall write a compiler to translate our high-level AdvLang language into our low-level language (consisting of html and javascript.) This can be split into two parts: analysis and synthesis.

The compiler will be a program written in the C language, and we shall call it compile.c. From this we shall produce an executible called compile. We shall put the high-level description of our adventure game in a file with extension .al. For instance, we may store the example from the last page in a file called toy.al . Then we shall "compile" toy.al as

compile < toy.al

The compiler will produce a html file called toy.html with the appropriate javascript and html codes in it. Simple!

To keep the compiler construction systematic it is customary to break up the process into modules, as shown in the pink boxes below.

This is essentially the same block diagram as the last one. However, we have used standard compiler terminology here. The front end is mde of three modules: lexical analysis, syntax analysis and semantic analysis. Lexical analysis is done first, then syntax and semantic analysis are done simultaneously. The back end consists of just one module: code generation. We shall explain all these modules in details in the subsequent pages.

Intermediate representation

Consider the blue boxes in the diagram above. They correspond to three representations of the same game information : at first it is represented as an AdvLang program, finally the same information is represented in HTML and Javascript. Between these two expreme representations we have the intermediate representation in terms of data structure. The front end of the compiler translates the AdvLang program to this representation, and the back end translates it to the final HTML and Javascript. The intermediate representation is used only inside the compiler, and so the compiler designer has absolute freedom to choose the data structures. In our example, we shall use the following C data structures and variables.

typedef struct {
    char* name;
    char* descr;
    int exits[4]; 
}
  locStruct;

locStruct locList[50];
int nLoc, startLoc;

The structure locStruct stores information about a single location. The array locList stores the list of all the locations. We have arbitrarily chosen 50 as its length. You may later replace it by, say, a linked list. The exit array is of size 4, since there are as many directions. We code north as 0, south as 1, east 2, and west 3. Thus, if the north exit from location 3 leads to location 9 then we shall have

locList[3].exits[0] = 9

If there is no exit to the east from location 6, then we shall have

locList[6].exits[2] = -1

The back end

It is not at all difficult to write the back end of our compiler. We shall write it as a number of C functions. Let us carefully understand what we want the C functions to write. We want to write a html file and two javascript files, which will be used by the html file. Why two javascript files? Because, part of the javascript remains the same for all games. We shall put all the fixed part in a file called fixed.js. The game-dependent javascript codes will go inside change.js. We discuss each of these below.

Producing the html

The html file starts by including the javascript files. Then it declares a form (which we have named ff) with the textarea and buttons.
toy.html:

<script language="javascript" src="fixed.js"/>
<script language="javascript" src="change.js"/>
<hr>
<center>
<form name="ff">
<table border=0>
<tr><td align="center">
<input type=button value="Start" onClick="backHome();">
<input type=button value="Give up!" onClick="giveUp();">
</td></tr>
<tr><td>
<textarea name="ta" rows=10 cols=40>
Welcome to Adventureland.
Press "Start" to begin.
</textarea></td></tr>
<tr><td>
<input type=button value="north" onClick="move(0);">
<input type=button value="south" onClick="move(1);">
<input type=button value="east" onClick="move(2);">
<input type=button value="west" onClick="move(3);">
</td></tr></table>
</form>
</center>
<hr>

Notice that it is always the same. So we can save it in the file toy.html once and for all.

Writing the javascript files

Most of the javascript actually remains the same from game to game, for example, the move function. Those things can be written in a file called fixed.js. Thus, fixed.js contains the following.
fixed.js:
function move(dirn) {
  if(map[curLoc][dirn]>=0) {
      curLoc = map[curLoc][dirn];
      nMove++;
      if(visited[curLoc]==0) {
        visited[curLoc] = 1;
        nVisit++;
      }
  }
  else {
     alert("Can't go in that direction");
     return;
  }
  document.ff.ta.value=locName[curLoc]+"\n\n  "+
                        locDescr[curLoc]+"\n\nYou have made "+
                        nMove+" moves.\nYou have visited "+
                        nVisit+" locations.";
}


function backHome() {
  curLoc = startLoc;
  nVisit = 1;
  nMove = 0;
  document.ff.ta.value=locName[curLoc]+"\n\n  "+
                        locDescr[curLoc]+"\n\nYou have made "+
                        nMove+" moves.\nYou have visited "+
                        nVisit+" locations.";
}

function giveUp() {
  if(curLoc != startLoc) 
    document.ff.ta.value="You have failed to return where\n"+
                         "you started from.\n"+
                         "So your score is 0.";
  else if(nMove==0) 
    document.ff.ta.value="Hey, you have not even moved!\n"+
                         "Your score is just 0.";
  else
    document.ff.ta.value="You have visited "+nVisit+
                         " locations in "+nMove+
                         " moves.\n Your score is "+ 
                         Math.ceil(100*nVisit/nMove);
}

Next we come to the part of the javascript that changes from game to game. We shall show the structure of the javascript and then a C function to write the javascript. There are three things to write: the map, the names and descriptions and the game state. In each case we first give the required output in a grey box, followed by a pink box containing a C program that produces the output.

First the map, stored as a two dimensional array. The javascript is like:

<script language="javascript">
map = new Array(nLoc);
map[0] = 
   new Array(comma separated list of 
             the exits of the 
             0-th location);
   .
   .
   .
map[nLoc-1] = 
   new Array(comma separated list of 
             the exits of the 
             (nLoc-1)-th location );

This can be produced using the function writeMap() below.

void writeMap(FILE *fout) {
  int i, j;
  fprintf(fout,"var map = new Array(%d);\n",nLoc);
  for(i=0;i<nLoc;i++) {
    fprintf(fout,"map[%d] = new Array(",i);
    for(j=0;j<4;j++) {
      fprintf(fout,"%d",locList[i].exits[j]);
      if(j<3) fprintf(fout,", ");
    }
    fprintf(fout,");\n");
  }
}
Next we have to store the names and descriptions of the locations in two arrays.
var locName = 
   new Array(A comma separated list 
             of the names); 
var descr = 
   new Array(A comma separated list 
             of the descriptions);
The following function writes produces this part of the javascript:
void writeNamesDescr(FILE *fout) {
  int i;
  /*The names*/

  fprintf(fout,"var locName = new Array(");
  for(i=0;i<nLoc;i++) {
    fprintf(fout,"\"%s\"",locList[i].name);
    if(i<nLoc-1) fprintf(fout,",\n");
  }
  fprintf(fout,");\n");

  /*The desriptions*/

  fprintf(fout,"var locDescr = new Array(");
  for(i=0;i<nLoc;i++) {
    fprintf(fout,"\"%s\"",locList[i].descr);
    if(i<nLoc-1) fprintf(fout,",\n");
  }
  fprintf(fout,");\n");
}
Finally, the game state: where the player currently is, how many moves have been made, how many locations have been visited. The visited array stores if a location has been visited. Intially only the 0-th location (i.e., the start location) has been visited).
curLoc = startLoc;
nVisit = 1;
nMove = 0;
visited = new Array(1,comma separated list of nLoc-1 0's);
Here is a C function to do this.
void writeState(FILE *fout) {
  int i;

  fprintf(fout,"startLoc = %d;\n",startLoc);
  fprintf(fout,"nMove = 0;\n");
  fprintf(fout,"nVisit = 1;\n");
  fprintf(fout,"visited = new Array(1,");
  for(i=1;i<nLoc-1;i++)
    fprintf(fout,"0,");
  fprintf(fout,"0);\n");
}
These three functions constitute the back end of the compiler, which we write as a single function emitCode():
void emitCode(FILE *fout) {
  writeMap(fout);
  writeNamesDescr(fout);
  writeState(fout);
}
We cannot use this function right now, because we are yet to write the front end of the compiler which should create the input for the back end. Once we finish the front end we shall come back to use this function.

Compiler/Interpreter/Byte-code compilation

The output of our compiler is a program in html and javascript. We need a browser like Internet Explorer or Netscape to use that output. It is possible to change the back end of our compiler slightly to make it a standalone software. Such a standalone software can directly interact with the player of the game. A typical session is shown below. Here the computer's output is shown in red, the human inputs are shown in black.

compile < toy.al
House

You are standing in front of your house.
Paths lead towards east and west.

Which way do you want to go? [e/w] : e


Flag

A flag is fluttering at a crossing.
Paths go in all four directions, except west.

Which way do you want to go? [n/s/e] : n

Such a standalone compiler is called an interpreter. The output of an interpreter is the final action itself. A compiler and an interpreter have the same front end, they differ only in their back ends.

One problem with interpreters is that they do not save their output in a file. So if you want to rerun a program using interpreters, you have to start everytime from the scratch. Some interpreters avoid this problem by implementing the front end and the back end as separate programs. The front end reduces the input program to an intermedite representation, and dumps it in a file. The back end program reads this file and takes the actions. If you need to rerun the program you only need to run the back end, since the intermediate representation is already stored in a file. This is called byte-code compilation. Java and Lisp are two major languages using this system. The so-called Java compiler javac is actually just the front end, the generated .class file is the intermediate representation, and the java program is the back end interpreter.

PrevNext
© Arnab Chakraborty (2007)

free html visitor counters
hit counter