Linguagens Livre de Contexto
<stmt>::=<if-stmt>|<while-stmt>|
<begin-stmt>|<assg-stmt>
<if-stmt>::=if <bool-expr> then <stmt>
else <stmt>
<while-stmt>::=while <bool-expr>
do <stmt>
<begin-stmt>::=begin <stmt-list> end
<stmt-list>::=<stmt>;<stmt-list>|<stmt>
<assg_stmt>::=<var>:=<arith-expr>
<bool-expr>::=
<arith-expr><comp-op><arith-expr>
<comp.-op>::=<|>|≤|≥|≠|=|
<arith-expr>::=<var>|<const>|
(<arith-expr><arith-op><arith-expr>)
<arith-op>::=+ | - | *| /
<const>::=0|1|2|3|4|5|6|7|8|9
<var>::=a|b|c|…|x|y|z
BNF (Backus-Naur form)dando a
definição formal de uma linguagem
de “programação”.
Mais Exemplos
• L = {anbn|n0} é livre de contexto.
• Se em L substituirmos ‘a’ por ‘(‘ e ‘b’
por ‘)’, cadeias de parênte-ses tais
como ( ( ) ) e ( ( ( ) ) ) estarão em L.
• L descreve uma estrutura aninhada
comum em linguagens de programação.
Gramáticas Livre De
Contexto
•As produções numa gramática regular são restritas de duas formas:
– o lado esquerdo deve conter uma
única variável,
– enquanto o lado direito tem uma
forma especial.
•Para criar uma gramática “mais
poderosa”, devemos relaxar algumas
dessas condições .
• Mantemos a restrição sobre o
lado esquerdo, mas permitimos
qualquer coisa no lado direito.
Definição: Uma gramática
G=<V,T,S,P> é livre de contexto
se todas as produções em P
tem a forma Ax, onde AV e
x(VT)*.
•A linguagem L é livre de contexto
sss existe uma gramática livre de
contexto G tal que L = L(G).
Obs: Toda linguagem regular é
livre de contexto.
Exemplos
• G=<{S},{a,b},S,P>, com produções SaSa; SbSb, S
• Uma derivação típica nessa
gramática é
SaSaaaSaaaabSbaaaaabbaa
• Isto torna claro que
L(G)={WWR|W{a, b}*}
Mais Exemplos
• A gramática
G=<{S, A, B}, {a, b}, S, P>,
onde P é
SabB; AaaBb; BbbAa; A
• L(G)={ab (bbaa)n bba (ba)n |n0}
Derivação Mais à Esquerda e
Mais à Direita
G=<{A,B,S},{a,b},S,P>
com produções:
1. SAB;
2. AaaA;
3. A;
4. BBb;
5. B.
L(G)={a2nbm|n0, m0}
S1AB2aaAB3aaB
4aaBb5aab
S1AB4ABb
2aaABb5aaAb
3aab
Definição:
• Uma derivação diz-se mais à
esquerda se em cada etapa a
variável mais a esquerda é
trocada na forma sentencial.
• Se em cada etapa a variável
mais a direita é trocada,
dizemos que a derivação é mais
à direita.
Exemplos
Considere a gramática com produções SaAB, AbBb, BA|
• uma derivação mais à esquerda da
cadeia abbbb:
SaABabBbBabAbBabbBbbB
abbbBabbbb
• uma derivação mais à direita:
SaABaAabBbabAbabbBbb
abbbb.
Árvores de Derivação
•Mostra derivações independente da
ordem em que as produções são
usadas.
•Uma árvore de derivação é uma árvore
ordenada onde:
– os nodos são rotulados com os lados
esquerdos das produções e
– o filho de cada nodo representa seus
correspondentes lados direitos.
Exemplo
Aa b A B c
A
a
b
A
B
c
Definição
Seja G=<V, T, S, P> uma gramática
livre de contexto. Uma árvore
ordenada é uma árvore de
derivação para G se e somente se
ela tem as seguintes propriedades:
1. A raiz tem rótulo S
2. Toda folha tem rótulo de T{}
3. Todo vértice interior tem um
rótulo de V.
4. Se um vértice tem rótulo A  V, e
seus filhos são rotulados(da esquerda para direita) a1, a2, …,an,
então P deve conter uma produção
da forma Aa1a2…an
5. Uma folha rotulada  o seu pai
não tem nenhum filho além dàquele
rótulado .
árvore de derivação parcial:
• Uma árvore que tem as propriedades 3, 4 e 5 mas não necessariamente 1 e
• a propriedade 2 é trocada por:
2a.Toda folha tem rótulo em VT{}
cadeia gerada
A cadeia de símbolos obtida
lendo-se, da esquerda para à
direita, omitindo qualquer 
encontrado, diz-se gerada pela
árvore.
Exemplo: Considere a gramática
G, com produções
SaAB
AbBb
BA |

