Upload
sandrodoom
View
234
Download
4
Embed Size (px)
DESCRIPTION
Semântica de Linguagens de Programação
Citation preview
Semntica de Linguagens de ProgramaoCentro de Informtica, UFPE
Luis Carlos ([email protected])Hermano Moura ([email protected])
ObjetivoIntroduzir conceitos de semntica formal de linguagens de programao
Motivao: Qual o significado do seguinte programa?program simples =var x : int := 3inx := x + 5end.?
Motivaoestudo de linguagens de programao requer que possamos descrever linguagens de programao de forma precisa e de fcil compreensoUtilizao de descries informais:Frases de significado duvidosoGerao de manuais imprecisosNo existe tcnicas que auxiliem a implementao (erros de codificao)Soluo: Utilizao de mtodos formais
Mtodos FormaisTcnica utilizada para desenvolvimento de sistemaUtiliza notaes bem-definidasSignificado descrito matematicamenteEvita a existncia de ambigidadesPermite a utilizao de tcnicas de verificao de erros e implementao automtica
Aplicaes em Linguagens de ProgramaoInterface entre projetistas, implementadores e usuriosProjetista: Define precisamente a linguagem desejadaPermite a identificao precoce de errosImplementador:Possibilita a utilizao de geradores (semi-)automticosDificulta o aparecimento de errosUsurios: Produo de bons manuais da linguagem
projetocompiladoresmanuais,livrosprottiposespecificaoformalCiclo de vida de LPbaseado em especificaesformais
Introduocaractersticas principais de uma lp:sintaxesemnticapragmtica
SintaxeDefine a forma e estrutura de uma linguagemSmbolos, palavras, frases e sentenas (estruturas)Principal formalismo: Gramticas Livres de Contexto e Expresses RegularesNotao mais utilizada: BNF (Backus-Naur Form)
Sintaxe Concreta x Sintaxe AbstrataSintaxe concreta: Descreve a estrutura da linguagem com todos os detalhes.Considera elementos estticos como comentrios, palavras reservadas, precedncia de operadores, e outros aucares sintticos.Utilizado para construir reconhecedores para programas.Sintaxe abstrata: Descreve apenas os elementos relevantes da linguagem de programao.Ignora comentrios e outros elementos que no contribuem para a semntica do programaUtilizada para representar programas internamente no compilador
Ferramentas de ImplementaoDisponveis ferramentas que geram implementaes eficientes:lex+yacc, javacc, etc.O desenvolvedor no utiliza linguagens de uso geral para implementao da linguagem.Mais detalhes: Disciplina de compiladores
Introduocaractersticas principais de uma lp:sintaxesemnticapragmtica
SemnticaObjetivo: Descrever o significados das estruturas do programa expressos na sua sintaxeTipos de semnticaSemntica esttica: Descreve as caractersticas de uma programa vlidoSemntica dinmica: Descreve os resultados da execuo do programa
Formalismos UtilizadosAo contrrio da sintaxe, no existe ainda um formalismo aceito globalmente para descrever a semntica da linguagemExemplos de formalismos:Semntica Operacional Estrutural, Mquinas de Estado Abstratas, Semntica Denotacional, Semntica de Aes, Montages, etc.
Abordagens para Descrio SemnticaA especificao semntica de uma linguagem pode:1 - Definir um mapeamento entre a sintaxe do programa e seu significado. Ex.: Semntica Denotacional, Semntica de Aes, Semntica Algbrica, etc.2 - Definir uma mquina que executa programas da linguagem. Ex.: Semntica Natural, Mquinas de Estado Abstratas.
Exemplo da 1a. AbordagemSemntica de [[ Exp1 + Exp2 ]] =Semntica de Exp1Semntica de Exp2SumA semntica traduz o programa em operadores de uma linguagem com significado conhecido
Exemplo 2a. Abordagemif (execute(x)=c1 and execute(y)= c2) then execute (x + y) = (c1+c2)
A semntica define como executar um programa diretamente, sem traduzi-lo para uma outra notao intermediria.
Semntica De Aes
Semntica De AesFormalismo para definio de linguagens de programao.Define um mapeamento da sintaxe do programa para o seu significado. Significado de programa dado atravs da notao de aes.
Notao de AesBiblioteca que descreve os principais conceitos encontrados em linguagens de programao que foram estudados nesse curso (valores, bindings, memria, etc.)Durante essa aula e a prxima estudaremos os operadores que implementam cada conceito estudado.Operadores que manipulam os mesmos conceitos so agrupados em facetas.
Definio de AesUma ao uma entidade que pode ser executada.Quando uma ao executada ela pode:Terminar com sucessoTerminar com um erroGerar uma exceo (escape)No-terminar (executar para sempre)Durante a execuo de uma ao ela produz e consome vrios tipos de informao: (transientes, bindings, memria, etc.)
Semntica de Aes - Faceta Bsica
DefinioA faceta bsica define operadores que no manipulam nenhum tipo de informao apenas controlam o fluxo do programa
Principais Operadorescomplete -- Executa com sucesso sem produzir nenhuma informao.fail -- Produz uma falha na execuo da aoa and then b -- Executa as aes a e b sequncialmentea or b -- Executa uma das aes e se esta falhar a outra ao ser executada.
Principais Operadores (cont.)unfolding a -- executa a ao a.unfold -- Desvia o fluxo da execuo para a ltima ao unfolding executada.
Exemplos de Aes:| complete|completeand thenor| complete| fail
| complete unfoldingand then| | complete| fail| and then| | unfold
Exemplo de DescriesComandos vazioSintaxe:Comando --> [[ ; ]]Semntica:execute _ :: Comando --> action.execute [[ ; ]] = complete.
Exemplo de DescriesSequncia de Comandos:Sintaxe:Comando --> [[ Comando Comando ]]Semntica:execute _ :: Comando --> action.execute [[ c1 c2 ]] =| execute c1and then| execute c2.
Semntica de Aes - Faceta Funcional
DefinioA faceta funcional define aes que manipulam valores temporrios (transitrios) produzidos pela execuo de um programa.Utilizao principal: Modelagem da avaliao de expresses em um programa.
Principais Operadores Funcionaisgive e -- produz o valor resultante da avaliao da expresso e.x then y -- Executa as aes x e y seqencialmente, os valores transitrios produzidos por x sero repassados para a ao y.the given t # n -- Expresso (produtor) que recupera o n-simo valor passado para essa ao e verifica se este do tipo t.
Exemplos de Aes
give 10
| give 20then| give sum(2,the given integer#1)
Exemplos de Aes(cont.)| | give 1| and then| | give 2then| give product(the given integer#1, | the given integer # 2)
Exemplo de DescrioLinguagens de Expresses1 + 245 * 2
Exemplo de descrioConstantes Numricas.Sintaxe:Expresso action.avalie [[ x : Integer ]] = give valuation of x.
Exemplo de descrioSoma de Expresses.Sintaxe:Expresso action.avalie [[ x + y ]] = |avalie x and then avalie y then | give sum(the given integer#1, the given integer#2).
UtilizaoQual a semntica de: 1 + 2
UtilizaoQual a semntica de 1 + 2 ?1o Passo: Analise Sinttica:1 + 2 ==> [[ [[ 1 ]] + [[ 2 ]] ]]
UtilizaoQual a semntica de 1 + 2 ?2o Passo: Executar Funo Semntica:avalie [[ [[ 1 ]] + [[ 2 ]] ]]
UtilizaoQual a semntica de 1 + 2 ?2o Passo: Executar Funo Semntica:| | avalie [[ 1 ]] | and then | | avalie [[ 2 ]]then| give sum| (the given integer#1, the given integer # 2)
UtilizaoQual a semntica de 1 + 2 ?2o Passo: Executar Funo Semntica:| | give valuation of 1 | and then | | give valuation of 2 then| give sum| (the given integer#1, the given integer # 2)
UtilizaoQual a semntica de 1 + 2 ?2o Passo: Executar Funo Semntica:| | give 1 | and then | | give 2then| give sum| (the given integer#1, the given integer # 2)
Semntica de Aes: Faceta Declarativa
DefinioA faceta declarativa define aes que controlam os bindings de um programa (mapeamento de identificadores e seus significados)Utilizao em LP: Modelagem de Declaraes em um programa.
Principais Operadores Declarativosbind n to b -- Associa o identificador n ao significado b.a hence b -- Executa as aes a e b seqencialmente, os bindings produzidos pela ao a sero repassados para a ao b the t bound to n -- Produtor que recupera o valor associado ao identificador n e testa se ele do tipo t
Exemplos de Aesbind x to 10
| | bind x to 20| and then| | bind y to 1hence| give sum(the value bound to x, | the value bound to y)
Outros Operadores Declarativosfurthermore a -- Executa a ao a e produz a unio entre os bindings recebidos pela ao os produzidos por a.x moreover y -- Executa as aes x e y sendo que os bindings produzidos por y tem prioridade aos bindings produzidos por x.x before y -- Executa a ao x, os bindings produzidos pela ao x so adicionados aos recebidos pela ao combinada e fornecidos para a ao y.
Exemplos:| bind x to 1| bind x to 2moreover before| bind x to 2| bind y to the | integer bound to x| bind x to 1hence| furthermore bind y to 2
Exemplo de DescrioLinguagens com declaraes:let x = 1 in x + 2let x = 1 in let y = 3 in x * y + 1
Exemplo de descrioDeclarao de Constantes.Sintaxe:Expresso action.elabore [[ let i = x in y ]] = | furthermore | | avalie x then bind token of i to the given value hence | avalie y.
Exemplo de descrioExpresses de Constantes.Sintaxe:Expresso action.avalie [[i : Identifier]] = give the value bound i.
Semntica de Aes:Faceta Imperativa
DefinioA faceta imperativa define aes que manipulam a memria do programaUtilizada principalmente na declarao de variveis
Principais Aesallocate a cell -- reserva uma posio de memria livre e retorna o valor alocado como valor transitriodeallocate c -- libera a posio de memria cstore x in c -- armazena o valor x na clula de memria c.the t stored in c -- Expresso que recupera o valor armazenado na posio de memria c.
Exemplos de Aes| allocate a cellthen| | store 10 in the given cell| and then| | store 20 in the given cell| and then| | give the integer stored in the given cell.
Exemplo de DescrioLinguagem com declaraes e variveis e comandos imperativos:int x;int y;x = 1;y = x + 1;
Exemplo de DescrioDeclarao de VariveisSintaxe:Declarao action.elabore [[ int i ]] = | allocate a cellthen| bind token of i to the given cell.
Exemplo de DescrioComando de AtribuioSintaxe:Comando action.execute [[ c = e ]] = | avalie ethen| store the given value in the cell bound to token to c.
Exemplo de DescrioComandos com declaraes locais de variveisSintaxe:Comando action.execute [[ d:Declarao c:Comando ]] =| furthermore elaborate dhence| execute c.
Notao de Aes:Faceta Reflexiva
DescrioA Faceta Reflexiva define operadores capazes de encapsular aes na forma de abstraes.Utilizada principalmente na modelagem de procedimentos e funes.
Principais Operadoresabstraction of a -- Expresso que retorna uma abstrao que incorpora a computao definida por aenact e -- Avalia a expresso e e se ela retornar uma abstrao executa-a. Caso contrrio gera uma mensagem de erro.closure a -- modifica a abstrao a de forma a incorporar os bindings correntes durante a avaliao de a.application of a to v -- define uma abstrao semelhante a abstrao a mas que quando for executada receber v como valores transitrios.
Exemplos| give abstraction of| | bind a to 5| | give 10| hencethen| | give closure abstraction of | enact the given abstraction.| | | give the integer bound to athen| give abstraction of | enact the given abstraction| | give the given integerthen| enact application the given| abstraction to 5
Pratica
Baixe os Seguintes Arquivos http://www.cin.ufpe.br/~rat/download/abaco-beta230.ziphttp://www.cin.ufpe.br/~if686/laboratorio.prjDescompacte o arquivo Zip em um diretrio de trabalho.Execute o arquivo abaco2.30.jar.