productions is of the form A → v, with |v| = k > 1. Show that the derivation
tree for any w ∈ L(G) has a height h such that
5.2 Parsing and Ambiguity
We have so far concentrated on the generative aspects of grammars. Given a
grammar G, we studied the set of strings that can be derived using G. In cases of
practical applications, we are also concerned with the analytical side of the
grammar: Given a string w of terminals, we want to know whether or not w is in
L(G). If so, we may want to find a derivation of w. An algorithm that can tell us
whether w is in L(G) is a membership algorithm. The term parsing describes
finding a sequence of productions by which a w ∈ L(G) is derived.
Parsing and Membership
Given a string w in L(G), we can parse it in a rather obvious fashion: We
systematically construct all possible (say, leftmost) derivations and see whether
any of them match w. Specifically, we start at round one by looking at all
productions of the form
S → x,
finding all x that can be derived from S in one step. If none of these results in a
match with w, we go to the next round, in which we apply all applicable
productions to the leftmost variable of every x. This gives us a set of sentential
forms, some of them possibly leading to w. On each subsequent round, we again
take all leftmost variables and apply all possible productions. It may be that
some of these sentential forms can be rejected on the grounds that w can never
be derived from them, but in general, we will have on each round a set of
possible sentential forms. After the first round, we have sentential forms that can
be derived by applying a single production, after the second round we have the
sentential forms that can be derived in two steps, and so on. If w ∈ L(G), then it
must have a leftmost derivation of finite length. Thus, the method will eventually
give a leftmost derivation of w.
For reference below, we will call this exhaustive search parsing or brute
tree for any w ∈ L(G) has a height h such that
5.2 Parsing and Ambiguity
We have so far concentrated on the generative aspects of grammars. Given a
grammar G, we studied the set of strings that can be derived using G. In cases of
practical applications, we are also concerned with the analytical side of the
grammar: Given a string w of terminals, we want to know whether or not w is in
L(G). If so, we may want to find a derivation of w. An algorithm that can tell us
whether w is in L(G) is a membership algorithm. The term parsing describes
finding a sequence of productions by which a w ∈ L(G) is derived.
Parsing and Membership
Given a string w in L(G), we can parse it in a rather obvious fashion: We
systematically construct all possible (say, leftmost) derivations and see whether
any of them match w. Specifically, we start at round one by looking at all
productions of the form
S → x,
finding all x that can be derived from S in one step. If none of these results in a
match with w, we go to the next round, in which we apply all applicable
productions to the leftmost variable of every x. This gives us a set of sentential
forms, some of them possibly leading to w. On each subsequent round, we again
take all leftmost variables and apply all possible productions. It may be that
some of these sentential forms can be rejected on the grounds that w can never
be derived from them, but in general, we will have on each round a set of
possible sentential forms. After the first round, we have sentential forms that can
be derived by applying a single production, after the second round we have the
sentential forms that can be derived in two steps, and so on. If w ∈ L(G), then it
must have a leftmost derivation of finite length. Thus, the method will eventually
give a leftmost derivation of w.
For reference below, we will call this exhaustive search parsing or brute