Exemplo (a)
(a)
• A árvore (a) é uma árvore de derivação parcial para G.
• A cadeia abBbB, gerada pela árvore, é uma
forma sentencial de G.
S
a
b
A
B
B
b
Exemplo (b)
• a árvore (b) é uma árvore de derivação.
• A cadeia gerada, abbbb é uma
sentença de L(G).
(b)
S
a
B
A
b
B

A
b
b
B

b
Relação entre Formas
Sentenciais e Árvores de
Derivações
•Árvores de derivação dão uma descrição explícita e compreensível de
derivações.
•Assim como grafo de transições
para autômatos finitos, elas são
úteis nos argumentos.
Teorema
Seja G=<V, T,S, P> uma gramática livre de
contexto.
Então pra todo wL(G) existe uma árvore
de derivação G cuja cadeia gerada é w.
Inversamente a cadeia gerada por qualquer árvore de derivação está em G.
Além disso, se tG é qualquer árvore de
derivação parcial para G cuja raiz é
rotulada S, então tG gera uma forma
sentencial de G.
Prova
• Primeiramente, mostraremos
que para toda forma sentencial
de G existe uma árvore de
derivação parcial.
• Faremos isso por indução no
número de etapas da derivação.
Prova (cont.): base
Como base, observemos que a afirmação é verdadeira pra toda forma
sentencial derivada em uma etapa.
Como Su implica que existe uma
produção Su, isto segue imediatamente da definição da árvore de
derivação.
Prova(cont.): passo
Suponhamos que para toda forma
sentencial derivável em n etapas,
existem uma árvore de derivação
parcial correspondente.
Prova(cont.): passo
Agora qualquer w derivável em
n+1 etapas deve ser tal que
S*x A y, x, y  (V U T)*, A V
em n etapas, e
x A yx a1, a2…amy = w,
ai  VT.
• mas por hipótese de indução existe
uma árvore de derivação parcial que
gera x A y.
• como G deve ter produção
Aa1a2…am, expandindo as folhas
rotuladas A, obtemos uma árvore de
derivação parcial que gera w.
• Logo, por indução, o resultado é
verdadeiro para toda forma sentencial.
• Usando um argumento análogo,
podemos mostrar que toda árvore
de derivação parcial representa
alguma forma sentencial.
• Uma árvore de derivação é uma
árvore de derivação parcial cujas
folhas são terminais.
• Logo toda sentença em L(G) é
gerada por alguma árvore de derivação de G e toda árvore de
derivação gerada está em L(G).
q.e.d
•Árvores de derivação mostram quais
produções são usadas para se obter
uma sentença, mas não dá a ordem
de suas aplicações.
•Árvores de derivações são capazes
de representar qualquer derivação,
refletindo o fato de que esta ordem é
irrelevante, uma observação que nos
permite fechar o buraco na discussão
anterior.
• Por definição, qualquer wL(G) tem
uma derivação mais a esquerda e
uma mais a direita.
• dada uma árvore de derivação, podemos sempre obter uma derivação
mais a esquerda pensando na árvore
como tendo sido construída de tal
modo que a variável mais a esquerda
foi sempre expandida primeiro.
• Todo w  L(G) tem pelo menosuma
derivação mais a esquerda e uma
mais a direita.