 |
www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com |
|
|
|
Push-Down Automaton (PDA)
A Push-Down Automaton or PDA is a useful type of finite state automaton, that has a really huge number of states. The state of a PDA is a stack containing integers.
PDAs are widely used in
compilers. Indeed, any compiler for C, Fortran, Java,
Pascal etc that you see, is driven by a PDA. While you may be familiar
with one or more of these high level languages, it is less likely that
you have ever peeped into the innards of their compilers. So first
let me tell you a little bit about how a compiler
works. For this purpose we shall use a language called EZ, that has
been designed just to explain the basic ideas.
EZ: an easy language
Here is a very small EZ program:
a = 5
b = a + 4
end
This program, just like any other valid EZ program, consists of a list of
statements and ends with the keyword end. To keep our
life simple, the only arithmetic
operation that it understands is +. It also has
parantheses so that you can write expressions like
(a+4)+2.
Here is a more complex EZ program that uses if-then constructs:
a = 0
if(a > 5) then
b = a + 8
c = b
endif
a = b+c
end
The reader should not have any problem in understanding this. Just keep in
mind that EZ does not allow any "else" clause (to keep the compiler
simple). If's can be nested freely, eg:
if(a>5) then
if(b>6) then
c=0
endif
if(b>9) then
c=9
endif
endif
end
Also, EZ allows only one logical operator, viz, >.
EZ syntax checking
Now imagine that when you type an EZ program, you have made some syntax
error, eg forgotten to write end at the end, or have not
matched parantheses properly, etc etc. An EZ compiler must be able to
detect any such syntax errors. A full-fledged compiler needs to do
other things also (eg, writing machine code) but here we focus our
attention on just the syntax checking aspect. Below we provide an interactive syntax checker for EZ that shows how the DFA works.
Playing with the syntax checker
The large textbox is where the input (ie, the program to be checked) is to be typed.
Paste a simple EZ program in it (or use the program already present there) and hit "Start". This wakes up the DFA.
The state of the DFA is a stack, and is shown to the left. We shall explain in the next page what this stack means.
Next hit "Input". This causes the DFA to read the first input. The input currently read is enclosed inside [...] in the program textbox, and also shown in the input textfield.
Now that we have both the state and the input ready, we proceed to compute the output. This we do by hitting "Output". Our DFA has only three possible outputs:
Done (ie, the program is syntactically correct), OK (ie, the syntax checking is not yet over, but so far it looks fine),
Error (ie, the syntax checker has detected some syntax error).
Next hit "State" to compute the next state. This causes the stack to change.
Go on repeating the "input"-"Output"-"State" cycle until you get "Error" or "Done" as output.
In the next page we shall explain how the output and next state are computed.
|
