Prévia do material em texto
Tradutores
Análise Sintática Bottom-Up
Sumário
Introdução
Analisadores Sintáticos Ascendentes
(Bottom Up)
Análise de Precedência de Operadores
Analisadores LR
LR canônico
SLR
LALR
Análise Sintática Bottom Up
Analisador
Léxico
Analisador
Sintático
Tabela de
Símbolos
token
Obtém prox.
token
Programa
fonte
Resto do
front end
Análise Sintática Bottom Up
Análise Sintática Bottom Up
Construção da árvode de derivação a partir
das folhas em direção à raiz
Gramáticas LR – Left to Right – Right
Most Derivation
Analisador Redutivo
Sentença de entrada é reduzida até o símbolo
inicial da gramática
Redução substituição do lado direito de uma
produção pelo símbolo não terminal
correspondente
Análise Sintática Bottom Up
Implementados com a utilização de um
autômato de pilha com o controle dirigido
por uma tabela de análise (tabela
sintática)
Processo
Transferir símbolos da fita de entrada para a
pilha até que se tenha na pilha o lado direito de
uma produção da gramática
Análise Sintática Bottom Up
Exemplo
Gramática
S [L] | a
L L;S | S
Derivação mais a direita ao reverso para a
entrada [a;a]
S [L] [L;S] [L;a] [S;a] [a;a]
Análise Sintática Bottom Up
Pilha Entrada Ação
$ [a;a]$ Empilha [
$[ a;a]$ Empilha a
$[a ;a]$ Reduz Sa
$[S ;a]$ Reduz LS
$[L ;a]$ Empilha ;
$[L; a]$ Empilha a
$[L;a ]$ Reduz Sa
$[L;S ]$ Reduz LL;S
$[L ]$ Empilha ]
$[L] $ Reduz S[L]
$S $ Entrada aceita!
Análise Sintática Bottom Up
Handle
Seqüências de símbolos que são lados direitos
de produção, tais que suas reduções levam, no
final, à redução para o símbolo inicial da
gramática.
Se uma gramática G não é ambígua, então
toda a forma sentencial gerada por G tem
exatamente um handle.
Análise Sintática Bottom Up
Handle
Analisador pode utilizar
informações que estão mais
abaixo na pilha para determinar
que produção utilizar
Análise Sintática Bottom Up
Ações possíveis para um analisador
bottom-up
Empilhar : coloca no topo da pilha o símbolo
lido e avança o cabeçote de leitura
Reduzir : Substitui o handle no topo da pilha
pelo não terminal correspondente
Aceitar : Reconhece que a sentença de
entrada foi gerada pela gramática
Emitir Erro: chama a rotina de tratamento de
erros
Conflitos
Para algumas gramáticas não é possível a
utilização de um analisador ascendente
Analisador chega em uma configuração em que
não é possível decidir entre reduzir ou empilhar
Conflito shift-reduce
Analisador chega em uma configuração em que
mais de uma produção pode ser utilizada em
uma redução
Conflito reduce-reduce
Conflitos
Exemplo
Conflito
shift-reduce
Conflitos
Exemplo 02
Produções envolvendo chamadas de procedimentos
e referências a índices de arranjos
Entrada: p(i,j)
Exercícios
Dada a seguinte gramática:
S → SS+ | SS* | a
Execute uma análise ascendente para a
seguinte entrada: aaa+a*+
Mostre a pilha e o restante da entrada a
em cada passo executado na seguinte
forma: ($pilha,entrada$)
Analisadores de Precedência de
Operadores
Utilização
Calculadoras
Perl 6 (em conjunto com recursivo descendente)
Operam sobre a classe de gramáticas de
precedência de operadores
Não terminais aparecem sempre separados por
símbolos terminais.
Nenhuma produção deriva a palavra vazia
E EOE
O + | - | * | / | **
Analisadores de Precedência de
Operadores
Vantagens
Bastante eficiente
Aplicada principalmente no reconhecimento de
expressões
Desvantagens
Dificuldade em lidar com operadores iguais que
possuam significados diferentes. Ex: operador
“-” pode ser unário ou binário.
Analisadores de Precedência de
Operadores
Funcionamento
Handle é identificado baseado nas relação de
precedência existente entre os tokens (operandos e
operadores).
Possíveis relações: <, > e =
Sendo a e b símbolos terminais, tem-se que:
a<b significa que a tem precedência menor que b
• Identifica o limite esquerdo do handle
a=b significa que a e b tem a mesma precedência
• Indica que os terminais pertencem ao mesmo handle
a>b significa que a tem precedência sobre b
• Identifica o limite direito do handle
Analisadores de Precedência de
Operadores
Funcionamento
Relações definem a identificação do handle
< identifica o limite esquerdo do handle
= identifica que os terminais pertencem ao mesmo
handle
> identifica o limite direito do handle
Analisador é guiado por uma tabela de
precedência, cujas relações definem o
movimento que o analisador deve fazer:
Empilhar, reduzir, aceitar ou chamar uma rotina de
erros
Analisadores de Precedência de
Operadores
Funcionamento
Tabela é uma matriz quadrada que relaciona
todos os terminais da gramática mais o
marcador $
Analisadores de Precedência de
Operadores
Funcionamento
Terminais nas linhas representam terminais no topo da
pilha
Terminais nas colunas representam terminais na
entrada
Sendo a o terminal mais ao topo da pilha e b o terminal
corrente na entrada, o analisador pode tomar a
seguintes decisões:
Se a<b ou a=b então empilha
Se a>b procura o handle na pilha (delimitado pelas
relações de precedência) e o substitui pelo não terminal
correspondente
Analisadores de Precedência de
Operadores
Movimentos do analisador
Entrada idvid&id
Analisadores de Precedência de
Operadores
Algoritmo do analisador
repita
se $S é o topo da pilha e $ está sob o cabeçote de leitura
então a entrada é aceita
senão /*seja a o terminal mais ao topo da pilha e b o terminal na entrada
se a < b ou a = b
então empilha b e avança para o próximo símbolo da entrada
senão se a > b
então repita /*reduzir*/
desempilha até encontrar a relação < entre o terminal do topo e o último
desempilhado
empilha o não terminal correspondente
imprime a produção aplicada
senão chama a rotina de tratamento de erro
Analisadores de Precedência de
Operadores
Construção da tabela de precedência de
operadores
Método intuitivo
Baseado no conhecimento da precedência e
associatividade dos operadores. Ex.: se * tem
precedência sobre +.
Método mecânico
Obtém a tabela diretamente a partir da gramática de
operadores desde que as produções reflitam a
associatividade e a precedência dos operadores.
Construção da tabela de precedência de
operadores
Método intuitivo
Conhecimento prévio da precedência e
associatividade dos operdadores.
Dois operadores: θ1 e θ2
Se o operador θ1 tem maior precedência que o
operador θ2 então θ1 (na pilha) > que θ2 (na
entrada), e θ2(na pilha) < θ1 (na entrada). Ex.: * > +,
logo *>+ e + < *
Se θ1 e θ2 têm igual precedência ou são iguais
• θ1>θ2 e θ2>θ1 – quando associativos a esquerda
• θ1<θ2 e θ2<θ1 – quando associativos a direita
Construção da tabela de precedência de
operadores
Método intuitivo (continuação)
As relações entre os operadores e os demais tokens
(operandos delimitadores) são fixas. Para todos os
operadores θ, tem-se:
θ < id θ < ( θ > ( θ > $
id > θ ( < θ ) > θ $ < θ
As relações entre os tokens que não são operadores
também são fixas:
( < ( ) > ) id > ( $ < (
( = ) ) > $ id > $ $ < id
( < id
Construção da tabela de precedência de
operadores
Exemplo:
E E+E | E*E | E**E | (E) | id
Tabela obtida pelo método intuitivo
Construção da tabela de precedência de
operadores
Operadores unários
No caso do operador “-” é difícil determinar a
precedência pois este pode ser tanto unário
quanto binário.
Possíveis soluções:
Analisador distinguiros dois tipos de operadores: - e
–u. Técnica utilizada pelo analisador da linguagem
Fortran
Analisador proibir a utilização do operador “-” unário.
(nada elegante). Ao invés de escrever –e o
programador teria que escrever 0-e.
Construção da tabela de precedência de
operadores
Método mecânico
Obtém as relações de precedência diretamente a partir
da gramática de operadores, a qual precisa ser não
ambígua.
Regras para a determinar as relações de precedência.
Sejam dois terminais a e b:
1. a=b se αaβbξ é lado direito de produção e β é ε ou um
único não terminal
2. a < b se αaXβ é lado direito de produção e X =>* ybξ
onde y é ε ou um não terminal. Também, $ < b se
S=>*ybξ, onde y é ε ou um não terminal
3. a > b se αXbβ é lado direito de produção e X =>* yaξ
onde ξ é ε ou um não terminal. Também a > $ se S
=>*ya ξ e ξ é ε ou um não terminal.
Construção da tabela de precedência de
operadores
Método Mecânico (continuação)
A regra 2 (αaXβ ) diz que um terminal a seguido
imediatamente de um não terminal X tem precedência
menor que os primeiros terminais deriváveis a partir de
X. Estes terminais estarão em um handle que será
reduzido antes do handle que contém a
A regra 3 (αXbβ ) diz que os últimos terminais que
podem ser derivados a partir de um não terminal X têm
precedência maior que um terminal que segue
imediatamente X. Estes terminais estarão num handle
que será reduzido antes do handle que contém b.
Funções de Precedência
Funções de precedência
Funções f e g que mapeiam símbolos terminais para
inteiros
Representação mais eficiente O(2*n)
Sejam a e b símbolos terminais. A determinação de f e
g é tal que:
f(a) < g(b) sempre que a < b
f(a) = g(b) sempre que a = b
f(a) > g(b) sempre que a > b
Na comparação de dois símbolos a e b usa-se a função
f para o símbolo da pilha e a função g para o símbolo
da entrada.
Algoritmo para encontrar as funções de
precedência
Entrada: matriz de precedência
Saída: funções de precedência (se existirem)
Método
Criar símbolos fa e ga para cada terminal a e para o símbolo $
Distribuir os símbolos criados em grupos, Se a=b, então fa e gb ficam
no mesmo grupo. Se a=b e c=b então fa e fc ficam no mesmo grupo
que gb. Se ainda c=d, então fa, fc, gb e gd ficam no mesmo grupo,
mesmo que a=d não ocorra
Gerar um grafo dirigido cujos nodos são os grupos anteriormente
formados. Para quaisquer a e b, se a > b, construir um arco do grupo
fa para o grupo gb e, se a < b, construir um arco do grupo gb para o
grupo fa. O grafo gerado é bipartido (não existem ligações entre dois
nodos f e dois nodos g)
Se o grafo contém ciclos, as funções de precedência não existem. Se
não houver ciclos, f(a) é igual ao comprimento do caminho mais longo
iniciando em f(a). Da mesma forma g(a) é igual ao comprimento do
caminho mais longo iniciando em g(a).
Algoritmo para encontrar as funções de
precedência
Analisadores Bottom-Up
Classe LR
Vantagem
Reconhecem praticamente todas as estruturas
sintáticas definidas por uma GLC.
Método mais geral de análise bottom-up
Descobre antecipadamente erros sintáticos
Desvantagem
Dificuldade de implementação
Analisadores Bottom-Up
Classe LR
SLR (Simple LR)
Fáceis de implementar
Aplicáveis a uma classe restrita de gramáticas
LR Canônico
Mais poderosos, podendo ser aplicados a um grande
número de linguagens livres de contexto
LALR (Look Ahead LR)
Nível intermediário e implementação eficiente. Funciona
para a maioria das linguagens de programação
Bison
• http://www.gnu.org/software/bison/
Analisadores Bottom-Up
Classe LR
Estrutura Geral
a1 .... ai .... an $
Analisador LR
s0
....
Xm-1
sm-1
Xm
sm
Entrada
Pilha
Saída
Ação Desvio
Analisadores Bottom-Up
Classe LR
Exemplo
(1) E E + T
(2) E T
(3) T T * F
(4) T F
(5) F (E)
(6) F id
Analisadores Bottom-Up
Classe LR
Funcionamento
Seja Em o estado no topo da pilha e ai o token
corrente na entrada. O analisador consulta a tabela
Ação[Em,ai] que pode conter os seguintes valores:
• Empilha Ex; causa o empilhamento de “aiEx”
• Reduz n (onde n é o número da produção A β): causa
o desempilhamento de 2r símbolos, onde r = |β|, e o
empilhamento de “AEy”, onde Ey resulta da consulta à
tabela Desvio[Em-r,A]
• Aceita: reconhece a sentença como válida
• Erro: identificação de um erro sintático
Analisadores Bottom-Up
Entrada id * id + id
(1) E E + T
(2) E T
(3) T T * F
(4) T F
(5) F (E)
(6) F id
Analisadores Bottom-Up
Analisadores LR
Funcionameto pode ser entendido através das
transformações que ocorrem na pilha e na fita de
entrada para cada ação. Configuração do analisador
(<pilha>,<entrada>)
Configuração inicial: (<E0>,<a1,a2,..an$>)
Supondo a seguinte configuração:
(<E0X1E1X2E2...XmEm>,<ai,ai+1...an$>)
Tem-se que a configuração resultante após cada ação é:
Ação[Em,ai] = empilha X
• (<E0X1E1X2E2...XmEmaiX>,<ai+1...an$>)
Ação[Em,ai] = reduz A β
• (<E0X1E1X2E2...Xm-rEm-rAEy>,<ai,ai+1...an$>)
Analisadores Bottom-Up
Classe LR
Construção de analisadores SLR
Baseada no conjunto canônico de itens LR(0)
Um item LR(0) para uma gramática G é uma
produção com um ponto em alguma posição do lado
direito.
Este ponto é utilizado como uma indicação de até
onde uma produção já foi analisada no processo de
reconhecimento
Analisadores Bottom-Up
Classe LR
Construção de analisadores SLR
Exemplo: a produção A XYZ origina quatro itens:
• A .XYZ
• A X.YZ
• A XY.Z
• A XYZ.
A produção A ε gera apenas um ítem:
• A .
Analisadores Bottom-Up
Classe LR
Construção de analisadores SLR
Requer duas operações
Acrescentar a gramática a produção S’ S (onde S
é o símbolo inicial da gramática)
Computar as funções closure e goto para a nova
gramática
Analisadores Bottom Up
Classe LR
Função closure
Se I é um conjunto de itens LR(0) para G,
então o conjunto de itens closure(I) é
construído a partir de I pelas regras:
1. Todo item em I pertence a closure(I)
2. Se A α.Xβ está no conjunto closure(I) e X y é
uma produção, então adicione X .y ao conjunto
Esta regra aumenta o conjunto com as produções dos
não terminais que aparecem com um ponto no lado
esquerdo.
Analisadores Bottom Up
Exemplo – Cálculo da função closure(I)
S a | [L]
L L ; S | S
Para I = {S [.L]} o conjunto closure(I) é
o seguinte:
closure({S [.L]}) = {S [.L], L .L;S, L.S,
S .a, S .[L]}
Analisadores Bottom Up
Classe LR
Função goto(I,X)
Informalmente representa o avanço do ponto sobre X
em I.
Consiste em coletar as produções com o ponto no lado
esquerdo de X, passar o ponto para o lado direito de X
e obter a função closure deste conjunto
Formalmente, para X (símbolo terminal ou não terminal
da gramática), goto(I,X) é a função closure do conjunto
de itens A αX.β tal que A α.Xβ pertence a I.
Analisadores Bottom Up
Exemplo – Cálculo da função goto(I,X)
Considerando o conjunto I = {S [L.],L L.;S}
goto(L,;) = {LL;.S, S.a, S.[L]}
Analisadores Bottom Up
Algoritmo para obter o conjunto canônico
de itens LR(0)
Para uma gramática G, o conjunto de itens LR
(0), referido por C, é obtido da seguinte
maneira:
Inicialização: C = {I0 = closure({S´.S})}
Para cada conjunto I em C e X símbolo de G, tal que
goto(I,X) ≠ ε, adicionar goto(I,X) a C
Até que todos os conjuntos tenham sido adicionados
a C
Analisadores Bottom Up
Construção da tabela SLR
A partir da gramática G, se obtém a gramática
aumentada G’ adicionando a produção S´ S.
A partir de G’ determina-se o conjunto canônico
C
A partir do conjunto de itens, a tabela é
construída
Analisadores Bottom Up
Algoritmo para construção databela SLR
Entrada: Conjunto C para G’
Saída: Tabela de análise SLR para G’ (se ela existir)
Método: Seja C = {I0, I1, I2,...,In}. Os estados do analisador são
0, 1, 2, ....n (0 é o estado inicial)
A linha i da tabela é construída a partir do conjunto Ii da
seguinte maneira:
1. Se goto(I,a) = Ij então Ação[i,a] = empilha j
2. Se Aα. está em Ii então para todo a em FOLLOW(A) fazer Ação
[i,a] = reduz n, onde n é o número da produção A α
3. Se S’S está em Ii então faça Ação[i,$] = aceita
Caso existam ações conflitantes, a gramática G não é SLR(1)
As transições para o estado i são construídas a partir da
seguinte regra
Se goto(Ii,A) = Ij, então Desvio[i,A] = j
Entradas não definidas pelas regras são consideradas
situações de erro
Analisadores Bottom Up
Exemplo
S’ S
1. Sa
2. S[L]
3. LL;S
4. L S
I0 = {S’.S, S.a, S.[L]}
goto(I0,S) = I1 = {S’S.}
goto(I0,a) = I2 = {Sa.}
goto(I0,[) = I3 = {S[.L], L.L;S, L.S, S,a, S.[L]}
goto(I3,L) = I4 = {S[L.], LL.;S}
goto(I3,S) = I5 = {LS.}
goto (I3,a) = I2
goto(I3,[)= I3
goto(I4,])= I6 = {S[L].}
goto (I4,;)= I7 = {LL;.S, S.a, S.[L]}
goto(I7,S)= I8 = {LL;S.}
goto(I7,a) = I2
goto(I7,[) = I3
Analisadores Bottom Up
C = {I1, I2, I3, I4, I5, I6, I7, I8}
“A tabela SLR é uma representação eficiente do autômato de
pilha que reconhece a linguagem.”
Exercícios
Considere a seguinte gramática:
1. E E + T | T
2. T T * F | F
3. F (E) | id
A. Obtenha a gramática aumentada
B. Construa o conjunto de itens LR(0)
C. Construa a respectiva tabela de análise
D. Mostre os passos realizados para a análise da
entrada id+id*id$
GNU Bison
Gerador de analisadores sintáticos
ascendentes
LALR
Recebe como entrada uma especificação
BNF
Gera como saída um analisador sintático
(parser) ascendente. Código C ou C++
GNU Bison
GNU Bison
http://www.gnu.org/software/bison/
GNU Bison Manual
http://www.gnu.org/software/bison/manual/
Understanding C parsers generated by
GNU Bison
http://cs.uic.edu/~spopuri/cparser.html
GNU Bison
Conceitos
Valores semânticos
Além do tipo, token armazena também um valor
semântico
Também aplicável a não terminais
• Ex.: uma expressão possui um valor semântico associado
Ações semânticas
Ações associadas a regras da gramática
• Código C
• Maioria das vezes utilizadas para calcular o valor semântico da
construção a partir dos valores semânticos de suas partes
GNU Bison
Formato do arquivo de entrada
GNU Bison
Seção “C declarations”
Variáveis utilizadas em ações
Includes
Seção “Yacc/Bison Declarations”
Nomes de símbolos terminais e não terminais
Precedência/Associatividade de operadores
Tipo associado ao valor semântico de cada
símbolo
GNU Bison
Seção “Grammar Rules”
Define como um símbolo não terminal deve ser
construído a partir de suas partes.
Produções da gramática
Seção “Additional C code”
Qualquer código C
Ex.: analisador léxico
GNU Bison
Integração com Flex
flex tokens.l
bison –y –d gramatica.y
gcc yytab.c lex.yy.c –o parser
GNU Bison
Exemplo 1 : calculadora simples
scalc.l
scalc.y
Exemplo 2: números romanos
romnum.l
romnum.y
Exemplo 3 : calculadora com variáveis
calcvar.l
calcvar.y
Exemplo 4: pascal simplificado
simpas.l
simpas.y