Descrevendo a Sintaxe e a
Semântica - Parte 2
Disciplina: Modelos – Linguagens
Programação-I
Prof. Francisco Veríssimo Luciano
Análise Sintática Descendente
Recursiva
A análise sintática é o processo de construir
uma árvore de análise para uma dada string de
entrada.
Analisadores usualmente não analisam
lexemas, isto é deixado para o analisador
léxico, o qual é chamado pelo analisador
sintático.
Uma Análise sintática descendente recursiva,
traça uma árvore de análise na ordem de cima
para baixo, isto é uma análise sintática top-
down.
2
Análise Sintática Descendente
Recursiva
Cada não terminal na gramática tem um
subprograma associado a ele, o
subprograma de análise sintática possui
todas as formas que o não terminal pode
gerar.
A Análise descendente recursiva dos
subprogramas são construídas diretamente
das regras da gramática.
3
Análise Sintática Descendente
Recursiva
- Função de Análise Sintática
<expr> <termo> { ( + | - ) <termo> }
- Nós podemos usar a seguinte subprograma(escrito em C) de
análise descendente recursiva
void expr() {
fator(); /* análise do primeiro termo*/
while (proximo_token == sinal_mais ||
proximo_token == sinal_menos) {
lexico(); /* pegue o proximo token da entrada */
termo(); /* analisa o próximo termo*/
}
}
4
Gramática de Atributos
É utilizada para descrever mais detalhes da
estrutura de uma linguagem de
programação, do que é possível com uma
gramática livre de contexto.
Um dos motivos da criação da gramática de
atributos foi o de descrever a semântica
estática da linguagens de programação, já
que na BNF a descrição é uma tarefa
geralmente problemática.
5
Gramática de Atributos – Recursos
Adicionais
Conjunto de Atributos está associado a cada
símbolo gramatical X, é composto por: A(X) = S(X)
e I(X)
S(X) = Atributos sintetizados, são usados para
passar informações semânticas acima em uma
árvore de análise.
I(X) = Atributos herdados, passam informações
semânticas abaixo na árvore de análise.
Conjunto de Funções Semânticas, pode ser vista
como um conjunto de funções na forma:
S(X0) = f(A(X1),…,A(Xn)).
6
Gramática de Atributos - Exemplos
Gramática de Atributos
1. Regra de Sintaxe: <expr> -> <var>[1] + <var>[2]
Regra de Semântica:
<expr>.tipo_efetivo <var>[1].tipo_efetivo
Predicado:
<var>[1].tipo_efetivo = <var>[2].tipo_efetivo
<expr>.tipo_esperado = <expr>.tipo_efetivo
2. Regra de Sintaxe: <var> -> id
Regra de Semântica:
<var>.tipo_efetivo lookup (id, <var>)
7
Gramática de Atributos - Árvore de
Análise
Árvore de Análise para A := A + B.
8
Gramática de Atributos - Como os valores dos
atributos são computados?
1. Se todos os atributos são herdados, a árvore
pode ser na ordem top-down.
Ex.: <expr>.tipo_esperado herdado dos pais
2. Se todos os atributos são sintetizados, a árvore
pode ser na ordem bottom-up.
Ex.:<var>[1].tipo_efetivo lookup (A, <var>[1])
<var>[2].tipo_efetivo lookup (B, <var>[2])
<var>[1].tipo_efetivo = <var>[2].tipo_efetivo
9
Gramática de Atributos - Como os valores dos
atributos são computados?
3. Em muitos casos, os dois tipos de atributos
são utilizados, e algumas combinações de
ordem top-down e bottom-up precisam ser
utilizadas.
Ex.: <expr>.tipo_efetivo <var>[1].tipo_efetivo
<expr>.tipo_efetivo = <expr>.tipo_esperado
10
Semântica Dinâmica
Nenhuma notação ou formalismo
extensamente aceitos foram idealizados
para a semântica dinâmica.
Semântica Operacional : Descreve o
significado de um programa ao executar
suas instruções em uma máquina, seja ela
real ou simulada. A mudança de estado da
máquina (memória, registradores, etc.)
definem o significado da instrução.
11
Semântica Dinâmica - Processo
Básico
Para usar a semântica operacional para
linguagens de alto nível, é preciso uma máquina
virtual.
Um interpretador pura para qualquer linguagem
de programação pode ser construído em
software, sendo uma máquina virtual para a
linguagem.
Mas o software de interpretação pura, pode ter
problemas:
O detalhamento de características de um computador
particular teriam ações difíceis de entender.
Como a definição da semântica seria dependente da
máquina.
12
Semântica Dinâmica - Processo
Básico
Uma alternativa melhor: Uma completa
simulação do computador
Funcionamento do Processo:
Construir um tradutor (traduz o código fonte para
código de máquina de um computador idealizado)
Construir um simulador para o computador
idealizado
Avaliação da semântica operacional:
Boa se usada informalmente
Em geral é extremamente complexa se usada
formalmente
Baseia-se em algoritmos
13
Semântica Axiomática
A semântica axiomática é baseada na lógica
formal (cálculo de predicado de primeira ordem)
É baseada na lógica matemática
Propósito Original: Verificação formal do
programa
Abordagem: Define axiomas ou regras de
inferência para cada tipo de instrução na
linguagem (para permitir transformações de
expressões para outras expressões).
As expressões são chamadas de Asserções.
14
Semântica Axiomática
Uma asserção que precede uma instrução
que descreve os relacionamentos e
restrições entre variáveis, são chamadas
pré-condição.
Uma asserção seguida de uma instrução,
descrevendo novas restrições as variáveis
depois da execução da instrução é chamada
pos-condição.
15
Semântica Axiomática
Uma pré-condição fraca é menos restritiva
que irá garantir a validade da pós-condição
associada.
Exemplos:
Forma Pré-Pós: {P} instrução {Q}
Um exemplo: a := b + 1 {a > 1}
Uma possível pré-condição: {b > 10}
Pré-condição mais fraca: {b > 0}
16
Semântica Axiomática
Um Axioma é uma afirmação lógica que se
presume verdadeira
Uma Regra de Inferência é um método de
suposição da verdade de uma asserção,
baseando-se nos valores de outras
asserções.
Para usar a semântica axiomática numa LP,
dever ser definida uma regra de inferência
para cada tipo de instrução da linguaguem.
17
Semântica Axiomática
Avaliação de Semântica Axiomática:
1. Desenvolvimento de axiomas ou regras de
inferência para todas as instruções de uma
linguagem é uma tarefa difícil.
2. É uma ferramenta poderosa para pesquisar
provas de exatidão, e uma excelente estrutura
para argumentar sobre programas, mas ela
não é útil para usuários da linguagem nem
para os desenvolvedores de compiladores.
18
Semântica Denotacional
É o método mais rigoroso e conhecido para
descrever o significado de programas.
Baseado na teoria de funcões recursivas
O método mais abstrato de descrição de
semântica
Originalmente desenvolvido por Scott e
Strachey (1970).
19
Semântica Denotacional
O processo de construir a semântica
denotacional para uma linguagem:
Definir um objeto matemático para cada
entidade da linguagem
Definir uma função que mapeie as instâncias da
entidade sobre as instâncias dos objetos
matemáticos correspondentes.
20
Semântica Denotacional
O significado da construção da linguagem são
definidos somente por valores das variáveis
do programa.
A diferença entre as semânticas denotacional
e operacional:
Na semântica operacional, a mudança de estado é
definida por algoritmos codificados
Na semântica denotacional, eles são definidos por
rigorosas funções matemáticas
O estado de um programa, são os valores de
todas as variáveis s = {<i1, v1>, <i2, v2>,
…, <in, vn>}
21
Semântica Denotacional - Exemplo
1. Números Decimais
<dec_num> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| <dec_num> (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)
Mdec('0') = 0, Mdec ('1') = 1, …, Mdec ('9') = 9
Mdec (<dec_num> '0') = 10 * Mdec (<dec_num>)
Mdec (<dec_num> '1’) = 10 * Mdec (<dec_num>) + 1
…
Mdec (<dec_num> '9') = 10 * Mdec (<dec_num>) + 9
22
Semântica Denotacional
Avaliação da Semântica Denotacional:
Pode ser usada para provar a exatidão de programas
Providencia um rigoroso meio para pensar sobre
programas
Pode ser uma ajuda no desenvolvimento da
linguagem
Tem sido usado na geração de sistemas de
compiladores
23
