Análise Sintática

A análise sintática decide se a cadeia de tokens deriva do símbolo inicial S de uma gramática livre de contexto G = (V, Σ, R, S). Se a derivação existe, o objeto é a árvore: nós internos são não-terminais, as folhas da esquerda para a direita são a sentença.

FIRST, FOLLOW, itens LR e a recuperação neste tópico — e verificação de tipos e as representações intermediárias nos seguintes — partem dessa derivação.

As páginas se agrupam em quatro blocos. O primeiro monta a quádrupla, registra a derivação e decide se a mesma cadeia admite duas árvores.

O segundo constrói a árvore da raiz para as folhas: calcula FIRST(α) e FOLLOW(A), preenche M[A, a] e reescreve fatoração ou recursão à esquerda quando duas produções colidem.

O terceiro constrói das folhas para a raiz: fecha itens A → α • β, escolhe empilhar ou reduzir, e distingue SLR(1) de LR(1) pelo símbolo à frente na redução.

O quarto retoma a análise quando não há movimento legal: descarta até um token de sincronização, ou insere, apaga ou substitui um token.

Duas árvores para a mesma cadeia estão em Gramáticas Livres de Contexto. Duas ações na mesma célula — empilhar/reduzir ou reduzir/reduzir — estão em Análise Ascendente.

Expandir o não-terminal mais à esquerda está em Análise Descendente. Reduzir o trecho no topo da pilha, desfazendo a derivação mais à direita, está em Análise Ascendente.

Célula M[A, a] vazia ou estado LR sem ação só marca o desvio. Descartar até o token de sincronização, ou inserir, apagar ou trocar um token, está em Tratamento de Erros Sintáticos.