> Uma GLC pode, de fato, gerar uma LR (ex: $S \to aS | a$ para $a^+$). Isso reforça que Tipo 3 é um subconjunto próprio de Tipo 2.
> **Notas do Apresentador:** A FNC é essencial para o algoritmo de reconhecimento **CYK (Cocke-Younger-Kasami)**, que tem complexidade $O(|w|^3)$.
* **Propriedade Chave:** Toda derivação na FNG adiciona **exatamente um terminal** no início da cadeia a ser derivada. * **Necessidade:** A FNG garante a **remoção da recursividade à esquerda** (direta e indireta). Recursividade à esquerda ($A \to A\mu$) causa *looping infinito* em analisadores Top-Down (Descendentes). * **Esboço de Conversão:** 1. Garantir que a GLC esteja simplificada e sem recursividade à esquerda. 2. Substituir variáveis no início da RHS (e.g., $A \to B w$) usando as regras de $B$ para forçar o primeiro símbolo a ser um terminal.
# Algoritmos de Reconhecimento (Parsing) * **Analisador Sintático (Parser):** Componente que verifica se uma palavra $w$ pertence à linguagem $L(G)$. | Estratégia | Descrição | Simula Derivação | Exemplos de Parsers | | :--- | :--- | :--- | :--- | | **Top-Down (Descendente)** | Constrói a árvore da **raiz (S)** para as **folhas (terminais)**. | Mais à Esquerda. | LL(k), Parser Recursivo Descendente. | | **Bottom-Up (Ascendente)** | Constrói a árvore das **folhas (terminais)** para a **raiz (S)**, reduzindo sequências. | Mais à Direita (reversa). | LR(k), CYK (Cocke-Younger-Kasami). | * **Complexidade:** * Algoritmos para GLCs não ambíguas: tipicamente $O(|w|^2)$ (Early). * Para GLCs arbitrárias (e.g., CYK): $O(|w|^3)$. ---
# Analisadores Top-Down * **LL(k):** "Left-to-right scan, Leftmost derivation, looking ahead $k$ tokens." * **Mecanismo:** Tenta adivinhar qual produção aplicar a uma variável (topo da pilha) olhando para os próximos $k$ símbolos da entrada. * **Restrição:** Exige que a gramática não tenha recursividade à esquerda (por isso a FNG é importante). * **Implementação (AP Descendente):** 1. Empilhar o Símbolo Inicial ($S$). 2. Se o topo for uma **Variável ($A$)**: Substituir $A$ por todas as regras $A \to w_i$. (Non-determinismo, ou escolha preditiva no LL(k)). 3. Se o topo for um **Terminal ($a$)**: Comparar com o próximo símbolo de entrada. Se coincidir, desempilhar e consumir o símbolo de entrada. --- # Analisadores Bottom-Up * **LR(k):** "Left-to-right scan, Rightmost derivation (in reverse), looking ahead $k$ tokens." * **Mecanismo:** A principal operação é a **Redução**. Quando um padrão de símbolos (terminais e/ou variáveis) corresponde ao lado direito de uma regra, ele é reduzido para a variável no lado esquerdo. * **Tipos Comuns:** LR(0), SLR, LALR. Esses parsers são considerados os mais poderosos na prática (aceitam a maior classe de GLCs determinísticas). ---
* **Diagrama da Pilha de Análise:** `{{INSERIR_DIAGRAMA_PILHA_ANALISE_AQUI: Diagrama simples de um AP. Mostre 3 componentes: Fita de Entrada (w), Cabeça de Leitura/Estado Atual (q), Pilha (Γ). Adicionar legenda indicando que a pilha fornece a memória adicional que faltava nos AFs.}}` > **Notas do Apresentador:** A pilha é a "memória infinita" que permite aos LLCs rastrear o balanço ou a recursão profunda (e.g., contando $a$'s para esperar a mesma quantidade de $b$'s).
> **Fluxo Simplificado:** > > **CÓDIGO FONTE** $\xrightarrow{\text{Lexer (LRs)}}$ **SEQUÊNCIA DE TOKENS** $\xrightarrow{\text{Parser (GLCs)}}$ **ÁRVORE SINTÁTICA**
* **Fluxograma:** `{{INSERIR_FLUXOGRAMA_COMPILADOR_AQUI: Tokens -> Parser (GLC) -> Parse Tree -> AST (Abstrato).}}`
3. **Recursividade vs. Forma Normal:** Qual é a relação entre recursividade à esquerda ($A \to A \mu$) e a eficiência de um analisador sintático Top-Down? Que Forma Normal resolve este problema e por quê?
* **Parsing:** A análise sintática (parsing) usa estratégias **Top-Down (LL)** ou **Bottom-Up (LR)** para construir a árvore de derivação.