Gramáticas Livres de Contexto

Prévia do material em texto

GRAMÁTICAS LIVRES DE 
CONTEXTO 
Marcelo Guerra 
INTRODUÇÃO 
 “Linguagens formais” são mecanismos formais 
para representação e especificação de linguagens, 
baseados na chamada Teoria da Computação. 
 
INTRODUÇÃO 
 Voltaremos nossa atenção das LR para uma 
classe maior de linguagens “Linguagens Livres 
de Contexto”. 
INTRODUÇÃO 
 Essas linguagens têm uma notação natural, 
recursiva, chamada “Gramática Livre de 
Contexto”. 
INTRODUÇÃO 
 As GLC representam um papel importante na 
tecnologia de compiladores desde a década de 60 
 Facilitaram significativamente a implementação de 
analisadores sintáticos 
 Têm sido utilizadas para descrever formatos de 
documentos por meio daquilo que chamamos 
Definição de um Tipo de Documento DTD, e que são 
utilizadas na comunidade XML para troca de 
informações na WEB. 
INTRODUÇÃO 
 As representações podem ser feitas por: 
 
 Reconhecedores: dispositivos formais que servem 
para verificar se uma sentença pertence ou não a 
determinada linguagem. 
 Autômatos. 
 
 Geradores: dispositivos formais que permitem a 
geração sistemática de todas as sentenças de uma 
linguagem. 
 Gramáticas. 
DEFINIÇÃO DE GLC 
 Há 4 componentes importantes em uma descrição 
gramatical de uma linguagem: 
 
1. Um conjunto finito de símbolos que formam as cadeias da 
linguagem, chamados de símbolos terminais ou 
simplesmente terminais. 
 
2. Um conjunto finito de variáveis, cada uma representando 
um conjunto de strings, chamadas de não-terminais. 
 
3. Uma variável representando a linguagem sendo definida. 
Ela é o símbolo de início e as outras variáveis 
representam classes auxiliares. 
 
4. Um conjunto finito de produções ou regras que 
representam a definição recursiva da linguagem. 
PRODUÇÕES 
 Cada produção consiste em : 
 
a) Uma variável definida pela produção corrente, 
chamada cabeça da produção. 
 
b) O símbolo de produção:  
 
c) Uma string de zero ou mais terminais e variáveis, 
chamada corpo da produção, que determinam um 
modo de formar strings na linguagem da cabeça da 
regra. 
 Deixamos os terminais inalterados e substituímos cada 
variável por qualquer string conhecido para a linguagem 
dessa variável. 
GLCS 
 Representaremos uma GLC por meio da 
quádrupla G = (V, T, P, S), onde: 
 V é um conjunto de variáveis finito. 
 T é o conjunto de símbolos terminais. 
 P é o conjunto de produções. 
 S é a variável de início. 
EXEMPLO 
 Gpal = ({P}, {0,1}, A, P), onde A é o seguinte 
conjunto de produções: 
 
1. P   
2. P  0 
3. P  1 
4. P  0P0 
5. P  1P1 
 
•Essa Gramática Livre de Contexto representam os palíndromos 
com o alfabeto {0,1}. 
•Um palíndromo é um string lido da mesma forma, da esquerda 
para a direita ou da direita para esquerda. 
EXEMPLO - EXPRESSÕES 
 A gramática a seguir determina como são 
tipicamente formadas as expressões aritméticas 
em linguagens de programação. 
 
 Consideramos apenas os operadores + e * quando 
aplicados sobre identificadores formados pelos 
símbolos {a, b, 0, 1}. 
EXEMPLO - PRODUÇÕES 
1. E  I 
2. E  E + E 
3. E  E * E 
4. E  (E) 
5. I  a 
6. I  b 
7. I  Ia 
8. I  Ib 
9. I  I0 
10. I  I1 
 A gramática é formalmente 
definida por Gexp = ({E,I}, T, P, E), 
onde: 
 T = {0,1,a,b,+, *,(,)}. 
 P são as produções ao lado. 
DERIVAÇÕES 
 Aplicamos as regras para inferir se certos strings 
estão na linguagem de uma certa variável. 
 
 Existem duas abordagens: 
 Usar as regras do corpo para a cabeça realizando 
