plp-aula03-cap3Sebesta

Prévia do material em texto

Paradigmas de 
Linguagem de 
Programação
Descrevendo a sintaxe e a 
semântica – Parte 2
 
Tópicos
 Métodos formais para descrever a 
sintaxe:
EBNF.
Grafos de sintaxe.
Gramáticas de atributos.
 
EBNF 
 EBNF – versão estendida da BNF:
Não aumenta poder descritivo, mas 
aumenta sua legibilidade e 
capacidade de escrita.
 
EBNF – parte opcional
 Parte opcional de um lado direito, 
definida por colchetes:
 Exemplo em C:
EBNF:
• <seleção> → if (<expressão>) <instrução> 
[else <instrução>];
BNF:
• <seleção> → if (<expressão>) <instrução>;
• <seleção> → if (<expressão>) <instrução> 
else <instrução>;
 
EBNF – repetição 
 Indicar que o lado direito pode ser repetido 
indefinidamente ou omitido completamente, definido 
por chaves.
 Permite que listas sejam criadas com uma única 
regra, em vez de usar recursão e duas regras.
 Exemplo:
 EBNF :
• <list_ident> → <identificador> {, <identificador>}
 BNF:
• <list_ident> → <identificador> 
• <list_ident> → <identificador>, <list_ident>
 
EBNF – múltipla escolha
 Opções de múltipla escolha: quando um 
único elemento deve ser escolhido de um 
grupo, as opções são colocadas entre 
parênteses e separadas por OU ‘|’.
Exemplo em Pascal:
• EBNF:
• <inst_for> → for <var> := <expr> (to|downto) <expr> 
do <inst>
• BNF:
• <inst_for> → for <var> := <expr> to <expr> do <inst> 
• <inst_for> → for <var> := <expr> downto <expr> do 
<inst>
 
EBNF
 Colchetes, chaves e parênteses são 
metassímbolos (ferramentas 
notacionais) e não símbolos 
terminais.
Nos casos em que estes 
metassímbolos também são símbolos 
terminais na linguagem sendo 
descrita, as instâncias dos símbolos 
terminais podem ser sublinhadas.
 
BNF x EBNF
 BNF:
<expr> -> <expr> + <termo> |
 <expr> - <termo> |
 <termo>
<termo> -> <termo> * <fator> |
<termo> / <fator> |
<fator>
 
BNF x EBNF
 EBNF:
<expr> -> <termo> {(+|-)<termo>}
<termo> -> <fator> {(*|/) 
<fator>}
 
Exercício 1
 Dadas as regras em BNF, escreva suas 
formas equivalentes em EBNF.
 <inst_atrib> → <ident> = <expr>;
 <signed_number> → <sign> <number> | <number> 
 <inst_while> → while <expr> { <lista_inst> } 
 <lista_inst> → <inst> | <inst> <lista_inst>
 
Solução 1
 BNF = EBNF: 
• <inst_atrib> → <ident> = <expr>;
 BNF:
• <signed_number> → <sign> <number> | <number> 
 EBNF:
• <signed_number> → [ <sign> ] number 
 BNF:
• <inst_while> → while <expr> { <lista_inst> } 
• <lista_inst> → <inst> | <inst> <lista_inst>
 EBNF:
• <inst_while> → while <expr> {{ <inst> }}
 
Exercício 2
 Dada a descrição EBNF para a instrução if em Ada, 
escreva seu correspondente em BNF:
 <inst_if> → if <condição> then <inst> {<else_if>} 
[else <inst>] end if
 <else_if> → elseif <condição> then <inst>
 
Solução 2
 EBNF:
 <inst_if> → if <condição> then <inst> {<else_if>} [else 
<inst>] end if
 <else_if> → elseif <condição> then <inst>
 BFN:
 <inst_if> → if <condição> then <inst> end if | 
if <condição> then <inst> else <inst> end if |
if <condição> then <inst> <elseif> end if |
if <condição> then <inst> <elseif> else <inst> end if
 <else_if> → elseif <condição> then <inst> |
 elseif <condição> then <inst> <else_if> 
 
Grafos de sintaxe
 As informações nas regras BNF e EBNF 
podem ser representadas em grafos 
dirigidos, chamados grafos de sintaxe.
 Um grafo distinto é usado para cada 
unidade sintática.
 Aumentam legibilidade ao permitir-nos 
visualizá-los.
 Símbolos:
