INÍCIO
Livros do Prof.
Análise Sintática: Conceitos e Gramáticas
Bem-vindo ao curso de Compiladores! Neste módulo, exploraremos os fundamentos da análise sintática, um componente essencial no processo de compilação. Aprenderemos sobre gramáticas livres de contexto, derivações, árvores sintáticas e muito mais.
Objetivos da Aula
Compreender o papel da análise sintática
Entender como a análise sintática se encaixa no processo de compilação e sua importância para a verificação estrutural de programas.
Estudar gramáticas livres de contexto
Dominar os conceitos fundamentais de GLCs e como elas são utilizadas para descrever a sintaxe de linguagens de programação.
Identificar ambiguidades e realizar fatoração
Reconhecer problemas de ambiguidade em gramáticas e aplicar técnicas de fatoração para resolvê-los.
Criar gramáticas para expressões
Desenvolver habilidades práticas na construção de gramáticas para expressões aritméticas e implementá-las usando Python/PLY.
Revisão da Análise Léxica
Antes de mergulharmos na análise sintática, vamos relembrar o papel da análise léxica no processo de compilação:
  • Transforma o código-fonte em uma sequência de tokens
  • Elimina comentários, espaços em branco e outros elementos irrelevantes
  • Identifica lexemas e os classifica em categorias (identificadores, palavras-chave, operadores, etc.)
  • Constrói a tabela de símbolos inicial
A análise léxica é a primeira fase do compilador, responsável por transformar o texto do programa em uma sequência de tokens que será utilizada pela análise sintática.
O que é Análise Sintática?
A análise sintática, também conhecida como parsing, é a segunda fase do processo de compilação. Ela verifica se a sequência de tokens gerada pelo analisador léxico está estruturalmente correta de acordo com as regras gramaticais da linguagem.
Verificação Estrutural
Determina se o programa possui uma estrutura válida conforme as regras da linguagem, identificando construções como expressões, declarações e blocos.
Construção da Árvore
Gera uma representação hierárquica do programa (árvore sintática ou de derivação) que reflete a estrutura gramatical do código.
Detecção de Erros
Identifica erros sintáticos, como parênteses não balanceados, falta de ponto-e-vírgula ou uso incorreto de estruturas de controle.
Papel do Parser no Compilador
O analisador sintático (parser) é um componente fundamental do compilador, atuando como uma ponte entre a análise léxica e a análise semântica. Ele recebe a sequência de tokens do analisador léxico e verifica se essa sequência pode ser derivada a partir da gramática da linguagem.
Além de validar a estrutura do programa, o parser cria uma representação intermediária (geralmente uma árvore sintática) que será utilizada nas fases subsequentes do compilador. Esta representação preserva a estrutura hierárquica do programa e facilita a análise semântica, a otimização e a geração de código.
Diagrama do Processo de Compilação
Código-Fonte
Programa escrito em linguagem de alto nível pelo programador.
Análise Léxica
Identifica tokens e constrói a tabela de símbolos.
Análise Sintática
Verifica a estrutura e constrói a árvore de derivação.
Análise Semântica
Verifica tipos, escopo e outras regras de significado.
Geração de Código
Produz código de máquina ou intermediário.
Este fluxo representa as principais fases do processo de compilação, destacando a posição central da análise sintática. Cada fase depende do trabalho realizado pelas fases anteriores e prepara os dados para as fases seguintes.
Gramáticas Formais: Definição
Uma gramática formal é um conjunto de regras que define como formar expressões válidas em uma linguagem. No contexto de linguagens de programação, as gramáticas formais são essenciais para especificar a sintaxe de uma linguagem de forma precisa e sem ambiguidades.
Formalmente, uma gramática G é definida como uma quádrupla G = (V, Σ, R, S), onde:
  • V é um conjunto finito de variáveis (símbolos não-terminais)
  • Σ é um conjunto finito de símbolos terminais (tokens)
  • R é um conjunto finito de regras de produção
  • S é o símbolo inicial (um elemento de V)
As gramáticas formais permitem definir, de maneira exata, quais sequências de símbolos pertencem a uma determinada linguagem, formando a base para o desenvolvimento de analisadores sintáticos.
Hierarquia de Chomsky
Noam Chomsky classificou as gramáticas formais em quatro tipos, conhecidos como a Hierarquia de Chomsky, organizados de acordo com seu poder expressivo:
1
2
3
4
1
Tipo 0
Gramáticas irrestritas (Turing completas)
2
Tipo 1
Gramáticas sensíveis ao contexto
3
Tipo 2
Gramáticas livres de contexto
4
Tipo 3
Gramáticas regulares
Na construção de compiladores, as gramáticas livres de contexto (Tipo 2) são as mais utilizadas para definir a sintaxe de linguagens de programação, enquanto as gramáticas regulares (Tipo 3) são usadas para definir tokens na análise léxica.
Gramáticas Livres de Contexto (GLC)
As Gramáticas Livres de Contexto (GLCs) são o tipo de gramática mais utilizado na definição da sintaxe de linguagens de programação. Elas são poderosas o suficiente para expressar a maioria das construções sintáticas presentes em linguagens de programação, mas simples o bastante para permitir a construção de analisadores eficientes.
Em uma GLC, cada regra de produção tem a forma:
A \rightarrow \alpha
Onde:
  • A é um único símbolo não-terminal
  • α é uma sequência (possivelmente vazia) de símbolos terminais e não-terminais
