1

Formal Syntax and Semantics of Programming Languages

Ken Slonneger and Barry Kurtz

3

5 6

Ø Gramática é uma 4-upla <Σ, N, P, S>Ø Símbolos não-terminais possuem a

forma: <nome-da-categoria>Ø Produções são da forma:

<declaração> ::= var <lista variáveis> : <tipo> ;

S

7

Ø BNF é uma linguagem para definição de linguagens, portanto, é uma metalinguagem

a <uma coisa> b := b <outra coisa>

<uma coisa> b := b <outra coisa> .Ø A expressão do lado direito não pode conter

menos símbolos que a do lado esquerdo

<expressão> := <expressão> * <termo>Ø Gramáticas BNF são gramáticas do Tipo 2

Ø A expressão do lado direito pode conter apenas um símbolo terminal seguido, ou não, de um símbolo não-terminal

A notação utilizada para descrever sintaxe é conhecida como Backus-Nour Form ou BNF

8

10

§ O símbolo denota um passo em uma derivação

12

Exercício

§ Find two derivation trees for thesentence “the girl saw a boy witha telescope” using the grammar in Figure 1.1 and show the derivationsthat correspond to the two trees.

(context-free grammar)

Pegadinha... Não é possível escrever sentenças sem o símbolo terminal “.” no fim.

13

Exercício

§ Using the grammar in Figure 1.6, derive the <sentence> aaabbbccc.§ Você consegue descrever esta

linguagem utilizando gramática livre de contexto, ou mesmo uma gramática regular?Não é possível. Apenas Tipo 0 e 1 podem descrevê-la.

14

Exercício

§Consider the following twogrammars, each of whichgenerates strings of correctlybalanced parentheses andbrackets. Determine if either orboth is ambiguous. The Greekletter ε represents an emptystring.

a) <string> ::= <string> <string> |( <string> ) | [ <string> ] | ε

b) <string> ::= ( <string> ) <string> | [ <string> ] <string> | ε

16 17

A Linguagem de Programação WREN

Ø Wren é uma linguagem fortemente tipadaØ Palavras reservadas são tratadas como

identificadores pré-definidos§ Facilita a descrição da semântica

Ø Sintaxe é dividida em duas partes:åLéxico (lexical): descreve as menores

unidades significativas, chamadas de tokens(identificadores, numerais, símbolos especiais e palavras reservadas)

çEstrutura das frases (phrase-struture): explica como os tokens são agrupados em um programa

Ø A divisão reflete a forma como uma linguagem de programação é implementada:§ Um programa é submetido a um analizador

léxico (scanner) que lê os caracteres e identifica os tokens da linguagem

§ A semântica do programa é obtida a partir da estrutura das frases. Os detalhes da estrutura interna de um token é irrelevante (e.g., basta saber que é um numeral, qual é o valor exato não é relevante)

18 19

<int expr>

20

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

Poderiam ser definidos na phrase-structure syntax

21

23

of Pascal: if expr1 then if expr2 then cmd1 else cmd2

24

Classificando Erros em WREN

Program illegal isvar a: boolean;

begina := 5

end

ØQual é o erro neste programa? Sintático ou semântico?ØNão poderia ser sintático, pois a

BNF de Wren não exclui a atribuiçãoØNão poderia ser semântico, pois é

um erro de “tipo”§ Como a linguagem é fortemente

tipada, este erro deveria ser detectado pelo compilador

25

Classificando Erros Sintáticos em WREN

Program illegal2 isconst c = 5;

begin5 := 66;c := 66;

end

ØO erro em “5 := 66” pode ser determinado através da gramática livre-de-contexto (BNF)ØO erro em “c := 66” é normalmente

reconhecido como parte da verificação de restrição no contextoØPortanto, erros sintáticos são divididos em

duas categorias:åErros baseados na sintaxe livre-de-

contexto (BNF)çErros baseados na sintaxe sensível-ao-

contexto: são as restrições descritas em linguagem natural que todo programa válido deve seguir

