Semântica de Linguagens de
Programação
Centro de Informática, UFPE
Luis Carlos ([email protected])
Hermano Moura ([email protected])
1
Objetivo
Introduzir conceitos de semântica
formal de linguagens de
programação
2
Motivação: Qual o significado do
seguinte programa?
program simples =
var x : int := 3
in
x := x + 5
end.
=
?
Motivação


estudo de linguagens de programação requer que
possamos descrever linguagens de programação
de forma precisa e de fácil compreensão
Utilização de descrições informais:




Frases de significado duvidoso
Geração de manuais imprecisos
Não existe técnicas que auxiliem a implementação
(erros de codificação)
Solução: Utilização de métodos formais
4
Métodos Formais


Técnica utilizada para desenvolvimento de
sistema
Utiliza notações bem-definidas



Significado descrito matematicamente
Evita a existência de ambigüidades
Permite a utilização de técnicas de
verificação de erros e implementação
automática
5
Aplicações em Linguagens de
Programação


Interface entre projetistas, implementadores e usuários
Projetista:



Implementador:



Define precisamente a linguagem desejada
Permite a identificação precoce de erros
Possibilita a utilização de geradores (semi-)automáticos
Dificulta o aparecimento de erros
Usuários: Produção de bons manuais da linguagem
6
Ciclo de vida de LP
baseado em especificações
projeto
formais
especificação
formal
protótipos
manuais,
livros
compiladores
Introdução

características principais de uma lp:



sintaxe
semântica
pragmática
8
Sintaxe



Define a forma e estrutura de uma linguagem
Símbolos, palavras, frases e sentenças
(estruturas)
Principal formalismo:


Gramáticas Livres de Contexto e Expressões Regulares
Notação mais utilizada: BNF (Backus-Naur Form)
9
Gramáticas Livres de Contexto

Estrutura principal:
Comando <-[[ “if” Expressão “then” Comando “else” Comando ]]

Significado:

Um Comando da linguagem definida pode ser formado
pela palavra chave “if” seguida de uma Expressão da
linguagem, da palavra chave “then”, de um Comando
da linguagem, da palavra chave “else”, e de um outro
Comando da linguagem.
10
Sintaxe Concreta x Sintaxe
Abstrata

Sintaxe concreta: Descreve a estrutura da
linguagem com todos os detalhes.



Considera elementos “estéticos” como comentários, palavras
reservadas, precedência de operadores, e outros “açucares
sintáticos”.
Utilizado para construir reconhecedores para programas.
Sintaxe abstrata: Descreve apenas os elementos
relevantes da linguagem de programação.


Ignora comentários e outros elementos que não contribuem
para a semântica do programa
Utilizada para representar programas internamente no
compilador
11
Ferramentas de Implementação

Disponíveis ferramentas que geram
implementações eficientes:


lex+yacc, javacc, etc.
O desenvolvedor não utiliza linguagens de
uso geral para implementação da
linguagem.

Mais detalhes: Disciplina de compiladores
12
Introdução

características principais de uma lp:



sintaxe
semântica
pragmática
13
Semântica

Objetivo:


Descrever o significados das estruturas do
programa expressos na sua sintaxe
Tipos de semântica


Semântica estática: Descreve as características
de uma programa válido
Semântica dinâmica: Descreve os resultados da
execução do programa
14
Formalismos Utilizados


Ao contrário da sintaxe, não existe ainda
um formalismo aceito globalmente para
descrever a semântica da linguagem
Exemplos de formalismos:

Semântica Operacional Estrutural, Máquinas de
Estado Abstratas, Semântica Denotacional,
Semântica de Ações, Montages, etc.
15
Abordagens para Descrição
Semântica

A especificação semântica de uma
linguagem pode:
1 - Definir um mapeamento entre a sintaxe do
programa e seu significado. Ex.: Semântica
Denotacional, Semântica de Ações, Semântica
Algébrica, etc.
2 - Definir uma máquina que executa programas
da linguagem. Ex.: Semântica Natural,
Máquinas de Estado Abstratas.
16
Exemplo da 1a. Abordagem
Semântica de [[ Exp1 “+” Exp2 ]] =
Semântica de Exp1
Semântica de Exp2
Sum

A semântica traduz o programa em
operadores de uma linguagem com
significado conhecido
17
Exemplo 2a. Abordagem
if (execute(x)=c1 and execute(y)= c2) then
execute (x “+” y) = (c1+c2)

A semântica define como executar um
programa diretamente, sem traduzi-lo para
uma outra notação intermediária.
18
Semântica De Ações
19
Semântica De Ações



Formalismo para definição de linguagens de
programação.
Define um mapeamento da sintaxe do
programa para o seu significado.
Significado de programa é dado através da
notação de ações.
20
Notação de Ações



Biblioteca que descreve os principais conceitos
encontrados em linguagens de programação que
foram estudados nesse curso (valores, bindings,
memória, etc.)
Durante essa aula e a próxima estudaremos os
operadores que implementam cada conceito
estudado.
Operadores que manipulam os mesmos conceitos
são agrupados em facetas.
21
Definição de Ações


