AULA Nº 6

(Download da Aula)
<< anterior próxima >>
menu de aulas dúvidas
 

Analisador Sintático

 Características

Constrói a árvore sintática;

Reconhece a forma (sintaxe) das cadeias de entrada;

 

Problema de Análise Sintática

Dados G = (VN , VT , S , P)

x = t1 t2 ... tn Î L(G)

O Analisador Sintático que reconhece x, segundo a gramática G, deve ter as seguintes características:

  1. Ler x da esquerda para a direita sem reler partes já lidas;
  2. O reconhecimento deve ser canônico (exatamente contrário ao da geração canônica);
  3. Qualquer subcadeia t da constituída de 2 partes

xe xd t = t e xd

O analisador sintático decide Quando o símbolo mais à esquerda de xd deve ser lido (chamada ao analisador léxico). Nesse caso não deve ( ou não pode) ser feito nenhum reconhecimento dos símbolos de t e .

 Problema central do Analisador Sintático

 

Decidir qual subcadeia de uma forma sentencial deve ser reconhecida como o lado direito de uma produção da gramática, fazendo a substituição desse lado direito pelo NT do lado esquerdo.

 

Exemplo: G5
 
  1. E ® T | E + T | E - T
  2. T ® F | T * F | T / F
  3. F ® i | F ** i

Análise da cadeia i + i * i

 

1 ª tentativa de reconhecimento:
 

 

Obs.: Não há produção de G5 onde o lado direito seja
 

E * i

E * F

E * T

E * E
 

2 ª tentativa de reconhecimento
 

 Dificuldades que o Analisador Sintático enfrenta

 

Passos com mais do que uma possibilidade de reconhecimento;

 

Evitar algumas substituições mais à esquerda no reconhecimento;

 Reconhecimento Canônico

 

Reconhece sempre as subcadeias mais à esquerda levando ao símbolo inicial (contrário da geração canônica)