Estratégias de Análise Sintática Top-Down e LL(1)

Estratégia de Desenvolvimento: Top-Down (Descendente)

Objetivo: Encontrar uma derivação mais à esquerda para uma cadeia de entrada, construindo a árvore gramatical a partir da raiz, criando os nós em pré-ordem (busca em profundidade).

Implementação

• Consiste em um conjunto de procedimentos, um para cada não-terminal da gramática;
• A execução começa com a ativação do procedimento referente ao símbolo inicial;
• O procedimento retorna sucesso se toda a cadeia de entrada puder ser derivada;
• As produções são escolhidas de modo arbitrário.

Problemas

• Uma gramática recursiva à esquerda pode levar o analisador a um laço infinito;
• O retrocesso (backtracking) causa repetição na leitura da entrada, custando tempo e dificultando a identificação de erros.

Solução

• Tratar a gramática para que identifique univocamente qual produção deve ser expandida.

Gramáticas LL(1)

São gramáticas cuja tabela sintática não possui entradas múltiplas. Elas não são ambíguas nem recursivas à esquerda.

Analisador Sintático Preditivo LL(1)

• Ideia: Evitar o retrocesso fazendo com que o token identifique exatamente qual produção aplicar na expansão de um não-terminal;
• O autômato de pilha é controlado por uma tabela de análise;
• Utiliza lookahead (1 símbolo) através das funções First e Follow;
• Requisitos:
  • A gramática não deve ser recursiva à esquerda;
  • Deve ser fatorada à esquerda;
  • Não-terminais com múltiplas produções devem ter os primeiros terminais deriváveis identificados univocamente.

Funções First e Follow

Funções que auxiliam na construção de analisadores sintáticos descendentes e ascendentes. O objetivo é inferir, a partir da estrutura gramatical, a relação entre símbolos terminais e não-terminais.

• FIRST: Conjunto de símbolos terminais que iniciam uma forma sentencial. Define quando qualquer produção pode ser usada.
• FOLLOW: Conjunto de símbolos terminais que podem aparecer após um símbolo não-terminal em alguma forma sentencial. Define quando uma produção do tipo A ::= ε deve ser usada.