Resumo das Aulas 04 a 06 de Tradutores (Professor Rezende)

Prévia do material em texto

semana 1 .semana 2 semana 3
aula 4: Implementação de linguagens. Interdependência de projetos de linguagens e processadores.
aula 5: Gramáticas Livre de Contexto. Métodos de parsing e formato BNF. Parsers. Análise da CFG.
aula 6: Análise Sintática Descendente. Tabelas de Parse LL(1). Rotinas sintáticas versus drivers.
Aula 4
24/11/98- Implementação de linguagens. Interdependência de projetos de linguagens e
processadores.
Regras de especificação de linguagens de programação
As regras de especificação de uma linguagem de programação atualmente podem ser
classificadas como
Sintáticas -
Lexicas: descrevem as unidades atômicas da linguagem em relação a um alfabeto de
entrada.
Livres de contexto: descrevem as construções permitidas na linguagem, através da
substituição de variáveis gramaticais por sequencias de variáveis e tokens (regras de
produção).
Semânticas -
Estáticas: descrevem as construções permitidas na linguagem, em regras que podem
ser descritas por atributos de lexemas mas que não têm expressão em termos de
produções gramaticais livres de contexto (Ex: regras de escopo, regras de
compatibilidade de tipos)
Dinâmicas: descrevem o comportamento dos elementos de um programa durante a
execução.
Modelos formais de especificação semântica
Operacional -
Descreve a execução de construções da linguagem através de sua interpretação em uma
máquina virtual
Axiomático -
Descreve a execução de construções da linguagem através de mudanças nas relações e
predicados entre variáveis do programa (úteis para verificar a correção de programas em
relação a especificações de mais alto nível, mas não conseguem descrever limitações de
recursos)
Denotacional -
Descreve a execução de construções da linguagem através de operações em um formalismo
algébrico inspirado nas construções sintáticas da linguagem
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
1 de 8 04/04/2018 15:17
Linguagens versus compiladores
Linguagens compiláveis precisam de um mínimo de estrutura estática em suas construções
para permitir alguma separação entre tradução e execução, não podendo conter operadores
cuja tradução requer informação presente apenas em tempo de execução.
Mínimo de estrutura estática para compilação -
Sintaxe
Escopo de identificadores
Amarração de tipos a ocorrencias de identificadores
Influências recíprocas entre linguagens e arquiteturas de processadores
A grande distância entre as linguagens de programação de alto nível e os circuitos lógicos
com base nos quais são projetados os processadores, permite estratégias distintas para o
delineamento da fronteira entre hardware (linguagem de maquina definida pelos
microprogramas do processador) e software (aplicativos e S.O.s)
CISC: esta filosofia de arquitetura de processadores (Complex Instruction Set
Computer) guia a construção de processadores em direção a projetos de circuitos que
buscam simpificar e agilizar o código para eles gerado por compiladores, visando
melhorar a eficiência destes, a um custo de maior complexidade para as instruções em
microcódigo e de seus circuitos.
RISC: esta filosofia de arquitetura de processadores (Reduced Instruction Set
Computer) guia a construção de processadores em direção a projetos de circuitos
simplificados e com paralelismo interno melhor explorado, visando melhorar sua
eficiência, a um custo de maior complexidade para os compiladores que irão para eles
gerar código.
Aula 5:
26/11/98- Gramáticas Livre de Contexto. Métodos de análise e formatos de CFGs. Parsers.
Análise da CFG.
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
2 de 8 04/04/2018 15:17
Gramáticas Livres de Contexto
O que são -
Gramáticas gerativas de Chomski Gque obedecem às seguintes carcterísticas:
G = (V,T,P,S)
V: Variáveis gramaticais;
T: símbolos Terminais (tokens);
P:{Pi: A® X1X2...Xm} = 
 regras de Produção Pi de G, 
 onde A ÎV; X ÎVÈT;
S: variável raiz de Sentença. (S ÎV)
Para que servem -
Especificar a estrutura das possíveis sentenças de uma linguagem no alfabeto T, deriváveis a
partir de S por sucessivas aplicações de produções deP (regras de produção) . As cadeias de
símbolos de VÈT abtidas com tais aplicações são chamadas formas sentenciais, e a aplicação
de uma regra de produção é chamada derivação de P.
Como funcionam -
Uma derivação substitui uma ocorrência da variável do lado direito da produção pelo
lado esquerdo, em uma forma sentencial de G. Uma derivação de P em (VÈT)* é
denotada por
gAg' Þ gX1X2...Xmg'
 Pi