O termo "livre de contexto" significa que um não-terminal pode ser substituído pela mesma sequência em qualquer contexto em que apareça, independentemente dos símbolos que o cercam.
Componentes de uma GLC
Variáveis (Símbolos Não-Terminais)
São símbolos que podem ser substituídos por sequências de outros símbolos de acordo com as regras de produção. Geralmente representados por letras maiúsculas (A, B, C) ou nomes entre colchetes angulares (<expr>, <stmt>).
Símbolos Terminais
São os elementos básicos da linguagem que não podem ser substituídos. Correspondem aos tokens da análise léxica (identificadores, números, operadores, palavras-chave).
Símbolo Inicial
É o símbolo não-terminal a partir do qual todas as derivações começam. Representa o programa completo ou a construção sintática de mais alto nível.
Produções
São regras que especificam como os símbolos não-terminais podem ser substituídos por sequências de símbolos terminais e não-terminais.
Exemplo Simples de GLC
Vamos considerar uma gramática livre de contexto simples que define uma linguagem de expressões aritméticas básicas:
G = ({E, T, F}, {id, +, *, (, )}, P, E)

Onde P contém as seguintes produções:
E → E + T | T
T → T * F | F
F → ( E ) | id
Nesta gramática:
  • Não-terminais: E (expressão), T (termo), F (fator)
  • Terminais: id (identificador), +, *, (, )
  • Símbolo inicial: E
  • Produções: As regras listadas acima, onde | indica alternativas
Esta gramática permite gerar expressões como "id + id * id" ou "(id + id) * id".
Notação BNF (Backus-Naur Form)
A Forma de Backus-Naur (BNF) é uma notação metassintática usada para expressar gramáticas livres de contexto. É amplamente utilizada para descrever a sintaxe de linguagens de programação, protocolos de comunicação e formatos de dados.
Características principais da notação BNF:
  • Símbolos não-terminais são representados entre colchetes angulares: <expressão>
  • O símbolo ::= indica uma definição
  • A barra vertical | separa alternativas
  • Símbolos terminais são escritos literalmente ou entre aspas
  • Parênteses podem ser usados para agrupar elementos
Existem várias extensões da BNF, como EBNF (Extended BNF) e ABNF (Augmented BNF), que adicionam recursos como repetição, opcional e agrupamento.
Exemplo: GLC para Expressões Matemáticas
A seguir, apresentamos uma gramática livre de contexto em notação BNF para expressões matemáticas simples:
<expr> ::= <expr> "+" <term> | <expr> "-" <term> | <term>
<term> ::= <term> "*" <factor> | <term> "/" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <number> | <id>
<number> ::= [0-9]+
<id> ::= [a-zA-Z][a-zA-Z0-9]*
Esta gramática define uma linguagem de expressões aritméticas que inclui:
  • Operações de adição, subtração, multiplicação e divisão
  • Uso de parênteses para agrupar subexpressões
  • Números inteiros positivos
  • Identificadores (variáveis) começando com uma letra
Observe que as produções para <expr> e <term> estabelecem implicitamente a precedência de operadores (* e / têm precedência maior que + e -).
O que é Derivação?
Derivação é o processo de aplicar sucessivamente as regras de produção de uma gramática, começando pelo símbolo inicial, para gerar uma sequência de símbolos terminais. Este processo é fundamental para entender como uma gramática reconhece strings válidas em sua linguagem.
Uma derivação começa com o símbolo inicial da gramática e, a cada passo, um símbolo não-terminal é substituído de acordo com uma das produções disponíveis. O processo continua até que todos os símbolos sejam terminais ou até que não seja possível fazer mais substituições.
Derivações são importantes porque:
  • Demonstram como uma string é gerada pela gramática
  • Estabelecem a estrutura sintática de uma string
  • São a base para a construção de árvores de derivação
  • Ajudam a identificar ambiguidades na gramática
Derivação à Esquerda
Na derivação à esquerda (leftmost derivation), a cada passo substituímos o não-terminal mais à esquerda da forma sentencial. Este tipo de derivação é particularmente importante para analisadores sintáticos descendentes, como os parsers LL.
Gramática:
E → E + T | T
T → T * F | F
F → ( E ) | id

Derivação à esquerda de "id + id * id":
E ⇒ E + T        (usando E → E + T)
  ⇒ T + T        (usando E → T)
  ⇒ F + T        (usando T → F)
  ⇒ id + T       (usando F → id)
  ⇒ id + T * F   (usando T → T * F)
  ⇒ id + F * F   (usando T → F)
  ⇒ id + id * F  (usando F → id)
  ⇒ id + id * id (usando F → id)
