Revision as of 16:27, 3 April 2010

What is a Grammar?

An unrestricted grammar is a quadruple , where is an alphabet; is the set of terminal symbols (); is the set of non-terminal symbols; is the initial symbol; and is a set of rules (a finite subset of ).

The following are defined:

• Direct derivation:
• Derivation:
• Generated language:

Context-free Grammars

The above grammar is unrestricted in its derivations capabilities and directly supports context-dependent rules.

In our coverage of programming language processing, though, only context-free grammars will be considered. This means that the set is defined on , i.e., only non-terminals are allowed on the left side of a rule.

The FIRST and FOLLOW sets

Computing the FIRST Set

The FIRST set for a given string or symbol can be computed as follows:

1. If a is a terminal symbol, then FIRST(a) = {a}
2. If X is a non-terminal symbol and X -> ε is a production then add ε to FIRST(X)
3. If X is a non-terminal symbol and X -> Y₁...Y_n is a production, then

   a ∈ FIRST(X) if a ∈ FIRST(Y_i) and ε ∈ FIRST(Y_j), i>j (i.e., Y_j ε)

As an example, consider production X -> Y₁...Y_n

• If Y₁ ε then FIRST(X) = FIRST(Y₁)
• If Y₁ ε and Y₂ ε then FIRST(X) = FIRST(Y₁) \ {ε} ∪ FIRST(Y₂)
• If Y_i ε (∀i) then FIRST(X) = ∪_i(FIRST(Y_i)\{ε}) ∪ {ε}

The FIRST set can also be computed for a string Y₁...Y_n much in the same way as in case 3 above.

Computing the FOLLOW Set

The FOLLOW set is computed for non-terminals and indicates the set of terminal symbols that are possible after a given non-terminal. The special symbol $ is used to represent the end of phrase (end of input).

1. If X is the grammar's initial symbol then {$} ⊆ FOLLOW(X)
2. If A -> αXβ is a production, then FIRST(β)\{ε} ⊆ FOLLOW(X)
3. If A -> αX or A -> αXβ (β ε), then FOLLOW(A) ⊆ FOLLOW(X)

The algorithm should be repeated until the FOLLOW set remains unchanged.

Exercises

• Exercise 1 - simple ambiguous grammar.