Arnab Chakraborty's compiler tutorial: page 2 of 11

www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com

My Guestbook

Home >

... tutorials >

... ... Compiler

A big example

Now we shall look into a big example, where we shall design a new language. Our language will be a simple language to make a web-based adventure game. The language by itself is of little value. The aim will be to teach the general techniques. However, such languages are in existence: examples being ALAN, TADS and INFORM. Indeed, there are world championships for writing adventure games, where the contestants write their games in these languages.

The domain knowledge

One reason behind choosing this somewhat artificial example is that it does not require much domain knowledge. So you can focus more attention on the compiler design techniques than the domain-specific details. The little domain knowledge that will be needed is given now. The example domain will need html and javascript. Do not worry if you do not know javacript or html. We are not going to need them much after this page. Whatever little we shall need may be done by copying-and-pasting the codes provided in this tutorial.

Our adventure games will be based on maps, like the one shown below.

A sample map

The sample map consists of 6 locations: Marsh, Treasure, House, Flag, Obelisk and Forest. You can follow the roads to move from one place to another. Some of the roads are one-way as shown by the arrow. In our adventure, we start from the House. Then we have to visit all the places except the Marsh (which is a deadly place, since there is no return path) and finally come back to the House.

Such a map may be turned into a game by introducing a suitable scoring system based on number of places visited, number of moves made etc. A web implementation of the game is shown below using the sample map:

How do you create such a web implentation using hatml and javascript? First, you have to number the locations like House=0, Obelisk=1, etc. Then you have to store the names of the locations in an array: the 0-th entry will be string "House", and so on.


locName = new Array("House","Obelisk","Marsh","Treasure","Flag","Forest");

Similarly, you need another array of strings to hold the descriptions of each location. The 0-th entry of this array, for instance, will be the string

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

We shall call this array descr. Then comes the tough part: making the map. We shall store the map as the matrix with one row for each location and one column for each direction.

	North	South	East	West
House	-	-	Flag	Forest
Obelisk	-	Flag	Flag	Treasure
Marsh	-	-	-	-
Treasure	Obelisk	-	Flag	Forest
Flag	Obelisk	House	Obelisk	-
Forest	Marsh	House	Treasure	-

The 0-th row of the matrix is, therefore,


map[0] = new Array(-1,-1,4,5);

The 0-th location was House. So this row tells us the paths from the House. The first number is the destination towards north. Here it is -1, meaning there is no northwards path from the House. Similarly, the next -1 blocks the south. The next number is for east. If you go east from the House you will arrive at location 4 (which is the Flag.) If you go west then you will arrive at location 5 (the Forest). There is no path from the Marsh (location 2). So we have


map[2] = new Array(-1,-1,-1,-1);

The current status of the game is stored in the following variables:


var curLoc=0; //Current location. Intially 0.
var nMove=0; //Number of modes made so far. Initially 0.
var nVisit=1; //Number of locations visited so far. Initially 1. 
var visited = new Array(1,0,0,0,0,0); //Keeps track of visited locations. 
                                      //If the i-th entry is 1, then the
                                      //i-th location has been visited.

Finally, we have to write a little javascript function that prints messages based on this map. The following function is called whenever you press a direction button:


function move(dirn) {
  if(map[curLoc][dirn]>=0) {
    curLoc = map[curLoc][dirn];
  }
  else {
    alert("Can't go in that direction");
    return;
  }
  document.ff.ta.value=locName[curLoc]+"\n\n  "+
                        descr[curLoc]+"\n\nYou have made "+
                        nMove+" moves.\nYou have visited "+
                        nVisit+" locations.";
}

The next two functions take care of reseting the game, and showing the score:


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

function giveUp() {

  if(curLoc != 0) 
    document.ff.ta.value="You have failed to return home.\nSo your score is 0.";
  else if(nMove==0) 
    document.ff.ta.value="Hey, you have not even moved!\nYour 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);
}

To make the textarea and the buttons we use the following html code in the body of the document.


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

That's all the domain knowledge that is required for our problem.

Why a new language?

So we already know how to implement our toy game (or any other game with the same background info) using javascript and html. Imagine clients coming to you with their own maps and they want you to write suitable html and javascript code so that they can embed the game in their webpages. I hope you will agree that writing the above code is not much fun for non-programmers people who love adventure games. In case you do not agree with me, consider the following points.

You have to know javascript or html to write the code. Learning these languages is much more complex than designing adventure games.
In the javascript you have to refer to the directions and locations as numbers. But ordinary people prefer to use names like House or Obelisk.
Much of the javascript and html remain the same from game to game. For instace, the forms, buttons, the move function. While implementing different games, you have to write these parts again and again. This is a botheration!
The map of the adventureland is difficult to write in javascript because there we have to use a matrix, and have to specify even all the paths that do not exist (by -1).
If you want to update your game, by adding or deleting a new location , or changing a path or two, the same changes will take quite some effort to be effected in the javascript and html codes.
In the javascript the details of the game is sadly confused with the programming details.

However, notice that the sample game can be nicely described in the following self-evident format:


LOCATION house
NAME "Your house"
DESCRIPTION "You are standing\nin front of your house.\nPaths lead towards east and west."
east flag
west forest

LOCATION obelisk
NAME "Obelisk"
DESCRIPTION "A big obelisk is\nstanding before you. You can either go east or west or south." 
south flag
east flag
west treasure

LOCATION marsh
NAME "Marsh"
DESCRIPTION "You are slowly swallowed by the mud.\nWhat a terrible end!"

LOCATION treasure
NAME "Treasure"
DESCRIPTION "A chest full of treasure is lying at your feet!\nExits are towards north, east and west."
north obelisk
east flag
west forest

LOCATION flag
NAME "Flag"
DESCRIPTION "A flag is fluttering at a crossing.\nPaths go in all four directions, except west."
north obelisk
south house
east obelisk

LOCATION forest
NAME "Forest"
DESCRIPTION "A north-south road goes through a thick forest.\nA trail goes towards east." 
north marsh
south house
east treasure

START_AT house

This contains all the info about the game, and producing the html and javascript code from it is a mechanical job.

All these observations should suggest to us that we should better turn the above format into a language, and write a compiler for that language to translate a program into javascript and html.

And that's where the making of a language begins...

Exercise 2.1:Suppose we want to attach scores with each location. When the player first visits a place, his/her score should go up/down by an amount depending on the location. How would you incorporate this in the highlevel format?

[Click here for solution.]

Exercise 2.2:Think of at least two other situations where you have similar justification for designing a new language.

hit counter