Gramáticas Livre de Contexto

Autômatos, Linguagens e Computação

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

Objetivos de Aprendizagem

• Definir formalmente uma Gramática Livre de Contexto.
• Demonstrar o processo de derivação () de uma sentença, aplicando a sequência de regras a partir do símbolo inicial.
• Entender o cenceito de Hierarquia de Linguagens.
• Explicar a importância central das GLCs no projeto de um analisador sintático (parser) de Linguagens de Programação e
• Entender por que a utilização de Formas Normais (como a FNC) é necessária para eliminar ambiguidades e garantir que o parsing seja eficiente.

Gramática

• Formalismo para definir linguagens formais.
• Uma gramática mostra como gerar todas as palavras de uma linguagem.
• Utilizam recursão.

Hierarquia de Chomsky

O Poder das GLCs

• Limitação das LR (Linguagens Regulares)
  • AFs possuem "memória limitada" (finita).
  • Não conseguem contar ou expressar estruturas de balanceamento, como .
  • O Lema do Bombeamento para LRs comprova que não é regular.
• LLCs Aumentam a Expressão
  • GLCs permitem descrever estruturas recursivas balanceadas.
  • Exemplo clássico: Balanço de parênteses ou blocos .
  • Aplicação central: GLCs são fundamentais no projeto de um analisador sintático (parser), especificando a gramática formal de Linguagens de Programação (LPs).

Definição Formal

• GLC (Gramática Livre de Contexto) é uma quádrupla .

• Restrição Principal: e devem ser disjuntos ().
• Variável inicial: Ao lado esquerdo da primeira regra, a menos que seja especificado o contrário.

Exemplo 1

Considere a gramática com as regras de produção abaixo:

Podemos gerar a cadeia pela sequência de produções (uma derivação):

Convenções e Componentes (V e )

• Variáveis ()
  • Representam categorias sintáticas (e.g., Sentença, Expressão, Verbo).
  • Geralmente representadas por letras maiúsculas (A, B, C...).
  • Símbolos não-terminais
  • Cada variável representa uma sub-linguagem.
• Terminais ( )
  • São os símbolos que formam as palavras finais (o alfabeto da linguagem).
  • Análogos ao alfabeto de entrada dos Autômatos Finitos.
  • Geralmente representados por letras minúsculas, números ou símbolos especiais (e.g., ).

Componentes e a Natureza "Livre de Contexto"

• Regras de Produção (P)
  • São regras de substituição no formato: .
  • Em GLCs, a estrutura é restrita:
    • Lado Esquerdo (): Deve ser uma única variável ().
    • Lado Direito (): Pode ser qualquer cadeia de variáveis e/ou terminais ().
• Caractere "Livre de Contexto"
  • A regra significa que o não-terminal pode ser substituído por .
  • Essa substituição é sempre válida, independentemente do contexto ( e ) em que aparece (i.e., ).
• Símbolo Inicial (S)
  • É a variável que inicia o processo de derivação de qualquer sentença da linguagem.

Aplicação de Regras e Notação

• Derivação (): A aplicação de uma regra de substituição.
• Exemplo de Regra: .
• Mecânica de Substituição:
  • Se na cadeia atual aparecer , ele pode ser substituído por .
  • Seja e uma regra, então .
• Tipos de Geração (Derivação):
  • : é gerada diretamente a partir de (1 passo).
  • : é derivável a partir de (aplicando 0 ou mais regras).
  • : é derivável a partir de (aplicando 1 ou mais regras).

A distinção entre (regra/produção) e (aplicação da regra/derivação) é fundamental.

Exemplo 2

Seja com o conjunto de regras .

Podemos gerar a cadeia , pela derivação:

Derivação e Formas Sentenciais

• Forma Sentencial: Qualquer cadeia que é derivável a partir do símbolo inicial (). Pode conter variáveis e terminais.
• Sentença: Uma forma sentencial que contém somente terminais (). É uma palavra válida na linguagem .
• Derivação Mais à Esquerda: Uma ordem de substituição que, a cada etapa, substitui a variável não-terminal mais à esquerda. Usada por analisadores sintáticos descendentes (Top-Down).

Exemplo de Derivação em Sequência

• GLC Clássica para Palíndromos: .
• Derivação da Sentença 'baab':

• Conclusão: é uma sentença de porque .

Árvore de Derivação (Parse Tree)

• Definição: Uma estrutura de árvore que representa graficamente as substituições aplicadas na derivação.

