Page 265 -

6.3 Syntactic Analysis 253

Since we were able to reach the starting symbol, we have confirmed that x
belongs to L generated by P, i.e., the grammar G recognizes x, or x E L(G).
Let us now consider the pattern string y = hhuudh. It is easy to see that y does
not belong to L(G), since no parsing is possible in this case. We see, therefore, that
the task of determining whether or not a pattern belongs to a given class is reduced
to seeing whether or not it can be parsed with the grammar rules. The reader may
find it interesting to change the rule set P in order to recognize string y, and other
strings as well.
Let us now modify the rules of Pt and P- as follows:

Consider the string x = udud. It can de derived in two ways:
S H P'S H udS H udPt t+ udud .
S H P+ H uSd H UP-d H udud .

When a grammar admits more than one derivation for the same string we call it
an ambiguous grammar. In general, there is a different semantic value for each
derivation. In the present example, we may interpret udud as a sequence of two
positive peaks or as a positive peak with a negative peak in the middle.
String grammars can be generalized to apply to more complex structures such as
trees and graphs.

6.3.2 Picture Description Language

Grammar strings that use concatenation as the only operation have a limited
representational capability, namely when relations among two-dimensional or
three-dimensional objects have to be represented. One way to cope with this
limitation is to use higher dimensional grammars such as tree or graph grammars.
This approach has met limited success in practical applications, given the inherent
difficulty of dealing with such grammars, namely in what concerns the building of
efficient parsers. Another way is to incorporate operations that are more complex
than concatenation into the grammar. This is the approach of the picture
description language, PDL, which provides an adequate representation of two-
dimensional patterns.
In PDL each primitive has two attaching points, tail and head, where it can be
linked to other primitives. The set of terminals includes four binary operators and
one unary operator that can be used to join primitives as shown in Table 6.1.