plp2014-aula02-cap3Sebesta

Prévia do material em texto

PARADIGMAS DE 
LINGUAGEM DE 
PROGRAMAÇÃO 
Descrevendo a sintaxe e a semântica – Parte 1 
Tópicos 
• O problema geral de descrever a sintaxe. 
• Reconhecedores e geradores. 
• Métodos formais para descrever a sintaxe. 
• BNF 
Introdução 
• A tarefa de apresentar uma descrição concisa e 
inteligível de uma linguagem de programação é 
difícil. 
• Implementadores: devem ser capazes de determinar 
como as expressões, as instruções e as unidades de 
programa são formadas e o efeito pretendido pelas 
mesmas quando executadas. 
• Usuários: devem ser capazes de determinar como 
codificar sistemas consultando o manual de referência 
da linguagem (livros didáticos ou cursos). 
Sintaxe e semântica 
• Estudo das linguagens de programação envolve: 
• Sintaxe: forma de suas expressões, de suas instruções 
e de suas unidades de programa. 
• Semântica: significado das expressões, instruções e 
unidades de programa. 
• Exemplo em C: 
if (<expr>) <instrução> 
 Semântica: se o resultado da expressão for verdadeiro então executa a 
instrução. 
 
Sintaxe e semântica 
• Em uma linguagem de programação bem projetada, a 
semântica deve seguir-se diretamente da sintaxe. 
• A forma da instrução deve sugerir fortemente o que esta pretende 
realizar. 
Sintaxe 
• Linguagem é um conjunto de sentenças. 
• Sentença ou instrução é a sequência de caracteres de algum 
alfabeto. 
• As regras de sintaxe especificam quais sequências de caracteres do alfabeto estão 
na linguagem. 
• Lexema é a unidade sintática de nível mais baixo da linguagem. 
• Ex: identificadores, literais, operadores e palavras reservadas. 
• Símbolo (token) é uma categoria de seus lexemas. 
 Ex: index = 2 * cont 
 
Lexemas Símbolos 
index identificador 
= Sinal_igual 
2 Int_literal 
* Op_multi 
cont Identificador 
O problema de descrever a sintaxe 
• Técnicas formais para descrever a sintaxe: 
• Reconhecedor – determina se uma sentença pertence 
ou não a linguagem. 
• Supondo uma linguagem L que use um alfabeto Σ. Um 
dispositivo de reconhecimento R deve, dada uma sequência de 
caracteres de Σ, aceitar ou rejeitar a sequência. 
• Linguagens úteis são, em geral, infinitas → reconhecedor não é 
útil como descritor. 
• Usado na fase de análise sintática de um compilador. 
O problema de descrever a sintaxe 
 Técnicas formais para descrever a sintaxe: 
 Geradores – dispositivos que podem gerar sentenças 
pertencentes a uma dada linguagem L. 
• Uma vez que uma sentença particular é imprevisível 
quando produzida por um gerador, este possui 
utilidade limitada como descritor da linguagem. 
• Pessoas preferem certas formas de geradores aos 
reconhecedores porque podem lê-los e entendê-los 
mais facilmente. 
• Uma gramática é um gerador. 
Métodos formais para descrever a sintaxe 
• Uma gramática é um mecanismo de geração formal de 
linguagem comumente utilizado para descrever a sintaxe. 
Gramáticas 
• Gramática livre de contexto: 
• Desenvolvidas por Noam Chomsky (lingüista) em meados da 
década de 50. 
• Gerador de sentenças para linguagens naturais. 
• Definiu uma classe de linguagens chamadas livre de contexto. 
• Backus-Naur Form (BNF): 
• Inventada por John Backus para descrever Algol 58 e ligeiramente 
modificada por Peter Naur. 
• BNF é equivalente a gramáticas livre de contexto. 
Gramáticas 
• Fundamentos: 
• Uma metalinguagem é uma linguagem usada para descrever outra 
linguagem. 
• BNF é uma metalinguagem para as linguagens de programação. 
• Em BNF abstrações são usadas para representar classes de estruturas 
sintáticas. 
Gramáticas 
• Uma instrução de atribuição em C poderia ser 
representada pela abstração: 
 <atribuição> → <var> = <expressão> 
 
 
Exemplo de sentença cuja estrutura sintática é descrita pela regra: 
total = sub1 + sub2 
• Uma regra é recursiva se o lado esquerdo aparecer 
em seu lado direito. 
 A → aA 
 
Regra 
LE (lado esquerdo) 
abstração 
LD (lado direito) 
definição do LE 
Gramáticas 
• Uma descrição BNF ou gramática é simplesmente 
um conjunto de regras. 
• A BNF é um dispositivo generativo para definir 
linguagens. 
• As sentenças da linguagem são geradas por uma 
sequência de aplicações das regras: 
• Iniciando com um símbolo não-terminal da gramática, 
chamado símbolo inicial. 
• Uma geração de sentença é chamada derivação. 
Gramáticas 
• Exemplo de gramática: 
 