• Componentes:

  • Raiz: O Símbolo Inicial ().
  • Nós Internos: Variáveis ().
  • Folhas: Terminais () ou .
  • Ordem: Os filhos de um nó interno correspondem ao lado direito da produção , lidos da esquerda para a direita.

• Exemplo: Árvore para 'baab' (usando a derivação anterior) na lousa.

Linguagem da Gramática

• Definição Formal: A linguagem gerada por uma GLC é o conjunto de todas as sentenças (cadeias de terminais) que podem ser derivadas a partir do símbolo inicial :

• LLCs vs. LRs: Todas as Linguagens Regulares (Tipo 3) são também Linguagens Livres de Contexto (Tipo 2), mas o contrário não é verdadeiro.

Exemplos de Linguagens LLC

• Observação: A regra permite a geração da palavra vazia.

Propriedades de Fechamento de LLCs

• O conjunto das LLCs é fechado para algumas operações:
  • União: Se e são LLCs, então também é LLC.
    • Esboço de Prova: Criar uma nova GLC com um novo símbolo inicial e regras (onde e são símbolos iniciais de e ).
  • Concatenação: Se e são LLCs, então também é LLC.
  • Fecho de Kleene (): Se é LLC, então também é LLC.
• Limitações (Não Fechamento):
  • Interseção: O conjunto das LLCs NÃO é fechado para interseção.
    • Exemplo: e são LLCs, mas não é LLC.
  • Complemento: O conjunto das LLCs NÃO é fechado para complemento.

Limitações Intrínsecas

• O que LLCs não conseguem descrever:
  • Enquanto LLCs conseguem fazer balanceamento duplo (e.g., ), não conseguem realizar balanceamento triplo.
• Exemplos de Linguagens NÃO Livres de Contexto:
  • Triplo Balanceamento: .
    • Intuição: O Autômato com Pilha (AP) tem apenas uma pilha. Ele consegue contar e balancear 's com 's. Mas, se precisar balancear 's também, a informação original (sobre 's ou 's) já foi perdida na pilha.
  • Cadeia Duplicada: .
    • O AP não consegue armazenar uma palavra inteira na pilha para depois compará-la com o segundo da entrada.

Lema do Bombeamento para LLCs

• Propósito: Técnica usada para provar que uma linguagem NÃO é Livre de Contexto.
• Ideia Central: Se é uma LLC infinita, qualquer palavra suficientemente longa deve ter repetições de variáveis em sua árvore de derivação (ciclos).
• Estrutura do Lema (Simplificada):
  • Se é uma LLC, existe uma constante tal que para toda palavra com , pode ser dividida em cinco partes: .
  • As restrições são:
    1. (o 'bombeamento' deve ocorrer dentro de uma subárvore limitada).
    2. (pelo menos uma parte a ser bombeada não é vazia).
    3. para todo (a repetição das partes e deve manter a palavra na linguagem).
• Diferença chave: O Lema para LLCs permite o bombeamento de duas seções ( e ) simultaneamente, refletindo o poder de empilhar e desempilhar fornecido pela pilha.

Formas Normais (FN): Introdução e Pré-processamento

• Motivação: GLCs são flexíveis, mas essa liberdade dificulta a construção de analisadores sintáticos e o uso em algoritmos de reconhecimento. FNs impõem restrições nas regras, facilitando o design de parsers e provas.
• Etapas de Simplificação (Pré-FN): Para alcançar as FNs, transformações são necessárias.
  1. Remoção de Recursividade no Símbolo Inicial: Introduzir para garantir que não seja recursivo.
  2. Eliminação de Regras (Nulidade): Remover exceto (se ).
  3. Eliminação de Regras de Cadeia (Unitárias): Remover regras do tipo .
  4. Remoção de Símbolos Inúteis: Remover variáveis que não geram terminais (TERM) e aquelas que não são alcançáveis (REACH).

Forma Normal de Chomsky (FNC)

• Definição: Uma GLC está na FNC se todas as suas regras de produção têm a seguinte forma:

• Propriedade Chave: As árvores de derivação na FNC são sempre binárias.
• Esboço de Conversão (Regras Remanescentes):
  1. Terminais Misturados: Substituir terminais na RHS que não estão sozinhos () por novas variáveis ().
  2. Cadeias Longas: Substituir regras com mais de dois símbolos na RHS () introduzindo novas variáveis temporárias, como em , , e assim por diante, até o par final.

Forma Normal de Greibach (FNG)

• Definição: Uma GLC está na FNG se todas as suas regras de produção têm a seguinte forma:

• 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 () 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., ) usando as regras de 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 pertence à linguagem .

