INÍCIO
Livros do Prof.
Análise Sintática: Parsing Ascendente
Aprenda todas as técnicas de análise sintática ascendente, desde o funcionamento básico até ferramentas avançadas como Yacc, Bison e PLY para implementação prática de compiladores.
Objetivos da Aula
Compreender o parsing bottom-up
Entender os princípios e mecanismos fundamentais que regem a análise sintática ascendente, diferenciando-a das técnicas descendentes.
Estudar tabelas LR
Explorar os diferentes tipos de tabelas LR(0), SLR e LR(1), seus algoritmos de construção e aplicações práticas na análise sintática.
Conhecer ferramentas geradoras
Familiarizar-se com ferramentas como Yacc, Bison e PLY para geração automática de analisadores sintáticos eficientes.
Praticar criação de parsers
Implementar na prática um analisador sintático funcional utilizando as técnicas e ferramentas estudadas durante a aula.
Parsing Descendente vs. Ascendente
Parsing Descendente (LL)
Inicia pela raiz (símbolo inicial) e tenta derivar a entrada. Constrói a árvore de cima para baixo, da esquerda para a direita.
  • Usa derivações mais à esquerda
  • Menos poderoso (LL(k))
  • Implementação mais simples
  • Exige remoção de recursão à esquerda
Parsing Ascendente (LR)
Começa pelos tokens da entrada e tenta reduzi-los até o símbolo inicial. Constrói a árvore de baixo para cima.
  • Usa derivações mais à direita em reverso
  • Mais poderoso (LR(k))
  • Implementação mais complexa
  • Aceita gramáticas com recursão à esquerda
O que é Parsing Bottom-Up?
O parsing bottom-up, ou análise sintática ascendente, é uma técnica que parte dos símbolos terminais (tokens) da entrada e gradualmente os agrupa em estruturas maiores até atingir o símbolo inicial da gramática.
Esta abordagem é como "reduzir" a entrada de volta à origem, invertendo o processo de derivação. O parser reconhece subsequências de tokens que correspondem ao lado direito de produções da gramática e as substitui pelo símbolo não-terminal do lado esquerdo.
"O parser ascendente tenta encontrar a derivação mais à direita em ordem inversa, partindo da sentença de entrada e chegando ao símbolo inicial."
Ideia Central do Parsing Ascendente
Na análise sintática ascendente, o objetivo é construir a árvore sintática a partir das folhas (símbolos terminais) em direção à raiz (símbolo inicial). Esta abordagem é particularmente eficiente para a maioria das linguagens de programação.
O processo envolve identificar sequências de símbolos que correspondem ao lado direito de uma regra de produção e substituí-las pelo símbolo não-terminal correspondente, "reduzindo" gradualmente a entrada até chegar ao símbolo inicial.
Leitura da entrada
Tokens são lidos da entrada e empilhados
Reconhecimento de padrões
Identificação de subsequências que correspondem a produções
Reduções
Substituição das subsequências por não-terminais
Aceitação
Redução completa até o símbolo inicial
Exemplo Intuitivo com Pilha: 3 + 4 * 5
Vamos analisar a expressão "3 + 4 * 5" usando uma pilha para demonstrar o processo de parsing ascendente. Consideramos a gramática para expressões aritméticas com precedência de operadores.
Observe como a precedência de operadores é naturalmente respeitada: primeiro calculamos 4 * 5 (reduzindo para E) antes de somar com 3.
Definição de LR: Left-to-right, Rightmost derivation in reverse
O termo LR (Left-to-right, Rightmost derivation in reverse) descreve precisamente o funcionamento do parsing ascendente:
Left-to-right
A entrada é lida da esquerda para a direita, um token por vez, sem retrocesso.
Rightmost derivation
Corresponde à derivação mais à direita, onde sempre se expande o não-terminal mais à direita.
In reverse
O processo inverte a derivação, partindo da sentença e chegando ao símbolo inicial.
O parsing LR é mais poderoso que o LL, capaz de reconhecer uma classe maior de gramáticas. Parsers LR podem analisar todas as gramáticas LL e muitas outras que os parsers LL não conseguem processar, incluindo gramáticas com recursão à esquerda.
Exemplo: Passo a Passo do Algoritmo Shift-Reduce
Vamos analisar a expressão "id + id * id" usando o algoritmo shift-reduce com a gramática:
E → E + T | T
T → T * F | F
F → id | (E)
Note como a precedência dos operadores é respeitada naturalmente: a multiplicação é realizada antes da adição devido às regras da gramática.
Visualização com Pilha e Entrada
O processo de análise sintática ascendente pode ser visualizado como uma manipulação de pilha, onde cada ação modifica o estado atual do analisador.
A visualização da pilha e da entrada restante é fundamental para entender o processo de parsing ascendente. À medida que tokens são lidos e empilhados (shift), e produções são reconhecidas e reduzidas (reduce), podemos acompanhar a construção gradual da árvore sintática.
Esta representação facilita a compreensão do algoritmo e é especialmente útil para depuração e desenvolvimento de parsers. Ferramentas automáticas frequentemente fornecem visualizações semelhantes durante o processo de análise sintática.
Vantagens do Parsing LR sobre LL
Maior poder de reconhecimento
Parsers LR reconhecem uma classe muito maior de gramáticas em comparação com os parsers LL. Praticamente todas as construções sintáticas encontradas em linguagens de programação podem ser expressas naturalmente por gramáticas LR.
Detecção de erros mais eficiente
Parsers LR detectam erros sintáticos assim que possível na leitura da entrada da esquerda para a direita, o que permite mensagens de erro mais precisas e recuperação mais eficiente.
Suporte à recursão à esquerda
Diferentemente dos parsers LL, que não podem lidar com recursão à esquerda direta, os parsers LR aceitam gramáticas com recursão à esquerda sem necessidade de transformações.
Geração automática mais simples
Embora os parsers LR sejam mais complexos para implementação manual, sua geração automática por ferramentas é bem estabelecida e eficiente, tornando seu uso prático.
Construção de Autômato LR(0): Conceitos
O autômato LR(0) é a base para a construção das tabelas de parsing LR. Ele representa os possíveis estados do parser durante a análise sintática.
Componentes Principais
  • Estados: conjuntos de itens LR(0)
  • Transições: movimentos entre estados ao ler símbolos
  • Fechamento: expansão de itens com ponto antes de não-terminais
  • Propagação: criação de novos estados ao avançar o ponto
