Teoria e Implementação de Linguagens Computacionais – IF688 Professor: André Santos Home page do curso: if688 Newsgroup do curso:

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 xADD R1 R2JUMPZ 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)/2in 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


• 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 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.


• 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 const do else endin let then var whileif ; : := ~( ) + - */ < > = \

Mini-Triangle: Não-terminais

• Program Command single-Command Expressionprimary-Expression V-nameDeclaration OperatorSingle-Declaration IdentifierType-denoterInteger-Literal

Mini-Triangle: Produções

• Program ::= single-CommandCommand ::= single-Command | Command ; single-Command


• 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


• Expression ::= primary-Expression | Expression Operator primary-Expressionprimary-Expression ::= Integer-Literal | V-name | Operator primary-Expression | ( Expression )V-name ::= IdentifierDeclaration ::= single-Declaration | Declaration ; single-Declaration


• Single-Declaration ::= const Indentifier ~ Expression | var Identifier : Type-denoterType-denoter ::= IdentifierOperator ::= + | - | * | / | < | > | = | \Identifier ::= Letter | Identifier Letter | Identifier DigitInteger-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 Command single-Command Expressionprimary-Expression V-nameDeclaration OperatorSingle-Declaration IdentifierType-denoterInteger-Literal

Mini-Triangle: Sintaxe Abstrata: Produções

• Program ::= Command ProgramCommand ::= 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 BinaryExpressionV-name ::= Identifier SimpleVnameDeclaration ::= const Indentifier ~ Expression | var Identifier : Type-denoter | Declaration ; DeclarationType-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 * min begin …; n := f (n); …;end

Ligação dinâmica

• let const m ~ 2; var n : Integer; func f (i : Integer) : Integer ~ i * min 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;

Documents

Teoria e Implementação de Linguagens Computacionais – IF688 Professor: André Santos Home page do curso: if688 Newsgroup do curso: