plp-aula02-cap3Sebesta

Prévia do material em texto

Paradigmas de 
Linguagem de 
Programação
Descrevendo a sintaxe e a 
semântica – Parte 1
Autora: Profª Valguima Odakura
 
Tópicos
 O problema geral de descrever a 
sintaxe.
Reconhecedores e geradores.
 Métodos formais para descrever a 
sintaxe.
BNF (Backus-Naur Form).
 
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>
 
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) bbaab
 
Solução 1
<S> → <A> a <B> b
<A> → <A> b | b
<B> → a <B> | a
a) baab (pertence)
<S> → <A> a <B> b → ba <B> b → baab
b) bbbab (não pertence)
<S> → <A> a <B> b → <A> aa b 
c) bbaaaaa (não pertence)
<S> → <A> a <B> b
d) bbaab (pertence)
<S> → <A> a <B> b → <A> b a <B> b → bba <B> b → 
bbaab
gramática
bn am b
 
Exercício 2
 Construa a árvore de análise para o 
item (a).baab
 
Solução 2
<S>
<A> <B>a b
b 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?
 
Solução 3
 Gramática: S → aSbS | bSaS | є
 Objetivo: abab
 Derivações mais á esquerda:
 S => aSbS => abS => abaSbS => ababS => abab
 S => aSbS => abSaSbS => abaSbS => ababS => 
abab
 Derivação mais á direita:
 S => aSbS => aSbaSbS => aSbaSb => aSbab => 
abab
 Que linguagem essa gramática gera?
 Sentenças com mesmo número de a’s e b’s
 
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 seqüências ab, 
aaabbb e aaaaabbbbb estão na 
linguagem, mas a, abb, ba, e aaabb 
não estão.
 
Solução 4
 S → aSb | ab 
 Gera:
ab, aabb, aaabbb, aaaabbbb, etc.
 
Exercício 5
 Prove que a seguinte gramática é 
ambígua:
<S> → <A>
<A> → <A> + <A> | <id>
<id> → a | b | c
 
Solução 5
 Gramática é ambígua:
<S> → <A>
<A> → <A> + <A> | <id>
<id> → a | b | c
<S> => <A> => <A> + <A> => <id> + <A> =>
a + <A> => a + <A> + <A> => a + <id> + <A> => a + b 
+ <A> => a + b + <id> => a + b + c
<S> => <A> => <A> + <A> => <A> + <id> =>
<A> + c => <A> + <A> + c => <A> + <id> + c => <A> + 
b + c => <id> + b + c => a + b + c
 
Solução 5
<A>
<A> <A>+
<id>
c
+<A> <A>
<id>
b
<id>a
<S>
<A> <A>+
b
+<A> <A>
<id>
a
<id>
<id>
c
<A>
<S>
 
Referências Bibliográficas
 Sebesta, R. Conceitos de 
Linguagens de programação. 5ª 
edição. Bookman, 2003. Cap 3.