Procedimento
  1. Crie o item inicial com o ponto no início da produção do símbolo inicial
  1. Compute o fechamento desse item
  1. Para cada símbolo após o ponto, crie um novo estado
  1. Continue até que nenhum novo estado possa ser criado
Itens LR(0): Definição e Exemplo
Um item LR(0) é uma produção da gramática com um marcador especial (ponto) que indica quanto da produção já foi reconhecido. O ponto pode estar em qualquer posição da parte direita da produção.
Definição formal
Para uma produção A → α, os itens LR(0) possíveis são todas as formas A → β•γ, onde αβγ e β pode ser vazio. O ponto (•) indica a posição atual de análise.
Interpretação
Um item A → β•γ significa "já vimos β e esperamos ver γ a seguir". Quando o ponto está no final (A → α•), temos um item de redução.
Para a produção E → E + T, os possíveis itens LR(0) são:
  • E → •E + T (ainda não vimos nada)
  • E → E• + T (vimos E, esperamos +)
  • E → E +• T (vimos E +, esperamos T)
  • E → E + T• (vimos toda a produção)
Construção de Estados LR(0)
A construção dos estados LR(0) é fundamental para criar a tabela de parsing. Cada estado representa um conjunto de itens LR(0) que compartilham um contexto sintático comum.
Item inicial
Comece com S' → •S (onde S' é um novo símbolo inicial e S é o símbolo inicial original)
Fechamento
Para cada item A → α•Bβ, adicione todos os itens B → •γ ao conjunto
Propagação (GOTO)
Para cada símbolo X, agrupe os itens onde o ponto precede X e avance o ponto
Repetição
Continue até que nenhum novo estado possa ser adicionado ao autômato
Esta construção resulta em um autômato finito determinístico cujos estados representam todos os possíveis contextos sintáticos durante a análise.
Tabela de Parsing LR(0): ACTION e GOTO
A tabela de parsing LR é dividida em duas partes: ACTION e GOTO. Estas tabelas guiam as decisões do analisador sintático durante o processo de parsing.
Tabela ACTION
Determina a ação a ser tomada com base no estado atual e no próximo token:
  • shift s: Empilha o token e vai para o estado s
  • reduce A → β: Reduz os |β| símbolos do topo da pilha para A
  • accept: Aceita a entrada (parsing bem-sucedido)
  • error: Reporta um erro sintático
