Introduction to Syntax

From Wiki**3

Revision as of 16:12, 3 April 2010 by Root (talk | contribs) (What is a Grammar?)

What is a Grammar?

Uma gramática é um quádruplo , onde é um alfabeto; é o conjunto de símbolos terminais (); é o conjunto de símbolos não terminais; é o símbolo inicial; e é o conjunto de regras (um subconjunto finito de ). As noções de derivação directa), de derivação, e de linguagem gerada são definidas como se segue:

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