Linguagens Livres de Contexto
1
n n
{a b }
R
{ww }
Linguagens Regulares
2
Linguagens Livres de Contexto
n n
{a b }
R
{ww }
Linguagens Regulares
3
Linguagens Livres de Contexto
Gramáticas
Livres de
Contexto
Autômatos
de Pilha
pilha
autômato
4
Gramáticas Livres de Contexto
5
Exemplo
Uma gramática livre de contexto
G:
S  aSb
S 
Uma derivação:
S  aSb  aaSbb  aabb
6
Uma gramática livre de contexto
G:
S  aSb
S 
Outra derivação:
S  aSb  aaSbb  aaaSbbb  aaabbb
7
S  aSb
S 
L(G)  {a b : n  0}
n n
(((( ))))
8
Exemplo
Uma gramática livre de contexto G :
S  aSa
S  bSb
S 
Uma derivação:
S  aSa  abSba  abba
9
Uma gramática livre de contexto G :
S  aSa
S  bSb
S 
Outra derivação:
S  aSa  abSba  abaSaba  abaaba
10
S  aSa
S  bSb
S 
L(G)  {ww : w {a, b}*}
R
11
Exemplo
Uma gramática livre de contexto G :
S  aSb
S  SS
S 
Uma derivação:
S  SS  aSbS  abS  ab
12
Uma gramática livre de contexto G :
S  aSb
S  SS
S 
Uma derivação:
S  SS  aSbS  abS  abaSb  abab
13
S  aSb
S  SS
S 
L(G)  {w : na (w) = nb (w),
e na (v) ³ nb (v)
em qualquer prefixo v}
() ((( ))) (( ))
14
Definição: Gramática Livre de Contexto
Gramática
Variáveis
G = (V, S, S, P)
Símbolos Variável
terminais inicial
Produções da forma:
A x
x é um string de variáveis e terminais
15
Definição: Linguagem Livre de Contexto
Uma linguagem
L é livre de contexto
se existe uma gramática livre de contexto
tal que
G
L  L(G )
16
Ordem de Derivação
1. S  AB
2. A  aaA
4. B  Bb
3. A  
5. B  
derivação mais à esquerda :
1
2
3
4
5
S  AB  aaAB  aaB  aaBb  aab
derivação mais à direita:
1
4
5
2
3
S  AB  ABb  Ab  aaAb  aab
17
S  aAB
A  bBb
B  A| 
derivação mais à esquerda:
S  aAB  abBbB  abAbB  abbBbbB
 abbbbB  abbbb
derivação mais à direita:
S  aAB  aA  abBb  abAb
 abbBbb  abbbb
18
Árvores de Derivação
19
B  Bb | 
A  aaA | 
S  AB
S  AB
S
A
B
20
B  Bb | 
A  aaA | 
S  AB
S  AB  aaAB
S
A
a
a
B
A
21
B  Bb | 
A  aaA | 
S  AB
S  AB  aaAB  aaABb
S
A
a
a
B
A
B
b
22
B  Bb | 
A  aaA | 
S  AB
S  AB  aaAB  aaABb  aaBb
S
A
a
a
B
A

B
b
23
B  Bb | 
A  aaA | 
S  AB
S  AB  aaAB  aaABb  aaBb  aab
Árvore de
derivação
a
S
A
a
B
A
B


b
24
B  Bb | 
A  aaA | 
S  AB
S  AB  aaAB  aaABb  aaBb  aab
Árvore de
derivação
a
S
A
a
B
A
B


resultado
b
aab
 aab
25
Árvore de derivação parcial
S  AB
B  Bb | 
A  aaA | 
Árvore de
derivação parcial
S
A
B
26
S  AB  aaAB
Árvore de
derivação parcial
S
A
a
a
B
A
27
S  AB  aaAB
Árvore de
derivação parcial
S
A
a
forma
sentencial
a
B
A
resulta
aaAB
28
À vezes, a ordem de derivação não importa
Mais à esquerda:
S  AB  aaAB  aaB  aaBb  aab
Mais à direita:
S  AB  ABb  Ab  aaAb  aab
S
Mesma árvore
de derivação
A
a
a
B
A
B


b
29
Ambiguidade
30
E  E  E | E  E | (E) | a
a  aa
E
E  E  E  a E  a EE
 a  a E  a  a*a
E

E
a
E

a
derivação
mais à esquerda
E
a
31
E  E  E | E  E | (E) | a
a  aa
E  EE  E  EE  a EE E
 a  aE  a  aa
derivação
mais à esquerda
E
a
E

E

E
a
a
32
E  E  E | E  E | (E) | a
a  aa
E
Duas árvores de derivação
E

E
a
E

a
E
E
a
a
E
E

E

E
a
a
33
E  E  E | E  E | (E) | a
A gramática
é ambígua:
string
a + a*a tem duas árvores de derivação
E
E
E

E
a
E

a
E
E
a
a
E

E

E
a
a
34
Definição:
Uma gramática livre de contexto
G
é ambígua
se algum string
w L(G )
tem duas ou mais árvores de derivação
35
Em outras palavras:
Uma gramática livre de contexto
G
é ambígua
se algum string
w L(G )
tem duas ou mais derivações mais à
esquerda (ou mais à direita)
36
Porque ambiguidade importa?
a  aa
tome
E
E

E
a
E

a
a2
E
E
a
a
E
E

E

E
a
a
37
2  22
E
E
E

E
2
E

2
E
E
2
2
E

E

E
2
2
38
2  22  6
2  22  8
8
E
6
E
2
E

2
2
E
2
4
E

2
E
2
E
2
2
4
E

2
E

2
E
2
2
39
Resultado correto:
2  22  6
6
E
2
E

2
2
E
2
4
E

2
E
2
40
• Ambiguidade é ruim
para linguagens de programação
• Gostaríamos de remover ambiguidade
41
Corrigindo a gramática ambígua:
E  E  E | E  E | (E) | a
Nova gramática não ambígua:
E  E T
E T
T T F
T F
F  (E)
F a
42
E  E T T T  F T  a T  a T F
 a  F F  a  aF  a  aa
a  aa
E
E  E T
E T
T T F
T F
F  (E)
F a
E

T
T
T
F
F
a
a

F
a
43
Única árvore de derivação
a  aa
E
E

T
T
T
F
F
a
a

F
a
44
A gramática G :
E  E T
E T
T T F
T F
F  (E)
F a
não é ambígua:
Todo string w L(G ) tem
uma única árvore de derivação
45
Ambiguidade Inerente
Algumas linguagens livres de contexto
possuem apenas gramáticas ambíguas
Exemplo:
S  S1 | S2
L  {a b c }  {a b c }
n n m
n m m
S1  S1c | A
S2  aS2 | B
A  aAb | 
B  bBc | 
46
n n n
O string
a b c
possui duas árvores de derivação
S1
S
S
S1
S2
c
a
S2
47
Download

ftc08