Tabela GOTO
Indica para qual estado ir após uma redução:
  • Após reduzir para um não-terminal A, consulta-se GOTO[estado,A] para determinar o próximo estado
  • Funciona como as transições do autômato para não-terminais
As tabelas ACTION e GOTO são construídas a partir do autômato LR(0) e são a base para o algoritmo de parsing LR.
Conflitos Shift-Reduce e Reduce-Reduce
Conflitos são situações onde o parser LR não pode decidir inequivocamente qual ação tomar. Eles representam ambiguidades na gramática que impedem a criação de um parser LR determinístico.
Conflito Shift-Reduce
Ocorre quando, para um mesmo estado e símbolo, é possível tanto empilhar (shift) quanto reduzir (reduce).
// Exemplo: gramática if-then-else ambígua
S → if E then S | if E then S else S | other
Na entrada "if E then if E then S else S", não sabemos se o "else" pertence ao primeiro ou ao segundo "if".
Conflito Reduce-Reduce
Ocorre quando, para um mesmo estado e símbolo, é possível reduzir por duas ou mais produções diferentes.
// Exemplo
S → aAc | aBd
A → b
B → b
Na entrada "abc", após ler "ab", não sabemos se devemos reduzir "b" para A ou para B.
Os conflitos indicam que a gramática não pode ser analisada diretamente por um parser LR(0). Técnicas como SLR, LR(1) e LALR podem resolver alguns desses conflitos.
O que é SLR (Simple LR)?
O SLR (Simple LR) é uma evolução do LR(0) que utiliza informações adicionais de lookahead para resolver alguns conflitos shift-reduce. Ele usa os conjuntos FOLLOW para determinar quando é seguro realizar uma redução.
LR(0)
Construção básica de estados e itens sem lookahead
SLR
Adiciona conjuntos FOLLOW para restringir reduções
LR(1)
Incorpora lookahead diretamente nos itens
No SLR, uma redução A → α só é realizada se o próximo token estiver no conjunto FOLLOW(A). Isso elimina muitos conflitos shift-reduce presentes no LR(0), tornando o parser capaz de analisar uma classe maior de gramáticas.
Embora mais poderoso que o LR(0), o SLR ainda não consegue lidar com todas as gramáticas LR(1). Em casos onde o SLR encontra conflitos, pode ser necessário utilizar técnicas mais avançadas como o LR(1) completo ou o LALR(1).
LR(1): Uso de Lookahead e Maior Poder
O LR(1) é a versão mais poderosa dos parsers LR, incorporando um símbolo de lookahead diretamente nos itens. Isso permite resolver a maioria dos conflitos encontrados em versões mais simples.
Itens LR(1)
Um item LR(1) tem a forma [A → α•β, a], onde:
  • A → α•β é um item LR(0)
  • a é um símbolo terminal ou $ (fim de entrada)
  • O lookahead a indica que a redução só deve ocorrer quando o próximo token for a
Vantagens do LR(1)
  • Maior poder de reconhecimento
  • Resolve a maioria dos conflitos práticos
  • Decisões mais precisas nas reduções
Desvantagens
  • Muito mais estados que LR(0) ou SLR
  • Tabelas maiores e mais complexas
Na prática, a versão LALR(1) (Look-Ahead LR) é frequentemente utilizada como um meio-termo, mantendo o poder do LR(1) mas com uma quantidade de estados similar ao SLR.
Introdução ao Yacc/Bison
Yacc (Yet Another Compiler Compiler) e seu sucessor Bison são ferramentas clássicas para geração automática de parsers LR. Elas transformam uma especificação de gramática em um programa C que implementa um analisador sintático.
Características
  • Geram parsers LALR(1) por padrão
  • Permitem associar ações semânticas às regras
  • Oferecem mecanismos para resolução de conflitos
  • Integram-se naturalmente com Lex/Flex para análise léxica
Estrutura de um arquivo .y
%{
/* Declarações em C */
%}

/* Declarações Yacc */
%token NUM ID
%left '+' '-'
%left '*' '/'