26

27 30

Exercício

§ (exercício 2 da página 16)Consider the followingspecification of expressions:

<expr> ::= <element> | <expr> <weak op> <expr>

<element> ::= <numeral> | <variable><weak op> ::= + | –

Demonstrate its ambiguity bydisplaying two derivation treesfor the expression “a–b–c”. Explain how the Wrenspecification avoids thisproblem.

31

Exercício

32

Exercício

§ This Wren program has a number of errors. Classifythem as context-free, context-sensitive, or semantic.

program errors wasvar a,b : integer ;var p,b ; boolean ;

begina := 34;if b≠0 then p := true

else p := (a+1);write p; write q

end

33

Exercício

§ This BNF grammar defines expressionswith three operations, *, -, and +, and thevariables “a”, “b”, “c”, and “d”.

<expr> ::= <thing> | <thing> * <expr><object> ::= <element> | <element> – <object><thing> ::= <object> | <thing> + <object><element> ::= a | b | c | d | (<object>)

a) Give the order of precedence among thethree operations.

b) Give the order (left-to-right or right-to-left) of execution for each operation.

c) Explain how the parentheses defined for the nonterminal <element> may be usedin these expressions. Describe theirlimitations.

34

Exercício

§ Show that the following grammarfor expressions is ambiguous andprovide an alternativeunambiguous grammar that defines the same set of expressions.

<expr> ::= <term> | <factor><term> ::= <factor> | <expr> + <term><factor> ::= <ident> | ( <expr> ) |

<expr> * <factor><ident> ::= a | b | c

35

Exercício

§Consider the following twogrammars, each of whichgenerates strings of correctlybalanced parentheses andbrackets. Determine if either orboth is ambiguous. The Greekletter ε represents an emptystring.

a) <string> ::= <string> <string> | ( <string> ) | [ <string> ] | ε

b) <string> ::= ( <string> ) <string> | [ <string> ] <string> | ε

37

38 39

The BNF definition of <digit> in Wren is already in the form of a regular expression. Numerals in Wren can be written as a regular expression using

<numeral> ::= <digit> • <digit>*.

The concatenation operator “•” is frequently omitted so that identifiers can be defined by

<identifier> ::= <letter> (<letter> | <digit>)*.

Several regular expressions have special abbreviations:

E+ = E • E* represents the concatenation of one or more strings from L(E).

En represents the concatenation of exactly n≥0 strings from L(E).

E?= e | E represents zero or one string from L(E).

For example, in a language with signed numerals, their specification can be expressed as

<signed numeral> ::= (+ | –)? <digit>+,

and the context-sensitive language defined in Figure 1.6 can be described as the set {anbncn | n≥1}. Although this set is not regular, it can be described succinctly using this extension of the notation. The new operators “+”, “n”, and “?” have the same precedence as “*”.

40

The major reason for using the language of regular expressions is to avoid an unnecessary use of recursion in BNF specifications.Braces are also employed to represent zero or more copies of some syntactic category, for example:

<declaration seq> ::= { <declaration> },<command seq> ::= <command> { ; <command> }, and<integer expr> ::= <term> { <weak op> <term> }.

In general, braces are defined by {E} = E*. The braces used in this notation bear no relation to the braces that delimit a set.

41

42 43

46

Exercício

§ Use braces to replacerecursion in specifying variablelists and terms in Wren.

§ Specify the syntax of theRoman numerals less that 100 using regular expressions.

48

49

Sintaxe Abstrata

ØBNF descreve a Sintaxe Concreta da linguagem§ Reconhece os símbolos básicos que

compõem o “texto” de um programa corretamente escrito

ØUm Analizador Léxico (ou scanner) processa o texto/programa para identificar os tokens utilizados em um programa (identificadores, numerais, operadores matemáticos, ...)ØUm Analizador Sintático (ou parser)

utiliza esses tokens para criar a árvore de derivação do programa

50

Sintaxe Abstrata

51 52

Árvore de Derivação5*a – (b+1)

53

