Sentential Forms, And Parse Tree

Sentential Forms:

For a grammar G, with start symbol S, any string a such that
S?* a is called a sentential form.
Let G = (V, T, P, S) be a CFG, and ? ? (V U T)*. If S?(??* )? then ? is a sentential form.

A sentential form that can be obtained by a rightmost derivation from the start symbol is a right-sentential form of the grammar (and similarly with leftmost derivations)

If S?(??rm )? then ? is a left-sentential form, and if S?(??rm )? then ? is a right-sentential form.
Note: L(G) is those sentential forms that are in T*.

Example 5: Recall G1:
E ? I | E + E | E * E | (E)
I ? a | b | Ia | Ib | I0 | I1

1? Then E * (I + E) is a sentential form since
E ?E * E ? E * (E) ? E * (E + E) ? E*(I + E)
This derivation is neither leftmost, nor right-most.
2? a * E left-sentential form, since

E ? E * E ? I * E ?a * E
3? E * (E + E) is a right-sentential form since
E ? E *E ? E * (E) ?E * (E + E)


4. Parse Trees.:

Graphical representations of derivations. The leaves of a parse tree for a fully filled out tree is a sentence.
Every derivation can be represented by a parse tree. The tree shows the symbols of a terminal string are grouped into substrings, each of which belongs to the language of one of the variables of the grammar.