%%
/* Regras gramaticais */
expr : expr '+' expr { $$ = $1 + $3; }
 | NUM { $$ = $1; }
 ;
%%

/* Código C adicional */
Fluxo: Definições Léxicas (Lex) + Sintáticas (Yacc)
O processo completo de análise envolve a integração entre um analisador léxico gerado pelo Lex/Flex e um analisador sintático gerado pelo Yacc/Bison.
Arquivo .l (Lex)
Contém as definições de tokens e expressões regulares para reconhecê-los
Arquivo .y (Yacc)
Contém a gramática e as ações semânticas associadas às regras
Compilação
Os geradores transformam os arquivos em código C/C++
Execução
O programa compilado realiza a análise completa da entrada
Este fluxo automatizado permite aos desenvolvedores concentrarem-se na especificação da linguagem em vez de se preocuparem com os detalhes de implementação do parser.
Exemplo de Arquivo .y: Expressões Aritméticas
Vejamos um exemplo completo de arquivo Yacc para análise de expressões aritméticas com operadores, parênteses e variáveis:
%{
#include 
#include 
void yyerror(char *s);
int yylex();
%}

%token NUMBER ID
%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS

%%

program:
    expr                { printf("Resultado: %d\n", $1); }
    ;

expr:
    expr '+' expr       { $$ = $1 + $3; }
  | expr '-' expr       { $$ = $1 - $3; }
  | expr '*' expr       { $$ = $1 * $3; }
  | expr '/' expr       { 
                          if ($3 == 0) {
                            yyerror("Divisão por zero");
                            $$ = 0;
                          } else {
                            $$ = $1 / $3;
                          }
                        }
  | expr '^' expr       { 
                          int i, result = 1;
                          for (i = 0; i < $3; i++)
                            result *= $1;
                          $$ = result;
                        }
  | '-' expr %prec UMINUS { $$ = -$2; }
  | '(' expr ')'        { $$ = $2; }
  | NUMBER              { $$ = $1; }
  | ID                  { $$ = /* valor da variável */; }
  ;

%%

void yyerror(char *s) {
    fprintf(stderr, "Erro: %s\n", s);
}

int main() {
    yyparse();
    return 0;
}
Este exemplo demonstra como definir precedência e associatividade de operadores, lidar com erros e associar ações semânticas a cada regra gramatical.
Yacc vs. Ferramentas em Python: Introdução ao ply.yacc
Para desenvolvedores Python, o PLY (Python Lex-Yacc) oferece funcionalidades equivalentes ao Yacc/Bison, com uma sintaxe mais integrada à linguagem Python.
Yacc/Bison
  • Linguagem específica para definição de gramáticas
  • Gera código C/C++
  • Mais estabelecido e otimizado
  • Melhor desempenho para compiladores de produção
  • Curva de aprendizado mais íngreme
PLY (Python)
  • Totalmente integrado com Python
  • Usa docstrings para definir a gramática
  • Mais fácil para prototipagem rápida
  • Melhor para ensino e projetos menores
  • Mais simples para quem já conhece Python
Ambas as abordagens seguem os mesmos princípios teóricos de parsing LR, mas com diferentes interfaces e linguagens de implementação. A escolha depende principalmente do contexto de uso e das necessidades específicas do projeto.
Vantagens das Ferramentas Automáticas na Prática
Redução da complexidade
A criação manual de um parser LR é extremamente complexa devido à quantidade de estados e tabelas envolvidas. Ferramentas automáticas eliminam essa complexidade, permitindo foco na gramática.
Detecção de ambiguidades
Geradores como Yacc e PLY identificam conflitos na gramática e reportam problemas potenciais, ajudando a refinar a definição da linguagem antes da implementação.
Manutenção simplificada
Alterações na linguagem requerem apenas modificações na especificação da gramática, não no código do parser. Isso facilita a evolução da linguagem ao longo do tempo.
Integração com ações semânticas
Ferramentas automáticas permitem associar código às regras gramaticais, facilitando a construção de árvores sintáticas, avaliação de expressões ou geração de código intermediário.
Estrutura Básica de um Parser com ply.yacc
O PLY (Python Lex-Yacc) permite criar parsers LR em Python com uma estrutura clara e intuitiva. Vejamos a estrutura básica de um arquivo usando ply.yacc:
import ply.yacc as yacc
import ply.lex as lex