Uma ação é uma entidade que pode ser
executada.
Quando uma ação é executada ela pode:





Terminar com sucesso
Terminar com um erro
Gerar uma exceção (escape)
Não-terminar (executar para sempre)
Durante a execução de uma ação ela produz e
consome vários tipos de informação: (transientes,
bindings, memória, etc.)
22
Semântica de Ações - Faceta
Básica
23
Definição

A faceta básica define operadores que não
manipulam nenhum tipo de informação
apenas controlam o fluxo do programa
24
Principais Operadores




complete -- Executa com sucesso sem
produzir nenhuma informação.
fail -- Produz uma falha na execução da
ação
a and then b -- Executa as ações a e b
sequêncialmente
a or b -- Executa uma das ações e se esta
falhar a outra ação será executada.
25
Principais Operadores (cont.)


unfolding a -- executa a ação a.
unfold -- Desvia o fluxo da execução para
a última ação unfolding executada.
26
Exemplos de Ações:
| complete
and then
| complete
|complete
or
| fail
| complete
and then
| fail
unfolding
| | complete
| and then
| | unfold
27
Exemplo de Descrições


Comandos vazio
Sintaxe:


Comando --> [[ “;” ]]
Semântica:


execute _ :: Comando --> action.
execute [[ “;” ]] = complete.
28
Exemplo de Descrições


Sequência de Comandos:
Sintaxe:


Comando --> [[ Comando Comando ]]
Semântica:


execute _ :: Comando --> action.
execute [[ c1 c2 ]] =
| execute c1
and then
| execute c2.
29
Semântica de Ações Faceta Funcional
30
Definição


A faceta funcional define ações que
manipulam valores temporários
(transitórios) produzidos pela execução de
um programa.
Utilização principal: Modelagem da
avaliação de expressões em um programa.
31
Principais Operadores Funcionais