e diz-se que a variável A foi expandida pela produção Pi (Pi substitui ocorrência de
Apor X1X2...Xm ).
Uma sequencia de derivações de P em (VÈT)* é chamada derivação sentencial de G,
abreviadamente uma derivação em G. Uma derivação em G é abreviadamente
denotada por
g0 Þ* gn
G
 representando uma cadeia de derivações gi-1 Þ gi de P, com 1 < i < n. Caso
exista uma tal cadeia, dizemos que gn é derivável a partir de g0 em G.
A linguagem gerada pela gramática G é o conjunto das formas sentenciais finais
(contendo apenas símbolos terminais) deriváveis a partir da variável raiz S. Estas
formas sentenciais finais são chamadas sentenças de L(G).
L(G)= {a1...ak |a1,..,ak ÎT Ù S Þ* a1...ak }
Notação e exemplos
Nestas notas de aula, usaremos a seguinte convenção acerca dos símbolos gramaticais,
empregados na especificação sintática de linguagens de programação:
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
3 de 8 04/04/2018 15:17
Simbologia
a,b...ÎT:letras inciais minúsculas do alfabeto latino designam símbolos terminais
(tokens);
A,B...ÎV:letras inciais maiúsculas do alfabeto latino designam variáveis gramaticais;
X,x,Y,y...ÎVÈT:letras finais do alfabeto latino designam símbolos de formas sentenciais;
[símbolos terminais ou variáveis gramaticais]
a,b,g...Î(VÈT)*: letras do alfabeto grego designam formas sentenciais da gramática.
[cadeias de símbolos terminais e/ou variáveis gramaticais] 
l.Î(VÈT)*: a forma sentencial vazia da gramática [cadeia com nenhum símbolo]
Exemplo de Gramática CFG
G0 =(V,T,P,S):
V = {<Prefix>, <Tail>, <Expr> };
T = {F, V, (, ), + };
P = {P1:<Expr> ® <Prefix> ( <Expr> )
P2:<Expr> ® V <Tail> 
P3:<Prefix> ® F
P4:<Prefix> ® l
P5:<Tail> ® + <Expr>
P6:<Tail> ® l };
S = <Expr>
O exemplo G0 acima especifica expressões formadas por chamada a função ou somas entre
variável e expressão, onde os argumentos dessas chamadas são também expressões. Se
F(V+V) for uma sentença de L(G0), haverá (pelo menos) uma cadeia de derivação S Þ*
F(V+V) em G0:
Exemplo de Derivação em uma gramática CFG
Métodos de Parsing
Objetivo
A análise sintática de uma sequência de tokens g = a1...ak consiste na reconstrução de uma
possível derivação de g em G -- ou da conclusão sobre sua inexistência -- identificando-se:
 1- as produções responsáveis por cada derivação;
2- as formas sentenciais intermediárias (caso haja na forma sentencial mais de uma
ocorrencia da variável a ser expandida) .
 S = g0 Þ g1 Þ g2Þ ... Þgn-1 Þ gn = g 
Dois métodos de análise sintática são hoje conhecidos para a implementação de parsers, que
a partir de uma ordenação fixa de P e de formas sentenciais a1...ak a serem analisadas,
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
4 de 8 04/04/2018 15:17
geram a sequência dos índices em P das produções responsáveis pelas derivações gi-1 Þ gi
de sua cadeia de derivação em G, caso exista.
Descendente (Top-down): Tenta identificar as produções responsáveis pela derivação
de g em G na sequencia S = g0 Þ g1; g1 Þ g2; ...g1n-1 Þ gn
Ascendente (Bottom-up): Tenta identificar as produções responsáveis pela derivação
de g em G na sequencia gn-1 Þ gn; gn-2 Þ gn-1; ...g1 Þ g0 = S
Análise sintática
Descendente Ascendente
S = g0 Þ g1 Þ ...gi-1Þ gi ... Þ gn-1Þ gn = g 
Pi ? 
 .
