Teoria e Implementação de Linguagens Computacionais

Revisão 1º EE

André Ricardo Schäffer Lopes – arsl@cin.ufpe.br

Rodrigo Diego Melo Amorim– rdma@cin.ufpe.br

Níveis de Linguagem

Linguagem de máquina Linguagem de alto nível Linguagem de montagem

Assembly language

Processadores de Linguagens

Manipulam programas expressos em alguma linguagem de programação:

Compiladores Interpretadores

Tradutores e Compiladores

TradutorLinguagem fonte -> Linguagem destino

Chinês para inglêsJava para C

CompiladorLing. de alto nível -> Ling. de baixo nível

Interpretadores

Programa fonte -> executa imediatamenteLê, analisa e executa as instruções, uma

de cada vez

Compiladores x Interpretadores

Compiladores Tempo de espera pela compilação Execução dos programas com máxima

performance, em linguagem de máquina

Interpretadores Resultados imediatos Execução (de linguagem de alto nível) até 100

vezes mais lenta que a versão compilada

Uso de interpretadores

Programador trabalha em modo interativo Quer ver o resultado de uma instrução antes de

entrar na próxima

Execução de instruções apenas um vez, ou raramente

Programas descartáveis Em que a velocidade de execução não é tão

importante

Diagramas Tombstone

Programas

Máquinas

P

L

M

Diagramas Tombstone

ExecuçãoPrograma P rodando na máquina M

P

M

M

sort

PPC

PPC

sort

PPC

x86X

Diagramas Tombstone

Compiladores S

L

T

Diagramas Tombstone

Tradução

Um programa fonte P expresso na linguagem S -> um programa objeto expresso na linguagem T, usando um tradutor de S para T executando na máquina M?

Diagramas Tombstone

Tradução

P

S

P

TS

M

T

M

Diagramas Tombstone

Interpretador S

L

Diagramas Tombstone

Interpretação

Um programa P expresso em uma linguagem S, usando um interpretador de S executando na máquina M?

Diagramas Tombstone

S

M

P

S

M

Compilação em estágios

sort

Java

sort

CJava

x86

C

x86

C

x86

x86

x86

sort

x86

Cross-Compiler

Roda em uma máquina hospedeira, mas gera código para outra máquinaMáquina destino débil em memória,

compilador ou outras ferramentas

Exemplo

Cross-Compiler

sort

Java

sort

PPCJava

x86

PPC

x86

sort

PPC

PPC

Interpretive Compiler

Características de interpretadores e compiladores

Simples e rápido de traduzir para ela, e simples e rápida de interpretar

Exemplo: Java, no JDK

Java no JDK

Java

M

JVM JVM

M

Java

M

JVM

M

JVM

M

P

JVM

M

P

Java

P

JVM

Máquina Real x Abstrata

Projeto de uma nova máquina “Ultima”

P

Ultima

Ultima

M

M

P

Ultima

Ultima

Bootstrapping

Compilação de uma linguagem utilizando um compilador dessa mesma linguagemUtilizado para melhorar a eficiência de um

compiladorPrecisa de um compilador escrito em outra

linguagem que depois será descartado

Bootstrapping- melhorando a eficiência

Ada

Mslow

Mfast

Ada

Mslow

Mslow

Ada

Ada

Mfast

M

Bootstrapping- melhorando a eficiência

Ada

Mslow

Mfast

M

P

Ada

P

Mfast

M

P

Mfast

Bootstrapping- melhorando a eficiência

Ada

Mslow

Mfast

M

Ada

Ada

Mfast Ada

Mfast

Mfast

Especificação de Linguagens

Sintaxe A forma do programa

Organização das frases Palavras reservadas

Semântica estática (Restrições contextuais) Regras de escopo e regras de tipo

Semântica Significado do programa

O processo de Compilação

beginif x = 5 then...

1100111 0011100011

Código Fonte Compilador Programa

output+ params

Fases de Compilaçãoab

stra

ção

implem

entação

Código fonte

Tokens e Lexemas

Árvoresintáticaabstrata

Códigomáquina

AST decorada

Análise Léxica

Análise SintáticaAnálise Semântica

Geração de Código

