Embed Size (px)
Citation preview
Tópicos
• Introdução• O problema de descrever a sintaxe• Métodos formais para descrever a
sintaxe• Gramáticas de atributos• Descrevendo o significado dos
programas: semântica dinâmica
Introdução
• Sintaxe– A forma ou estrutura das expressões, das instruções e das
unidades de programas
• Semântica– O significa das expressões, das instruções e das unidades de
programas
• Exemplo: comando if na linguagem C– Sintaxe
• if (<expr>) <instrução>
– Semântica• Se o valor da expressão for verdadeiro, a instrução será
executada
Introdução
• A sintaxe e a semântica provêm a definição da linguagem– Usuários da definição da linguagem
• Projetistas de linguagens• Programadores
• Descrever a sintaxe é mais fácil do que a semântica– Uma notação concisa e universal para a sintaxe
existe
Descrevendo a sintaxe: terminologia
• Uma sentença é uma cadeia de caracteres sobre um alfabeto
• Uma linguagem é uma conjunto de sentenças• Um lexema é a unidade sintática de mais
baixo nível de uma linguagem– Exemplos: *, sum, begin
• Um token é uma categoria dos lexemas– Exemplo: identificador, op_mult
Descrevendo a sintaxe: terminologia
• Em alguns casos, um token tem apenas um único lexema possível.
• Exemplo de instrução em C– index = 2 * cont + 17;
ponto_e_vírgula;
int_literal17
op_soma+
identificadorCont
op_mult*
int_literal2
sinal_igual=
Identificadorindex
TokenLexema
Definição formal de linguagens
• Reconhecedores de linguagens
– Um dispositivo que recebe uma string como entrada e verifica se a mesma pertence a linguagem
– Exemplo: análise sintática (parte de um compilador)
• Geradores de linguagens
– Um dispositivo que gera sentenças de uma linguagem
– É possível determinar se a sintaxe de uma sentença em particular está correta através da comparação dela com a estrutura do gerador
Métodos formais para descrever a sintaxe
• Forma de Backus-Naur e Gramática Livre de Contexto– Método mais usado para descrever a
sintaxe das linguagens de programação
• Extended BNF (Backus-Naur Form)
– Aumenta readability e writability da BNF
BNF e Gramáticas Livres de Contexto
• Gramáticas Livres de Contexto– Desenvolvida por Noam Chomsky nos
meados da década de 1950
– Objetivando descrever a sintaxe das linguagens naturais
– Define uma classe de linguagens chamadas de linguagens livres de contexto
Backus-Naur Form (BNF)
• Backus-Naur Form (1959)– Inventada por John Backus para descrever o Algol
58– BNF é equivalente a gramáticas livre de contexto– BNF é uma metalinguagem usada para descrever
outras linguagens– Em BNF, abstrações são usadas para representar
classes de estruturas sintáticas• Agem como variáveis sintáticas (também chamadas de
símbolos não-terminais)
BNF Fundamentos
• Não-terminais: BNF abstrações
• Terminais: lexemas e tokens
• Gramática: uma coleção de regras
– Exemplos de regras BNF:<ident_list> → identifier | identifier, <ident_list>
<if_stmt> → if <logic_expr> then <stmt>
Abstrações
Regras BNF
• Uma regra possui um lado esquerdo (LHS) e um lado direito (RHS), e consiste de símbolos terminais e não-terminais
• Uma gramática é um conjunto não vazio de regras
• Uma abstração (ou símbolo não-terminal) pode ter mais de um RHS
<stmt> → <single_stmt>
| begin <stmt_list> end
Descrevendo Listas
• Listas sintáticas são descritas usando recursão<ident_list> → ident
| ident, <ident_list>
• Uma derivação é a aplicação de regras repetidas vezes, começando com um símbolo inicial e finalizando com uma sentença formada de símbolos terminais
Uma gramática para uma pequena linguagem
Uma gramática para instruções de atribuição simples
Árvore de Análise (Parse Tree)
Ambigüidade em gramáticas
• Uma gramática é ambígua se e somente se ela gera uma sentença para a qual há duas ou mais árvores de análise distintas
Uma gramática ambígua para instruções de atribuição simples
Duas árvores de análise para a mesma sentença
Uma gramática não-ambígua para expressões
A árvore de análise única para a expressão
Associatividade de operadores
• Associatividade de operadores podem ser indicados pela gramática
<expr> -> <expr> + <expr> | const (ambígua)
<expr> -> <expr> + const | const (não-ambígua)
<expr><expr>
<expr>
<expr> const
const
const
+
+
Uma árvore de análise ilustrando a associatividade da adição
BNF estendida
• Partes opcionais são colocadas entre colchetes [ ]<proc_call> -> ident [(<expr_list>)]
• Opções de múltipla escolha, partes alternativas da RHS são colocadas dentro de parênteses e separadas por barras verticais<term> → <term> (+|-) const
• Repetições (0 ou mais) são colocadas dentro de chaves { }<ident> → letter {letter|digit}
BNF e EBNF
Gramáticas de Atributos
• Gramáticas livres de contexto (GLC) não podem descrever toda a sintaxe de linguagens de programação– Compatibilidade de tipos
• Pois a gramática iria se tornar grande demais – Exigindo símbolos não-terminais e regras
adicionais
• Gramáticas de atributos incorporam informações semânticas nas parse trees
Gramáticas de Atributos
• Exemplos de regras que não podem ser especificadas na BNF– Determina que todas as variáveis devem ser
declaradas antes de serem referenciadas– O end do subprograma Ada seguido de um nome
deve coincidir com o nome do subprograma
• Esses dois problemas exemplificam a categoria das regras de linguagem chamada de semântica estática– Leva esse nome pois a análise necessária para
verificar essas especificações pode ser feita na compilação
Gramáticas de Atributos:Exemplo
• Em um procedimento em Ada, o nome no end
deve ser igual ao 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
Gramáticas de Atributos:Exemplo
Verificação das regras de tipos de uma instrução de atribuição simples
Parte sintática da gramática<assign> → <var> = <expr><expr> → <var> + <var> | <var><var> → A | B | C
Observações:As variáveis podem ser de dois tipos: int ou real
O tipo do lado esquerda expressão deve ser o mesmo do lado direito
O tipo da expressão quando os tipos dos operandos são diferentes é real
Gramáticas de Atributos do exemplo anterior
Gramáticas de Atributos:uma árvore de análise
Gramáticas de Atributos:computando os valores de atributo
1. <var>.tipo_efetivo ← look-up(A) • Regra 4
2. <expr>.tipo_esperado ← var.tipo_efetivo• Regra 1
3. <var>[2].tipo_efetivo ← look-up (A) • Regra 4
<var>[3].tipo_efetivo ← look-up (B) • Regra 4
4. <expr>.tipo_efetivo ← int ou real • Regra 2
5. <expr>.tipo_esperado = <expr>.tipo_efetivoé TRUE ou FALSE
• Regra 2
Gramáticas de Atributos:computando os valores de atributo
• Valores finais nos vértices, adotando A como real e B como int
Gramáticas de Atributos:avaliação
• Têm sido utilizadas em diversas aplicações– Descrições completas da sintaxe e da semântica
de linguagens de programação– Como a definição formal de uma linguagem
(geração de compiladores)– Sistemas de processamento de linguagens naturais
• Dificuldades– Complexo e grande– Dificuldade de leitura e escritas das gramáticas