Observe que, a cada passo, substituímos apenas o não-terminal mais à esquerda, seguindo um percurso que corresponde a uma travessia em pré-ordem da árvore de derivação.
Derivação à Direita
Na derivação à direita (rightmost derivation), a cada passo substituímos o não-terminal mais à direita da forma sentencial. Este tipo de derivação é usado em analisadores sintáticos ascendentes, como os parsers LR.
Gramática:
E → E + T | T
T → T * F | F
F → ( E ) | id

Derivação à direita de "id + id * id":
E ⇒ E + T          (usando E → E + T)
  ⇒ E + T * F      (usando T → T * F)
  ⇒ E + T * id     (usando F → id)
  ⇒ E + F * id     (usando T → F)
  ⇒ E + id * id    (usando F → id)
  ⇒ T + id * id    (usando E → T)
  ⇒ F + id * id    (usando T → F)
  ⇒ id + id * id   (usando F → id)
A cada passo, substituímos apenas o não-terminal mais à direita, seguindo um percurso que corresponde a uma travessia em pós-ordem da árvore de derivação.
Exemplo Passo a Passo de Derivação
Vamos acompanhar uma derivação à esquerda detalhada para a expressão "a + b * c" usando a gramática:
E → E + T | T
T → T * F | F
F → id
Passo 1: Começamos com o símbolo inicial E
Passo 2: Aplicamos E → E + T
Passo 3: No não-terminal E, aplicamos E → T
Passo 4: No não-terminal T, aplicamos T → F
Passo 5: No não-terminal F, aplicamos F → id (substituindo por "a")
Passo 6: No não-terminal T, aplicamos T → T * F
Passo 7: No não-terminal T, aplicamos T → F
Passo 8: No não-terminal F, aplicamos F → id (substituindo por "b")
Passo 9: No não-terminal F, aplicamos F → id (substituindo por "c")
Resultado final: "a + b * c"
Importância da Ordem da Derivação
A ordem em que as substituições são feitas durante uma derivação é extremamente importante por vários motivos:
Precedência de Operadores
A ordem da derivação pode refletir a precedência dos operadores na linguagem. Por exemplo, em expressões aritméticas, a multiplicação deve ter precedência sobre a adição.
Associatividade
A ordem também determina a associatividade dos operadores (à esquerda ou à direita). Por exemplo, em a-b-c, a associatividade à esquerda resultaria em ((a-b)-c).
Implementação de Parsers
Diferentes estratégias de parsing seguem diferentes ordens de derivação. Parsers descendentes seguem derivações à esquerda, enquanto parsers ascendentes seguem derivações à direita.
Ambiguidade
Diferentes ordens de derivação para a mesma entrada podem revelar ambiguidades na gramática, o que é problemático para compiladores.
Exercício: Derivar a + b * c
Vamos praticar a derivação da expressão "a + b * c" usando a gramática:
E → E + T | T
T → T * F | F
F → id
Seu desafio é realizar uma derivação à esquerda completa desta expressão, anotando cada passo e a regra de produção aplicada. Lembre-se de que na derivação à esquerda, sempre substituímos o não-terminal mais à esquerda da forma sentencial.
A derivação deve refletir a precedência correta dos operadores, de modo que "a + b * c" seja interpretado como "a + (b * c)" e não como "(a + b) * c".
Esta prática ajudará a solidificar seu entendimento sobre o processo de derivação e como ele relaciona-se com a estrutura sintática das expressões.
Resolução: Derivação de a + b * c
Vamos resolver o exercício de derivação da expressão "a + b * c" usando a gramática fornecida:
E → E + T | T
T → T * F | F
F → id

Derivação à esquerda:
E ⇒ E + T        (usando E → E + T)
  ⇒ T + T        (usando E → T)
  ⇒ F + T        (usando T → F)
  ⇒ id + T       (usando F → id, substituindo por "a")
  ⇒ id + T * F   (usando T → T * F)
  ⇒ id + F * F   (usando T → F)
  ⇒ id + id * F  (usando F → id, substituindo por "b")
  ⇒ id + id * id (usando F → id, substituindo por "c")
Observe que a derivação resultante respeita a precedência correta dos operadores, onde a multiplicação é realizada antes da adição. Isso é refletido na estrutura hierárquica implícita na derivação, onde "b * c" forma uma subexpressão que é então adicionada a "a".
Observações sobre a Forma Canônica
A forma canônica de uma derivação refere-se a uma maneira padronizada de realizar substituições durante o processo de derivação. As duas formas canônicas principais são a derivação mais à esquerda e a derivação mais à direita.
Derivação Mais à Esquerda
  • Sempre substitui o não-terminal mais à esquerda
  • Utilizada por analisadores descendentes (top-down)
  • Corresponde a uma travessia pré-ordem da árvore
  • Notação: ⇒lm (leftmost)
