Compiladores - Resumão para P2
Aula VII
Derivação
Sequência de substituições de não-terminais por uma escolha das regras de produção gramaticais.
Método utilizado para a construção de uma cadeia específica de terminais, partindo de uma não-terminal inicial.
Existem várias derivações para a construção da mesma cadeia de não-terminais.
Verificar se a sequência de tokens é aceita:
- Inicia-se com um símbolo não-terminal chamado raiz.
- Aplica-se produções, substituindo não-terminais, até somente restarem terminais.
- Uma derivação substitui um não-terminal pelo lado direito de uma de suas produções.
- O símbolo “ -> “ denota um passo de derivação.
Exemplo
Solução
À esquerda e à dirieta
Derivação mais à esquerda:
é a sequência de formas sentenciais que se obtém derivando sempre o símbolo não-terminal mais à esquerda.
Derivação mais à direita:
é a sequência de formas sentenciais que se obtém derivando sempre o símbolo não-terminal mais à direita.
À esquerda
À direita
Observe que o código final é o mesmo nos dois casos.
Exercício 1
Solução
Apenas a 3
Por que 1 não está na gramática?
Pois é impossível ter apenas 1 C após usar o Y.
Por que 2 não está na gramática?
Pois é impossível ter 2 Cs sem B.
Por que 4 não está na gramática?
Pois é impossível ter 3 Bs com apenas 2 Cs.
Propriedades
A recursividade em uma GLC é importante, pois a possibilita a construção da repetição.
As produções vazias (ℇ - produções) são úteis para definir estruturas opcionais da linguagem.
Ambiguidade
Quando existe mais de uma árvore de derivação para a mesma sentença.
Isso representa um problema para o analisador sintático, pois ele não especifica com precisão a estrutura sintática do programa.
O problema pode ser comparado aos autômatos não determinísticos, onde dois caminhos podem aceitar a mesma cadeia
Isso pode mudar todo o entendimento do comando -> mudar o if e else.
Porém, a eliminação de ambiguidade de uma gramática não é tão simples como a eliminação de não-determinismo em autômatos.
O que deve ser feito:
- Estabelecer uma regra que especifique para cada caso ambíguo qual é o caminho correto.
Exemplo
A ordenação das operações matemáticas está errada.
Eliminação da ambiguidade
Eliminação de ambiguidade:
- Tratar conceitos de precedência e associatividade.
- Especificar uma ordem na avaliação dos operadores.
- Operadores com maior precedência são avaliados primeiro.
- Operadores de igual precedência são avaliados de acordo com a associatividade (esquerda-direita, vice-versa).
Precedência
Agrupamentos dos operadores de igual precedência.
Para cada nível de precedência introduz-se um não terminal e uma regra gramatical.
Associatividade
Cria-se regras gramaticais recursivas à esquerda ou à direita.
Correção
Exemplo 2
Solução
A eliminação da ambiguidade pode ser feita a seguinte forma:
Associar cada ‘else’ ao ‘if’ mais próximo que ainda não tenha sido associado.
Exercício 2
Solução
É ambígua, pois não tem níveis diferentes, ou seja, a soma e a multiplicação possuem o mesmo nível de prioridade.
Primeira representação -> ambíguo.
Segunda representação -> não ambíguo.
Exercício 3
Solução
Exercício 4
Solução
Exercício 5
Solução
G1 e G3 são ambíguas, pois possuem dois símbolos não-terminais (S) do lado direito.
G2 apresente apenas 1, por isso não é.
Aula VIII
Notação BNF
Uma das representações formais utilizadas para descrever a sintaxe de uma linguagem.
Desenvolvida por John Backus e Peter Naur.
É possível construir um parser (analisador sintático) automaticamente com apenas a gramática em BNF.
-
Símbolos não-terminais são representados por textos delimitados por “<” e “>”.
-
O meta-spimbolo “ -> “ é substituido por “ ::= “.
-
Todas as alternativas de substituição para um mesmo não-terminal são agrupadas, separando-as com .
Exemplo
Exemplo 2
BNF estendida com fecho transitivo
” * “ = operação de fecho
1º
| linha < X > ::= a< X > | a |
ao invés de ficar na recursão “X” deriva “aX” ou “a” (infinitos “a”s), podemos reduzir ao símbolo mínimo (“a”), ou seja, “X” deriva “ aa* “.
” aa* “ já está passando a ideia da recursão.
então fica < X > ::= aa*
2º
| linha < Z > ::= cd< Z > | e< Z > | f |
ao invés de ficar na recursão “Z” deriva “cd
” (cd e)* “ já está passando a ideia da recursão.
| então fica < Z > ::= (cd | e)* | f |
Simplificando ainda mais
BNF extensões
” [ a ] “ -> “a” opcional.
| ” [ a | b ] “ -> “a” ou “b” opcionais. |
| ” { a | b } “ -> vários itens (“a” ou “b”). |
” {“;”
Exemplo
Exercício 1
BNF:
| < S > ::= (< M >) | a | b |
| < M > ::= < M >;< N > | < N > | |
| < N > ::= < N >,< S > | < S > |
Qual a representação formal?
Solução
Representação formal:
G = (V, T, P, S)
G = ({M,N,S}, {a, b, (, ), “,” , ;}, P, S)
P = {
S -> (M) | a | b
M -> M;N | N
N -> N,S | S
}
Exercício 2
Gramática:
G = (Vt, Vn, P, S), sendo:
Vt = {a, b},
Vn = {A, S},
P = {S -> A, A -> aAb, A -> ab}
Qual a gramática em notação BNF?
Solução
BNF:
< S > ::= < A >
< A > ::= a< A >b
< A > ::= ab
Autômato com pilha
Parser é definido através de uma gramática livre de contexto, o que nos obriga a utilizar um autômato a pilha na sua implementação.
O autômato a pilha é a ferramenta básica na construção do parser.
Estrutura da pilha
Como funciona?
Dependendo do estado corrente, símbolo da fita e símbolo da pilha, determina o novo estado e a palavra a ser gravada na pilha.
Um AP é definido pela 6-tupla:
E = alfabeto
Q = conjunto de estados
& = funções transição
q0 = estado inicial
F = estados finais
V = alfabeto da pilha
Observação
Exemplo
Construindo um AP
1) pilha começa não vazio - tem simbolo inicial (símbolo inicial da gramática).
2) apenas 1 estado - aceitação de pilha vazia.
2.1) &(q,x,x) = (q,λ), para cada simbolo (x) do alfabeto do alfabeto.
2.2) para cada A -> y, a transição &(q,λ,A) = (q,y).
Exemplo
Exemplo 2
Aula 10
Exercício
Árvore sintática gerada
Análise sintática descendente
-
Toma-se uma determinada palavra P e o símbolo inicial S da gramática.
-
Procura-se por uma regra de derivação que permita derivar P em sua totalidade ou pelo menos se aproximar desta.
-
Repetir o passo acima até que a palavra P não apresente mais símbolos não-terminais.
-
Por fim, verifica-se se a cadeia obtida coincide com P. No caso negativo, tem-se que a cadeia analisada não pertence a linguagem.
Analisador sintático preditor
-
O analisador recebe uma sequência de entrada.
-
Manipula uma estrutura de dados tipo pilha.
-
Para cada símbolo de entrada, consulta uma tabela de análise sintática para aplicação da regra.
-
Emite uma sequência de saída (regras).
Observações:
Entrada
Sentença a ser analisada seguida pelo delimitador $.
Pilha: contém uma sequência de símbolos da gramática precedida pelo indicador de base de pilha $.
TAS: é uma matriz M[A,a], onde A é um não-terminal e a é um terminal ou dólar $.
O topo da pilha é na direita
Saída
Constará as produções aplicadas a partir do símbolo inicial (S) na geração da sentença.
Regras
-
1 - Se X é um terminal = próximo_símbolo = $, o analisador encerra sua atividade e comunica fim da análise sintática com sucesso.
-
2 - Se X é um terminal = próximo_símbolo ≠ $, o analisador elimina X do topo da pilha e avança para o próximo símbolo de entrada.
-
3 - Se X é um terminal ≠ próximo_símbolo, o analisador acusa um erro de sintaxe (ativa rotina de tratamento de erros).
-
4 - Se X é um não-terminal, o analisador consulta M[X,próximo_símbolo]
a) Se a resposta for uma regra de produção X ::= MVU, o analisador desempilha X do topo da pilha e empilha UVM, sendo M no topo da pilha.
b) Se M[X, próximo_símbolo] = ERRO, o analisador acusa um erro de sintaxe e ativa rotina de tratamento de erros.
Exemplo 1
Exercício 1
Exercício 2
Exercício 3
Exercício 4
Da erro, não é possível completar.
Aula 11
Como construir a tabela?
Analisador preditor
- conjunto FIRST
- conjunto FOLLOW
Etapas do analisador preditor
Durante análise descendente -> as variáveis FIRST e FOLLOW nos ajudam a escolher qual produção deve ser usada, com base no próxim símbolo de entrada.
| Dada uma entrada ‘a’ e o não-terminal ‘A’, deve-se saber qual das produções alternativas ‘A -> B1 | B2 | …’ deriva a sequência que inicia por ‘a’. |
Primeiro são calculados os conjuntos de primeiros símbolos produzios por todas as alternativas na gramática, ou seja, os conjuntos FIRST.
Sendo Y uma string de símbolos e não-terminas, FIRS(Y) é o conjunto de todos os terminais que podem iniciar strings derivadas de Y.
Algoritmo geral
Regras do FIRST
Exemplo 1
Tabela inicial
Todos os símbolos não-terminais iniciam com vazio.
Nota: λ = E (vazio).
Calculando ‘S’
Firts(S) = First(ABS) U First(aA)
First(ABS) = First(A) \ {λ}
First(ABS) = ∅ \ {λ}
First(ABS) = ∅
Calculou apenas o ‘A’ de ‘ABS’, pois ‘A’ não possui ‘λ’, então não precisa calcular o ‘B’.
First(aA) = First(a) \ {λ}
First(aA) = {a} \ {λ}
First(aA) = {a}
Calculou apenas o ‘a’ de ‘aA’, pois ‘a’ não possui ‘λ’, então não precisa calcular o ‘A’.
First(S) = {a}
Calculando ‘A’
First(A) = First(λ) U First(a)
First(λ) = {λ} First(a) = {a}
First(A) = {λ,a}
Calculando ‘B’
First(B) = First(Bb) + First(cd)
First(Bb) = First(B) \ {λ}
First(Bb) = ∅ \ {λ}
First(Bb) = ∅
Calculou apenas o ‘B’ de ‘Bb’, pois ‘B’ não possui ‘λ’, então não precisa calcular o ‘b’.
First(cd) = First(c) \ {λ}
First(cd) = {c} \ {λ}
First(cd) = {c}
Calculou apenas o ‘c’ de ‘cd’, pois ‘c’ não possui ‘λ’, então não precisa calcular o ‘d’.
First(B) = {c}
Nova tabela
Recalcular
Como FIRST de ‘S’ depende de ‘A’ e ‘A’ teve seu valor alterado, devemos recalcular ‘S’.
Calculando ‘S’
Firts(S) = First(ABS) U First(aA)
First(ABS) = First(A) \ {λ}
First(ABS) = {λ,a} \ {λ}
First(A) agora tem ‘λ’, então vamos calcular o First(B).
First(ABS) = {a} U First(B) \ {λ}
First(ABS) = {a} + {c}
First(aA} = {a}
First(S) = {a,c}
Nova tabela 2
Exemplo 2
First(S) = First(cAd) = {c}
First(A) = First(b) U First(a) = {b,a}
Exemplo 3
Podemos simplificar
| Z ::= d | XYZ |
| Y ::= λ | c |
| X ::= Y | a |
Tabela inicial
Z = ∅
Y = ∅
X = ∅
XYZ = ∅
Calculando ‘Z’
First(Z) = First(d) U First(XYZ)
First(Z) = {d} U {∅}
First(Z) = {d}
First(Y) = First(λ) U First(c)
First(Y) = {λ} U {c}
First(Y) = {λ,c}
First(X) = First(Y) U First(a)
First(X) = {λ,c} U {a}
First(X) = {λ,c,a}
Nova tabela
First(Z) = {d}
First(Y) = {λ,c}
First(X) = {λ,c,a}
Recalculando Z
First(Z) = First(d) U First(XYZ)
First(Z) = {d} U First(X) \ {λ} U First(YZ)
First(Z) = {d} U {c,a} U First(Y) \ {λ} U First(Z)
First(Z) = {d} U {c,a} U {c} U First(Z) \ {λ}
First(Z) = {d} U {c,a} U {c} U {d}
First(Z) = {c,a,d}
Nova tabela 2
First(Z) = {c,a,d}
First(Y) = {λ,c}
First(X) = {λ,c,a}
Exemplo 4
Podemos simplificar
S ::= AaAb | Bb
A ::= λ
B ::= λ
Tabela inicial
S = ∅
A = ∅
B = ∅
Calculando S
First(S) = First(AaAb) U First(B)
First(S) = First(A) U First(B)
First(S) = {∅} U {∅}
First(S) = {∅}
Calculando A
First(A) = {λ}
Calculando B
First(B) = {λ}
Nova tabela
First(S) = {∅}
First(A) = {λ}
First(B) = {λ}
Recalculando S
First(S) = First(AaAb) U First(B)
First(S) = First(A) \ {λ} U First (aAb) U First(B) U First(b)
First(S) = {a} U {b}
First(S) = {a,b}
Nova tabela 2
First(S) = {a,b}
First(A) = {λ}
First(B) = {λ}
Exemplo 5
S -> cAa
A -> cB | B
B -> bcB | λ
Tabela inicial
S = ∅
A = ∅
B = ∅
First(B) = First(bcB) U First(λ)
First(B) = {b} U {λ}
First(B) = {b,λ}
First(A) = First(cB) U First(B)
First(A) = {c} U {b,λ}
First(A) = {c,b,λ}
First(S) = First(cAa)
First(S) = {c}
Nova tabela
S = {c}
A = {b,c,λ}
B = {b,λ}
Exercício
S -> aS | Ab
A -> XYZ | λ
X -> cS | λ
Y -> dS | λ
Z -> eS
Tabela inicial
S = ∅
A = ∅
X = ∅
Y = ∅
Z = ∅
First(Z) = First(eS)
First(Z) = {e}
First(Y) = First(dS) U First(λ)
First(Y) = {d} U {λ}
First(Y) = {d,λ}
First(X) = First(cS) U First(λ)
First(X) = {c} U {λ}
First(X) = {c,λ}
First(A) = First(XYZ) U First(λ)
First(A) = First(X) \ {λ} U First(Y) \ {λ} U First(Z) U First(λ)
First(A) = {c} U {d} U {e} U {λ}
First(A) = {c,d,e,λ}
First(S) = First(aS) U First(Ab)
First(S) = {a} U First(A) \ {λ} U First(b)
First(S) = {a} U {c,d,e} U {b}
First(S) = {a,b,c,d,e}
Nova tabela
First(S) = {a,b,c,d,e}
First(A) = {c,d,e,λ}
First(X) = {c,λ}
First(Y) = {d,λ}
First(Z) = {e}
Aula 12
Conjunto Follow.
Criação da tabela preditiva.
FOLLOW - Regras
follow(S) = {$}
follow(A) = First(b) \ {λ}
follow(A) = {b}
follow(Z) = follow(A)
follow(Z) = {b}
follow(Y) = first(Z)
follow(Y) = {e}
follow(X) = first(Y) U first(Z)
follow(x) = {d,λ} U {e}
follow(x) = {d,e}
Recalculando S
follow(S) = follow(X) U follow(Y) U follow(Z)
follow(S) = {$,b,d,e}
Como o ‘S’ é o símbolo inicial, Follow(S) recebe ‘$’ e deixamos o resto por último.
Follow(A) é ‘b’ pois em ‘S’ temos ‘A’ com ‘b’ em seguida (lado direito).
Follow(Z) é ‘b’ pois eu tenho ‘Z’ em ‘XYZ’, como não tem nada do lado direito, pega o mesmo valor de FOLLOW(A).
Follow(Y) é ‘e’ pois o FIRST(Z) é ‘e’ (pegou o FIRST pois o ‘Z’ está no lado direito).
Follow(X) é ‘d,e’ pois temos ‘Y’ e ‘Z’ no lado direito e o First de ‘Y’ e ‘Z’ é ‘d,λ’ e ‘e’ respectivamente (só calculou o First de Z pois Y tem palavra vazia).
Agora, vamos recalcular o Follow(S), que é ‘$’ com a soma do Follow(X), Follow(Y) e Follow(Z) (pois S não tem nada do lado direito então pega X, Y e Z),resultando em ‘$,b,d,e’.
Exercício ENADE
Tabela preditiva M(X,t)
Exemplo 1
Linha ‘S’.
First(cAa) = {c}, por isso a localização em ‘S’, ‘c’.
Linha ‘A’.
First(B) = {b,λ}, por isso a localização em ‘A’, ‘b’.
Como First(B) tem {λ}, analisamos o Follow(B) = {a}, ou seja, também coloca em ‘A’, ‘a’.
First(cB) = {c}, por isso a localização em ‘A’, ‘c’.
Linha ‘B’
First(λ) = {λ}, analisamos o Follow(B) = {a}, por isso a localização em ‘B’, ‘a’.
First(bcB) = {b}, por isso a localização em ‘B’, ‘b’.
O resto é erro.
Exercício 1
FIRST
First(A) = First(λ)
First(A) = {λ}
First(B) = First(λ)
First(B) = {λ}
First(S) = First(AaAb) U First(Bb)
First(S) = First(AaAb) \ {λ} U First(Bb) \ {λ}
First(S) = {a} U {b}
First(S) = {a,b}
FOLLOW
Follow(S) = {$}
Não existe ‘S’ em nenhuma outra parte, então fica assim.
Follow(A) = First(aAb) \ {λ} U First(b) \ {λ}
Follow(A) = {a} U {b}
Follow(A) = {a,b}
Follow(B) = First(b)
Follow(B) = {b} \ {λ}
Follow(B) = {b}
Exercício 2
Linha Z
First(eS) é {s}, logo, ‘Z -> eS’ vai em ‘Z,e’
Linha Y
First(dS) é {d}, logo, ‘Y -> dS’ vai em ‘Y,d’
Como tem {λ}, devemos seguir Follow(Y) que é {e}, , logo, ‘Y -> λ’ vai em ‘Y,e’
Linha X
First(cS) é {c}, logo, ‘X -> cS’ vai em ‘X,c’
Como tem {λ}, devemos seguir Follow(X) que é {d,e}, , logo, ‘X -> λ’ vai em ‘X,d’ e ‘X,e’
Linha A
First(XYZ) é {c,d,e}, logo, ‘A -> XYZ’ vai em ‘A,c’, ‘A,d’ e ‘A,e’
Como tem {λ}, devemos seguir Follow(A) que é {b}, , logo, ‘A -> λ’ vai em ‘A,b’
Linha S
First(aS) é {a}, logo, ‘S -> aS’ vai em ‘S,a’
First(Ab) é {c,d,e,λ}, e como possui {λ}, calculamos o {b} também, então ‘S -> Ab’ vai em ‘S,b’, ‘S,c’, ‘S,d’, ‘S,e’
Exercícios para treinar
…
Aula 13
Analisador semântico
Verifica o uso de:
- Análise contextual - declarações prévias de variáveis, procedimentos, etc
- Checagem de tipos - o tipo da variável é o correto para o operador?
- Unicidade - o identificador é único no escopo?
Verificações semânticas
- X foi declarado apenas uma vez?
- X foi declarado/definido antes do seu primeiro uso?
- X é um tipo escalar, um array, uma função, ou uma classe?
- X é declarado mais nunca utilizado?
- A que declaração X se refere?
- Os tipos de uma expressão são compatíveis?
- As dimensões casam com o declarado?
Tipos de análise semânticas
- Estática: em tempo de compilação (linguagens tipadas).
- Dinâmica: em tempo de execução (variáveis são determinadas pelo con texto de uso).
Gramática de atributos
Identifica quais ações serão realizadas em relação ao:
- comportamento semântico das operações
- checagem de tipos
- manipulação de erros
- tradução do programa
Tabela de símbolos
Permite saber durante a compilação de um programa:
- tipo e endereço dos elementos
- escopo dos elementos
- número e tipo dos parâmetros de um procedimento
Gramática de atributos
Uma das formas de descrever a semântica.
- São agregados atributos aos símbolos não-terminais da gramática.
- São agregadas regras semânticas às produções da gramática, as quais computam os valores dos atributos dos símbolos.
Atributos VS Regras Semânticas
Atributos: elementos associados aos símbolos gramaticais.
- Ex: valor e escopo, representados na forma x.valor, x.escopo
Regras semânticas: manipulam os atributos
- Ex.: regra para somar os atributos valores de 2 variáveis -> x:=a+b, cuja regra é x.valor:=a.valor+b.valor
Amarração
Atributos podem ser fixados durante a compilação ou na execução do programa.
A associação de um valor a um atributo é chamada “amarração” do atributo.
Acontece em “tempo de amarração”:
– Em tempo de compilação, amarração estática – Em tempo de execução, amarração dinâmica
Exemplo 1
Cálculo dos atributos
Deixe um comentário