AULA 10: FORMAS NORMAIS
======================

Notar que na aula passada se utilizassemos a gramatica
  E -> E+T | T
  T -> T*F | F
  F -> (E) | a  para fazer a analise sintatica top-down sempre entrariamos
em loop.

==> podemos fazer modificacoes na gramatica para que problemas como esses 
 nao acontecam (sem mudar a linguagem gerada).

Tipos de modificacoes:
  1) eliminacao de simbolos inuteis -- sua deteccao auxilia na verificacao
se uma gramatica (grande) foi totalmente definida
  2) eliminacao de regras A->epsilon (A e' uma variavel anulavel)
  3) eliminacao de regras em cadeia ou unitarias (A->B)

FORMAS NORMAIS: (Chomsky e Greibach)
  impoe restricoes na forma das producoes permitidas na
  gramatica (sem alterar o poder de expressao).  Colocando uma gramatica
  na forma normal de Greibach, por exemplo, garante que o analisador
  sintatico top-down sempre termine.

0) PRELIMINARES
   ============

LEMA: Seja G=(V, Sigma, P,S) uma gramatica livre de contexto.  Se A=>* w,
entao G'=(V, Sigma, P uniao {A->w}, S) e' equivalente a G.

0) ELIMINACAO DA RECURSAO DO SIMBOLO INICIAL
   ========================================
   se o simbolo inical S aparece do lado direito de alguma producao,
   criar um novo simbolo inicial na gramatica S' e a producao S'->S

1) ELIMINACAO DE REGRAS A->epsilon
   ===============================
  eliminacao de simbolos "anulaveis":  objetivo diminuir o comprimento
  das derivacoes.

     Ex: S -> SaB | aB                 S -> SaB | Sa | aB | a
         B -> bB | epsilon             B -> bB | b

    derivacao da palavra aaaa

Feito em tres passos:
   1) obtencao do conjunto de variaveis anulaveis (N)
        N:= {A | A->epsilon pertence a P}
        repita
          N_ant:= N;
          N:= N uniao { A->w | w em N_ant*}
        ate' que N = N_ant

      Ex: S-> ACA
          A-> aAa | B | C
          B-> bB | b
          C-> cC | epsilon             N:={S,A,C}


   2) elimine todas as regras A->epsilon.  Manter S->epsilon se S pertence
a N

   3) se A->X_1 X_2...X_n entao adicionar todas as producoes
A->alpha_1...alpha_n tal que:
      . se X_i nao pertence a N (nao e' anulavelal) ental alpha_i = X_i
      . se X_i e' anulavel entao alpha_i e' X_i ou epsilon
      . nem todos os alpha_i sao epsilon (ou seja, nao inclua A->epsilon)


   Usando o exemplo:  S'-> S | epsilon
                      S -> ACA | AC | CA | AA | A | C
                      A -> aAa | aa | B | C
                      B -> bB | b
                      C -> cC | c

2) ELIMINACAO DE REGRAS UNITARIAS (regras da forma A->B)
   ==============================

- objetivo: diminuir o tamanho da derivacao

Ex: E->E+T | T
    T->T*F | F
    F->(E) | a

- algoritmo para obter as variaveis B tal que A=>* B somente usando regras
unitarias.

  enc(A):= {A}
  repita
    novos:= {B nao pertencente a enc(A) | C->B para algum C em enc(A)}    
    enc(A):= enc(A) uniao novos
  ate' que novos = vazio

- obtencao de uma gramatica G' equivalente a G=(V,Sigma,P,S) 
sem regras unitarias

  1) eliminar todas as regras unitarias em P
  2) acrescentar as regras
     {A->w | B pertence a enc(A) e B->w pertence a P}


3) ELIMINACAO DE SIMBOLOS INUTEIS:
   ==============================
DEF: Seja G=(V, Sigma, P, S).  Uma variavel X em V e' util sse existem
u,v em (V uniao Sigma)* tal que:
  1) S =>* uXv
  2) existe w em Sigma* tal que uXv =>* w

Ex: P-> AB | a
    B-> b
    C-> c           . A,B,C sao inuteis
                    . P->a e' uma gramatica equivalente

Fazer nesta ordem:

1) Obtencao de uma gramatica G'=(V', Sigma, P', S) equivalente a G tal que
para todo X em V',  X =>* w, w em Sigma*

   - V':= emptyset  /* I contera o novo conjunto de variaveis em G'*/
     repita
        N:= { X em V | X nao esta' em  V' e X->z e z em (V' uniao Sigma)*}
        V':= V' uniao N
     ate' que N = emptyset

   - eliminar todas as producoes que tem variaveis em V-V'

2) Obtencao de uma gramatica G'' equivalente tal que para todo X em V'
S=>* uXv

   - V'':= {S}; 
     repita
       N:= {X em V'| X nao esta' em V'' e Y->uXv para algum Y em N}
       V'':= V'' uniao N
     ate' que N = emptyset

   - eliminar todas as producoes que tem variaveis em V' - V''

Ex: A->ABC | AEF | BD
    B-> B0 | 0
    C-> 0C | EB
    D -> 1D | 1
    E-> BE
    F-> 1F1 | 1

Por que a ordem e' importante?  Qual o resultado da eliminacao de simbolos
inuteis em:  

S->AB | a  
A->a


SEMPRE FAZER NA ORDEM:	
=====================
 0) eliminar recursao do simbolo inicial
 1) eliminar regras A->epsilon
 2) eliminar regras unitarias
 3) eliminar regras inuteis: 3.1) uXv =>* w
                             3.2) S =>* uXv

