Universidade Federal da ParaíbaDepartamento de Informática
Construção de Compiladores
Análise Sintática
Universidade Federal da ParaíbaDepartamento 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
• A analise sintática também deve rejeitar tokens inválidos Reportar erros sintáticos
atribuição
identificador
identificador
expressão
expressãoexpressão
número
:=
35SOMA SOMA
+
Universidade Federal da ParaíbaDepartamento de Informática
Análise Sintática
• A análise sintática é mais complexa em natureza do que a análise léxicaPrecisamos de uma linguagem mais avançada
• Hierarquia de Chomsky
Universidade Federal da ParaíbaDepartamento de Informática
Análise Sintática
• Tente representar as seguintes linguagens com uma gramática regularL1 = {anbn | n 0 }
L2 = {anbman | n 0, m 1}
Relembrando as regras da gramática regularA wB
A w
A
Universidade Federal da ParaíbaDepartamento de Informática
Análise Sintática
• Exemplo mais concretoExpressões aritméticas
Num[[+|-|x|/]num]*
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
Modifique de forma a suportar “(“ e “)”
Universidade Federal da ParaíbaDepartamento 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íbaDepartamento 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íbaDepartamento de Informática
Análise Sintática
• Autômato de Pilha (exemplo)Seja A = < , Q, , , q0, I, F>
Σ = {a, b} Q = {0, 1, 2}Γ = {X, A} q0 = 0I=X 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)}δ(1, b, A) → {(1, ε)}δ(0, a, A) → {(0, AA)}δ(1, ε, X) → {(2, X)}δ(0, b, A) → {(1, ε)}
Desempilhou A
Não fez nada
Empilhou ADesempilhou A
Empilhou A
Universidade Federal da ParaíbaDepartamento de Informática
Análise Sintática
• Autômato de Pilha (exemplo)Detalhes da notação:
Símbolo ε no resultado da função indica um pop– δ(1, b, A) = {(1, ε)}
Nas operações de push, sempre é representado o antigo topo da pilha no resultado
– δ(0, a, X) = {(0, AX)}
Operações de push podem empilhar mais do que um elemento
– δ(0, a, X) = {(0, XXAX)}
XA
X
A
XA
X
Antigo topo da pilha
X XA
X
X
Universidade Federal da ParaíbaDepartamento de Informática
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íbaDepartamento 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íbaDepartamento 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íbaDepartamento 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íbaDepartamento de Informática
Analise Sintática
• A maioria dos construtores das LP´s são expressos em GLCLinguagens são projetadas a partir de GLC
• É comum dividir os construtores em categorias sintáticas que englobam algum conceito particularExpressões: usada no cálculo de valoresStatements: ações que ocorrem em um fluxoDeclarações: propriedades dos nomes usados em
outras partes do programa
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• Cada categoria sintática é denotada por um não terminal principalExpSifSwhSat ...
• Categorias sintáticas podem se referir a não terminais de outras categorias Podem também ser recursivas
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• DerivaçõesMétodo de reescrever as regras gramaticais através de
substituição dos seus símbolos não-terminaisAs substituições devem ser feitas até que apenas
restes símbolos terminaisA seqüência de terminais restante deve ser definida
pela linguagem
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• Definição formal para derivaçãoA 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íbaDepartamento de Informática
Analise Sintática
• Definição baseada em derivação para uma linguagem gerada por uma GLCDado 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íbaDepartamento de Informática
Analise Sintática
• ExemploDado 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íbaDepartamento 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íbaDepartamento de Informática
Analise Sintática
• Árvore SintáticaPode 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íbaDepartamento de Informática
Analise Sintática
-Árvores sintática para a palavra aabbbcc
• 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
Universidade Federal da ParaíbaDepartamento 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íbaDepartamento de Informática
Analise Sintática
• Exemplo de problemaProduçõ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íbaDepartamento 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
3523
Universidade Federal da ParaíbaDepartamento de Informática
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íguaOutra opção é o uso de semântica externa para
decidir pela árvore correta
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• Precedência de operadoresExplicitar precedência nas gramáticas
2 + 3 * 5
Como tirar essa ambigüidade?
Universidade Federal da ParaíbaDepartamento 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íbaDepartamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguasConsidere a seguinte gramática ambígua:
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 num
E E E’
E E’
E’ numÚnica árvore que pode se gerada
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguasE se for associativa a direita?
Forçar a gramática a ser recursiva a direita
E se for não associativa? Sem regras recursivas
E E’ E
E E’
E’ num
E E’ E’
E E’
E’ num
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguasExpandindo a idéia...
Operadores com a mesma precedência
E E + E’
E E - E’
E E’
E’ num
Universidade Federal da ParaíbaDepartamento de Informática
Analise Sintática
• Reescrevendo expressões gramaticais ambíguasExpandindo 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íbaDepartamento de Informática
Analise Sintática
• Outras fontes de ambigüidadeExemplo clássico do “else” em comandos de decisão
A convenção é casar o “else” com o “if” mais perto que ainda não tenha sido casado
Como representar isso na gramática?
If p then if q then s1 else s2
Universidade Federal da ParaíbaDepartamento 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íbaDepartamento 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