Exercício 08.34

Converta para a Forma Normal de Greibach a gramática:

G = ({E, T, F}, {a, +, *, (, )}, P, E)
P = {< E >  ->  < E > + < T >
            |   < T > * < F >
            |   ( < E > )
            |   a
     < T >  ->  < T > * < F >
            |   ( < E > )
            |   a
     < F >  ->  ( < E > )
            |   a }

Resposta

1. Simplificação da gramática livre do contexto

A gramática livre do contexto já está simplificada.

G = ({E, T, F}, {a, +, *, (, )}, P, E)
P = {< E >  ->  < E > + < T >
            |   < T > * < F >
            |   ( < E > )
            |   a
     < T >  ->  < T > * < F >
            |   ( < E > )
            |   a
     < F >  ->  ( < E > )
            |   a }

2. Renomeação das variáveis em uma ordem crescente qualquer

G = ({A, B, C}, {a, +, *, (, )}, P, A)
P = {< A >  ->  < A > + < B >
            |   < B > * < C >
            |   ( < A > )
            |   a
     < B >  ->  < B > * < C >
            |   ( < A > )
            |   a
     < C >  ->  ( < A > )
            |   a }

3. Transformação de produções para a forma < Ar > -> < As > α, onde r ≤ s

G = ({A, B, C}, {a, +, *, (, )}, P, A)
P = {< A >  ->  < A > + < B >
            |   < B > * < C >
            |   ( < A > )
            |   a
     < B >  ->  < B > * < C >
            |   ( < A > )
            |   a
     < C >  ->  ( < A > )
            |   a }

4. Exclusão das recursões da forma < Ar > -> < Ar > α

G = ({A, A₁, B, B₁, C}, {a, +, *, (, )}, P, A)
P = {< A >  ->  < B > * < C > < A₁ >
            |   ( < A > ) < A₁ >
            |   a < A₁ >
            |   < B > * < C >
            |   ( < A > )
            |   a
     < A₁ > ->  + < B > < A₁ >
            |   + < B >
     < B >  ->  ( < A > ) < B₁ >
            |   a < B₁ >
            |   ( < A > )
            |   a
     < B₁ > ->  * < C > < B₁ >
            |   * < C >
     < C >  ->  ( < A > )
            |   a }

5. Um terminal no início do lado direito de cada produção

G = ({A, A₁, B, B₁, C}, {a, +, *, (, )}, P, A)
P = {< A >  ->  ( < A > ) < B₁ > * < C > < A₁ >
            |   a < B₁ > * < C > < A₁ >
            |   ( < A > ) * < C > < A₁ >
            |   a * < C > < A₁ >
            |   ( < A > ) < A₁ >
            |   a < A₁ >
            |   ( < A > ) < B₁ > * < C >
            |   a < B₁ > * < C >
            |   ( < A > ) * < C >
            |   a * < C >
            |   ( < A > )
            |   a
     < A₁ > ->  + < B > < A₁ >
            |   + < B >
     < B >  ->  ( < A > ) < B₁ >
            |   a < B₁ >
            |   ( < A > )
            |   a
     < B₁ > ->  * < C > < B₁ >
            |   * < C >
     < C >  ->  ( < A > )
            |   a }

6. Produções da forma < Ar > -> a α onde α é composto por variáveis

G = ({A, A₁, B, B₁, C, X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇, Y₀, Y₁, Y₂, Y₃, Y₄, Y₅, Y₆, Y₇, Y₈}, {a, +, *, (, )}, P, A)
P = {< A >  ->  ( < A > < Y₀ > < B₁ > < X₀ > < C > < A₁ >
            |   a < B₁ > < X₁ > < C > < A₁ >
            |   ( < A > < Y₁ > < X₂ > < C > < A₁ >
            |   a < X₃ > < C > < A₁ >
            |   ( < A > < Y₂ > < A₁ >
            |   a < A₁ >
            |   ( < A > < Y₃ > < B₁ > < X₄ > < C >
            |   a < B₁ > < X₅ > < C >
            |   ( < A > < Y₄ > < X₆ > < C >
            |   a < X₇ > < C >
            |   ( < A > < Y₅ >
            |   a
     < A₁ > ->  + < B > < A₁ >
            |   + < B >
     < B >  ->  ( < A > < Y₆ > < B₁ >
            |   a < B₁ >
            |   ( < A > < Y₇ >
            |   a
     < B₁ > ->  * < C > < B₁ >
            |   * < C >
     < C >  ->  ( < A > < Y₈ >
            |   a
     < X₀ > ->  *
     < X₁ > ->  *
     < X₂ > ->  *
     < X₃ > ->  *
     < X₄ > ->  *
     < X₅ > ->  *
     < X₆ > ->  *
     < X₇ > ->  *
     < Y₀ > ->  )
     < Y₁ > ->  )
     < Y₂ > ->  )
     < Y₃ > ->  )
     < Y₄ > ->  )
     < Y₅ > ->  )
     < Y₆ > ->  )
     < Y₇ > ->  )
     < Y₈ > ->  ) }

Recomendamos

Agenda TI Vida de Programador Duolingo