Ex: S-> (L)
    L-> LE | epsilon
    E-> a | S

Com a aplicacao das transformacoes acima temos o seguinte teorema:

TEOREMA:  Seja G=(V,Sigma,P,S) uma gramatica livre de contexto.  Entao
existe uma gramatica equivalente G' cujas regras sao da forma:
   . S->epsilon se epsilon pertence a L(G)
   . A->a para a em Sigma*
   . A->w para |w| >=2

Com uma gramatica nesta forma, o algoritmo de analise sintatica bottom-up
sempre consegue determinar se uma palavra w, |w| = n, pertence a L(G) com
no maximo 2n-1 reducoes (sao n reducoes de um terminal a para A e como 
cada regra da forma A->w reduz o tamanho da forma sentencial de 1, portanto, 
temos n-1 reducoes ate' chegar ao simbolo inicial).

FORMA NORMAL DE CHOMSKY
=======================
Def: uma GLC G=(V,Sigma,P,S) esta' na forma normal de Chomsky se todas as
producoes sao da forma:
  . S->epsilon se epsilon pertence a L(G)
  . A->a para a em Sigma
  . A->BC para B,C em V

Depois das transformacoes ja' apresentadas, para transformar uma gramatica
na forma normal de Chomsky basta colocar as producoes da forma A->w tal
que |w|>=2 na forma A->BC.  Para isso, fazer:

1) modificar cada regra A->w, |w|>=2, para que w contenha apenas nao
terminais: para cada terminal a em w.  Criar uma regra Y->a, onde Y e'
uma nova variavel e substituir as ocorrencias de a por Y em w.

2) criar regras de tamanho 2:  substituir cada regra A->Y1 Y2... Yn, n>=3
pelo conjunto das regras: A->Y1 Z1, Z1-> Y2 Z2,... Z_{n-2}-> Y_{n-1} Yn

Exemplo:  S->(L) | ()
          L->LE | a | (L) | ()
          E->a | (L) | ()

Exemplo: S -> bA | aB
         A -> bAA | aS | a
         B -> aBB | bS | b

ELIMINACAO DE RECURSAO A ESQUERDA
=================================

lembrar do exemplo E->E+T|T.... para o analisador top-down.

Ideia:  transformar recursao a esquerda em recursao a direita
          A-> AB | a 
          B-> bB | b

        A=>AB=>ABB=>ABBB=>ABBBB=>....=>ABB...BB => aBB...BB
 
          A -> a | aB'
          B'-> B | BB'
          B -> bB | b

        A=>aB'=>aBB'=>aBBB'=>aBBBB'=>......=>aBB...BB'=> aBB...BB


Seja uma GLC G=(V,Sigma,P,S) e A->A alpha_1 | A alpha_2 |...| A alpha_r
o conjunto de producoes de A nas quais o simbolo mais a esquerda e' A.
Seja A-> beta_1 | beta_2 |...| beta_s as demais producoes de A.  A
gramatica G'=(V uniao {B}, Sigma, P',S) e' equivalente a G, onde P'
substitui todas as producoes de A por:
   A-> beta_i | beta_i B  para todo i, 1 <= i <= s
   B-> alpha_i | alpha_i B  para todo i, 1 <= i <= r

Ex:  E->E+T | T
     T->T*F | F
     F-> (E) | a

FORMA NORMAL DE GREIBACH
========================
DEF:  Uma GLC G=(V,Sigma,P,S) esta' na forma normal de Greibach se todos
as producoes estao na forma:
  . S->epsilon se epsilon pertence a L(G)
  . A->aX, onde a pertence a Sigma e X pertence a V*

Metodo:

0) eliminar recursao do simbolo inicial
   eliminar regras A->epsilon
   eliminar regras unitarias
   eliminar regras inuteis

1) em toda producao A->w tal que |w|>1, substituir cada terminal a em w
a partir do segundo simbolo por um novo nao terminal Y.  Acrescentar a producao
Y->a 

2) numerar as variaveis de forma aleatoria, porem S deve receber o numero 1.

Fazer os passos 3 e 4 ate' nao poder mais:

3) se existe uma regra A->By, B e' um nao terminal, |y|>=1, tal que o
numero  de B e' menor que o de A, substitui-se 
A->By por {A->wy | B->w pertence a P}

4) eliminar recursao a esquerda
   terminado este processo, as producoes da variavel de maior numero An sao
   da forma An->aw, onde a pertence a Sigma e w pertence a V*

5) para todo i=n ate' 2 decrescentemente
     se A_{n-1} -> A_n w, substituir por {A_{n-1}->yw | A_n -> y pertence a P}

6) fazer a substituicao nas novas variaveis introduzidas no passo 4.
EX: A->CB
    B->BBD | b
    C->BBC | Dc
    D->AD | d

o passo 0 ja' foi feito (eliminacao de regras epsilon, unitarias, etc)

CONSEQUENCIA: a analise sintatica top-down usando uma gramatica na forma
============= normal de Greibach sempre termina e a derivacao de uma 
palavra de tamanho n tem n passos (cada passo da derivacao cria um terminal).