Construção de Compiladores
Análise Sintática
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Tem a função de combinar a lista de tokens
 Criação de uma estrutura chamada Árvore Sintática
atribuição
identificador
:=
expressão
expressão
+
expressão
identificador
número
SOMA
35
SOMA
• A analise sintática também deve rejeitar tokens inválidos
 Reportar erros sintáticos
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• A análise sintática é mais complexa em natureza
do que a análise léxica
 Precisamos de uma linguagem mais avançada
• Hierarquia de Chomsky
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Tente representar as seguintes linguagens com
uma gramática regular
 L1 = {anbn | n  0 }
 L2 = {anbman | n  0, m  1}
 Relembrando as regras da gramática regular
A  wB
Aw
A
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Exemplo mais concreto
 Expressões aritméticas
 Num[[+|-|x|/]num]*
Modifique de forma a suportar “(“ e “)”
 Como representar casamento de parênteses?
 Não é possível contar o número de parênteses “não
casados” ou abertos
 Como estabelecer precedências?
 O string é tratado como uma expressão plana, não tendo
estrutura
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Linguagens Livre de Contexto
 “Constituem um conjunto de linguagens que podem
ser geradas por gramáticas livre de contextos (GLC),
reconhecidas por autômatos de pilha”
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Autômato de Pilha
 É uma 7-tupla < , Q, , , q0, I, F>, onde:







, alfabeto de símbolos de entrada
Q, conjunto finito de estados possíveis do autômato
, alfabeto da pilha
, função de transição : Q x (  {}) x   Q x *
q0, estado inicial tal que q0  Q
I, símbolo inicial da pilha
F, conjunto de estados finais, tais que F  Q
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Autômato de Pilha (exemplo)
 Seja A = < , Q, , , q0, I, F>
Σ = {a, b}
Γ = {X, A}
I=X
Q = {0, 1, 2}
q0 = 0
F = {2}
A função δ:{0,1,2}×{a,b,ε}×{X,A} → P({0,1,2}×{X,A}*) é dada por
δ(0, a, X) → {(0, AX)}
Empilhou A
δ(1, b, A) → {(1, ε)}
Desempilhou A
δ(0, a, A) → {(0, AA)}
Empilhou A
δ(1, ε, X) → {(2, X)}
Não fez nada
δ(0, b, A) → {(1, ε)}
Desempilhou A
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Autômato de Pilha (exemplo)
 Detalhes da notação:
A
 Símbolo ε no resultado da função indica um pop
– δ(1, b, A) = {(1, ε)}
X
X
A
X
A
X
 Nas operações de push, sempre é representado o antigo
topo da pilha no resultado
– δ(0, a, X) = {(0, AX)}
Antigo topo da pilha
 Operações de push podem empilhar mais do que um
elemento
– δ(0, a, X) = {(0, XXAX)}
X
Universidade Federal da Paraíba
Departamento de Informática
X
X
A
X
Análise Sintática
• Gramáticas livre de contexto
 Quádrupla G = (N, T, P, S), onde:




N, conjunto finito de símbolos não-terminais
T, conjunto finito de símbolos terminais
P, conjunto finito de regras gramaticais na forma   
S, símbolo inicial da gramática pertencente a N
 Regras gramaticais (P) na forma:
 N
   (N T)*
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Gramáticas livre de contexto (exemplos)
 A linguagem L1 = {anbn | n  0 } é gerada por qual
gramática?
 A linguagem L2 = {anbman | n  0, m  1} é gerada por
qual gramática?
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• E o balanceamento de parênteses e a
precedência de operadores?
Exp  Exp + Exp
Exp  Exp - Exp
Exp  Exp * Exp
Exp  Exp / Exp
Exp  numero
Exp  (Exp)
Gramática para expressões aritméticas simples
Universidade Federal da Paraíba
Departamento de Informática
Análise Sintática
• Outro exemplo em programação
Stat  Id := Exp
Stat  Stat;Stat
Stat  if Exp then Stat else Stat
Stat  if Exp then Stat
Gramática para statements
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• A maioria dos construtores das LP´s são
expressos em GLC
 Linguagens são projetadas a partir de GLC
• É comum dividir os construtores em categorias
sintáticas que englobam algum conceito particular
 Expressões: usada no cálculo de valores
 Statements: ações que ocorrem em um fluxo
 Declarações: propriedades dos nomes usados em
outras partes do programa
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Cada categoria sintática é denotada por um não
terminal principal
 Exp
 Sif
 Swh
 Sat
 ...
• Categorias sintáticas podem se referir a não
terminais de outras categorias
 Podem também ser recursivas
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Derivações
 Método de reescrever as regras gramaticais através de
substituição dos seus símbolos não-terminais
 As substituições devem ser feitas até que apenas
restes símbolos terminais
 A seqüência de terminais restante deve ser definida
pela linguagem
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Definição formal para derivação
 A relação de derivação “” é definida via três regras
 N   , se existe uma regra N  
 
   , se existe um  tal que    e   
 Note que ,  e   (T  N)*
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Definição baseada em derivação para uma
linguagem gerada por uma GLC
 Dado uma GLC G com símbolo inicial S, símbolos