Derivação Mais à Direita
  • Sempre substitui o não-terminal mais à direita
  • Utilizada por analisadores ascendentes (bottom-up)
  • Corresponde a uma travessia pós-ordem da árvore
  • Notação: ⇒rm (rightmost)
A forma canônica é importante porque:
  • Permite uma descrição não ambígua do processo de derivação
  • Facilita a implementação de algoritmos de parsing
  • Fornece uma base para provar propriedades teóricas de gramáticas
O que é uma Árvore de Derivação?
Uma árvore de derivação (ou árvore sintática) é uma representação gráfica hierárquica do processo de derivação de uma string a partir de uma gramática. Ela mostra a estrutura sintática da string e como ela foi gerada aplicando-se as regras de produção da gramática.
Características principais de uma árvore de derivação:
  • A raiz da árvore é o símbolo inicial da gramática
  • Os nós internos são símbolos não-terminais
  • As folhas são símbolos terminais que formam a string derivada
  • Cada nó interno e seus filhos diretos correspondem a uma produção da gramática
  • A leitura das folhas da esquerda para a direita produz a string derivada
As árvores de derivação são extremamente úteis para visualizar a estrutura sintática de programas e expressões, facilitando a implementação de analisadores sintáticos e a detecção de ambiguidades.
Construindo a Árvore de Derivação
A construção de uma árvore de derivação segue um processo sistemático baseado nas regras de produção da gramática e na string a ser analisada. Vamos entender os passos fundamentais:
Iniciar com o Símbolo Inicial
Crie o nó raiz da árvore com o símbolo inicial da gramática.
Selecionar uma Produção
Escolha uma produção aplicável ao não-terminal atual. Em uma derivação à esquerda, sempre selecionamos o não-terminal mais à esquerda.
Expandir o Nó
Crie nós filhos correspondentes aos símbolos do lado direito da produção escolhida, da esquerda para a direita.
Repetir o Processo
Continue expandindo os nós não-terminais até que todos os nós folha sejam símbolos terminais, formando a string analisada.
A árvore resultante representa visualmente a estrutura hierárquica da expressão, mostrando como cada parte se relaciona com as regras da gramática.
Exemplo Visual: Árvore para a + b * c
A árvore de derivação para a expressão "a + b * c" usando a gramática:
E → E + T | T
T → T * F | F
F → id
Observe as características importantes desta árvore:
  • A raiz é o símbolo inicial E
  • Cada nó interno corresponde à aplicação de uma produção
  • As folhas, lidas da esquerda para a direita, formam a expressão "a + b * c"
  • A precedência de operadores é refletida na estrutura da árvore, com a multiplicação (*) ocorrendo em um nível mais profundo que a adição (+)
  • A expressão é interpretada como "a + (b * c)" devido à estrutura hierárquica da árvore
Relação entre Árvore e Derivação
A árvore de derivação e a sequência de derivação estão intimamente relacionadas, mas representam o mesmo processo de maneiras diferentes:
  • A derivação é uma sequência linear de substituições que mostra a evolução da forma sentencial ao longo do tempo
  • A árvore é uma representação hierárquica que mostra a estrutura das substituições e suas relações
Para uma mesma string, podemos ter:
  • Diferentes sequências de derivação (à esquerda, à direita, ou outras)
  • Uma única árvore de derivação (se a gramática for não ambígua)
A árvore de derivação pode ser construída a partir de qualquer sequência de derivação válida para uma string. Inversamente, podemos extrair diferentes sequências de derivação de uma mesma árvore, dependendo da ordem em que visitamos os nós.
Árvore Binária e Precedência de Operadores
A estrutura de uma árvore de derivação reflete naturalmente a precedência e associatividade dos operadores em expressões. Em uma gramática bem projetada para expressões aritméticas, os operadores de maior precedência aparecem em níveis mais profundos da árvore.
Principais características de árvores binárias para expressões:
  • Operadores aparecem como nós internos
  • Operandos aparecem como folhas
  • Subexpressões formam subárvores
  • A altura relativa dos operadores na árvore define sua precedência
  • Operadores de mesma precedência seguem a associatividade definida pela gramática
Por exemplo, na expressão "a + b * c", o operador "*" aparece em um nível mais profundo que "+", refletindo sua maior precedência. Isso garante que a multiplicação seja realizada antes da adição na avaliação da expressão.
Atividade: Construa a Árvore de (a + b) * c
Agora é sua vez de praticar! Construa a árvore de derivação para a expressão "(a + b) * c" usando a gramática:
E → E + T | T
T → T * F | F
F → ( E ) | id
Dicas para construir a árvore:
  • Comece com o símbolo inicial E como raiz
  • Siga uma derivação à esquerda, sempre expandindo o não-terminal mais à esquerda
  • Preste atenção aos parênteses, que agrupam "a + b" como uma subexpressão
  • Verifique se a estrutura da sua árvore reflete a precedência correta dos operadores, considerando o efeito dos parênteses