casamento de padrões (chamada inferência recursiva). 
 Expandir o símbolo da cabeça usando uma de suas regras 
até derivarmos um string composto apenas por terminais 
(chamada derivação). 
 
 A linguagem de uma gramática é o conjunto de todos 
os strings que podem ser obtidos através de derivação 
a partir do símbolo de início da gramática. 
EXEMPLO: 
INFERÊNCIA RECURSIVA PARA 
 
 
1. E  I 
2. E  E + E 
3. E  E * E 
4. E  (E) 
5. I  a 
6. I  b 
7. I  Ia 
8. I  Ib 
9. I  I0 
10. I  I1 
 
Inf 
recurs 
String 
inferido 
Para 
linguagem 
de 
Prod 
usada 
Str 
usado 
I a I 5 - 
II b I 6 - 
III b0 I 9 II 
IV b00 I 9 III 
V a E 1 I 
VI b00 E 1 IV 
VII a+b00 E 2 V,VI 
VIII (a+b00) E 4 VII 
IX a*(a+b00) E 3 V,VIII 
a*(a+b00) 
DERIVAÇÕES 
 O processo de derivação exige a introdução de um 
novo símbolo relacional:  
 
 Suponha G=(V, T, P, S). Seja A um string 
composto por terminais e variáveis onde A é uma 
variável e  e  são strings sobre (V + T)* 
 Se A   é uma produção de P, então 
 
 
Dizemos que “a produção A   é aplicada à string 
A para obter ” ou que “ deriva 
diretamente de A na gramática G”. 

G
A 
CONVENÇÕES 
1. Letras minúsculas 
próximas ao início do 
alfabeto: a,b,... 
 Representam terminais, 