Símbolos terminais
Símbolos não terminais
 
Grafos de sintaxe
 <inst_atrib> → <ident> = <expr>;
Símbolos 
terminais 
sublinhados
=
inst_atrib
ident expr ;
{while }inst
inst_while
expr
 <inst_while> → while <expr> {{ <inst> }}
 
Exercício 3
 Construa os grafos de sintaxe para a 
descrição EBNF da instrução if em 
Ada:
<inst_if> → if <condição> then 
<inst> {<else_if>} [else <inst>] end if
<else_if> → elseif <condição> then 
<inst>
 
Solução 3
else_if instthencondiçãoelseif
 <inst_if> → if <condição> then <inst> {<else_if>} [else <inst>] 
end if
 <else_if> → elseif <condição> then <inst>
inst_if
end_if
elseelse_ifinstthencondiçãoif inst
 
Gramática de 
atributos
 
Gramática de atributos
 Usada para descrever mais detalhes de uma 
LP do que é possível com uma gramática 
livre de contexto.
 
Semântica estática
 Exemplos de características de LP difíceis ou impossíveis de 
escrever em BNF:
 Regras de compatibilidade de tipos são difíceis de escrever:
• Ex: em Java um valor real não pode ser atribuído a uma variável 
do tipo inteiro, ainda que o oposto seja legal → exige símbolos não 
terminais e regras adicionais para ser especificado.
 Não é possível descrever a regra segundo a qual todas as variáveis 
devem ser declaradas antes de serem referenciadas.
 Esses exemplos fazem parte da categoria das regras de 
linguagem chamada semântica estática.
 Semântica estática se relaciona apenas indiretamente com o 
significado dos programas durante a execução, tem relação com 
as formas legais dos programas (sintaxe).
 
Gramáticas de atributos
 Usadas para descrever mais detalhes de uma LP do que é 
possível com uma gramática livre de contexto.
 São gramáticas com adição de:
 Atributos: associados a símbolos gramaticais (são 
semelhantes a variáveis na medida em que podem 
ter valores atribuídos a eles).
 Funções de computação de atributos (funções 
semânticas): são associadas as regras gramaticais 
para especificar como os valores de atributos são 
computados.
 Funções predicadas: declaram a parte da sintaxe e 
as regras semânticas estáticas da linguagem. 
 
Gramáticas de atributos
 Proposta por Knuth, 1968.
 Definição: uma gramática de atributos é 
uma gramática BNF com as seguintes 
adições:
Para cada símbolo gramatical X há um 
conjunto A(X) de valores de atributos.
Cada regra tem um conjunto de funções que 
define certos atributos dos símbolos não 
terminais na regra. 
Cada regra tem um conjunto de predicados 
(possivelmente vazio) para verificar 
consistência de atributos.
 
Gramáticas de atributos
 Atributos:
Os símbolos terminais têm atributos 
intrínsecos (que descrevem a informação 
léxica a cada um deles associada). 
Os símbolos não-terminais são associados 
com atributos genéricos, através dos quais 
se poderá sintetizar informação semântica 
(subindo na árvore de sintaxe abstrata, das 
folhas para a raiz), ou herdar informação 
semântica (descendo na árvore de sintaxe 
abstrata, do topo para as folhas), 
 
Gramáticas de atributos
 Seja X0 → X1 ... Xn uma regra:
 Funções na forma S(X0) = f(A(X1), ... A(Xn)) definem 
atributos sintetizados. 
 Funções na forma I(Xj) = f(A(X0), ... , A(Xj-1)), para i ≤ j 
 ≤ n, definem atributos herdados.
 Inicialmente, os atributos intrínsecos estão nas 
folhas.
 Função predicada tem a forma de expressão 
booleana no conjunto de atributos {A(X0), ..., A(Xn)}. 
• As únicas derivações permitidas são aquelas em 
que todo predicado associado a cada não 
terminal é verdadeiro. 
• Uma função predicada falsa indica uma violação 
das regras de sintaxe ou semântica estática da 
linguagem.
 
Gramáticas de atributos
 Uma árvore de análise de uma 
gramática de atributos é aquela baseada 
em sua gramática BNF subjacente, com 
um conjunto possivelmente vazio de 
valores de atributos anexados a cada 
vértice.
 Uma árvore de análise é dita totalmente 
atribuída se todos os valores de 
atributos tiverem sido computados.
 