Árvore da Sintaxe Abstrata5*a – (b+1)

Árvore de Derivação

Árvore Sint. Abst 1

Árvore Sint. Abst 2

54

55 56

58 59

60 65

66

Gramática de Atributos

ØApresente uma gramática que reconhece sentenças da forma

anbncn

67

68 69

70 71

72 73

74 75

76 77

78 79

80 81

82

Qual a “semântica/significado”de 100.101?

83

Atributos Sintetizados

84

Qual a “semântica/significado”de 1101.01?

86

Exercício

5. Expand the binary numeral attribute grammar (eitherversion) to allow for binarynumerals with no binary point(1101), binary fractions with no fraction part (101.), and binaryfractions with no whole numberpart (.101).

89 90

91 92

93 94

95 96

97

Exercícios

98

99 100

101 102

Exercícios

103 104

105 106

Exercícios

4. Apresente a definição de variáveis ligadas em uma expressão lambda E, denotado por BV(E)

107

Lambda Reduction

108

109 110

111 112

113

rightmost

û

114

115 116rightmost

117 118

119 120

121 122

124 125

Definição Recursiva

ØA execução de um programapode ser considerado a “semântica” do próprio programaØIsto é verdade pois “o quê” o

programa vai de fato “fazer/realizar” seráfeito/realizado durante a execução do mesmoØPortanto, a execução de um

programa provê uma “especificação operacional” do mesmoØEste tipo de especificação é

considerada informal

126

Definição Metacircular

ØProgramas podem ser “executados”de duas formas:§ Interpretador§ Compilador

ØAmbas as formas fornecem uma definição operacional da linguagem de programaçãoØ Interpretadores e compiladores

podem ser implementados na própria linguagem de programação, criando uma implementação denominada “metacircular”ØQuais seriam as vantagens e

desvantagens de tal approach?

127

Compiladores

Ø Uma implementação metacircular, apesar de interessante, tem pouco uso prático

Ø Normalmente interpretadores e compiladores são implementados utilizando uma outra linguagem de programação

Ø Enquanto um interpretador “executa”diretamente o programa fonte; o compilador “traduz” o mesmo para uma outra linguagem de programação, normalmente de um nível de abstração menor

Ø A execução do programa produzido por um compilador captura a semântica do programa fonte (na linguagem de maior nível de abstração)

Ø A tradução do programa fonte para o programa executável é um exemplo de semântica de translação/transladação

128

Translational Semantics(semântica de translação)

Ø A semântica de translação é normalmente baseada em dois princípios:§ Preservação da semântica: a semântica

da linguagem de programação fonte deve ser preservada quando ela for transladada em outra forma na linguagem de programação destino§ A linguagem de programação destino é

normalmente definida por um pequeno número de primitivas que são diretamente relacionadas a arquitetura hipotética ou real da maquina/computador que será utilizada na execução

Ø O processo de translação (ou “tradução”entre a linguagem fonte e a linguagem destino) pode ser realizada através de uma gramática de atributos

129

130 131

Exercícios

1. Produza código objeto que ésemânticamente equivalente ao seguinte programa que multiplica dois números:

2. Apresente código objeto que avalia a seguinte expressão:

2*(x–1)*(y/4)–(12*z+y)

132 133

134 135

136

Expressão

ØUma expressão possui a forma genérica:<left operand> <operator> <right operand>

ØQue pode ser “tratada” de uma forma genérica pela seguinte sequência de código:

§ Onde n é o valor do atributo herdado Temp, que será utilizado para nomear as variáveis temporárias

137

Exemplo: x/(y–5)*(z+2*y)

138 139

140 141

x/(y–5)*(z+2*y)

142

Gramática de Atributos

144

145

Semântica Operacional

ØO modelo semântico apresentado no capítulo anterior descreve apenas o significado de um determinado programa: o quê o programa fazØA semântica operacional é utilizada

para descrever como a computação é realizadaØUsualmente uma linguagem de

programação é descrita através de um conceito operacional§ Por exemplo, uma atribuição V := E é

