AULA 9: ANALISE SINTATICA
=========================

Objetivo: verificar se uma dada palavra faz parte da linguagem.
     Ex: programa Pascal sintaticamente correto

DEF: Derivacao mais a esquerda: e' o processo de derivacao com "expansao" 
  do nao terminal mais a esquerda da forma sentencial.

Teorema: seja G=(V, Sigma, P, S) uma gramatica.  Uma palavra w em Sigma*
  pertence a L(G) sse existir uma derivacao mais a esquerda de w a partir de
  S. 

  Prova: intuitivamente, isto e' verdadeiro porque a gramatica e' livre de
contexto e, portanto, a ordem da "expansao" dos nao terminais nao e'
importante. 

  ==> note que nem toda forma sentencial pode ser obtida por uma derivacao
mais a esquerda.  Ex:  S->AB  A->aA | epsilon  B->bB | epsilon
Obter S => A

  Consequencia do teorema:  para verificar se uma palavra w pertence a L(G)
basta verificar se existe uma derivacao mais a esquerda.

DEF:  uma gramatica G e' ambigua se existe uma palavra w em L(G) que pode
ser obtida por 2 derivacoes mais a esquerda.  
   OU
uma gramatica G e' ambigua se existe uma palavra w em L(G) com 2 arvores de
derivacao distintas.

Ex:  E-> E+E | E*E | (E) | a   e' ambigua

     E-> E + T | T
     T-> T * F | F
     F-> (E) | a               nao e' ambigua

     Como derivar   a+a*a ?

===> ambiguidade e' uma caracteristica da gramatica e nao da linguagem, 
embora existam linguagens inerentemente ambiguas, ou seja, que nao existe
uma gramatica nao ambigua que a gere.
   Ex: {a^n b^n c^m d^m | n, m >= 0} union {a^n b^m c^m d^n | n, m >= 0}
       intuitivamente, as palavras da forma a^n b^n c^n d^n podem ser
       obtidas tanto de uma forma como de outra.
   Ex: {a^n b^m c^k | n = m ou m = k}

Tirar a ambiguidade de uma gramatica e' muito importante, por exemplo
para a construcao de um compilador.  Vamos ver diversas formas de modificar
a gramatica de uma linguagem (formas normais).  Porem,
o problema de determinar se uma gramatica ou ambigua ou nao e' indecidivel.

Dois tipos de analisadores sintaticos a partir de uma GLC: bottom-up e
top-down.
  . bottom-up: gera derivacao mais a direita (reverso)
  . top-down:  gera derivacao mais a esquerda

Lembrar que o que sera' visto em sala de aula e' um resumo do que e'
tratado no livro -- o material sera' visto com mais detalhe na materia
de construcao de compiladores.

Exemplo: derivacao de a+a*a  usando E ->  T | TE'
                                    E'-> +T | +TE'
                                    T ->  F | FT'
                                    T'-> *F | *FT'
                                    F -> (E)| a

   top-down:  E=> T => F => (E)
                         => a
                    => FT' => (E)T'
                           => aT' => a*F 
                                  => a*FT'
               => TE' => FE'=> (E)E'
                            => aE'=> a+T => a+F => a+(E)
                                                => a+a
                                         => a+FT' => a+(E)T'
                                                  => a+aT'=>a+a*F=>a+a*(E)
                                                                 =>a+a*a

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

   bottom-up:                                                        ******   
a+a*a <= F.+a*a <= T.+a*a <= E.+a*a <= E+.a*a <= E+a.*a <= E+F.*a <= E+T.*a
      <= E+E.*a <= E+E*.a <= E+E*a. <= E+E*F <= E+E*T <= E+E*E       ******  

backtrack to E+T.*a <= E+T*.a <= E+T*a. <= E+T*F <= E+T <= E

===> olhar a derivacao resultante de tras para a frente ==> derivacao mais a
     direita que gera a palavra