Gramáticas de atributos
 Como os valoresdos atributos são 
computados?
Se todos os atributos forem herdados, 
a árvore pode ser construída de cima 
pra baixo. 
Se todos os atributos forem 
sintetizados, a árvore pode ser 
construída de baixo para cima. 
Em muitos casos, ambos atributos 
são usados, e alguma combinação 
deve ser usada.
 
Gramáticas de atributos
 Exemplo de gramática de atributos que descreve a regra na qual o 
nome end de um procedimento em Ada deve coincidir com o nome 
do procedimento.
Regra de sintaxe: <def_proc> → procedure <nome_do_proc>[1] 
<corpo_do_proc> end <nome_do_proc>[2];
Regra semântica: <nome_do_proc>[1].string = 
<nome_do_proc>[2].string
Observações:
 O atributo de cadeia de <nome_do_proc> é <nome_do_proc>.string 
 Há mais de uma ocorrência do não-terminal <nome_do_proc>, então 
utiliza-se colchetes para distingui-las.
 
Gramáticas de atributos
 Exemplo de gramática de atributos usada para 
verificar as regras de tipo de uma instrução 
simples de atribuição.
 BNF:
<atribuição> → <var> = <expr>
<expr> → <var> + <var>
| <var>
<var> → A | B | C
 
Gramáticas de atributos
 Parte sintática da gramática de atributos:
<atribuição> → <var> = <expr>
<expr> → <var> + <var>
| <var>
<var> → A | B | C
 Atributos para os símbolos não-terminais:
 tipo_efetivo: um atributo sintetizado associado a <var> e <expr>.
• Usado para armazenar o tipo efetivo, int ou real. No caso de uma expressão o 
tipo é determinado a partir dos tipos reais do vértice-filho. No caso de uma 
variável o tipo é intrínseco.
 tipo_esperado: um atributo herdado associado a <expr>.
• Usado para armazenar o tipo int ou real, esperado para expressão, conforme 
determinado pelo tipo da variável no lado esquerdo da atribuição.
 
Gramáticas de atributos
Regra de sintaxe: <atribuição> → <var> = <expr>
Regra semântica: <expr>.tipo_esperado ← <var>.tipo_efetivo
Regra de sintaxe: <expr> → <var>[2] + <var>[3]
Regra de semântica: <expr>.tipo_efetivo ← 
if (<var>[2].tipo_efetivo = int) e (<var>[3].tipo_efetivo = int) then 
int 
else real 
endif
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
Regra de sintaxe: <expr> → <var> 
Regra de semântica: <expr>.tipo_efetivo ← <var>.tipo_efetivo
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
Regra de sintaxe: <var> → A | B | C
Regra de semântica: <var>.tipo_efetivo ← look_up( <var>.string)
A função look-up 
pesquisa 
determinado nome 
de variável na tabela 
de símbolos e 
retorna o tipo desta.
 
Gramáticas de atributos
<atribuição>
<expr>
<var>
<var>[2] <var>[3]
A BA= +
Árvore de análise para A = A + B
 
<atribuição>
<expr>
<var>
<var>[2] <var>[3]
A BA= +
Fluxo dos atributos na árvore de análise para A = A + B
tipo_efetivo
tipo_efetivo tipo_efetivo
tipo_efetivotipo_esperado
Gramáticas de atributos
<var>.tipo_efetivo ← look-up(A)
<expr>.tipo_esperado ← 
<var>.tipo_efetivo
<var>[2].tipo_efetivo ← look-up(A)
<var>[3].tipo_efetivo ← look-up(B)
<expr>.tipo_efetivo ← int ou real 
<expr>.tipo_esperado = 
<expr>.tipo_efeitvo (Verdadeiro ou 
Falso)
 
<atribuição>
<expr>
<var>
<var>[2] <var>[3]
A BA= +
Árvore de análise completamente atribuída para A = A + B
tipo_efetivo = real
tipo_efetivo = real
tipo_efetivo = int
tipo_esperado = real
tipo_efetivo = real
Gramáticas de atributos
Exemplo:
A definido como real
B definido como inteiro
Regra semântica: <expr>.tipo_efetivo ← 
if (<var>[2].tipo_efetivo = int) e (<var>[3].tipo_efetivo = int) then 
int else real endif
 
Gramáticas de atributos
 São usadas para:
 Fornecer descrições completas da sintaxe e 
