Page 267 -

6.3 Syntactic Analysis 255

Figure 6.8. Primitives for character description using picture description language.

String grammars are easily generalized to PDL descriptions. We will show this
by presenting the string grammar that describes the characters "Po, "R", "F" and
"E":

G= (T, N, P,S};
T= {v, h, d, h, -, +, -, (, 11;
N = {S, P, R, F, E, LEFTCORNER ) ;
P={SH(PIRJFIE), R H~+P, PH b+(-v),
LEFTCORNER H v - (-h), F I+ LEFTCORNER + LEFTCORNER
E H(-h)+F).

Shape descriptions can also be generated using other types of features, namely
line segments derived by chain coding, as explained in section 6.1.2. A variant of
this method, using appropriate concatenation rules, is described in the work of
Nishida (1996) and applied to structural analysis of curve deformation.

6.3.3 Grammar Types

The string grammar defined in section 6.3.1 states the production rules in the most
general way, constituting what is called an unrestricted grammar. By imposing
restrictions on the production rules of this grammar, it is possible to define other
types of grammars, as listed in Table 6.2.

Table 6.2. Chomsky's hierarchy of grammar types.

Type Name Production rules

GO Unrestricted a~ ,f?, with a€ V+, PE T/+ u{k}
GI Context-sensitive H P, with a, P E V+ and la1 < 101

G2 Context-free a~ P, with a€ N, PE V+
G3 Regular a~a,6lalA, with FEN, ~ E T