| - Up - | Next >> |
In the previous chapter, we learned that finite state recognizers are machines that tell us whether a given input is accepted by some finite state automaton. We can give a word to a recognizer and the recognizer will say ``yes'' or ``no''. But often that's not enough: in addition to knowing that something is accepted by a certain FSA, we would like to have an explanation of why it was accepted. A finite state parser gives us that kind of explanation by returning the sequence of transitions that was made.
This distinction between recognizer s and parser s is a standard one: Recognizers just say ``yes'' or ``no'' while parsers also give an analysis of the input. It does not only apply to finite state machines, but also to all kinds of machines that check whether some input belongs to a language, and we will make use of it throughout the course.
| - Up - | Next >> |