✅ Condição LL(1)
Uma gramática é LL(1) se podemos construir um parser preditivo que toma decisões corretas olhando apenas um token à frente. A condição formal é:
📐 Condição LL(1)
Para cada par de produções A \rightarrow \alpha \mid \beta:
- \text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \varnothing
- Se \varepsilon \in \text{FIRST}(\alpha), então \text{FIRST}(\beta) \cap \text{FOLLOW}(A) = \varnothing
- Se \varepsilon \in \text{FIRST}(\beta), então \text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \varnothing
Intuitivamente, estas condições garantem que o parser pode sempre decidir qual produção aplicar baseando-se apenas no próximo token de entrada.
Se uma gramática satisfaz a condição LL(1), podemos construir uma tabela de parsing que mapeia (não-terminal, terminal) para a produção correta a aplicar. Esta tabela permite parsing linear em tempo proporcional ao tamanho da entrada!
Verificação de LL(1)
Vamos verificar se nossa gramática de expressões é LL(1):
Para E' \rightarrow + T E' \mid \varepsilon:
- \text{FIRST}(+ T E') = \{+\}
- \text{FIRST}(\varepsilon) = \{\varepsilon\}
- Satisfaz condição 1: \{+\} \cap \{\varepsilon\} = \varnothing ✓
- Satisfaz condição 2: \{+\} \cap \text{FOLLOW}(E') = \{+\} \cap \{), \$\} = \varnothing ✓
Para T' \rightarrow * F T' \mid \varepsilon:
- \text{FIRST}(* F T') = \{*\}
- \text{FIRST}(\varepsilon) = \{\varepsilon\}
- Satisfaz condição 1: \{*\} \cap \{\varepsilon\} = \varnothing ✓
- Satisfaz condição 2: \{*\} \cap \text{FOLLOW}(T') = \{*\} \cap \{+, ), \$\} = \varnothing ✓
Para F \rightarrow (E) \mid \text{id}:
- \text{FIRST}((E)) = \{(\}
- \text{FIRST}(\text{id}) = \{\text{id}\}
- Satisfaz condição 1: \{(\} \cap \{\text{id}\} = \varnothing ✓
Nossa gramática é LL(1)! Isto significa que podemos construir um parser descendente eficiente sem backtracking.