Análise Léxica (Scanning)

Código fonte -> sequência de tokensSímbolos como identificadores, literais,

operadores, palavras-chave, pontuação etc.

if (n == 0) { return 1;} else { ...}

RPAR LCUR

RCUR

if LPAR

return

else

"n"id

"0"intLit

assign

"1"intLit comm

Análise Sintática

Agrupa caracteres ou Tokens em uma estrutura hierárquica com algum significado

Determina se uma dada cadeia de entrada pertence ou não à linguagem definida por uma gramática

int y = 0,k = 0;int x = y+++k;

A seguinte construção é válida?

Gramáticas – descrevendo Linguagens

Gramáticas Livres de Contexto são utilizadas para descrever linguagens de programação

ProduçõesSímbolos terminaisSímbolos não-terminaisSímbolo inicial

Exemplo

S → S ; S

S → id := E

S → print (L)

E → id

E → num

E → E + E

E → (S , E)

L → E

L → L , E

Terminais: id print , + ; := ( ) num Não terminas: S E L Símbolo inicial: S → é utilizado na notação de

produções

A cadeia seguinte pertence à gramática?

a := 7;

b := c + (d := 5 + 6, d)

Derivações

S S ; S S ; id := E id := E ; id := E id := num ; id := E id := num ; id := E + E id := num ; id := E + (S, E) id := num ; id := id + (S, E) id := num ; id := id + (id := E, E) id := num ; id := id + (id := E + E, E) id := num ; id := id + (id := E + E, id) id := num ; id := id + (id := num + E, id) id := num ; id := id + (id := num + num, id)

Parse treeS

SS

E

Eid :=;

E:=id

id