<programa> -> <lista_inst> 
<lista_inst> -> <inst> | <inst> ; <inst> 
<inst> -> <var> = <expr> 
<var> -> a | b | c | d 
<expr> -> <term> + <term> | <term> - 
<term> 
<term> -> <var> | const 
Símbolo inicial 
ou 
Não-terminais 
terminais 
Gramáticas 
• Exemplo de derivação: 
 
<programa> => <lista_inst> => <inst> 
 => <var> = <expr> => a = <expr> 
 => a = <term> + <term> 
 => a = <var> + <term> 
 => a = b + <term> 
 => a = b + const 
derivação 
Derivação: substituição de símbolos não-terminais por terminais. 
Sentença gerada é formada apenas de símbolos terminais. 
Árvore de análise 
 <programa> 
 
 
 <lista_inst> 
 
 
 <inst> 
 
 
 <var> = <expr> 
 
 
 a <term> + <term> 
 
 
 <var> const 
 
 
 b 
Folhas são terminais 
Vértices internos são 
símbolos não terminais 
Gramáticas 
• Ao escolher lados direitos alternativos de regras para substituir 
não-terminais na derivação é possível gerar diferentes 
sentenças na linguagem. 
 
• Ao escolher exaustivamente todas as combinações de opções 
a linguagem inteira é gerada. 
 
• A maioria das linguagens é infinita – não se pode gerar todas 
as sentenças em tempo finito. 
Gramática ambígua 
• Uma gramática é ambígua quando gera uma sentença 
para a qual há duas ou mais árvores de análise distintas. 
 
Gramática ambígua 
• Exemplo de gramática ambígua: 
<atribuição> → <id> = <expr> 
<id> → A | B | C 
<expr> → <expr> + <expr> | 
 <expr> * <expr> | 
 (<expr>) | 
 <id> 
Gramática ambígua 
<atribuição> 
<id> <expr> = 
A 
B 
C 
+ 
* 
<expr> <expr> 
<expr> <expr> 
<id> 
<id> 
<id> 
A 
<atribuição> 
<id> <expr> = 
A 
A 
B 
* 
+ 
<expr> <expr> 
<expr> <expr> 
<id> 
<id> 
<id> 
C 
Duas árvores de análise distintas para mesma sentença: A = B + C * A 
Gramática ambígua 
• A ambiguidade sintática das estruturas de linguagem é 
um problema porque os compiladores frequentemente 
baseiam a semântica dessas estruturas em suas 
formas sintáticas: 
• O compilador decide qual código gerar para uma 
instrução examinando sua árvore de análise. 
• Se uma estrutura de linguagem tiver mais de uma 
árvore de análise, o significado dela não pode ser 
determinado de maneira única. 
 
Gramática não ambígua 
 Exemplo de gramática não ambígua: 
<atribuição> → <id> = <expr> 
<id> → A | B | C 
<expr> → <id> + <expr> | 
 <id> * <expr> | 
 (<expr>) | 
 <id> 
Gramática não ambígua 
• Só há uma maneira de gerar expressão A = B + C * A 
<atribuição> 
<id> <expr> = 
A 
+ 
* 
<id> <expr> 
<id> <expr> 
C 
B 
<id> 
A 
Exercício 1 
• Considere a seguinte gramática: 
 <S> → <A> a <B> b 
 <A> → <A> b | b 
 <B> → a <B> | a 
 Quais das seguintes sentenças estão na linguagem 
gerada por essa gramática? 
 a) baab 
 b) bbbab 
 c) bbaaaaa 
 d) bbaabExercício 2 
• Construa a árvore de análise para o item (a). 
• baab 
Exercício 3 
• Considere a gramática: 
• S → aSbS | bSaS | є 
• Mostre que essa gramática é ambígua mostrando duas 
derivações mais à esquerda diferentes para a sentença 
abab. 
• Construa as derivações mais à direita correspondentes 
para abab. 
• Que linguagem esta gramática gera? 
 
• Observações: 
• Є é uma transição vazia 
• Derivação mais à esquerda (direita) sempre escolhe o não terminal 
mais à esquerda (direita) para substituir. 
 
Exercício 4 
• Escreva uma gramática para a linguagem consistindo em 
sequências que têm n cópias da letra a seguida do 
mesmo número de cópias da letra b, em que n > 0. 
• Por exemplo, as sequências ab, aaabbb e aaaaabbbbb estão na 
linguagem, mas a, abb, ba, e aaabb não estão. 
Exercício 5 
• Prove que a seguinte gramática é ambígua: 
<S> → <A> 
<A> → <A> + <A> | <id> 
<id> → a | b | c 
Referências Bibliográficas 
• Sebesta, R. Conceitos de Linguagens de 
programação. 5ª edição. Bookman, 2003. Cap 3.