Difference between revisions of "Introduction to Syntax"

From Wiki**3

(Exercises)
Line 33: Line 33:
 
= Exercises =
 
= Exercises =
  
* [[Introduction to Syntax/Exercise 1|Exercise 1]]
+
* [[Introduction to Syntax/Exercise 1|Exercise 1]] - simple ambiguous grammar.
  
 
[[category:Teaching]]
 
[[category:Teaching]]
 
[[category:Compilers]]
 
[[category:Compilers]]

Revision as of 15:46, 3 April 2010

What is a Grammar?

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 -> Y1...Yn is a production, then
    a ∈ FIRST(X) if a ∈ FIRST(Yi) and ε ∈ FIRST(Yj), i>j (i.e., Yj ε)

As an example, consider production X -> Y1...Yn

  • If Y1 ε then FIRST(X) = FIRST(Y1)
  • If Y1 ε and Y2 ε then FIRST(X) = FIRST(Y1) \ {ε} ∪ FIRST(Y2)
  • If Yi ε (∀i) then FIRST(X) = ∪i(FIRST(Yi)\{ε}) ∪ {ε}

The FIRST set can also be computed for a string Y1...Yn 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