descrita em através das etapas realizadas: avaliação da expressão E, e a modificação do valor associado/ligado àvariável V ao valor de E

146

Semântica Operacional Estrutural

ØÉ um modelo semântico que descreve uma linguagem de programação através da execução de um programa em uma máquina abstrataØDesenvolvida por Gordon Plotkin em

1981ØRepresenta computação através de

um sistema dedutivo que modela uma máquina abstrata através de um sistema lógico de inferênciaØPortanto, a prova de que um

programa satisfaz uma determinada propriedades pode ser deriva diretamente dos construtores da linguagem

147

Regras de Inferência

ØNa semântica operacional estrutural, as definições são introduzidas através de regras de inferênciaØUma regra de inferência consiste

de uma conclusão, que segue de um conjunto de premissas, possivelmente sob alguma condição que deve ser satisfeita:

148

Regras de Inferência

ØPor exemplo, modus ponens éuma regra de inferência da lógica conhecida como dedução natural

ØUma regra de inferência que não possui premissa é chamada de axioma

149

Dedução Natural

ØOutro exemplo de dedução natural pode ser vista nas regras de inferência que permitem a eliminação e a introdução da conjunção:

ØQuais são as regras de inferência para introdução e eliminação da disjução?

150

Dedução Natural

ØO quantificador universal pode ser introduzido através da seguinte regra de inferência:

§ Assumindo que a não ocorre em P(x), e nem em qualquer condição da qual P(a) dependa

151

Sintaxe de Wren

ØNeste capítulo algumas simplificações serão assumidas:§ Todo programa (ou fragmento de

programa) é assumido como sintaticamente correto (incluíndoa sintaxe sensível ao contexto)§ Todo identificador declarado como

inteiro pertence ao conjunto Id, enquanto todo identificador do tipo booleano pertence ao conjunto Bid

152

Categorias Sintáticas de Wren

Ø Os “objetos/elementos” da máquina abstrata utilizada para descrever o significado da linguagem de programação Wren são apresentados a seguir:

153

Sintaxe Abstrata de Wren

ØRegras de inferência devem ser introduzidas para capturar os componentes essenciais dos construtores da linguagemØPor exemplo, a propriedade

fundamental de uma atribuição éque o identificador e a expressão devem ser do mesmo tipo:

154

Sintaxe Abstrata de Wren

155

Sintaxe Abstrata de Wren

156

Sintaxe Abstrata de Wren

157

Exemplo de Derivação

158

Exercícios

159

Indução Estrutural

ØA sintaxe abstrata de Wren poderia ser definida através de uma especificação na notação BNF (ou EBNF), ou mesmo outras técnicas/convenções para especificação de sintaxeØQualquer que seja a notação

utilizada, uma característica importante é a natureza indutiva das definiçõesØUm conjunto de objetos é descrito a

partir de alguns elementos atômicos “bem” conhecidos, e então são apresentadas regras que descrevem como objetos mais complexos podem ser obtidos através dos objetos pré-existentes

160

Indução Estrutural

ØPor exemplo, considere como o conjunto de objetos Iexp – expressão do tipo inteiro – pode ser definido:åBase: são descritos os elementos

atômicos de Iexp (são os elementos que não são compostos, ou obtidos a partir, de outros elementos)§ Exemplo,

∀n∈Num, id∈Id ∙ {n, id}⊂IexpçIndução: é descrito como

obter/construir novos elementos de Iexp através dos elementos atômicos de Iexp (ou, se for o caso, utilizando elementos de outro conjunto bem definido)§ Exemplo,

∀ie1,ie2∈Iexp, iop∈Iop ∙(ie1 iop ie2)∈Iexp

161

Sistema de Inferência

Ø Indução estrutural permite a utilização de uma técnica de prova baseada na induçãoØUm objeto é:å Um elemento básico (isto é, sem

estrutura interna), ou ç É criado a partir de outro(s) objeto(s)

através de construtores bem definidosØPara provar que uma determinada

