Etapa 3: Analisador Sintático LL Manual

Published

17/03/2026

Modified

17/03/2026

Objetivos

  • Compreender o funcionamento de um Analisador Sintático Descendente Recursivo (Recursive Descent Parser).
  • Implementar a gramática de expressões respeitando precedência de operadores.
  • Integrar o Parser com a AST, construindo a árvore durante a análise.

Fundamentação Teórica

O Parser verifica se a sequência de tokens está gramaticalmente correta. Na abordagem descendente recursiva, cada Não-Terminal da gramática vira um método no código Java. Exemplo: Para a regra A -> B C, criamos um método parseA() que chama parseB() e depois parseC().

Dicas de implementação (para não se perder)

Você não precisa implementar um “Pascal completo” de uma vez. Comece pequeno e evolua.

Estado do parser: currentToken, advance() e match()

Um parser LL costuma manter um token atual e consumir tokens com um método central, para evitar chamadas “espalhadas” de scanner.nextToken():

  • currentToken: o token que o parser está olhando agora.
  • advance(): consome o token atual e lê o próximo do scanner.
  • match(expectedType): verifica se currentToken.type == expectedType; se sim, chama advance(). Se não, lança SyntaxException.

Precedência e associatividade: por que usamos while

O truque para respeitar precedência é dividir a gramática em níveis (Expression, Term, Factor).

O uso de while em parseExpression() e parseTerm() implementa a associatividade à esquerda, construindo nós como ((a + b) + c) em vez de a + (b + c).

Factor: números, identificadores e parênteses

Uma implementação típica de parseFactor(): - Se o token atual for NUMBER: retorna Literal(...). - Se for IDENTIFIER: retorna Identifier(...). - Se for "(": consome "(", chama parseExpression(), consome ")" e retorna a expressão.

Opcional: tratar - unário (ex.: -x) como UnaryExpression ou como 0 - x.

Comece pelo mínimo obrigatório

Para reduzir complexidade inicial, implemente primeiro: - Atribuição: id := expression ; - Expressões com + - * / e parênteses

Depois disso, adicione if/while/block gradualmente.

Atividades Práticas

1. Gramática de Expressões (Precedência)

Crie um pacote br.com.comcet.tp3. Implemente nele o Parser que utiliza a técnica descendente recursiva. Para garantir que a multiplicação (*) tenha precedência sobre a soma (+), estruturamos a gramática em níveis:

  • Expression: Trata soma e subtração.
  • Term: Trata multiplicação e divisão.
  • Factor: Trata números, identificadores e parênteses.

Pseudocódigo do método parseExpression():

public Expression parseExpression() {
    Expression left = parseTerm(); // Desce um nível
    while (currentToken is '+' or '-') {
        Operator op = currentToken;
        match(op); // Consome o operador
        Expression right = parseTerm();
        left = new BinaryExpression(left, right, op); // Monta o nó
    }
    return left;
}

2. O Método match()

Crie um método auxiliar match(TokenType expected): - Se o token atual for do tipo esperado: consome o token (chama scanner.nextToken()) e retorna. - Se não for: Lança uma SyntaxException (“Esperado X, encontrado Y”).

3. Recuperação de Erros (Panic Mode)

Implemente uma estratégia simples: Quando ocorrer um erro sintático dentro de um comando, o compilador não deve parar imediatamente. - Reporte o erro. - Pule tokens (skip) até encontrar um delimitador de sincronização seguro, como um ponto-e-vírgula (;) ou end. - Retome a análise.

4. Implementação dos Comandos

Implemente métodos para: - parseCommand(): Verifica o próximo token para decidir se é if, while, identificador (atribuição) ou block. - parseAssignment(): Espera id, :=, expression, ;. - parseIf(): Espera if, expression, then, command, opcionalmente else, command.

5. Testes Automatizados (JUnit) — públicos

Nesta etapa, além do teste manual (rodar o parser e imprimir a AST), crie ao menos um teste JUnit público para validar:

  • Integração Scanner (Etapa 2) → Parser (Etapa 3).
  • Construção correta da AST.
  • Precedência de operadores (*// antes de +/-).

Crie, por exemplo, src/test/java/br/com/comcet/tp3/ParserTest.java:

package br.com.comcet.tp3;

import br.com.comcet.tp1.ast.*;
import br.com.comcet.tp2.Scanner;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

public class ParserTest {

    @Test
    void respeitaPrecedenciaMultiplicacao() {
        // Esperado: 10 + (5 * 2)
        String codigo = "x := 10 + 5 * 2;";

        Scanner scanner = new Scanner(codigo);
        Parser parser = new Parser(scanner);

        Command cmd = parser.parseCommand(); // ou parseAssignment(), conforme seu desenho

        assertTrue(cmd instanceof AssignmentCommand);
        AssignmentCommand a = (AssignmentCommand) cmd;

        assertTrue(a.expr() instanceof BinaryExpression);
        BinaryExpression plus = (BinaryExpression) a.expr();
        assertEquals("+", plus.operator());

        assertTrue(plus.left() instanceof Literal);
        assertTrue(plus.right() instanceof BinaryExpression);

        BinaryExpression mult = (BinaryExpression) plus.right();
        assertEquals("*", mult.operator());
    }

    @Test
    void parentesesAlteramPrecedencia() {
        // Esperado: (10 + 5) * 2
        String codigo = "x := (10 + 5) * 2;";

        Scanner scanner = new Scanner(codigo);
        Parser parser = new Parser(scanner);

        Command cmd = parser.parseCommand(); // ou parseAssignment(), conforme seu desenho

        assertTrue(cmd instanceof AssignmentCommand);
        AssignmentCommand a = (AssignmentCommand) cmd;

        assertTrue(a.expr() instanceof BinaryExpression);
        BinaryExpression mult = (BinaryExpression) a.expr();
        assertEquals("*", mult.operator());

        assertTrue(mult.left() instanceof BinaryExpression);
        BinaryExpression plus = (BinaryExpression) mult.left();
        assertEquals("+", plus.operator());
    }
}

Observação: ajuste imports/métodos conforme sua organização. A ideia do teste é sempre a mesma: construir o scanner a partir de uma String, passar para o parser e verificar a estrutura da AST (tipos dos nós e operador na raiz).

O que entregar

  • O código do Parser.
  • Um programa principal que lê um arquivo fonte, faz o parsing e imprime a AST resultante (use printTree() da Etapa 1 para uma saída legível).
  • Pelo menos um teste JUnit público (como acima) cobrindo precedência e integração Scanner→Parser.

Exemplo de Saída da AST para x := 10 + 5;:

Program
  CommandList
    AssignmentCommand (Target: x)
      BinaryExpression (+)
        Literal (10)
        Literal (5)
Back to top