Compare sua árvore com a árvore da expressão "a + b * c" que vimos anteriormente. Observe como os parênteses alteram a estrutura da árvore e, consequentemente, a ordem de avaliação da expressão.
Diferenciar Árvores à Esquerda e à Direita
Árvore de Derivação à Esquerda
Corresponde a uma derivação onde sempre substituímos o não-terminal mais à esquerda:
  • Utilizada em analisadores descendentes (LL)
  • Construída de cima para baixo, da esquerda para a direita
  • Reflete uma travessia em pré-ordem da árvore
Árvore de Derivação à Direita
Corresponde a uma derivação onde sempre substituímos o não-terminal mais à direita:
  • Utilizada em analisadores ascendentes (LR)
  • Construída de baixo para cima, da direita para a esquerda
  • Reflete uma travessia em pós-ordem da árvore
Embora a estrutura final da árvore seja a mesma em ambos os casos (para gramáticas não ambíguas), a ordem em que os nós são criados e visitados é diferente, o que tem implicações importantes para a implementação de analisadores sintáticos.
O que é Ambiguidade Gramatical?
Uma gramática é considerada ambígua quando existe pelo menos uma string na linguagem que pode ser derivada de mais de uma maneira, resultando em árvores de derivação diferentes. A ambiguidade é um problema sério no desenvolvimento de compiladores, pois pode levar a interpretações diferentes do mesmo código.
Formalmente, uma gramática G é ambígua se e somente se existe uma string w na linguagem L(G) que possui mais de uma árvore de derivação distinta ou, equivalentemente, mais de uma derivação à esquerda (ou à direita) distinta.
Consequências da ambiguidade em compiladores:
  • Interpretação imprevisível de expressões
  • Dificuldade na implementação de analisadores sintáticos
  • Possíveis erros de semântica ou geração de código incorreto
  • Necessidade de regras adicionais para resolver a ambiguidade
Exemplo de Gramática Ambígua
Considere a seguinte gramática para expressões aritméticas:
E → E + E | E * E | ( E ) | id
Esta gramática é ambígua porque uma expressão como "a + b * c" pode ser derivada de duas maneiras diferentes:
Interpretação 1: (a + b) * c
E ⇒ E * E
  ⇒ E + E * E
  ⇒ id + E * E
  ⇒ id + id * E
  ⇒ id + id * id
Nesta derivação, o operador + é aplicado antes do operador *, resultando na expressão (a + b) * c.
Interpretação 2: a + (b * c)
E ⇒ E + E
  ⇒ id + E
  ⇒ id + E * E
  ⇒ id + id * E
  ⇒ id + id * id
Nesta derivação, o operador * é aplicado antes do operador +, resultando na expressão a + (b * c).
As duas derivações produzem a mesma string "a + b * c", mas representam estruturas sintáticas diferentes com significados semânticos distintos.
Mesma String, Múltiplas Árvores: Perigo!
Quando uma gramática é ambígua, a mesma string pode ter múltiplas árvores de derivação, o que representa um sério problema para compiladores e interpretadores. Vejamos por que isso é perigoso:
Comportamento Imprevisível
O compilador pode escolher arbitrariamente uma das interpretações possíveis, levando a resultados inesperados.
Dificuldade de Implementação
Analisadores sintáticos determinísticos não podem lidar diretamente com gramáticas ambíguas, exigindo técnicas especiais ou modificações na gramática.
Bugs Sutis
A ambiguidade pode causar bugs difíceis de detectar, especialmente quando diferentes implementações do compilador escolhem interpretações diferentes.
Inconsistência Semântica
Diferentes árvores de derivação podem levar a diferentes significados semânticos e, consequentemente, a diferentes resultados durante a execução.
Gramáticas Ambíguas para Expressões Aritméticas
As expressões aritméticas são particularmente propensas a ambiguidades gramaticais, especialmente quando envolvem múltiplos operadores com diferentes precedências e associatividades. Vamos examinar algumas fontes comuns de ambiguidade:
1
Precedência de Operadores
Quando a gramática não estabelece claramente que certos operadores (como * e /) têm precedência maior que outros (como + e -), expressões como "a + b * c" podem ser interpretadas de diferentes maneiras.
2
Associatividade
Sem regras claras de associatividade, expressões como "a - b - c" podem ser interpretadas como "(a - b) - c" ou "a - (b - c)", produzindo resultados diferentes.
3
Operadores Unários
A interação entre operadores unários (como negação -) e binários pode causar ambiguidade. Por exemplo, "-a + b" pode ser interpretado como "(-a) + b" ou "-(a + b)".
Para resolver essas ambiguidades, é necessário redesenhar a gramática de modo a refletir explicitamente as regras de precedência e associatividade desejadas.
Ambiguidade em Operadores Associativos
Operadores associativos são aqueles onde a ordem de aplicação não altera o resultado quando apenas esse operador está presente. No entanto, a forma como definimos a associatividade na gramática pode introduzir ambiguidades ou afetar a eficiência do parser.
Associatividade à Esquerda
Operações são agrupadas da esquerda para a direita:
E → E + T | T
A expressão "a + b + c" é interpretada como "(a + b) + c"
Ideal para operadores como - e / que não são matematicamente associativos.
Associatividade à Direita
Operações são agrupadas da direita para a esquerda:
E → T + E | T
A expressão "a + b + c" é interpretada como "a + (b + c)"
Útil para operadores como = (atribuição) e ^ (exponenciação) em algumas linguagens.
Gramáticas ambíguas para operadores associativos:
E → E + E | E - E | T // Ambígua: não define associatividade
Fatoração à Esquerda: Definição
A fatoração à esquerda é uma técnica de transformação de gramáticas que visa eliminar prefixos comuns em produções alternativas para o mesmo não-terminal. Esta técnica é particularmente importante para analisadores sintáticos descendentes, que têm dificuldade em decidir qual produção aplicar quando várias produções começam com os mesmos símbolos.
Formalmente, se uma gramática tem produções da forma:
A → αβ₁ | αβ₂ | ... | αβₙ | γ₁ | γ₂ | ... | γₘ
Onde α é um prefixo comum e β₁, β₂, ..., βₙ, γ₁, γ₂, ..., γₘ são sequências de símbolos (possivelmente vazias), podemos fatorá-la para:
A → αA' | γ₁ | γ₂ | ... | γₘ
A' → β₁ | β₂ | ... | βₙ
Onde A' é um novo não-terminal introduzido para representar as partes que diferem após o prefixo comum α.
Fatorar uma Gramática Simples (Exemplo)
Vamos aplicar a fatoração à esquerda em uma gramática simples com prefixos comuns:
Gramática Original
S → if E then S else S
  | if E then S
  | a