propriedade é verdadeira para todo objeto de um determinado conjunto, basta provar que:å Base: todo elemento básico do conjunto

preserva a propriedadeç Indução: todo construtor do conjunto

preserva a propriedade

162

Sistema de Inferência

Ø Exemplo:§ Lema: para qualquer expressão

e ∈ (Iexp ∪ Bexp)que não contém operadores unários (isto é, não contém o operador unário inteiro “-” nem o operador unário booleano “not”), o número de operandos é maior que o número de operadores em e. A notação

#rand(e) > #rador(e)é utilizada para expressar esta relação

Ø Prova:§ Existem 7 casos a serem considerados: 4

tipos de objeto básico (número inteiro, valor booleano, identificador de inteiro, identificador de booleano) e 3 tipos de construtores de objetos (construtores de inteiros Iop, construtores de booleanos Bop, e construtores de relações Rop)● Os 4 tipos de objeto básico correspondem ao

caso base da prova por indução● Os 3 tipos de construtores correspondem ao

passo de indução da prova por indução

163

Sistema de Inferênciaå Base§ Para objetos básicos, nenhum operador existe,

portanto o número de operador é zero, enquanto o número de operandos é um

#rand(obj_básicos) > #rador(obj_básicos)1 > 0

ç Indução§ Caso 1: construtores do tipo inteiro (+, -, ¬ e /)

● e = ie1 iop ie2, para algum iop ∈ Iop e ie1, ie2 ∈ Iexp

● Pela hipótese da indução, #rand(ie1) > #rador(ie1) e #rand(ie2) > #rador(ie2)

● Portanto, #rand(ie1) ≥ #rador(ie1)+1 e #rand(ie2) ≥ #rador(ie2)+1ou seja, #rand(ie1)+rand(ie2) ≥#rador(ie1)+#rador(ie2)+2

● Como #rand(e)=#rand(ie1)+#rand(ie2)e #rador(e)= #rador(ie1)+#rador(ie2)+1

● Temos que #rand(ie1)+rand(ie2) > #rador(ie1)+#rador(ie2)+1

§ Caso 2: construtores do tipo booleano (and, or), é similar ao caso 1§ Caso 3: construtores de relações (<, ≤, =, ≥, > e

<>), é similar ao caso 1 164

Sistema de Inferênciaç Indução (outra opção!!)§ Caso 1: construtores do tipo inteiro (+, -, ¬ e /)

● e = ie1 iop ie2, para algum iop ∈ Iop e ie1, ie2 ∈ Iexp

● Pela hipótese da indução, #rand(ie1) > #rador(ie1) e#rand(ie2) > #rador(ie2)

● Portanto, #rand(ie1) ≥ #rador(ie1)+1 e #rand(ie2) ≥ #rador(ie2)+1ou seja, #rand(ie1)+rand(ie2) ≥#rador(ie1)+#rador(ie2)+2

● Como #rand(e)=#rand(ie1)+#rand(ie2)e #rador(e)= #rador(ie1)+#rador(ie2)+1

● Temos que #rand(ie1)+rand(ie2) > #rador(ie1)+#rador(ie2)+1

§ Caso 2: construtores do tipo booleano (and, or), é similar ao caso 1§ Caso 3: construtores de relações (<, ≤, =, ≥, > e

<>), é similar ao caso 1

165

Sistema de InferênciaExercícios

ØUtilizando prova por indução, demonstre que: 1. O número de parênteses abrindo

“(“ e parênteses fechando “)” é o mesmo.Assuma que parênteses podem ser utilizados (de forma correta) em expressões em Wren

2. Qualquer comando em Wrenpossui uma quantidade de ocorrências da palavra reservada then no mínimo igual àquantidade de ocorrências da palavra reservada else

166

Semântica Operacional Estrutural

ØDado o sistema de inferência de indução estrutural, é possível construir um sistema dedutivo que transforma os elementos da linguagem Wren em valores que representam seu significadoØPrimeiramente será abordado o

