Teoria e Implementação de
Linguagens Computacionais – IF688
• Professor: André Santos
• Home page do curso:
http://www.cin.ufpe.br/~if688
• Newsgroup do curso:
news://news.cin.ufpe.br/if688
Motivação
• Conhecimento das estruturas e algoritmos usados
na implementação de linguagens: noções
importantes sobre uso de memória, eficiência, etc.
• Aplicabilidade freqüente na solução de problemas
que exigem alguma forma de tradução entre
linguagens ou notações.
• Implementação de linguagens para um domínio
específico.
Motivação
• A disciplina de implementação de
linguagens faz uso de um grande número de
conceitos estudados em outras disciplinas
do curso:
• Introdução à Programação, Algoritmos e
Estruturas de Dados, Infraestrutura de
software, Infraestrutura de Hardware,
Paradigmas de LP, Informática Teórica,…
Introdução
1. Linguagens de programação de alto nível
x Linguagens de programação de baixo
nível
2. Processadores de linguagens
3. Especificação da sintaxe e semântica de
linguagens de programação
Níveis de Linguagens de
Programação
• Linguagens de programação são uma
notação formal para expressar algoritmos
• Além de poder expressar e analisar
algoritmos, programadores precisam de
meios para editar, traduzir e interpretar os
programas em um computador: precisam de
Processadores de Linguagens de
Programação
Linguagem de Máquina
• Computadores entendem código de
máquina ou linguagem de máquina:
seqüência de instruções primitivas
expressas por uma seqüência de bits, que é
interpretada para executar uma determinada
operação (primitiva): carregar dados, somar
registradores, desvios condicionais e
incondicionais, etc.
Linguagem de Máquina
• Originalmente se escrevia diretamente em
linguagem de máquina:
0000 0001 0011 0010
• Problemas: dificuldade em ler, escrever,
editar; controle explícito dos endereços de
memória para dados e para o próprio
programa;
• Limite: alguns milhares de instruções
Linguagem de Montagem
• Notação simbólica para facilitar a escrita, leitura e
edição:
LOAD x
ADD R1 R2
JUMPZ h
• Tradução para linguagem de máquina: montagem
do programa
• Assembly language
• Uso de um programa montador (assembler)
• Instruções ainda muito próximas da linguagem de
máquina (relação de 1 para 1)
Linguagens de Programação de
alto nível
• Maior nível de abstração:
let s = (a+b+c)/2
in sqrt (s*(s-a)*(s-b)*(s-c))
• Ao invés de:
LOAD R1 a; ADD R1 b; ADD R1 c; DIV R1 #2;
LOAD R2 R1; LOAD R3 R1; SUB R3 a;
MULT R2 R3; LOAD R3 R1; SUB R3 b;
MULT R2 R3; LOAD R3 R1; SUB R3 c;
MULT R2 R3; LOAD R0 R2; CALL sqrt;
Linguagens de alto nível devem
suportar os seguintes conceitos:
• uso de expressões, usando notação semelhante à
matemática;
• tipos de dados primitivos e compostos;
• estruturas de controle como if-then-else, while,
for etc.;
• declarações de variáveis, tipos, funções,
procedimentos etc.;
• abstração: o que é feito x como é feito;
• encapsulamento (ou abstração de dados): classes,
pacotes, módulos (orientação a objetos).
Processadores de Linguagens de
Programação
• Sistemas que manipulam programas
expressos em alguma linguagem de
programação: editores, tradutores,
compiladores, interpretadores.
• Ferramentas de software (Unix) x
processadores integrados (IDEs: Integrated
Development Environments)
• Exemplo: JDK x JBuilder
Especificação de Linguagens de
Programação
• Projetista (designer): projeta linguagens de
programação;
• Implementador: implementa uma linguagem;
• Programador: é usuário da linguagem.
• Todos devem ter o mesmo entendimento da
linguagem: ter como referência a especificação da
linguagem
Especificação de Linguagens de
Programação
• Sintaxe: define a forma do programa: palavras
reservadas, organização das frases;
• Restrições contextuais (semântica estática): regras
de escopo e regras de tipo;
• Semântica: significado do programa. Podemos ver
o significado do programa como uma função
mapeando a entrada no resultado (denotacional);
ou baseado no seu comportamento (operacional);
Especificação de Linguagens de
Programação
• Especificação informal: texto em linguagem
natural (inglês ou outra). Riscos: especificação
imprecisa, incompleta ou ambígua.
• Especificação formal: consistente, completa, não
ambígua. Porém mais difícil de escrever e difícil
de ser entendida por pessoas que não conhecem a
notação utilizada.
Especificação de Linguagens de
Programação
• Na prática:
– especificação formal da sintaxe
– Especificação informal das restrições
contextuais e da semântica
Sintaxe
• É especificada usando gramáticas livres de
contexto (BNF – Backus-Naur Form):
– Conjunto finito de símbolos terminais:
‘>=’, ‘while’, ‘;’.
– Conjunto finito de símbolos não-terminais:
Programa, Comando, Expressão, Declaração.
– Um Símbolo inicial (um dos não-terminais):
Programa
– Conjunto finito de regras de produção.
Mini-Triangle: Terminais
• begin
in
if
(
/
const
let
;
)
<
do
then
:
+
>
else
var
:=
=
end
while
~
*
\
Mini-Triangle: Não-terminais
• Program
single-Command
primary-Expression
Declaration
Single-Declaration
Type-denoter
Integer-Literal
Command
Expression
V-name
Operator
Identifier
Mini-Triangle: Produções
• Program ::= single-Command
Command ::= single-Command
| Command ; single-Command
Mini-Triangle: Produções
• single-Command ::=
V-name := Expression
| Identifier ( Expression )
| if Expression
then single-Command
else single-Command
| while Expression
do single-command
| let Declaration
in single-Command
| begin Command end
Mini-Triangle: Produções
• Expression ::= primary-Expression
| Expression Operator
primary-Expression
primary-Expression ::= Integer-Literal
| V-name
| Operator primary-Expression
| ( Expression )
V-name ::= Identifier
Declaration ::= single-Declaration
| Declaration ; single-Declaration
Mini-Triangle: Produções
• Single-Declaration ::=
const Indentifier ~ Expression
| var Identifier : Type-denoter
Type-denoter ::= Identifier
Operator ::= + | - | * | / | <
| > | = | \
Identifier ::= Letter
| Identifier Letter
| Identifier Digit
Integer-Literal ::= Digit
| Integer-Literal Digit
Árvore Sintática
• Cada gramática livre de contexto G gera uma
linguagem (seqüência de símbolos terminais).
• Uma árvore sintática de G é uma árvore com labels
ordenada em que: as folhas são símbolos terminais;
os nós são símbolos não-terminais.
• Uma frase de G é uma seqüência de símbolos
terminais de uma árvore sintática.
• Uma sentença de G é uma S-frase de G, onde S é o
símbolo inicial.
Sintaxe
• Sintaxe concreta:
– Define a estrutura das frases, a ordem em que
sub-frases devem ser escritas, e os símbolos
terminais que as delimitam;
– Define como escrever programas sintaticamente
bem formados;
– Não é utilizada para a descrição semântica do
programa;
Árvores Sintáticas: Exemplos
• d + 10 * n
• while b do begin n := 0;
b := false
end
• let var y: Integer
in y := y + 1
Sintaxe Abstrata
• Usada como referência na descrição semântica do
programa
• Não gera frases, mas se baseia na estrutura das
frases do programa
• Gera árvores sintáticas abstratas (Abstract Syntax
Trees – ASTs)
• Nas ASTs cada nó representa uma produção, com
uma sub-árvore para cada subfrase
Mini-Triangle: Sintaxe Abstrata:
Não-terminais
• Program
single-Command
primary-Expression
Declaration
Single-Declaration
Type-denoter
Integer-Literal
Command
Expression
V-name
Operator
Identifier
Mini-Triangle: Sintaxe Abstrata:
Produções
• Program ::= Command
Program
Command ::=
V-name := Expression Assignment
| Identifier ( Expression ) Call
| Command ; Command
Sequential
| if Expression
IfCommand
then Command
else Command
| while Expression WhileCommand
do Command
| let Declaration
LetCommand
in Command
Mini-Triangle: Sintaxe Abstrata:
Produções
• Expression ::=
Integer-Literal
IntegerExpression
| V-name
VnameExpression
| Operator Expression UnaryExpression
| Expression Operator Expresion
BinaryExpression
V-name ::= Identifier
SimpleVname
Declaration ::=
const Indentifier ~ Expression
| var Identifier : Type-denoter
| Declaration ; Declaration
Type-denoter ::= Identifier
SimpleTypeDenoter
Árvores Sintáticas Abstratas:
Exemplos
• d + 10 * n
• while b do begin n := 0;
b := false
end
• let var y: Integer
in y := y + 1
Restrições Contextuais
• Necessárias para expressar situações em que
a possibilidade de a frase ser bem formada
ou não, depende do seu contexto.
• Regras de escopo:
ocorrência de ligação (declaração) x
ocorrência de uso
• Exemplos: declaração de variáveis, let
Ligação estática x Ligação
dinâmica
• Estática = em tempo de compilação, sem
rodar o programa;
• Dinâmica: só rodando o programa.
Ligação estática
• let
const m ~ 2;
var n : Integer;
func f (i : Integer) : Integer ~
i * m
in begin
…;
n := f (n);
…;
end
Ligação dinâmica
• let
const m ~ 2;
var n : Integer;
func f (i : Integer) : Integer ~
i * m
in begin
…;
n := let m ~ 3 in f (n);
…;
end
Regras de Tipos
• Normalmente, valores são classificados em
tipos.
• Cada operação na linguagem tem uma regra
de tipos, que define os tipos esperados para
os operandos e o tipo do resultado (se
existir).
• Qualquer operação utilizando um valor com
tipo de errado gera um erro de tipos.
Classificação de Linguagens em
Relação a Tipos
• Estaticamente tipada: todos os erros de tipos
podem ser detectados estaticamente, sem
executar o programa.
• Dinamicamente tipada, se (alguns) erros de
tipos só podem ser detectados durante a
execução do programa.
Regras de tipos: exemplo
• Regra de tipos para o operador ‘>’:
se os dois operandos são do tipo int, então o
resultado é do tipo bool;
• Regra de tipos para ‘while E do C’:
E deve ser do tipo bool;
Em linguagens dinamicamente
tipadas
• Uma variável pode assumir diversos valores,
de tipos diferentes, durante a execução do
programa;
Em linguagens estaticamente
tipadas
• Toda expressão bem-formada E tem um tipo
único T, que pode ser inferido (descoberto)
sem avaliar E;
• Quando E for avaliada, ela vai gerar um valor
do tipo T.
Semântica da Linguagem
Ver especificação informal, no livro, para:
• Atribuição;
• Chamada de funções;
• Comando sequencial;
• If;
• While;
• Let;