Observe que as duas primeiras produções têm o prefixo comum "if E then S".
Gramática Fatorada
S → if E then S S'
  | a

S' → else S
   | ε
Introduzimos o novo não-terminal S' para representar a parte opcional "else S" e a string vazia ε.
A fatoração à esquerda:
  • Elimina a necessidade de retrocesso (backtracking) em analisadores descendentes
  • Torna a gramática mais adequada para parsers LL
  • Não altera a linguagem gerada pela gramática
  • Pode ser aplicada recursivamente se necessário
Transformar Gramática Ambígua em Não Ambígua
Para transformar uma gramática ambígua em não ambígua, precisamos reestruturá-la de modo a eliminar as múltiplas interpretações possíveis. Vamos ver um exemplo com expressões aritméticas:
Gramática Ambígua
E → E + E | E * E | ( E ) | id
Esta gramática é ambígua porque não estabelece precedência entre + e * e não define associatividade.
Gramática Não Ambígua
E → E + T | T
T → T * F | F
F → ( E ) | id
Nesta versão, a estrutura hierárquica estabelece que * tem maior precedência que + e ambos são associativos à esquerda.
Observações importantes:
  • A nova gramática gera a mesma linguagem que a original
  • A estrutura reflete as regras de precedência e associatividade desejadas
  • Cada string na linguagem tem uma única árvore de derivação
  • A gramática é adequada para implementação de parsers determinísticos
Conceito de Análise Descendente
A análise sintática descendente (top-down parsing) é uma estratégia de parsing que constrói a árvore de derivação partindo do símbolo inicial da gramática (raiz) e tentando derivar a string de entrada (folhas). Este método segue derivações à esquerda, sempre expandindo o não-terminal mais à esquerda da forma sentencial.
Principais características da análise descendente:
  • Inicia com o símbolo inicial da gramática
  • Tenta encontrar uma sequência de produções que derive a string de entrada
  • Constrói a árvore de cima para baixo e da esquerda para a direita
  • Implementa uma derivação à esquerda
  • Pode ser realizada com ou sem retrocesso (backtracking)
Dois métodos principais de análise descendente são o parsing recursivo (recursive-descent parsing) e o parsing preditivo (predictive parsing), que é implementado por parsers LL.
Parsing Recursivo
O parsing recursivo (recursive-descent parsing) é uma técnica de análise descendente onde cada não-terminal da gramática é implementado como uma função que analisa a parte correspondente da entrada. É uma abordagem intuitiva e direta para implementar analisadores sintáticos.
// Exemplo simplificado de parser recursivo em pseudocódigo
função parseE() {
    parseT();
    enquanto (próximoToken() == '+') {
        consumirToken('+');
        parseT();
    }
}

função parseT() {
    parseF();
    enquanto (próximoToken() == '*') {
        consumirToken('*');
        parseF();
    }
}

função parseF() {
    se (próximoToken() == '(') {
        consumirToken('(');
        parseE();
        consumirToken(')');
    } senão se (próximoToken() == 'id') {
        consumirToken('id');
    } senão {
        erro("Esperado '(' ou identificador");
    }
}
O parser recursivo é relativamente fácil de implementar e entender, mas pode ter problemas com recursão à esquerda e retrocesso excessivo.
Problemas com Recursão à Esquerda
A recursão à esquerda ocorre quando um não-terminal deriva uma forma sentencial que começa com ele mesmo. Isso pode ser direto (A → A α) ou indireto (A → B α, B → A β). A recursão à esquerda causa problemas sérios em parsers recursivos descendentes.
Exemplo de Recursão à Esquerda
E → E + T | T
Implementação ingênua em pseudocódigo:
função parseE() {
    parseE();  // PROBLEMA: recursão infinita!
    consumirToken('+');
    parseT();
    // OU
    parseT();
}
Consequências
  • Recursão infinita na implementação
  • Stack overflow
  • Impossibilidade de implementar diretamente
  • Necessidade de transformação da gramática