significado de expressões, que possuem um modelo semântico mais simples, pois expressões não modificam o estado da máquinaØConcluindo este capítulo, será

apresentado o significado dos comandos, que alteram o estado da máquina

167

Semântica de Expressões

Ø O significado de uma expressão ébasicamente representado pelo valor resultante da sua avaliação

Ø Devido à existência de identificadores, faz-se necessária a utilização de uma estrutura que associa um identificador ao seu valor: store§ store modela a memória do computador

(ou a fita da máquina de Turing!)Ø Como a quantidade de identificadores em

um programa é finita, store pode ser representado por uma função finita. Portanto:

dom (store) = conjunto de identificadoresØ Como exemplo, assuma a existência de três

variáveis – a, b e c – cujos valores são 1, 2 e 3, respectivamente. Portanto:

dom (store) = {a, b, c}store = {a↦1, b↦2, c↦3}

168

Semântica de Expressões

Ø Como uma implementação real de store não érelevante, pois estamos tratando de um modelo semântico, uma meta-variável seráutilizada para representá-lo: sto

Ø Para manipular sto, serão utilizados três operadores abstratos (ou funções auxiliares):§ emptySto – representa um sto sem

nenhum mapeamento, isto é, todo identificador é indefinido§ updateSto (sto, id, n) e updateSto (sto,

bid, b) – representa um novo store que ésimilar a sto, mas que difere em id e bid, com id↦n e bid↦b§ applySto (sto, id) e applySto (sto, bid) –

retornam o valor associado a id ou bid em sto. Se o identificador for indefinido em sto, então a operação falha, bloqueando a dedução (similar a um autômato não-determinístico que está em um estado que não possui transição para um elemento do alfabeto)

169

Semântica de Expressões

ØComo é assumido que o programa Wren estásintáticamente correto, não seránecessário verificar que applySto (sto, id) é definido se e apenas se id ∈dom(sto). A mesma propriedade deve ser observada para o caso de identificadores booleanoØComo expressões não podem

alterar o estado, o operador updateSto não é necessário para apresentar a semântica de expressões

170

Semântica de Expressões

ØDa mesma forma que identificadores devem ser mapeados em objetos “reais”, os operadores de Wrendevem ser “abstraídos” em operadores “reais”ØSerá utilizado uma função genérica

abstrata compute (op, arg1, arg2)para representar o resultado de execução/computação do operador op com operandos arg1 e arg2§ Por exemplo, compute(+,3,5) retorna o

numeral 8, compute(<,3,5) retorna true e compute(and,true,false) retorna false§ Observe que compute(/,n,0) é indefinido,

portanto, qualquer avaliação de uma expressão dessa forma deve “falhar”

171

Semântica de Expressões

ØPara avaliar uma expressão énecessário uma “configuração” que é representada por par <e,sto>composto da expressão em si e o store que representa o contexto da computação§ O resultado final da avaliação de uma

expressão é também um par <n,sto> ou <b,sto>, onde o primeiro elemento é o valor que representa a avaliação da expressão e o segundo o store utilizado na avaliação§ O símbolo ➙ será utilizado para denotar

a “transição” de uma configuração inicial (antes da avaliação) para uma configuração final (após a avaliação):<5≥12,emptySto> ➙ <false,emptySto>

pois compute(≥,5,12) = false

172

Sistema de Inferência para Expressões

Ø As regras de inferências (1)-(3) definem a estratégia adotada para a avaliação de expressões§ O operando/argumento mais a

esquerda (ie1) em uma expressão binária deve ser avaliada/simplificada primeiro

173

Sistema de Inferência para Expressões

ØApós a avaliação do operando mais a esquerda, as regras (4)-(6) indicam que o operando/argumento mais a direita (ie2) deve ser o próximo a ser avaliado

174

Sistema de Inferência para Expressões

Ø Uma vez que os argumentos/operandostenham sido avaliados, as regras (7)-(9) definem o significado associado a cada tipo de expressão, mapeando o seu valor ao valor retornado pela função abstrata/semântica compute