# Definição do analisador léxico
tokens = (
    'NUMBER',
    'PLUS',
    'MINUS',
    'TIMES',
    'DIVIDE',
    'LPAREN',
    'RPAREN',
)

# Regras léxicas
t_PLUS    = r'\+'
t_MINUS   = r'-'
t_TIMES   = r'\*'
t_DIVIDE  = r'/'
t_LPAREN  = r'\('
t_RPAREN  = r'\)'
t_ignore  = ' \t'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

def t_error(t):
    print(f"Caractere ilegal '{t.value[0]}'")
    t.lexer.skip(1)

# Construir o lexer
lexer = lex.lex()

# Regras sintáticas
def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''
    if p[2] == '+'  : p[0] = p[1] + p[3]
    elif p[2] == '-': p[0] = p[1] - p[3]
    elif p[2] == '*': p[0] = p[1] * p[3]
    elif p[2] == '/': p[0] = p[1] / p[3]

def p_expression_group(p):
    'expression : LPAREN expression RPAREN'
    p[0] = p[2]

def p_expression_number(p):
    'expression : NUMBER'
    p[0] = p[1]

def p_error(p):
    if p:
        print(f"Erro de sintaxe em '{p.value}'")
    else:
        print("Erro de sintaxe no final da entrada")

# Construir o parser
parser = yacc.yacc()

# Função para testar
def parse(s):
    return parser.parse(s)
Esta estrutura integra o analisador léxico e sintático em um único arquivo Python, facilitando o desenvolvimento e manutenção.
Definindo as Regras com Precedência: %left, %right
Uma das vantagens do PLY é a facilidade para definir precedência e associatividade de operadores, resolvendo potenciais conflitos shift-reduce.
Tipos de Precedência
  • %left: Associatividade à esquerda (a+b+c = (a+b)+c)
  • %right: Associatividade à direita (a=b=c = a=(b=c))
  • %nonassoc: Sem associatividade (a>b>c é inválido)
A precedência é determinada pela ordem: operadores definidos depois têm maior precedência.
Exemplo em PLY
# Ordem de precedência (do menor para o maior)
precedence = (
    ('left', 'PLUS', 'MINUS'),
    ('left', 'TIMES', 'DIVIDE'),
    ('right', 'UMINUS'),  # Menos unário
)

def p_expression_uminus(p):
    'expression : MINUS expression %prec UMINUS'
    p[0] = -p[2]
A diretiva %prec permite atribuir uma precedência específica a uma regra, útil para casos como o menos unário, que tem precedência diferente do menos binário.
Funções Python como Produções da Gramática
No PLY, cada regra de produção é implementada como uma função Python, permitindo associar ações semânticas diretamente à análise sintática.
Estrutura da função
def p_nome_da_regra(p):
    'não_terminal : sequência de símbolos'
    # ou
    '''não_terminal : alternativa1
                   | alternativa2
                   | alternativa3'''
    # Ações semânticas aqui
    p[0] = ... # Valor retornado pelo não-terminal
Acesso aos valores
O parâmetro p é uma lista onde:
  • p[0]: Valor do não-terminal à esquerda
  • p[1]: Valor do primeiro símbolo à direita
  • p[2]: Valor do segundo símbolo à direita
  • E assim por diante...
Exemplo de uma função que implementa uma produção para declaração de variável:
def p_declaration(p):
    'declaration : TYPE ID ASSIGN expression SEMICOLON'
    p[0] = ('declare', p[1], p[2], p[4])  # Cria uma tupla representando a declaração
    symbol_table[p[2]] = {'type': p[1], 'value': None}  # Adiciona à tabela de símbolos
Esta abordagem permite construir facilmente árvores sintáticas abstratas, avaliar expressões em tempo de análise ou realizar outras ações semânticas.
Exemplo Completo: Analisador Sintático de Expressões
Vamos examinar um exemplo completo de analisador sintático para expressões aritméticas com variáveis, usando PLY:
import ply.yacc as yacc
import ply.lex as lex

# Definição do analisador léxico
tokens = ('NUMBER', 'ID', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', 'EQUALS')

# Regras léxicas
t_PLUS    = r'\+'
t_MINUS   = r'-'
t_TIMES   = r'\*'
t_DIVIDE  = r'/'
t_LPAREN  = r'\('
t_RPAREN  = r'\)'
t_EQUALS  = r'='
t_ID      = r'[a-zA-Z_][a-zA-Z0-9_]*'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

t_ignore = ' \t'

def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)