Eliminando Recursão à Esquerda
Para implementar um parser recursivo descendente, precisamos eliminar a recursão à esquerda da gramática. Aqui está um método sistemático para eliminar a recursão à esquerda direta:
Gramática com Recursão à Esquerda
A → A α | β
Onde α é uma sequência não vazia de símbolos e β é uma sequência (possivelmente vazia) que não começa com A.
Gramática sem Recursão à Esquerda
A → β A'
A' → α A' | ε
Onde ε representa a string vazia. Esta transformação substitui a recursão à esquerda por uma iteração.
Aplicando esta transformação à gramática E → E + T | T, obtemos:
E → T E'
E' → + T E' | ε
Esta nova gramática gera a mesma linguagem, mas é adequada para implementação em um parser recursivo descendente.
Objetivo: Construir uma Gramática para Expressões
Agora que conhecemos os conceitos fundamentais de gramáticas e análise sintática, vamos aplicá-los para construir uma gramática para expressões aritméticas. Nosso objetivo é criar uma gramática que:
Seja Não Ambígua
Cada expressão válida deve ter uma única árvore de derivação, garantindo uma interpretação consistente.
Reflita Precedência de Operadores
Multiplicação e divisão devem ter precedência maior que adição e subtração. Parênteses devem permitir sobrepor a precedência padrão.
Defina Associatividade
Operadores binários devem ser associativos à esquerda (por exemplo, a-b-c deve ser interpretado como (a-b)-c).
Seja Implementável
A gramática deve ser adequada para implementação em um parser recursivo descendente ou em ferramentas como PLY, sem recursão à esquerda.
Tokens Esperados para Expressões Aritméticas
Antes de definir a gramática, precisamos identificar os tokens (símbolos terminais) que serão reconhecidos pelo analisador léxico. Para nossa gramática de expressões aritméticas, consideraremos os seguintes tokens:
ID
Identificadores (variáveis) como a, b, x, y, etc. Na análise léxica, seriam definidos por um padrão como [a-zA-Z][a-zA-Z0-9]*
Operadores Aritméticos
Os símbolos +, -, *, / para representar adição, subtração, multiplicação e divisão, respectivamente.
Parênteses
Os símbolos ( e ) para agrupar subexpressões e alterar a precedência padrão dos operadores.
Estes tokens serão os blocos de construção básicos para nossas expressões aritméticas. O analisador léxico será responsável por identificá-los no código fonte e passá-los para o analisador sintático.
Definição da Gramática para Expressões
Aqui está uma gramática inicial para expressões aritméticas, que reflete a precedência e associatividade desejadas para os operadores:
Expr → Expr + Term | Expr - Term | Term
Term → Term * Factor | Term / Factor | Factor
Factor → (Expr) | ID
Nesta gramática:
  • Expr representa expressões de adição e subtração
  • Term representa expressões de multiplicação e divisão
  • Factor representa expressões básicas (identificadores ou subexpressões entre parênteses)
A estrutura hierárquica da gramática estabelece que multiplicação e divisão têm precedência maior que adição e subtração. As produções recursivas à esquerda (como Expr → Expr + Term) definem a associatividade à esquerda para os operadores binários.
Esta gramática, embora correta do ponto de vista da linguagem gerada, contém recursão à esquerda, o que é problemático para implementação em parsers recursivos descendentes.
Problemas: Recursão à Esquerda
Nossa gramática inicial para expressões aritméticas contém recursão à esquerda em duas produções:
Expr → Expr + Term | ...
Term → Term * Factor | ...
Como discutimos anteriormente, a recursão à esquerda causa problemas em parsers recursivos descendentes, levando a loops infinitos na implementação. Para utilizar esta gramática em um parser descendente, precisamos eliminar a recursão à esquerda.
Além disso, a recursão à esquerda pode causar problemas de desempenho mesmo em parsers que a suportam teoricamente, como os gerados por ferramentas como PLY. A eliminação da recursão à esquerda geralmente resulta em parsers mais eficientes e menos propensos a erros.
Versão Fatorada da Gramática
Aplicando a técnica de eliminação de recursão à esquerda à nossa gramática original, obtemos uma versão equivalente sem recursão à esquerda:
Expr → Term Expr'
Expr' → + Term Expr' | - Term Expr' | ε

Term → Factor Term'
Term' → * Factor Term' | / Factor Term' | ε

