Forum Moderators: phranque
Illustrate a simple finite state machine that ensures that each start tag in a data format is matched by a corresponding end tag, assuming that tags of the same kind cannot be nested and that there is only a finite set of possible tags.
does anyone have any idea?
im really stuck
macca
(PS i realise its not a webmaster-related question but im in a real panic!)
Define an array to contain a flag for each type of tag. The flag will tell whether you've encountered a start tag of that type, but not yet found a corresponding end tag.
Then, read though the data. When you see a start tag, set its flag to 1. When you see an end tag, set it to 0.
When you run out of data, all flags must be 0. And if a flag is already 1 when you're trying to set it to 1, that's an error.
I don't know if this is technically a finite state machine, but it's close, and I think it's the most logical way to deal with multiple types of tags.
You could use an FSM for nesting like:
<a> <b> </b> <c> </c> </a>
But I don't think it would work with:
<a> <c> <b> </c> </a> </b>
Either way, a stack or a pushdown list would be more natural.
With an FSM, I reckon you'd have to know what the tags were in advance. With a stack, you could handle arbitrary tags.
The FSM will deal with any kind of nesting. But it won't guarantee correct nesting. You could also change the flags to counters, to allow tags of the same kind to be nested within each other. And if you use an associative array (hash), you could deal with unknown tags.
A stack will guarantee correct nesting, but it won't work if incorrect nesting is acceptable.
Quite right -- thanks for the correction. I shouldn't write these things without enough coffee.
