Arnab Chakraborty's DFA tutorial: page 8 of 11

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

My Guestbook

Home >

... tutorials >

... ... DFA

What do those tables mean?

The tables store the grammar of the EZ language. To see how first let's think how you, a human being, would go about checking syntax of an EZ program. For instance, as you go through the following code


if(a>4)
  a = a + 4
endif
end

you will stop just after you have read upto


if(a>4)
  a

You expected a "then" but found "a", an ID, and so you knew without reading further that the program could not be syntactically correct. What made you expect a "then"? Your knowledge of EZ, and the part of the code that you have already read told you that

These three pieces of info were all that you needed to detect the syntax error. It should not be difficult to see that at each point during reading the program you always determine your position w.r.t. high level constructs like "if-block"s "assignment statement"s and so on. To know you postion in any such construct you need only the three pieces of info as above:

Well, the numbers 0,...,25 that we put into the stack each represent one such triple. For instance, the above triple is coded by the number 16. Note that each such triple gives you only local info. It does not tell you what happened before the current high level construct. But that may be important later. For instance, if an assignment-statement occurs inside an if-block then we must remember to expect an "endif" somewhere down the line. That's why need the stack. It tells us about all the highlevel constructs that we are currently in. Next let's see how table 1 comes into picture. Here is table1 reproduced from the last page for ready reference.

Table 1

EOF end ID = if ( ) then endif NUM + >

0:  E    E   6    E  7    E   E   E    (2,1)  E   E   E 
1:  D    E   E    E  E    E   E   E      E    E   E   E 
2:  E   24   6    E  7    E   E   E      E    E   E   E 
3:  E  (2,2)(2,2) E (2,2) E   E   E    (2,2)  E   E   E 
4:  E  (3,1)(3,1) E (3,1) E   E   E    (3,1)  E   E   E 
5:  E  (3,1)(3,1) E (3,1) E   E   E    (3,1)  E   E   E 
6:  E    E   E    8  E    E   E   E      E    E   E   E 
7:  E    E   E    E  E    9   E   E      E    E   E   E 
8:  E    E   11   E  E    E   E   E      E   12   E   E 
9:  E    E   11   E  E    E   E   E      E   12   E   E 
10: E  (4,3)(4,3) E (4,3) E   E   E    (4,3)  E  15   E 
11: E  (6,1)(6,1) E (6,1) E (6,1) E    (6,1)  E (6,1)(6,1)
12: E  (6,1)(6,1) E (6,1) E (6,1) E    (6,1)  E (6,1)(6,1)
13: E    E   E    E  E    E  16   E      E    E   E   E 
14: E    E   E    E  E    E   E   E      E    E  18   17  
15: E    E  11    E  E    E   E   E      E   12   E   E 
16: E    E   E    E  E    E   E  20      E    E   E   E 
17: E    E  11    E  E    E   E   E      E   12   E   E 
18: E    E  11    E  E    E   E   E      E   12   E   E 
19: E  (6,3)(6,3) E (6,3) E (6,3) E    (6,3)  E (6,3)(6,3)
20: E    E   6    E  7    E   E   E    (2,1)  E   E   E 
21: E    E   E    E  E    E (7,3) E      E    E  18   E 
22: E    E   6    E  7    E   E   E     23    E   E   E 
23: E  (5,7)(5,7) E (5,7) E   E   E    (5,7)  E   E   E 
24:(1,2) E   E    E  E    E   E   E      E    E   E   E 
25: E  (2,1)(2,1) E (2,1) E   E   E    (2,1)  E   E   E

Suppose that the top of the stack is 16. And you see an "ID". You know that is an error (because you expected an "then") We store this info in table 1, by writing an E as its entry at row 16 and column "ID". Indeed, all the entries in the row for 16 are E's, except the entry under "then". When we see a "then" we naturally move to the triple

(same as before)

and this triple is given code 20 (the choice of the number is arbitrary). So we see 20 as the entry in table 1 at row 16 column "then".

Next we discuss the role of table 2.

Table 2

0 1 2 3 4 5 6 7

Suppose that we are at the end of some high level construct. For instance, if we are at 23 (ie, the top of the stack is 23), which denotes the triple

Compare 2 and 3 to see that this means "we are at the end of an if-block". Now suppose we see an "ID". This surely marks the beginning of the following statement. We do not need to remember the inner details of the if-block any more. So we shall pop off all those numbers in the stack that were keeping track of these details. As we moved through the 7 pieces of a generic if-block:

if, (, condition, ), then, statements, endif

we surely had 7 numbers in the stack. So we need to pop off 7 numbers. The number 7 depends only on the generic form of an "if-block" in EZ, and not on the particular program at hand. So we can hardcode this 7 as the second element in the pair entry in table 1 at row 23 column "ID". We have collapsed the 7 pieces into a single "high level" piece, viz, an if-block. We give each high level piece a code number from 0,...,7 (there are 8 high level pieces in EZ). The code for "if-block" is 4, which we see as the first element in the pair. After popping the stack, the new top of the stack reminds us what we were doing before we entered the if-block. table 2 tells us how to fit the "if-block" into that context. After fitting the if-block we still need to go back to step1 to deal with the "ID" that we just read. So this explains briefly the "magic" of the tables.

Now let me warn you by saying that I have disregarded certain subtle details in the above bird's eye view. If you feel interested to learn more about compilers, you may like to consult standard texts on compiler design.

hit counter