Page 269 -
P. 269
6.3 Syntactic Analysis 257
Figure 6.9 represents the block diagram of a syntactic recogniser, having the
primitive string as input and class labels together with the syntactic derivations
obtained by the parser as outputs. A language L(Gi) represents the set of all strings
corresponding to class wi. For the example in the previous section the languages
would correspond to the sub-grammars producing the derivations for the characters
,y, "R", "F" and "E".
Notice that, when parsing a string, one of the following three situations may
occur:
- The string belongs to only one of the class languages. This is the desirable
situation.
- The string belongs to more than one of the class languages. This is an
ambiguous "borderline" string, reminiscent of feature vectors that lie in a reject
region.
- The string does not belong to any of the class languages. This is also a reject or
a "don't care" situation. For instance, when parsing strings of signal primitives,
we may encounter in the tail of a parsed signal wave a sequence of primitives
that are not parsed, corresponding to a "don't care" situation.
6.3.4 Finite-State Automata
A broad variety of syntactic recognition tasks can be achieved with the simple G3
grammars referred to previously. Fortunately for these grammars the parsing task is
quite simple to implement, using a device known as afinite-state automaton.
We define a finite-state automaton (or finite-state machine) as a quintuple
WT, Q, 6, 90, F):
- Tis a symbol set (corresponding to the set of primitives);
- Q is a set of states of the machine;
- Sis a function mapping from QxT into subsets of Q;
- qo~ Q is the initial machine state;
- F L Q is the set of final states.
A finite-state automaton can be represented as a labelled digraph, known as
state-diagram, with arcs representing state transitions. Let us exemplify this with:
T= {h, u, d}
Q = (S, U+, D+, U-, D-, F) ; go = S
S (S, h)=S; S (S, u)=U+;
8 (U+, h)=S; S(U+, u)=U+;
8(D+, h)=F; 6 (D +, u)=F;
8 (D-, h)=S; 6(D-, u)=U-;
S(U-, h)=F; S(U-, u)=U-;