assim como os dígitos e 
outros caracteres como 
(,+,... 
2. Letras minúsculas 
próximas ao fim do 
alfabeto: w,z,... 
 Representam strings de 
terminais. 
3. Letras maiúsculas 
próximas ao início do 
alfabeto: A, B,... 
 Representam variáveis. 
4. Letras maiúsculas 
próximas ao final do 
alfabeto: X, Y,... 
 Representam terminais 
ou variáveis. 
5. Letras gregas 
minúsculas: , ,... 
 Representam strings 
contendo terminais e/ou 
variáveis. 
6. Não há notação especial 
para strings de apenas 
variáveis. 
 Este conceito não 
desempenha nenhum 
papel importante. 
FECHAMENTO REFLEXIVO E TRANSITIVO 
DE  
 Suponha que 1, 2, ..., m são strings em (V+T)
*, 
m  1 e que 
 
 
 Dizemos então que 
 
 O relacionamento representa zero ou mais 
derivações. 
 Base: para qualquer string  de variáveis e terminais 
dizemos que  *  
 Indução: se  *  e   , então  *  
m
G
m
GG
  13221 ,...,,
m
G

*
1 
*
G

FECHAMENTO REFLEXIVO E TRANSITIVO 
DE  
  *  significa que existe uma sequencia de 
strings 1,...,n para algum n  1 tal que: 
1.  = 1 
2.  = n 
3. Para i=1,..., n-1 temos que i  i+1 
 
 Se  deriva de  por exatamente i passos, 
escrevemos: 
 

i

EXEMPLO 
 Considere a gramática para expressões 
aritméticas vista anteriormente. 
 
 A inferência de que a * (a + b00) 
pertence a L(Gexp) é dada pela seguinte 
derivação: 
 
E  E * E  I * E  a * E  a * (E)  
a * (E + E)  a * (I + E)  a * (a + E)  
a * (a + I)  a * (a + I0)  a * (a + I00)  
a * (a + b00) 
 
 
1. E  I 
2. E  E * E 
3. E  E + E 
4. E  (E) 
5. I  a 
6. I  b 
7. I  Ia 
8. I  Ib 
9. I  I0 
10. I  I1 
 
DERIVAÇÕES MAIS À ESQUERDA OU À 
DIREITA 
 Servem para restringir o número de escolhas na 
substituição de variáveis em derivações. 
 
 Derivação mais à esquerda: exige que a variável 
mais à esquerda seja escolhida para ser trocada 
pelo corpo de uma de suas produções. 
 
 Notação: (leftmost) 
 
 Derivação mais à direita: 
 
 Notação: (rightmost) 
 
*
lmlm
ou 
*
rmrm
ou 
EXEMPLO 
 O exemplo anterior de derivação é uma derivação 
mais à esquerda: 
 
 
 
 
 
 Podemos resumir escrevendo E a * (a + b00) 
 
 
 
 
E lm E * E lm I * E lm a * E lm a * (E) lm 
a * (E + E) lm a * (I + E) lm a * (a + E) lm 
a * (a + I) lm a * (a + I0) lm a * (a + I00) lm 
a *(a + b00) 
EXEMPLO 
 Uma derivação mais à direita equivalente existe 
 
 
 
 Esta derivação nos permite concluir que 
 E a* (a+b00) 
 
 Qualquer derivação tem uma derivação lm e uma 
rm equivalente (prova na seção 5.2). 
 
E rm E * E rm E * (E)  rm E * (E+E)  rm 
E * (E+I)  rm E * (E+I0)  rm E * (E+I00) rm 
E * (E+b00)  rm E * (a+b00)  rm a* (a+b00) 
A LINGUAGEM DE UMA GLC 
 Se G = (V, T, P, S) é uma GLC, a linguagem de G, 
denotada L(G), é o conjunto de strings terminais 
que têm derivações partindo-se do símbolo de início. 
 L(G) = { w  T* | S * w } 
 
 Se L é uma linguagem de uma GLC, L é dita uma 
Linguagem Livre de Contexto (LLC). 
 
 Exemplo: 
 A linguagem da gramática Gpal, apresentada 
anteriormente é uma LLC sobre {0,1}. 
FORMAS SENTENCIAIS 
 Derivações a partir de um símbolo inicial 
produzem strings que têm um papel especial. 
 
 Por esse motivo são chamadas formas sentenciais 
 Se G = (V, T P, S) é uma GLC, então qualquer  em 
(V + T)* tal que S *  é uma forma sentencial. 
 S  é uma forma sentencial mais à direita. 
 S  é uma forma sentencial mais à esquerda. 
 
 L(G) é composta pelas formas sentenciais em T*, 
ou seja, ela consistem em terminais apenas. 
 
EXEMPLO 
 E * (I + E) é uma forma sentencial de Gexp pois 
existe a derivação 
 E  E * E  E * (E)  E * (E + E)  E * (I + E) 
 
 Esta derivação não é lm nem rm, mas como exemplo 
desses tipos de derivações, temos: 
 
 a * E através de E lm E * E lm a * E é uma 
forma sentencial lm. 
 
 E * (E + E) através de E rm E * E rm E * (E) 
rm E * (E + E) é uma forma sentencial rm. 
EXERCÍCIOS 
 Seja G a gramática, dê uma derivação de 
ababccddcc 
 S → abSc | A 
 A → cAd | cd. 
 
 S → abSc 
 → ababScc 
 → ababAcc 
 → ababcAdcc 
 → ababccddcc 
 
EXERCÍCIOS 
 Seja G a gramática, dê uma derivação à 
esquerda de aabbba. 
 S → ASB | λ 
 A → aAb | λ 
 B → bBa | ba 
 
 S → ASB 
 → aAbSB 
 → aaAbbSB 
 → aabbSB 
 → aabbB 
 → aabbba 
EXERCÍCIOS 
 Seja G a gramática, dê uma derivação à direita de 
abaabbbabbaa. 
 S → ASB | λ 
 A → aAb | λ 
 B → bBa | ba 
 
 S → ASB 
 → ASbBa 
 → ASbbaa 
 → AASBbbaa 
 → AASbabbaa 
 → AAbabbaa 
 → AaAbbabbaa 
 → AaaAbbbabbaa 
 → Aaabbbabbaa 
 → aAbaabbbabbaa 
 → abaabbbabbaa 
EXERCÍCIOS 
 Para a gramática regular a seguir, dê uma 
expressão regular para a linguagem gerada pela 
gramática: 
 
 S → aA 
 A → aA | bA | b 
 
a(a ∪ b)*b 
 
EXERCÍCIOS 
 Para a gramática regular a seguir, dê uma 
expressão regular para a linguagem gerada pela 
gramática: 
 
 S → aA 
 A → aA | bB 
 B → bB | λ 
 
aa*b*b