Analisadores Top-Down

• LL(k): "Left-to-right scan, Leftmost derivation, looking ahead tokens."
• Mecanismo: Tenta adivinhar qual produção aplicar a uma variável (topo da pilha) olhando para os próximos 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 ().
  2. Se o topo for uma Variável (): Substituir por todas as regras . (Non-determinismo, ou escolha preditiva no LL(k)).
  3. Se o topo for um Terminal (): 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 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).

O Autômato com Pilha e a Análise

• AP (Autômato com Pilha): Máquina aceitadora de LLCs (Tipo 2). Essencialmente um Autômato Finito Não-Determinístico () mais uma pilha de memória ilimitada.
• Função de Transição (): Define a mudança de estado e o manuseio da pilha.

• Mecânica da Transição (Exemplo): :
  • No estado , lendo na entrada e tendo no topo da pilha...
  • ...vai para o estado , desempilha , e empilha .

Aplicação em Compiladores

• Análise Léxica (Lexing/Scanning):
  • Função: Agrupar caracteres de entrada em tokens (e.g., identificadores, palavras-chave, operadores).
  • Formalismo: Linguagens Regulares (LRs), Expressões Regulares (ERs) e Autômatos Finitos.
• Análise Sintática (Parsing/Sintaxe):
  • Função: Verificar se a sequência de tokens está estruturalmente correta, seguindo as regras da Linguagem de Programação (LP).
  • Formalismo: Gramáticas Livres de Contexto (GLCs).

Ambiguidade e a Construção da AST

• Problema da Ambiguidade:
  • Uma GLC é ambígua se uma palavra () possui duas ou mais árvores de derivação (ou duas ou mais derivações mais à esquerda).
  • Em LPs, isso é indesejável, pois leva a múltiplas interpretações estruturais (e.g., precedência de operadores).
  • Exemplo: para a cadeia .
• Árvore Sintática Abstrata (AST):
  • O objetivo final do parsing é gerar uma representação hierárquica da estrutura do código.
  • A AST (Abstract Syntax Tree) é uma versão simplificada da Árvore de Derivação, eliminando detalhes sintáticos irrelevantes e focando na estrutura semântica para posterior geração de código.

Exercícios de Criação de GLCs

1. GLC para Linguagem com Contagem Desbalanceada (LLC):
   • Desenvolva uma GLC para . (O número de 's é estritamente maior que o número de 's).
   • Dica: Gaste os 's em par com 's, e garanta que reste pelo menos um .
2. GLC para Expressão Aritmética (Parênteses):
   • Desenvolva uma GLC (usando variáveis ) que aceite expressões simples com soma e multiplicação (e.g., ).

Exercícios de Derivação e Ambiguidade

1. Derivação (Sequência):
   • Dada a GLC :

   • Mostre a sequência de derivação mais à esquerda para a sentença (i.e., ).
2. Verificação de Ambiguidade:
   • A GLC a seguir, que gera cadeias com o mesmo número de 'a's e 'b's, é ambígua? Justifique.

   • Dica: Tente encontrar duas derivações mais à esquerda (ou duas árvores) para a cadeia .

Perguntas para Reflexão (Discussão)

1. Poder de Expressão: Por que as GLCs, mesmo sendo mais poderosas que as LRs, ainda não conseguem descrever linguagens como ou ? O que falta no modelo do Autômato com Pilha?
2. Ambiguidade na Prática: Por que a ambiguidade de uma gramática é um problema grave no contexto de um compilador de Linguagem de Programação?
3. Recursividade vs. Forma Normal: Qual é a relação entre recursividade à esquerda () e a eficiência de um analisador sintático Top-Down? Que Forma Normal resolve este problema e por quê?

Resumo / Principais Lições

• Formalismo: GLCs (Tipo 2) são definidas por , onde o lado esquerdo de cada regra é uma única variável.
• Capacidade: GLCs descrevem estruturas que exigem balanceamento e memória infinita (e.g., parênteses aninhados, ), superando as Linguagens Regulares.
• Aceitação: São reconhecidas pelo Autômato com Pilha (AP), que usa uma pilha para memória.
• Parsing: A análise sintática (parsing) usa estratégias Top-Down (LL) ou Bottom-Up (LR) para construir a árvore de derivação.
• Restrições: FNC e FNG impõem formatos restritos às regras para facilitar algoritmos de análise e garantir a remoção de recursão à esquerda.
• Limitação: LLCs não conseguem balancear três ou mais quantidades distintas (e.g., ).