Arnab Chakraborty's DFA tutorial: page 7 of 11

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

My Guestbook

Home >

... tutorials >

... ... DFA

Exploring our DFA

In the last page we have seen that the EZ parser is a DFA whose state is represented by a stack. The output set consists of three messages:

Done, Error, OK

and the input set consists of

ID NUM if then endif ) ( + > end EOF

Here ID stands for any variable name (like a,b,x,y). NUM stands for any number. EOF denotes the End-Of-File marker that tells the parser that the entire program has been read in.

Now for the state set, ie stack configurations. For the EZ parser the stack can contain only the numbers 0,...,25. Thus here are some possible stack configurations, ie states:

The "---" denotes the bottom of the stack. Remember that the stack is to be filled with only the numbers 0,...,25. You can repeat each number any number of times.

The configuration


0
---

is the initial state.

The output and state functions

Recall from the definition of DFA that given the current state, s, and the current input, i, we compute the output as f(s,i), and the next state as g(s,i).

For this purpose we have two tables to help us. The first table is of size 26 by 12. We shall call it table 1. The second table is 26 by 8. We shall call it table 2.

Note that each entry of tab1 is of 4 possible types.

Each entry of tab2 is either blank or has a number.

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

Table 2

0 1 2 3 4 5 6 7

Now for the use of the two tables. We shall see later what these tables mean.

There are three steps to using them for computing the f(s,i) and g(s,i). Here s is the current configuration of the stack, and i is the current input.


loop:
Let stackTop = top number in the stack
Let entry1 = table 1 entry at row stackTop, and column i.
If entry1 is D then
   output "Done"
   return
else if entry1 is E then 
   output "Error"
   return
else if entry1 is a single number then
   output "OK" 
   push entry1 onto the stack
   return
else if entry1 is a pair of numbers then
   Let (a,b) = entry
   pop the topmost b elements from the stack
   Let stackTop = top of the stack
   Let entry2 =  table 2 entry at row stackTop and col a.
   //entry2 is guaranteed to be a number
   Push entry2 onto the stack. 
   Go to loop
endif

Examples

Here we shall denote the stack horizontally between [ and ) like this: [0,4,6,7) will mean that the stack contains the numbers 0,4,6,7 with 0 at the bottom and 7 at the top.

Example 1: Suppose that the stack is [0,6) and the input is `='. Here the stackTop is 6. Look up table 1 at row 6 and column `=' to find that entry1 is 8. Since entry1 is a single number we output "OK" and push 8 onto the stack to get [0 6 8).

Example 2: Suppose that in the above example we had input `57' Since `57' is a number we shall consider it as `NUM'. Looking up table 1 at row 6 and column `NUM' we get entry1=E. So we output "Error" (and leave the stack unchanged.)

Exercise: Suppose the current state (ie, the stack) is [0,6,8,12) and the input is `end'. Follow the algorithm to compute the output and the next state.

A few points about the algorithm. The tables are so constructed that you will never have any problem in carrying out what the algorithm demands. In particular,

hit counter