is an s-grammar. The grammar
is not an s-grammar because the pair (S, a) occurs in the two productions S → aS
and S → aSS.
While s-grammars are quite restrictive, they are of some interest. As we will
see in the next section, many features of common programming languages can
be described by s-grammars.
If G is an s-grammar, then any string w in L(G) can be parsed with an effort
proportional to |w|. To see this, look at the exhaustive search method and the
string w = a 1 a 2 …a n . Since there can be at most one rule with S on the left, and
starting with a 1 on the right, the derivation must begin with
Next, we substitute for the variable A 1 , but since again there is at most one
choice, we must have
We see from this that each step produces one terminal symbol and hence the
whole process must be completed in no more than |w| steps.
Ambiguity in Grammars and Languages
On the basis of our argument we can claim that given any w ∈ L(G), exhaustive
search parsing will produce a derivation tree for w. We say “a” derivation tree
rather than “the” derivation tree because of the possibility that a number of
different derivation trees may exist. This situation is referred to as ambiguity.
Definition 5.5
A context-free grammar G is said to be ambiguous if there exists some w ∈
L(G) that has at least two distinct derivation trees. Alternatively, ambiguity
implies the existence of two or more leftmost or rightmost derivations.
is not an s-grammar because the pair (S, a) occurs in the two productions S → aS
and S → aSS.
While s-grammars are quite restrictive, they are of some interest. As we will
see in the next section, many features of common programming languages can
be described by s-grammars.
If G is an s-grammar, then any string w in L(G) can be parsed with an effort
proportional to |w|. To see this, look at the exhaustive search method and the
string w = a 1 a 2 …a n . Since there can be at most one rule with S on the left, and
starting with a 1 on the right, the derivation must begin with
Next, we substitute for the variable A 1 , but since again there is at most one
choice, we must have
We see from this that each step produces one terminal symbol and hence the
whole process must be completed in no more than |w| steps.
Ambiguity in Grammars and Languages
On the basis of our argument we can claim that given any w ∈ L(G), exhaustive
search parsing will produce a derivation tree for w. We say “a” derivation tree
rather than “the” derivation tree because of the possibility that a number of
different derivation trees may exist. This situation is referred to as ambiguity.
Definition 5.5
A context-free grammar G is said to be ambiguous if there exists some w ∈
L(G) that has at least two distinct derivation trees. Alternatively, ambiguity
implies the existence of two or more leftmost or rightmost derivations.