give e -- produz o valor resultante da
avaliação da expressão e.
x then y -- Executa as ações x e y
seqüencialmente, os valores transitórios
produzidos por x serão repassados para a
ação y.
the given t # n -- Expressão (produtor)
que recupera o n-ésimo valor passado para
essa ação e verifica se este é do tipo t. 32
Exemplos de Ações
give 10
| give 20
then
| give sum(2,the given integer#1)
33
Exemplos de Ações(cont.)
| | give 1
| and then
| | give 2
then
| give product(the given integer#1,
| the given integer # 2)
34
Exemplo de Descrição

Linguagens de Expressões



1+2
4
5*2
35
Exemplo de descrição


Constantes Numéricas.
Sintaxe:
Expressão <-- [[ Integer ]].

Semântica:
avalie _ :: Expressão --> action.
avalie [[ x : Integer ]] = give valuation of x.
36
Exemplo de descrição


Soma de Expressões.
Sintaxe:
Expressão <-- [[ Expressão “+” Expressão ]].

Semântica:
avalie _ :: Expressão --> action.
avalie [[ x “+” y ]] =
|avalie x and then avalie y
then
| give sum(the given integer#1, the given integer#2).
37
Utilização

Qual a semântica de: 1 + 2
38
Utilização
Qual a semântica de “1 + 2” ?
1o Passo: Analise Sintática:
1 + 2 ==> [[ [[ “1” ]] “+” [[ “2” ]] ]]

39
Utilização
Qual a semântica de “1 + 2” ?
2o Passo: Executar Função Semântica:
avalie [[ [[ “1” ]] “+” [[ “2” ]] ]]

40
Utilização
Qual a semântica de “1 + 2” ?
2o Passo: Executar Função Semântica:

| | avalie [[ “1” ]]
| and then
| | avalie [[ “2” ]]
then
| give sum
| (the given integer#1, the given integer # 2)
41
Utilização
Qual a semântica de “1 + 2” ?
2o Passo: Executar Função Semântica:

| | give valuation of “1”
| and then
| | give valuation of “2”
then
| give sum
| (the given integer#1, the given integer # 2)
42
Utilização
Qual a semântica de “1 + 2” ?
2o Passo: Executar Função Semântica:

| | give 1
| and then
| | give 2
then
| give sum
| (the given integer#1, the given integer # 2)
43
Semântica de Ações:
Faceta Declarativa
44
Definição


A faceta declarativa define ações que
controlam os bindings de um programa
(mapeamento de identificadores e seus
significados)
Utilização em LP: Modelagem de
Declarações em um programa.
45
Principais Operadores
Declarativos



bind n to b -- Associa o identificador “n” ao
significado “b”.
a hence b -- Executa as ações “a” e “b”
seqüencialmente, os bindings produzidos pela
ação “a” serão repassados para a ação “b”
the t bound to n -- Produtor que recupera o
valor associado ao identificador “n” e testa se ele
é do tipo “t”
46
Exemplos de Ações
bind “x” to 10
| | bind “x” to 20
| and then
| | bind “y” to 1
hence
| give sum(the value bound to “x”,
| the value bound to “y”)
47
Outros Operadores Declarativos



furthermore a -- Executa a ação “a” e produz a
união entre os bindings recebidos pela ação os
produzidos por “a”.
x moreover y -- Executa as ações “x” e “y”
sendo que os bindings produzidos por “y” tem
prioridade aos bindings produzidos por “x”.
x before y -- Executa a ação “x”, os bindings
produzidos pela ação “x” são adicionados aos
recebidos pela ação combinada e fornecidos para
a ação “y”.
48
Exemplos:
| bind “x” to 1
moreover
| bind “x” to 2
| bind “x” to 2
before
| bind “y” to the
| integer bound to “x”
| bind “x” to 1
hence
| furthermore bind “y” to 2
49
Exemplo de Descrição

Linguagens com declarações:


let x = 1 in x + 2
let x = 1 in let y = 3 in x * y + 1
50
Exemplo de descrição


Declaração de Constantes.
Sintaxe:
Expressão <--[[ “let” Identifier “=“ Expressão “in” Expressão ]].

Semântica:
avalie _ :: Expressão --> action.
elabore [[ “let” i “=“ x “in” y ]] =
| furthermore
| | avalie x then bind token of i to the given value
hence
| avalie y.
51
Exemplo de descrição


Expressões de Constantes.
Sintaxe:
Expressão<--[[ Identifier ]].

Semântica:
avalie _ :: Expressão --> action.
avalie [[i : Identifier]] =
give the value bound “i”.
52
Semântica de Ações:
Faceta Imperativa
53
Definição


A faceta imperativa define ações que
manipulam a memória do programa
Utilizada principalmente na declaração de
variáveis
54
Principais Ações




allocate a cell -- reserva uma posição de
memória livre e retorna o valor alocado como
valor transitório
deallocate c -- libera a posição de memória “c”
store x in c -- armazena o valor “x” na célula de
memória “c”.
the t stored in c -- Expressão que recupera o
valor armazenado na posição de memória c.
55
Exemplos de Ações
| allocate a cell
then
| | store 10 in the given cell
| and then
| | store 20 in the given cell
| and then
| | give the integer stored in the given cell.
56
Exemplo de Descrição
Linguagem com declarações e variáveis e
comandos imperativos:
int x;
int y;
x = 1;
y = x + 1;

57
Exemplo de Descrição


Declaração de Variáveis
Sintaxe:


Declaração <-- [[ “int” Identifier ]] .
Semântica:


elabore _ :: Declaração --> action.
elabore [[ “int” i ]] =
| allocate a cell
then
| bind token of i to the given cell.
58
Exemplo de Descrição


Comando de Atribuição
Sintaxe:


Comando <-- [[ Identifier “=” Expressão]] .
Semântica:


execute _ :: comando --> action.
execute [[ c “=” e ]] =
| avalie e
then
| store the given value in the cell bound to token to c.
59
Exemplo de Descrição


Comandos com declarações locais de variáveis
Sintaxe:


Comando <-- [[ Declaração Comando ]] .
Semântica:


execute _ :: Comando --> action.
execute [[ d:Declaração c:Comando ]] =
| furthermore elaborate d
hence
| execute c.
60
Exemplo de Descrição


Comando While
Sintaxe:


Comando <-- [[ “while” Expressão “do” Commando “endwhile” ]]
Semântica:

execute [[ “while” e “do” c “endwhile” ]] =
unfolding
| | avalie e
| then
| | | check the given value is true and then
| | | execute c and then unfold
| | or
| | | check the given value is false.
61
Notação de Ações:
Faceta Reflexiva
62
Descrição


A Faceta Reflexiva define operadores
capazes de encapsular ações na forma de
abstrações.
Utilizada principalmente na modelagem de
procedimentos e funções.
63
Principais Operadores




abstraction of a -- Expressão que retorna uma abstração
que incorpora a computação definida por “a”
enact e -- Avalia a expressão “e” e se ela retornar uma
abstração executa-a. Caso contrário gera uma mensagem
de erro.
closure a -- modifica a abstração “a” de forma a
incorporar os bindings correntes durante a avaliação de
“a”.
application of a to v -- define uma abstração
semelhante a abstração “a” mas que quando for
executada receberá “v” como valores transitórios.
64
Exemplos
| give abstraction of
| | give 10
then
| enact the given abstraction.
| give abstraction of
| | give the given integer
then
| enact application the given
| abstraction to 5
| | bind “a” to 5
| hence
| | give closure abstraction of
| | | give the integer bound to “a”
then
| enact the given abstraction
65
Exemplos de Descrição


Declaração de Procedimentos
Sintaxe:


Declaração <-- [[ “proc” Identifier “is”
Commando “end” ]].
Semântica:

elabore [[ “proc” i “is” c “end” ]] =
bind token of i to closure abstraction of
| execute c.
66
Exemplos de Descrição


Chamada a procedimento
Sintaxe:


Comando <-- [[ Identifier “()” ]] .
Semântica:

execute [[ i “()” ]] =
enact the abstraction bound to i.
67
Pratica
68

Baixe os Seguintes Arquivos




http://www.cin.ufpe.br/~rat/download/abaco-beta230.zip
http://www.cin.ufpe.br/~if686/laboratorio.prj
Descompacte o arquivo Zip em um diretório de trabalho.
Execute o arquivo abaco2.30.jar.
69