The scanner part of any program that processes a language is probably
a DFA.
There are three main methods to code DFAs. Two use an explicit
variable to represent state in this fashion:
int state = INITIAL_STATE;
while (!is_accepting_state(state)) {
char ch = get_next_char();
state = transition(ch, state);
if (state == ERROR_STATE) {
take_error_action();
break;
}
}
Now this is pseudocode. The question is how to implement
transition(char ch, int state);
Simplest way is with tables
int transition[256][N_STATES];
boolean is_accepting[N_STATES];
The is_accepting[] array is normally fine. But the 2d array
transition gets big quickly, especially if the number of possible
input "characters" is high. So there are various "table compression
schemes". Run length encoding of table rows is a common method.
The other way to encode is nested switch statements.
Finally - and you see this less often but it often results in the
fastest DFAs:
You use "goto" and use labels to represent state implicitly. For
example, here is a simple DFA that recognizes floating point numbers.
There are 4 possible input characters: '-', D, '.', '*' where D
stands for a digit and * stands for any char that is not -,D, or .
State 0 is the initial state:
current '-' D '.' *
0 1 2 3 err
1 err 2 3 err
2 err 2 3 accept
3 err 4 err accept
4 err 4 err accept
Code this with goto logic as follows:
state0:
switch (get_next_char()) {
case '-': goto state1;
case '0'...'9': goto state2;
case '.': goto state3;
default: goto err;
}
state1:
switch (get_next_char()) {
}
state2:
switch (get_next_char()) {
}
state3:
switch (get_next_char()) {
}
state4:
switch (get_next_char()) {
}
accept:
// accept action goes here
return;
err:
// error action goes here
return;
Of course there are many variations on these 3, but the principles
stay the same.
On Apr 6, 1:39 pm, Doom <[email protected]> wrote:
> Any pointers to a code using NFA / DFA computation model?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