Estratégias
A arquitetura do parser busca eliminar graus desnecessários de liberdade na análise sintática,
através da vinculação de seus dois objetivos por meio da escolha antecipada da variável
expandida em cada derivação gi-1 Þ gi de P, adequada ao método de análise escolhido. Estas
escolhas antecipadas podem ser:
Derivação à esquerda (Leftmost derivation): Em cada derivação gi-1 Þ gi de P em S
Þ* g, a variável que ocorre mais à esquerda na forma sentencial gi-1 será expandida
por alguma produção de P. Neste caso denotamos esta derivação de g em G por S LÞ*
g.
Derivação à direita (Rightmost derivation): Em cada derivação gi-1 Þ gi de P em S
Þ* g, a variável que ocorre mais à direita na forma sentencial gi-1 será expandida por
alguma produção de P. Neste caso denotamos esta derivação de g em G por S RÞ* g.
A derivação à esquerda é adequada ao método descendente, enquanto a derivação à direita ao
método ascendente. Se G permite exatamente uma derivação à esquerta e uma derivação à
direita de qualquer sentença de L(G), então G é dita inambígua.
Parsers determínisticos
Um parser determinístico é um parser capaz de decidir a1...ak ÎL(G)?, e em caso afirmativo
construir uma única árvore de derivação de a1...ak em G.
Para atender as necessidades da análise sintática de um compilador atual, um parser precisa
ser determinístico e de complexidade linear. (tempo de execução e armazenamento
temporário O(k)). A inambiguidade de G é condição necessária -- mas não suficiente -- para
a linguagem por ela gerada ser reconhecível por um parser determinístico com estas
características.
.
Representação
Uma derivação S Þ* g em G corresponde a uma árvore, onde as ramificações representam
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
5 de 8 04/04/2018 15:17
produções e a concatenação das folhas a1,...,ak produz a sentença g = a1...ak gerada por
esta derivação. Esta árvore é chamada Arvore de derivação (árvore de parse) de g em G.
Se a gramática G for inambígua esta árvore será única, correspondendo a uma única
derivação à esquerda S LÞ* g e uma única derivação à direita S RÞ* g de a1...ak em G. Os
nomes dos métodos de parsing se referem à construção desta árvore, e portanto:
Um parser determinístico que use o método descendente e estratégia adequada a este
método listará -- do começo ao fim -- as produções de S LÞ* g enquanto tenta
construir -- da raiz às folhas -- a árvore de derivação de a1...ak em G.
Um parser determinístico que use o método ascendente e estratégia adequada a este
método listará -- do fim ao começo -- as produções de S RÞ* g enquanto tenta
construir -- das folhas à raiz -- a árvore de derivação de a1...ak em G.
Exemplo de parsing 
Derivação a ser construída na gramática G0 (como no exemplo acima)
<E> Þ* F(V+V)
Método descendente Método ascendente 
.
O formato BNF
O que é (Bachus-Naum Form):
Convenção para codificação abreviada de gramáticas livre de contexto que especificam
linguagens de programação.
O que faz:
Padroniza formatos para arquivos de entrada das ferramentas que geram parsers para estas
linguagens.
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
6 de 8 04/04/2018 15:17
Como é descrito:
Regras léxicas que distinguem entre terminais e variáveis gramaticais, possibilitando
uma crítica da entrada de dados pela ferramenta de geração de parser (ex.: símbolos ou
produções inúteis).
Regras de compactação de notação que, via símbolos de controle, representam
produções que expandem a mesma variável ou que implementem recursão na
linguagem (os símbolos de controle funcionam como macros para a ferramenta de
geração de parsers)
Exemplo de implementação de BNF
Notação compacta Produções expandidas
Classificação de Parsers
Quanto ao exame antecipado de tokens:
Lookahead.
Quanto à direção da leitura de tokens:
L ou R
Quanto à estratégia de análise:
L ou R.
Análise da Gramática
First.
Follow.
Predict.
Aula 6
27/11/98- Análise Sintática Descendente. Tabelas de Parse LL(1). Rotinas sintáticas versus
drivers.
.
Predição de produções
O que é -
Tomada de decisão sobre que produção aplicar.
O que deve ser feito -
Montar-se uma tabela que codifica possibilidades.
Como deve ser feito -
Calculando-se Pretict( Pi ).
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
7 de 8 04/04/2018 15:17
Gramáticas e tabelas de parse LL(1)
Quais são -
Propriedades
Como montar a tabela de predições -
 Calcula-se os predicts, tabula-se as predições e verifica-se ausencia de conflitos.
Como usar a tabela de predições -
Parser dirigido por tabela com descendencia recursiva.
Parser dirigido por tabela com descendencia driver
Construção de Parsers Descendentes Recursivos com rotinas semanticas
Construção de Parsers Descendentes Recursivos com driver
próxima aula
________________{CONTINUAMENTE EM CONSTRUÇÃO}___________________
Alerta:Nenhum conteúdo desta página dever ser entendido como definitivo.
Consulte-a periodicamente para atualizar-se com correções e inclusões
materia http://cic.unb.br/~rezende/compiladores_files/materia2.htm
8 de 8 04/04/2018 15:17