Aula 09: Análise Sintática Descendente (LL)
Objetivos
- Entender algoritmos de parsing Top-Down.
- Construir tabelas de parsing LL(1).
Conteúdo
A análise Top-Down tenta construir a árvore da Raiz para as Folhas. Ou seja, ela “adivinha” qual produção usar baseada no token atual.
Parsers Preditivos (LL)
Parsers que não precisam de backtracking. Eles olham o token atual (Lookahead \(k=1\)) e decidem deterministicamente o caminho. - Left-to-right scan (Lê da esquerda pra direita). - Leftmost derivation (Gera a derivação mais à esquerda).
Conjuntos FIRST e FOLLOW
Para construir a tabela de decisão do parser, calculamos dois conjuntos auxiliares para cada não-terminal:
- FIRST(\(\alpha\)): O conjunto de terminais que podem começar a string derivada de \(\alpha\).
- Se eu tenho a regra
A -> c B, entãocestá no FIRST(A).
- Se eu tenho a regra
- FOLLOW(A): O conjunto de terminais que podem aparecer imediatamente após o não-terminal A na derivação.
- É necessário para regras que podem sumir (\(\epsilon\)). Se
A -> \epsilon, o parser só aplica essa regra se o token atual estiver no FOLLOW(A).
- É necessário para regras que podem sumir (\(\epsilon\)). Se
A Tabela de Parsing \(M\)
Uma matriz \(M[A, a]\) onde \(A\) é o não-terminal e \(a\) é o token atual. - Se \(a \in FIRST(\alpha)\), então \(M[A, a] = A \to \alpha\). - Se \(\alpha\) pode ser nulo e \(a \in FOLLOW(A)\), então \(M[A, a] = A \to \epsilon\). - Se uma célula tiver mais de uma regra, a gramática não é LL(1) (tem conflitos).
Referências
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
- Cooper, K., & Torczon, L. (2011). Engineering a Compiler.