Linguagens livre de contexto

Prévia do material em texto

1
 Linguagens Livres de 
Contexto
 
2
 
Linguagens 
Regulares
}{ nnba }{
Rww
3
 
Linguagens Regulares
}{ nnba }{
Rww
Linguagens Livres de Contexto
4
Linguagens Livres de Contexto
Autômato
de Pilha
Gramáticas
Livres de Contexto
pilha
autômato
5
 Gramática Livre de 
Contexto
 
6
Exemplo
 
Uma gramática livre de contexto:


S
aSbS
aabbaaSbbaSbS 
G
Uma derivação:
7
 
Uma gramática livre de contexto:
:


S
aSbS
aaabbbaaaSbbbaaSbbaSbS 
G
Outra derivação:
8


S
aSbS
)(GL
(((( ))))
}0:{ nba nn
9



S
bSbS
aSaS
abbaabSbaaSaS 
Uma gramática livre de contexto:
: G
Uma derivação:
Exemplo
10



S
bSbS
aSaS
abaabaabaSabaabSbaaSaS 
Uma gramática livre de contexto:
G
Outra derivação:
11



S
bSbS
aSaS
)(GL }*},{:{ bawwwR 
12



S
SSS
aSbS
ababSaSbSSSS 
Uma gramática livre de contexto:
: G
Uma derivação:
Exemplo
13



S
SSS
aSbS
abababaSbabSaSbSSSS 
Uma gramática livre de contexto:
G
Uma derivação:
14



S
SSS
aSbS
}prefixanyin 
)()( and
),()(:{
v
vnvn
wnwnw
ba
ba


() ((( ))) (( ))
)(GL
15
Definição: Gramática Livre de 
Contexto
Gramática
Produções da forma:
xA
x é um string de variáveis e terminais
),,,( PSTVG 
Variáveis Símbolos
terminais
Variável
Inicial
16
Definição: Gramática Livre de 
Contexto
Uma linguagem é livre de contexto
se e soemente se
existe uma gramática livre de contexto 
 
tal que
L
G
)(GLL 
17
Ordem de Derivação
 ABS.1


A
aaAA
.3
.2


B
BbB
.5
.4
aabaaBbaaBaaABABS
54321

derivação mais à esquerda:
aabaaAbAbABbABS
32541

derivação mais à direita:
18
|AB
bBbA
aABS



derivação mais à esquerda:
abbbbabbbbB
abbBbbBabAbBabBbBaABS


derivação mais à direita:
abbbbabbBbb
abAbabBbaAaABS


19
Árvores de Derivação
 
20
 
ABS
ABS |aaAA |BbB
S
BA
21
ABS |aaAA |BbB
aaABABS 
a a A
S
BA
22
ABS |aaAA |BbB
aaABbaaABABS 
S
BA
a a A B b
23
ABS |aaAA |BbB
aaBbaaABbaaABABS 
S
BA
a a A B b

24
ABS |aaAA |BbB
aabaaBbaaABbaaABABS 
S
BA
a a A B b
 
Árvore de derivação
25
aabaaBbaaABbaaABABS 
yield
aab
baa


S
BA
a a A B b
 
Derivation Tree
ABS |aaAA |BbB
26
Árvore de Derivação Parcial 
 
ABS
S
BA
Árvore de derivação parcial
ABS |aaAA |BbB
27
 
aaABABS 
S
BA
a a A
Árvore de derivação parcial
28
 
aaABABS 
S
BA
a a A
Árvore de derivação parcial
forma 
sentencial
yield
aaAB
29
 
aabaaBbaaBaaABABS 
aabaaAbAbABbABS 
S
BA
a a A B b
 
Mesma árvore de derivação
Algumas vezes, ordem de derivação não 
importaMais à esquerda:
Mais à direita:
30
Ambiguidade
 
31
aEEEEEE |)(|| 
aaa 
E
EE
EE

a
a a

aaaEaa
EEaEaEEE
*

derivação mais à esquerda
32
aEEEEEE |)(|| 
aaa 
E
EE

a a

EE a
aaaEaa
EEaEEEEEE


lederivação mais à direita
33
aEEEEEE |)(|| 
aaa 
E
EE

a a

EE a
E
EE
EE

a
a a

Duas árvores de derivação
34
A gramática aEEEEEE |)(|| 
é ambígua:
E
EE

a a

EE a
E
EE
EE

a
a a

string aaa  tem 2 árvores de derivação
35
string aaa  tem 2 derivações mais à esq.
aaaEaa
EEaEEEEEE


aaaEaa
EEaEaEEE
*

A gramática aEEEEEE |)(|| 
é ambígua:
36
Definição:
Uma gramática livre de contexto 
é ambígua
se algum string tem:
 duas ou mais árvores de derivação
G
)(GLw
37
Em outras palavras:
Uma gramática livre de contexto 
é ambígua
se algum string tem:
 duas ou mais derivações mais à esquerda
G
)(GLw
(ou mais à direta)
38
Porque ambiguidade importa?
E
EE

a a

EE a
E
EE
EE

a
a a

aaa 
tome 2a
39
E
EE


EE
E
EE
EE


222 
2
2 2 2 2
2
40
E
EE


EE
E
EE
EE


6222 
2
2 2 2 2
2
8222 
4
2 2
2
6
2 2
24
8
41
E
EE
EE


6222 
2
2 2
4
2 2
2
6
Resultado correto:
42
•Queremos remover ambiguidade
• Ambiguidade é ruim 
para linguagens de programação
43
Modificamos a gramática ambígua:
aEEEEEE |)(|| 
Nova gramática não ambígua:
aF
EF
FT
FTT
TE
TEE






)(
44
aF
EF
FT
FTT
TE
TEE






)(
aaaFaaFFa
FTaTaTFTTTEE


E
E T
T  F
F
a
T
F
a
a
aaa 
45
E
E T
T  F
F
a
T
F
a
a
aaa 
Árvore de derivação única
46
A gramática : 
aF
EF
FT
FTT
TE
TEE






)(
não é ambígua:
Todo string tem
uma única árvore de derivação 
G
)(GLw
47
Ambiguidade Inerente
Algumas linguagens livres de contexto
têm apenas gramáticas ambíguas
Exemplo: }{}{ mmnmnn cbacbaL 
|
|11
aAbA
AcSS


|
|22
bBcB
BaSS

21 | SSS
48
O string nnn cba
tem duas árvores de derivação
S
1S
S
2S
1S c 2Sa
	Linguagens Livres de Contexto
	PowerPoint Presentation
	Slide 3
	Slide 4
	Gramática Livre de Contexto
	Exemplo
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Definição: Gramática Livre de Contexto
	Slide 16
	Ordem de Derivação
	Slide 18
	Árvores de Derivação
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Árvore de Derivação Parcial
	Slide 27
	Slide 28
	Slide 29
	Ambiguidade
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Ambiguidade Inerente
	Slide 48