def t_error(t):
    print(f"Caractere ilegal '{t.value[0]}'")
    t.lexer.skip(1)

# Construir o lexer
lexer = lex.lex()

# Precedência e associatividade
precedence = (
    ('left', 'EQUALS'),
    ('left', 'PLUS', 'MINUS'),
    ('left', 'TIMES', 'DIVIDE'),
    ('right', 'UMINUS'),
)

# Dicionário para armazenar variáveis
variables = {}

# Regras de gramática
def p_statement_assign(p):
    'statement : ID EQUALS expression'
    variables[p[1]] = p[3]
    p[0] = ('assign', p[1], p[3])

def p_statement_expr(p):
    'statement : expression'
    p[0] = ('expr', p[1])

def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''
    if p[2] == '+'  : p[0] = ('add', p[1], p[3])
    elif p[2] == '-': p[0] = ('sub', p[1], p[3])
    elif p[2] == '*': p[0] = ('mul', p[1], p[3])
    elif p[2] == '/': p[0] = ('div', p[1], p[3])

def p_expression_uminus(p):
    'expression : MINUS expression %prec UMINUS'
    p[0] = ('neg', p[2])

def p_expression_group(p):
    'expression : LPAREN expression RPAREN'
    p[0] = p[2]

def p_expression_number(p):
    'expression : NUMBER'
    p[0] = ('num', p[1])

def p_expression_id(p):
    'expression : ID'
    p[0] = ('var', p[1])

def p_error(p):
    if p:
        print(f"Erro de sintaxe em '{p.value}'")
    else:
        print("Erro de sintaxe no final da entrada")

# Construir o parser
parser = yacc.yacc()

# Função para testar
def parse(s):
    return parser.parse(s)

# Exemplo de uso
resultado = parse("x = 10 + 20 * (30 - 5)")
print(resultado)
Este exemplo constrói uma árvore sintática abstrata para expressões aritméticas e atribuições, permitindo representar a estrutura da expressão para processamento posterior.
Execução Passo a Passo e Depuração
O PLY oferece recursos de depuração que facilitam a identificação e resolução de problemas durante o desenvolvimento do parser.
Ativando a depuração
# Modo detalhado de depuração
parser = yacc.yacc(debug=True)

# Ou na hora de analisar
resultado = parser.parse(texto, debug=True)
Com o modo de depuração ativado, o PLY mostra cada passo da análise, incluindo shifts, reduces e os estados da pilha.
Erros comuns
  • Conflitos shift-reduce: Gramática ambígua
  • Símbolos inalcançáveis: Regras definidas mas não utilizadas
  • Erros de tipagem: Valores incompatíveis nas ações semânticas
  • Regras não definidas: Símbolos utilizados mas não definidos
