Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

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 Sa 
$[S ;a]$ Reduz LS 
$[L ;a]$ Empilha ; 
$[L; a]$ Empilha a 
$[L;a ]$ Reduz Sa 
$[L;S ]$ Reduz LL;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,;) = {LL;.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.  Sa 
2.  S[L] 
3.  LL;S 
4.  L S 
I0 = {S’.S, S.a, S.[L]} 
goto(I0,S) = I1 = {S’S.} 
goto(I0,a) = I2 = {Sa.} 
goto(I0,[) = I3 = {S[.L], L.L;S, L.S, S,a, S.[L]} 
goto(I3,L) = I4 = {S[L.], LL.;S} 
goto(I3,S) = I5 = {LS.} 
goto (I3,a) = I2 
goto(I3,[)= I3 
goto(I4,])= I6 = {S[L].} 
goto (I4,;)= I7 = {LL;.S, S.a, S.[L]} 
goto(I7,S)= I8 = {LL;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

Mais conteúdos dessa disciplina