semântica estática de linguagens de 
programação.
Definição formal de uma linguagem que pode 
ser introduzida em um sistema de geração 
de compiladores.
Processamento de linguagens naturais.
 Grande número de atributos e de regras 
semânticas necessárias dificulta leitura e 
escrita dessas gramáticas.
 
Exercício 1
 Escreva uma gramática de atributos cuja base BNF é 
dada abaixo, mas cujas regras de linguagem sejam as 
seguintes: tipos de dados não podem ser misturados 
em expressões, mas as instruções de atribuição não 
precisam ter os mesmos tipos em ambos os lados do 
operador de atribuição.
<atribuição> → <var> = <expr>
<expr> → <var> + <var>
| <var>
<var> → A | B | C
 
Gramáticas de atributos
Regra de sintaxe: <atribuição> → <var> = <expr>
Regra semântica: <expr>.tipo_esperado ← <var>.tipo_efetivo
Regra de sintaxe: <expr> → <var>[2] + <var>[3]
Regra de semântica: <expr>.tipo_efetivo ← 
if (<var>[2].tipo_efetivo = int) e (<var>[3].tipo_efetivo = int) then 
int 
else real 
endif
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
Regra de sintaxe: <expr> → <var> 
Regra de semântica: <expr>.tipo_efetivo ← <var>.tipo_efetivo
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
Regra de sintaxe: <var> → A | B | C
Regra de semântica: <var>.tipo_efetivo ← look_up( <var>.string)
 
Solução 1
 Regra de sintaxe: <atribuição> → <var> = <expr>
Regra de sintaxe: <expr> → <var>[2] + <var>[3]
Regra de semântica: <expr>.tipo_efetivo ← 
if (<var>[2].tipo_efetivo = <var>[3].tipo_efetivo) then 
<var>[2].tipo_efetivo
else ERRO
endif
Regra de sintaxe: <expr> → <var> 
Regra de semântica: <expr>.tipo_efetivo ← 
<var>.tipo_efetivo
Regra de sintaxe: <var> → A | B | C
Regra de semântica: <var>.tipo_efetivo ← 
look_up( <var>.string)
 
<atribuição>
<expr>
<var>
<var>[2] <var>[3]
A CB= +
Árvore de análise completamente atribuída para A = B + C
tipo_efetivo = real
tipo_efetivo = int
tipo_efetivo = int
tipo_efetivo = int
Solução 1
Exemplo:
A definido como real
B definido como inteiro
C definido como inteiro
Regra semântica: <expr>.tipo_efetivo ← if 
(<var>[2].tipo_efetivo = <var>[3].tipo_efetivo) then 
<var>[2].tipo_efetivo else ERRO endif
 
Exercício 2
 Escreva uma gramática de atributos 
cuja base BNF é dada abaixo e que 
seja capaz de realizar verificação de 
tipos.
<atribuição> → <id> = <expr>
<id> → A | B | C
<expr> → <id> + <expr>
| <id> * <expr>
| (<expr>)
| <id>
 
Solução 2
Regra de sintaxe: <atribuição> → <id> = <expr>
Regra de semântica: <expr>.tipo_esperado ← <id>.tipo_efetivo
Regra de sintaxe: <id> → A | B | C
Regra de semântica: <id>.tipo_efetivo ← 
look_up( <id>.string)
Regra de sintaxe: <expr> → (<expr>[2])
Regra de semântica: <expr>.tipo_efetivo ← 
<expr>[2].tipo_efetivo
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
Regra de sintaxe: <expr> → <id>[2]
Regra de semântica: <expr>.tipo_efetivo ← 
<id>[2].tipo_efetivo
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
 
Solução 2
Regra de sintaxe: <expr> → <id>[3] + <expr>[3]
Regra de semântica: <expr>.tipo_efetivo ← 
if (<id>[3].tipo_efetivo = int ) e (<expr>[3].tipo_efetivo = int) then 
int
else real
endif
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
Regra de sintaxe: <expr> → <id>[4] * <expr>[4]
Regra de semântica: <expr>.tipo_efetivo ← 
if (<id>[4].tipo_efetivo = int ) e (<expr>[4].tipo_efetivo = int) then 
int
else real
endif
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
 
Referências Bibliográficas
 Sebesta, R. Conceitos de 
Linguagens de programação. 5ª 
edição. Bookman, 2003. Cap 3.