Para depurar efetivamente, é útil testar com expressões simples antes de avançar para casos mais complexos. A saída detalhada do modo de depuração permite visualizar exatamente como o parser está interpretando a entrada e quais decisões está tomando.
Atividade Prática: Parser para Expressões
Vamos implementar um parser para expressões aritméticas com parênteses e operadores básicos usando PLY.
Defina os tokens
tokens = (
    'NUMBER',
    'PLUS', 'MINUS', 'TIMES', 'DIVIDE',
    'LPAREN', 'RPAREN',
)
Implemente as regras léxicas
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t
Defina precedência
precedence = (
    ('left', 'PLUS', 'MINUS'),
    ('left', 'TIMES', 'DIVIDE'),
    ('right', 'UMINUS'),
)
Implemente as regras gramaticais
def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression'''
    # Implemente as operações aqui
Esta atividade prática permite aplicar os conceitos de análise sintática ascendente na construção de um parser funcional. Teste com expressões como "3 + 4 * (5 - 2)" para verificar o funcionamento correto.
Resumo da Aula
Parsing Bottom-Up
Analisamos o funcionamento da análise sintática ascendente, que parte dos tokens para o símbolo inicial.
Tabelas LR
Estudamos a construção de autômatos e tabelas LR(0), SLR e LR(1) para guiar o processo de análise.
Ferramentas Automáticas
Conhecemos ferramentas como Yacc/Bison e PLY para geração automática de parsers.
Implementação Prática
Implementamos um analisador sintático funcional para expressões aritméticas usando PLY.
Os parsers ascendentes são fundamentais na construção de compiladores modernos devido ao seu poder de reconhecimento e eficiência. As ferramentas automáticas estudadas facilitam significativamente a implementação, permitindo que os desenvolvedores se concentrem na gramática da linguagem em vez dos detalhes técnicos do parsing.
Na próxima aula, exploraremos como integrar a análise sintática com a análise semântica para criar compiladores completos.
Tarefa: Implementar um Parser com PLY
Sua tarefa é implementar um analisador sintático utilizando PLY para uma linguagem simples com comandos if, while e print.
Especificação da Gramática
program : statement_list

statement_list : statement
               | statement_list statement

statement : if_statement
          | while_statement
          | print_statement
          | assign_statement

if_statement : IF condition THEN statement_list END
             | IF condition THEN statement_list ELSE statement_list END

while_statement : WHILE condition DO statement_list END

print_statement : PRINT expression SEMICOLON

assign_statement : ID EQUALS expression SEMICOLON

condition : expression GREATER expression
          | expression LESS expression
          | expression EQUALS EQUALS expression

expression : expression PLUS term
           | expression MINUS term
           | term

term : term TIMES factor
     | term DIVIDE factor
     | factor

factor : NUMBER
       | ID
       | LPAREN expression RPAREN
Exemplo de Código Fonte
x = 10;
y = 20;

if x < y then
    print x;
else
    print y;
end

while x < 100 do
    print x;
    x = x + 10;
end
Requisitos
  • Implementar análise léxica com ply.lex
  • Implementar análise sintática com ply.yacc
  • Construir uma árvore sintática abstrata
  • Lidar adequadamente com os erros
Integrando o Parser com o Analisador Léxico
Para criar um compilador funcional, é essencial integrar o analisador léxico e o sintático de forma eficiente.
Comunicação entre analisadores
No PLY, o analisador sintático chama o léxico para obter tokens através da função lexer.token(). Esta integração é automatizada quando você constrói o parser:
# Construir o lexer
lexer = lex.lex()

# Construir o parser usando o lexer
parser = yacc.yacc()

# Analisar uma entrada
resultado = parser.parse(texto, lexer=lexer)
Compartilhando informações
É comum compartilhar informações entre os analisadores através de:
  • Objetos token: Adicionar atributos como lineno e lexpos
  • Estado global: Tabela de símbolos compartilhada
  • Contexto: Passar informações adicionais via parâmetros
A tabela de símbolos é frequentemente um componente central na integração, armazenando informações sobre identificadores que ambos os analisadores precisam acessar.
Aplicações Práticas do Parsing LR
Os conceitos de parsing LR têm aplicações que vão além da criação de compiladores tradicionais.
Compiladores
A aplicação clássica é na construção de compiladores para linguagens de programação, onde o parser transforma código fonte em árvores sintáticas para geração de código.
DSLs
Linguagens de domínio específico (DSLs) beneficiam-se de parsers para transformar notações especializadas em estruturas de dados processáveis.
Processamento de configuração
Arquivos de configuração complexos podem usar parsers LR para validar a sintaxe e converter em estruturas de dados internas.
Linguagens de consulta
Bancos de dados usam parsers LR para analisar consultas SQL e outras linguagens de consulta, transformando-as em planos de execução.
A compreensão dos princípios de parsing LR proporciona uma base sólida para enfrentar uma ampla gama de problemas de processamento de linguagens, desde compiladores completos até interpretadores de comandos simples.
Próximos Passos na Jornada de Compiladores
Após dominar a análise sintática ascendente, você está pronto para avançar para os próximos tópicos na construção de compiladores.
Análise Léxica
Tokenização e reconhecimento de padrões
Análise Sintática
Parsing descendente e ascendente
Análise Semântica
Verificação de tipos e escopo
Geração de Código
Tradução para código intermediário ou de máquina
Recomendamos que pratique a implementação de parsers para gramáticas cada vez mais complexas, explorando recursos avançados do PLY como precedência dinâmica e integração com sistemas de tipos.
Não se esqueça de consultar a documentação oficial do PLY e explorar exemplos práticos disponíveis online. A prática constante é a chave para dominar estas técnicas e aplicá-las em projetos reais.