Ø Observe a “side condition” para expressões do tipo inteiro, elas evitam a divisão por zero

175

Sistema de Inferência para Expressões

ØAs regras (10)-(11) definem a semântica do operador unário not, enquanto as dias últimas regras apresentam o significado de expressões atômicas (isto é, expressões que são identificadores)

176

Sistema de Inferência para Expressões

Ø O significado de uma expressão é descrita como uma seqüência de configurações, onde cada transição é justificada por uma das regras de inferência:

<e1,Sto> ➙ <e2,Sto> ➙ ... ➙ <en,Sto>Ø Adicionando uma regra (14) que permite

que o operador ➙ seja transitivo

Ø Pode-se abreviar a expressão <e1,Sto> ➙ <e2,Sto> ➙ ... ➙ <en,Sto>por<e1,Sto> ➙ <en,Sto>

177

Sistema de Inferência para Expressões

ØDa mesma forma, o operador ➙ pode ser definido como possuindo a propriedade de ser reflexivo:

<e1,Sto> ➙ <e1,Sto>

178

Sistema de Inferência para Expressões

Ø Exemplo – a avaliação da expressão x+y+6com store = {x↦17, y↦25} é representada pela seguinte seqüência de computação:

a. <y,sto> ➙ <25,sto> applySto(sto,y)=25 (12)

b. <y+6,sto> ➙ <25+6,sto> (1)+a

c. <25+6,sto> ➙ <31,sto> Compute(+,25,6)=31 7

d. <y+6,sto> ➙ <31,sto> (14)+b+c

e. <x,sto> ➙ <17,sto> applySto(sto,x)=17 (12)

f. <x+(y+6),sto> ➙<17+(y+6),sto> (1)+e

g. <17+(y+6),sto> ➙ <17+31,sto> (4)+d

h. <x+(y+6),sto> ➙ <17+31,sto> (14)+f+g

i. <17+31,sto> ➙ <48,sto> Compute(+,17,31)=48 (7)

j. <x+(y+6),sto> ➙ <48,sto> (14)+h+i

179

Sistema de Inferência para Expressões

ØExercícios:§ Avalie as seguintes expressões

Assumindo:

§ Modifique o sistema de inferência para expressões em WREN de forma que expressões binárias podem ter o argumento/operando esquerdo ou direito avaliado primeiro

180

Sistema de Inferência para Expressões

ØExercícios:§ Defina regras que especificam o

significado de expressões booleanas da forma “b1 and b2” e “b1 or b2” diretamente no estilo utilizado na regra (11) para not§ Re-escreva a especificação para

expressões Wren de forma que and then e or else são interpretados como operadores condicionais. A condição and – por exemplo, “b1 and then b2” – éequivalente a “if b1 then b2 elsefalse”

181

Sistema de Inferência para Expressões

ØExercícios:§ Apresente uma definição lazy

(preguiçosa) dos operadores booleanos and e or. A expressão booleana●“b1 and b2” é falsa quando b1 ou

b2 for falso, independente do valor verdade do outro argumento

●“b1 or b2” é verdadeira quando b1 ou b2 forem verdadeiros, independente do valor verdade do outro argumento

183

Semântica de Comandos

ØA semântica de expressões érelativamente simples, pois expressões não modificam o estado do computadorØ Isto reflete nas equações

semânticas, que não modificam o estado stoØsto é apenas utilizado nas regras

(12) e (13), quando é necessário obter o valor associado a um identificador inteiro e booleano, respectivamente. Este valor está“armazenado” no mapeamento stoØPode-se dizer que expressões não

geram efeito colateral

184

Semântica de Comandos

ØA semântica de comandos descreve os passos de uma computação, pois comandos modificam o estado da máquinaØOs comandos read e write, são

modelados como operadores sobre as listas in e out, respectivamenteØNeste modelo, a execução de um

comando read remove o primeiro elemento da lista in e modifica o mapeamento da variável para o valor deste elementoØDa mesma forma, o comando write

