Arnab Chakraborty's compiler tutorial: page 8 of 11

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

My Guestbook

Home >

... tutorials >

... ... Compiler

Back to AdvLang

Here is the complete AdvLang grammar for quick reference.


(Rule 1)  program : locnSpecList startSpec 
(Rule 2)  startSpec : tok_START tok_IDENT
(Rule 3)  locnSpec : tok_LOCN tok_IDENT nameSpec descrSpec exitList 
(Rule 4)  nameSpec : tok_NAME tok_STRING 
(Rule 5)  descrSpec : tok_DESCR tok_STRING 
(Rule 6)  exit : tok_DIRN tok_IDENT 
(Rule 7)  locnSpecList : locnSpec 
(Rule 8)  locnSpecList : locnSpecList locnSpec 
(Rule 9)  exitList : 
(Rule 10) exitList: exitList exit

Virtual Lab:

After lexical analysis an AdvLang program becomes a list of tokens. During syntax analysis the tokens are grouped step by step into non terminals, the non terminals are then grouped into possibly other non terminals and so on. For instance, the two tokens


tok_DIRN tok_IDENT

are grouped into the non terminal exit. A bunch of exit non terminals are grouped into one exitList. The idea is to finally arrive at the non terminal program, which is the highest non terminal, so to speak. If we fail to arrive at it, we have a syntax error, otherwise our program is syntactically correct. The entire process of combining tokens into non terminals, the non terminals into other non terminals until we arrive at the highest non terminal, is called derivation, as we have learned in the last page.

Virtual Lab

The box to the left provides a virtual laboratory that shows the steps involed in the derivation of an AdvLang program. To use it type or paste any AdvLang program in the program window. A small sample program has already been provided in it to get you started. Press the Next button again and again to step through the parsing. The BNF window will display the next action of the compiler. It will be either a BNF rule to be used (reduce), or the command "Read the next token" (shift). Continue clicking on the "Next" button until you get either an error message or the message that the program is syntactically correct. The contents of the second window constitute the steps of the derivation.

Pen and paper

It is essential that you understand each step in the derivation. Consider the program


LOCATION cave
NAME "A dark cave"
DESCRIPTION "A granite cave is before you"
north hill
south cave

START_AT cave

Let us write down the entire derivation of this program. To save space we have only shown the part of program to the left of the dot (i.e., the part we have already read). Initially we have nothing to the left of the dot.

    tok_LOCN
     tok_LOCN tok_IDENT
     tok_LOCN tok_IDENT tok_NAME
     tok_LOCN tok_IDENT tok_NAME tok_STRING
    ⁴ tok_LOCN tok_IDENT nameSpec
     tok_LOCN tok_IDENT nameSpec tok_DESCR
     tok_LOCN tok_IDENT nameSpec tok_DESCR tok_STRING
    ⁵ tok_LOCN tok_IDENT nameSpec descrSpec
    ⁹ tok_LOCN tok_IDENT nameSpec descrSpec exitList
     tok_LOCN tok_IDENT nameSpec descrSpec exitList tok_DIRN
     tok_LOCN tok_IDENT nameSpec descrSpec exitList tok_DIRN tok_IDENT
    ⁶ tok_LOCN tok_IDENT nameSpec descrSpec exitList exit
    ¹⁰ tok_LOCN tok_IDENT nameSpec descrSpec exitList
     tok_LOCN tok_IDENT nameSpec descrSpec exitList tok_DIRN
     tok_LOCN tok_IDENT nameSpec descrSpec exitList tok_DIRN tok_IDENT
    ⁶ tok_LOCN tok_IDENT nameSpec descrSpec exitList exit
    ¹⁰ tok_LOCN tok_IDENT nameSpec descrSpec exitList
    ³ locnSpec
    ⁷ locnSpecList
     locnSpecList tok_START
     locnSpecList tok_START tok_IDENT
    ² locnSpecList startSpec
    ¹ program

Exercise 8.1:Hand-parse the following program, and then check you answer using the virtual lab.
LOCATION cave NAME "Cave Front" DESCRIPTION "You are standing in front of a cave" north cave south lake LOCATION lake NAME "Lake" DESCRIPTION " A big lake is in front of you" START_AT cave
(Warning: It might be a bit boring. But going through the gory details would help consolidate your understanding.)

In this page we have learned about syntax analysis. It is nothing but applying shift and reduce rule judiciously to the sequence of tokens until we end up with the starting non terminal (program, in this example). For our simple language it is not diificult to decide when to shift and when to reduce. There are algorithms to make the decision automatically for more general languages. We shall talk about them later. In the next page we shall learn about semantic analysis.

hit counter