terminais T e produções P, a linguagem L(G) que
G gera é definida para ser o conjunto de todas as
strings de símbolos terminais que podem ser
obtidas por derivação a partir de S usando as
produções P, ou seja, o conjunto {w  T* | S  w}
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Exemplo
 Dado a gramática G, verifique se o string aabbbcc
pertence a L(G)




TR
T  aTc
R
R  RbR
Reposta?
T
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Diferentes derivações para a mesma questão
 Qual a diferença?
 Derivação mais a esquerda X Derivação mais a direita
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Árvore Sintática
 Pode ser representada como uma árvore
 A raiz é o símbolo inicial
 Resultados da produção dos símbolos não terminais são
filhos
 As folhas devem conter apenas símbolos terminais
 Lendo as folhas da esquerda para a direita temos a palavra
derivada
 Produções que levam ao vazio também devem ser
representadas, apesar de serem ignoradas na formação da
palavra
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Dada uma gramática G, a escolha da produção a ser
derivada influencia na forma da árvore sintática




TR
T  aTc
R
R  RbR
-Árvores sintática para a
palavra aabbbcc
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Quando uma gramática permite diferentes
árvores sintáticas ela é dita ambígua
• Quando usamos gramáticas para impor estrutura
sobre um conjunto de tokens, tal estrutura tem
que ser sempre a mesma
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Exemplo de problema
 Produções
E  E + E | E * E | Numero
 Como gerar a sentença
 3+4*5
E  E + E  Numero + E  3 + E  3 + E * E  3 + Numero * E
 3 + 4 * E  3 + 4 * Numero  3 + 4 * 5
E  E * E  E + E * E  Numero + E * E  3 + E * E  3 + Numero * E
 3 + 4 * E  3 + 4 * Numero  3 + 4 * 5
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Exemplo de problema
E  E + E  Numero + E  3 + E  3 + E * E  3 + Numero * E
 3 + 4 * E  3 + 4 * Numero  3 + 4 * 5
E  E * E  E + E * E  Numero + E * E  3 + E * E  3 + Numero * E
 3 + 4 * E  3 + 4 * Numero  3 + 4 * 5
23
Universidade Federal da Paraíba
Departamento de Informática
35
Analise Sintática
• Em muitos (mas não todos) os casos, uma
gramática ambígua pode ser reescrita em uma
gramática não-ambígua
 Outra opção é o uso de semântica externa para
decidir pela árvore correta
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Precedência de operadores
 Explicitar precedência nas gramáticas
 2+3*5
 Como tirar essa ambigüidade?
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Alguns conceitos iniciais
 Operador  pode ser associativo a esquerda
 Operador  pode ser associativo a direita
 Operador  pode ser não associativo
• Convenção
 - e / são obrigatoriamente associativos a esquerda
 + e * são opcionalmente associativos a esquerda
 Exemplo de operador associado a direita
 a=b=c {atribuição em C} a=(b=c)
 Exemplo de operador não associativo
 2 < 3 < 4 {comparação em Pascal} Não permitido
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguas
 Considere a seguinte gramática ambígua:
EEE
E  num
 Como torná-la não ambigua?
 Se  é associativo a esquerda, devemos forçar a gramática a
ser recursiva a esquerda
E  E  E’
E  E’
Única árvore que
pode se gerada
Universidade Federal da Paraíba
Departamento de Informática
E’  num
Analise Sintática
• Reescrevendo expressões gramaticais ambíguas
 E se for associativa a direita?
 Forçar a gramática a ser recursiva a direita
E  E’  E
E  E’
E’  num
 E se for não associativa?
 Sem regras recursivas
E  E’  E’
E  E’
E’  num
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguas
 Expandindo a idéia...
 Operadores com a mesma precedência
E  E + E’
E  E - E’
E  E’
E’  num
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguas
 Expandindo a idéia...
 Operadores com diferentes precedências
Exp  Exp + Exp2
Exp  Exp - Exp2
Exp  Exp2
Exp2  Exp2 * Exp3
Exp2  Exp2 / Exp3
Exp2  Exp3
Exp3  num
Exp3  (Exp)
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Outras fontes de ambigüidade
 Exemplo clássico do “else” em comandos de decisão
If p then if q then s1 else s2
 A convenção é casar o “else” com o “if” mais perto
que ainda não tenha sido casado
 Como representar isso na gramática?
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• If-the-else podem ser tratados como operadores
associativos a direita
• Quando um “if” e um “else” casam, todas as
ocorrências entre eles devem estar casadas
• Precisamos de dois símbolos não-terminais
 Matched: condicionais com o “else”
 Unmatched: condicionais sem o “else”
Universidade Federal da Paraíba
Departamento de Informática
Analise Sintática
• Gramática não ambígua para comandos
Stat
 Stat2 ; Stat
Stat
 Stat2
Stat2
 Matched
Stat2
 Unmatched
Matched  if Exp then Matched else Matched
Matched  id := Exp
Unmatched  if Exp then Matched else Unmatched
Unmatched  if Exp then Stat2
Universidade Federal da Paraíba
Departamento de Informática