Factor → (Expr) | ID
Nesta gramática fatorada:
  • Introduzimos os não-terminais Expr' e Term' para substituir a recursão à esquerda por uma iteração
  • O símbolo ε representa a string vazia (opção de não continuar a expressão)
  • A gramática gera exatamente a mesma linguagem que a gramática original
  • A precedência e associatividade dos operadores são preservadas
  • A gramática é adequada para implementação em parsers recursivos descendentes
Construção de Árvore Sintática para a + b * c
Vamos construir a árvore sintática para a expressão "a + b * c" usando nossa gramática fatorada:
Expr → Term Expr'
Expr' → + Term Expr' | - Term Expr' | ε
Term → Factor Term'
Term' → * Factor Term' | / Factor Term' | ε
Factor → (Expr) | ID
Observe que, apesar da estrutura diferente da gramática fatorada, a árvore sintática resultante ainda reflete a mesma precedência de operadores que teríamos com a gramática original: a multiplicação (b * c) tem precedência sobre a adição, formando uma subexpressão que é então adicionada a "a".
A diferença está principalmente na forma como os não-terminais Expr' e Term' capturam a possibilidade de continuar uma expressão com operadores adicionais, substituindo a recursão à esquerda por uma estrutura iterativa.
Uso da Gramática com PLY (Python)
PLY (Python Lex-Yacc) é uma implementação das ferramentas lex e yacc para Python, permitindo a criação de analisadores léxicos e sintáticos. Vamos ver como implementar nossa gramática fatorada usando PLY:
import ply.yacc as yacc
import ply.lex as lex

# Definição do analisador léxico (simplificado)
tokens = ('ID', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN')
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_ID = r'[a-zA-Z][a-zA-Z0-9]*'
t_ignore = ' \t'

# Definição das regras de produção
def p_expr(p):
 '''expr : term expr_prime'''
 if p[2] is None: # Se expr_prime resultou em epsilon
 p[0] = p[1]
 else:
 p[0] = p[2]

def p_expr_prime(p):
 '''expr_prime : PLUS term expr_prime
 | MINUS term expr_prime
 | '''
 if len(p) == 1: # Regra vazia (epsilon)
 p[0] = None
 elif p[1] == '+':
 if p[3] is None: # Se o próximo expr_prime é epsilon
 p[0] = ('add', p[-1], p[2])
 else:
 p[3][1] = ('add', p[-1], p[2])
 p[0] = p[3]
 # ... implementação similar para MINUS
Demonstração: Parse e Árvore
Vamos ver como nosso parser PLY processaria a expressão "a + b * c" e construiria a árvore sintática correspondente:
Passos do processo de parsing:
  1. O analisador léxico identifica os tokens: ID(a), PLUS, ID(b), TIMES, ID(c)
  1. O parser começa com a regra expr e deriva term expr_prime
  1. term deriva factor term_prime, e factor deriva ID(a)
  1. term_prime deriva epsilon (não há operadores * ou / após 'a')
  1. expr_prime deriva PLUS term expr_prime
  1. O segundo term deriva factor term_prime, e factor deriva ID(b)
  1. O segundo term_prime deriva TIMES factor term_prime
  1. O terceiro factor deriva ID(c)
  1. O terceiro term_prime deriva epsilon
  1. O segundo expr_prime deriva epsilon
O resultado é uma árvore que representa corretamente "a + (b * c)".
Resumo: GLC, Derivações, Árvores, Ambiguidade
Gramáticas Livres de Contexto
Formalismos para definir a sintaxe de linguagens de programação, compostos por variáveis, símbolos terminais, produções e um símbolo inicial.
Derivações
Sequências de aplicações de regras de produção para gerar strings. Podem ser à esquerda (para parsers descendentes) ou à direita (para parsers ascendentes).
Árvores de Derivação
Representações hierárquicas da estrutura sintática, mostrando como uma string foi derivada a partir da gramática e refletindo a precedência de operadores.
Ambiguidade
Situação onde uma string pode ser derivada de múltiplas maneiras, causando problemas de interpretação. Pode ser resolvida com reestruturação da gramática.
Fatoração e Eliminação de Recursão
Técnicas para transformar gramáticas em formas mais adequadas para implementação de parsers, preservando a linguagem gerada.
Tarefa Prática: Gramática para Expressões Booleanas
Como atividade para fixação do conteúdo, desenvolva uma gramática para expressões booleanas que inclua:
  • Operadores booleanos AND, OR e NOT
  • Operadores de comparação (==, !=, <, >, <=, >=)
  • Variáveis booleanas e expressões aritméticas como operandos
  • Parênteses para agrupamento
Sua gramática deve:
  1. Estabelecer precedência correta entre operadores (NOT > AND > OR)
  1. Definir associatividade (geralmente à esquerda para AND e OR)
  1. Ser não ambígua
  1. Estar em uma forma adequada para implementação (sem recursão à esquerda)
Na próxima aula, exploraremos tabelas e algoritmos de parsing, incluindo métodos LL e LR, tabelas de análise preditiva e técnicas de recuperação de erros. Prepare-se revisando o conteúdo desta aula!