escreve o valor que está mapeado àvariável no final da lista out

185

Semântica de Comandos

ØAssim, o estado do computador éuma estrutura st composta da lista de entrada in, lista de saída out e mapeamento dos identificadores a seus respectivos valores sto

estado ≈ st (in, out, sto)ØPara a manipulação das listas de

entrada e saída, são utilizadas as funções auxiliares head, tail e affix:§ head (list) retorna o primeiro elemento

de list. E.g., head ([2,0,1,0]) = 2§ tail (list) retorna uma lista que é

equivalente a list sem o primeiro elemento. E.g., tail ([2,0,1,0]) = [0,1,0]§ affix (list,elem) retorna uma lista

equivalente a list, mas com elemadicionado ao final da mesma. E.g., affix ([2,0,1,0],5) = [2,0,1,0,5]

186

Sistema de Inferência para Comandos

Ø Assim como em expressões, é apresentada uma estratégia para a execução de comandos

Ø Os comandos que dependem da avaliação de uma expressão devem, primeiro, avaliar a expressão

187

Sistema de Inferência para Comandos

Ø Os únicos comandos que modificam o estado da máquina são: := (atribuição) e read§ O comando write altera a lista de saída out,

mas o valor desta lista não afeta nenhuma computação

Ø Isto reflete nas respectivas regras, que são as únicas que utilizam a função semântica updateSto

Ø Observe a “side condition” para a execução do comando read: a lista de entrada in não pode estar vazia!

Ø Observer ainda que os comandos :=, read e writesão comandos elementares: reduzem a skip

188

Sistema de Inferência para Comandos

Ø A semântica de comandos Wren éapresentada nos próximos três slides

189

Sistema de Inferência para Comandos

Ø Observe a definição do while: recursiva e depende do if

190

Sistema de Inferência para Comandos

191

Sistema de Inferência para Comandos

ØMais duas regras, sobre a relação ➙, devem ser adicionadas: § Uma que diz que ela é transitiva

§ Outra que diz que ela é reflexiva

192

Configuração Inicial

ØA configuração inicial de um programa c é um estado que contém uma lista de entrada inpré-inicializada com um número finito de valores [n1, n2, ..., nn], uma lista de saída out vazia (denotada por [ ]), e um mapeamento de identificadores para valores vazia (denotada pela função auxiliar emptySto)

<c, st([n1, n2, ..., nn], [ ], emptySto)>

193

Configuração Inicial

<c, st([n1, n2, ..., nn], [], emptySto)>

ØA medida que os comandos do programa vão sendo executados:åUma atribuição “adiciona” um novo

mapeamentos em stoçCada comando read “consume”

um elemento do início de in, adicionando um novo mapeamento em stoéCada comando write “adiciona”

um elemento ao final da lista de saída out

194

Configuração Final

ØA configuração <skip, state>representa a forma normal para uma computação§ Nenhuma regra pode ser aplicada para

tal configuraçãoØNeste caso, state representa o

resultado da computação – pois não há mais nenhum comando para ser executado: a lista de saída out e estado/mapeamento final sto

state = st (in, out, sto)§ O mapeamento sto e a lista in não

devem ser de interesse ao final da execução

195

Configuração Final

Ø Infelizmente, a configuração <skip, state> nem sempre é o resultado de uma computação:§ <skip, state> representa uma

computação que pára § É possível que uma configuração

seja alcançada onde nenhuma regra possa ser aplicada: é o caso do comando 10/0 (divisão por zero), ou quando um identificador não declarado é utilizado§ É possível que nunca seja obtida

uma configuração normal, pois a computação nunca termina: é o caso do comando while true do skipA notação denota tal situação

196

Sistema de Inferência para Comandos

ØAs regras (8) e (9), combinadas com a regra (13), podem ser combinadas para tornar a notação concisa:

ØA justificativa é simples:

197

Exemplo de Computação

ØVer páginas 257-260 do livro texto

201

Exercícios

202

Exercícios