+ E

)( , ES

Eid :=id

EE +

num num

num

Construída conectando cada derivação à sua origem.

Obs. Na prática não é implementada pelos compiladores.

Gramática Ambígua

A partir dela uma sentença pode dar origem a mais de uma árvore de parsing diferente

Indeterminismo

Eliminação de ambigüidade

Refatoração da gramática

Exemplo

x := 1 + 2 + 3;

S

Eid :=

E + E

E + E num

num num

S

Eid :=

E + E

E + Enum

num num

Refatoração

S → S ; S

S → id := E

S → print (L)

E → id

E → num

E → E + E

E → (S , E)

L → E

L → L , E

S → S ; S

S → id := E

S → print (L)

E → id

E → num

E → E + T

E → T

E → (S , E)

L → E

L → L , E

Parsers

Avaliam uma entrada quanto à sintaxePodem ser

Top-down Recursive-descent / LL(k)

Bottom-up LR(k)

Recursive descent parser

Algoritmo baseado em previsões

Funções mutuamente recursivas

Simples implementaçãoUma função para cada não-terminalUma cláusula para cada produçãoVerifica o primeiro símbolo terminal para

decidir qual função usar

Exemplo

A ::= aBcC

B ::= CB | cC

C ::= da

parseA() { accept(‘a’); parseB(); accept(‘c’); parseC();}

parseB() { case (d): parseC(); parseB(); case (c): accept(‘c’); parseC();}

parseC() { accept(‘d’); accept(‘a’); }

Recursive descent parser

Na prática, constrói uma tabela de produções indexadas por não-terminais e terminais

A ::= aBcC

B ::= CB | CA

C ::= da

a c d

A A::= aBcC

B B::= CBB::= CA

C C::= da

Recursive descent parser

VantagensFácil de implementarFácil de entender

DesvantagensPerformance deficienteGramática reconhecida possui restrições

Sem recursão à esquerdaDeve estar fatorada

Recursive descent parser

A ::= aBcC

B ::= CB | CA

C ::= da

A ::= aBcC

B ::= CX

X ::= B | A

C ::= da

a c d

A A::= aBcC

B B::= CX

C C::= da

X X::=A X::=B

GramáticaLL(k)

Parsers LL(k)

Gramáticas SEM entradas duplicadas na tabela são conhecidas como LL(k)

LL(1) -> Left-to-right, leftmost-derivation, 1-symbol lookahead Left-to-right – direção na qual os símbolos serão examinados Leftmost-derivation – ordem pela qual os símbolos não-

terminais serão expandidos 1-symbol lookahead – não mais que um símbolo será

avaliado por vez

Também existem LL(2), LL(3),... Toda LL(1) é LL(2), toda LL(2) é LL(3),... LL(k)

Recursão à esquerda

Gramáticas LL(1) são vulneráveis a entradas duplicadas. Por exemplo, o fragmento a seguir:

E → E + TE → T

O fato de E aparecer no início do lado direito da produção é a causa do problema. Isso é conhecido como Recursão à Esquerda. Para corrigir, precisamos refatorar a gramática com Recursão à Direita:

E → T E´E´ → +T E´ E´ →

Parsers LR(k)

Supera as fraquezas de LL(k) LR(1) -> Left-to-right, rightmost-derivation, 1-

symbol lookahead

Uso de uma pilha para armazenar símbolos de forma temporária

Possui duas operações, shift e reduce shift - move o primeiro símbolo para o topo da pilha reduce - escolhe uma regra da gramática do tipo X→A B

C. pop C B A da pilha e push X.

Parsing LR- de Gramáticas Ambíguas

Gramáticas ambíguas ocasionam conflitos em parsers LR

Shift-reduce conflictO parser não consegue decidir se empilha o

próximo símbolo da entrada, ou se reduz para uma regra já disponível

Reduce-reduce conflictO parser pode realizar uma redução para duas

regras distintas

Parsing LR- de Gramáticas Ambíguas

Dangling-else

if a then if b then s1 else s2

if a then { if b then s1 else s2 }

if a then { if b then s1 } else s2

?

Parsing LR- de Gramáticas Ambíguas

Solução:Transformar a gramática

Introdução dos conceitos de matched e unmatched

S ::= 'if' E 'then' S 'else' SS ::= 'if' E 'then' SS ::= ...

S ::= M | U

M ::= 'if' E 'then' M 'else' M | ...

U ::= 'if' E 'then' S | 'if' E 'then' M 'else' U

Análise Semântica (Contextual)

Verifica se o programa está de acordo com as restrições contextuais da linguagem fonte

Em uma linguagem com tipos estáticos e ligação estática: Verifica regras de escopo Verifica regras de tipos

Duas fases: Identificação Verificação

Identificação

Faz a ligação entre uso de nomes e sua definição

Tabela de identificação (tabela de símbolos), com nome e atributos de cada identificador

Cada definição tem o seu escopo – parte do programa sobre a qual ela tem efeitoDelimitado por um bloco

Estrutura de blocosde um programa

Monolítica:O único bloco é o programa inteiro

Declarações estão em um escopo globalRegras de escopo:

Nenhum identificador pode ser declarado mais de uma vez

Nenhum identificador pode ser usado sem ter sido definido

Estrutura de blocosde um programa

PlanaO programa pode ser particionado em

vários blocos disjuntosDois níveis de escopo:

Escopo local: ocorrências de identificadores declarados localmente são restritos a um bloco em particular

Outras declarações têm escopo global

Estrutura de blocosde um programa

Aninhada Blocos podem ser aninhados um dentro do

outroVários níveis de escopo:

Declarações no nível mais externo têm escopo global (nível 1)

Declarações dentro de um bloco interno são locais ao bloco

Cada bloco está dentro de outro bloco, com um nível a mais

Passos

Travessia do programa fonteUm compilador de um passo atravessa o

programa uma única vezUm compilador de múltiplos passos faz

várias travessias

O projeto de um compilador é diretamente relacionado ao número de passos

Compilação em múltiplos passos

Módulo principal (driver)Chama cada um dos passos

Driver do Compilador

Analisador Sintático Analisador Contextual Gerador de Código

Compilação em passo único

Analisador sintáticoRealiza/chama as atividades à medida que

lê e reconhece o programa

Analisador Sintático

Analisador Contextual Gerador de Código

Driver do Compilador

Pontos relevantesno Projeto de um Compilador

Velocidade – possível vantagem para um passo

Espaço – possível vantagem para um passo

(dados x programa) Modularidade – vantagem de múltiplos passos

Flexibilidade – vantagem de múltiplos passos

Transformações/otimizações de programas – vantagem de múltiplos passos