TEORIA DA
COMPUTAÇÃO
Prof. Yandre Maldonado - 1
Parte II
 Linguagens Livres de
Contexto
Prof. Yandre Maldonado e Gomes da Costa
TEORIA DA COMPUTAÇÃO

Linguagem Livre de Contexto - LLC

Compreende um universo mais amplo que
as LR, permitindo tratar questões como:
• Parênteses Balanceados;
• Construções Bloco-Estruturadas;
• Outras estruturas próprias de linguagens como C,
Pascal, etc.
Prof. Yandre Maldonado - 2


Os algoritmos que as implementam são
simples e possuem uma boa eficiência.
Aplicações: analisadores sintáticos,
tradutores de linguagens e processadores
de texto etc.
TEORIA DA COMPUTAÇÃO

As LLC´s podem ser especificadas
através de:

Gramática Livre de Contexto – GLC
Prof. Yandre Maldonado - 3
• Formalismo gerador de sentenças da
linguagem que define;

Autômato com Pilha – AP
• Formalismo reconhecedor de sentenças
da linguagem que define;
TEORIA DA COMPUTAÇÃO

Prof. Yandre Maldonado - 4
GLC é uma quádrupla (V, T, P, S), onde:
 V é um conjunto finito de símbolos não-terminais
(ou variáveis);
 T é um conjunto finito de símbolos terminais
disjunto de V;
 P é um conjunto finito de pares, denominados
regras de produção tal que a primeira
componente é um símbolo de V e a segunda
componente é palavra de (VT)*;
 S é um elemento de V, denominado símbolo
inicial (ou símbolo de partida).
TEORIA DA COMPUTAÇÃO


Prof. Yandre Maldonado - 5
Os símbolos de T são aqueles que
aparecem nos programas de uma
linguagem de programação. É o alfabeto
em cima do qual a linguagem é definida;
Os elementos de V são símbolos auxiliares
que são criados para permitir a definição
das regras da linguagem. Eles
correspondem à “categorias sintáticas” da
linguagem definida:


Português: sentença, predicado, verbo, ...;
Pascal: programa, bloco, procedure, ...;
TEORIA DA COMPUTAÇÃO



Prof. Yandre Maldonado - 6


Uma regra de produção (V, ) é
representada por V;
As regras de produção definem as
condições de geração das sentenças;
A aplicação de uma regra de produção é
denominada derivação;
Uma regra V indica que V pode ser
substituído por  sempre que V aparecer;
Enquanto houver símbolo não-terminal na
cadeia em derivação, esta derivação não
terá terminado;
TEORIA DA COMPUTAÇÃO


O símbolo inicial é o símbolo através do qual
deve iniciar o processo de derivação de uma
sentença;
Observações:


Prof. Yandre Maldonado - 7


VT = 
Os elementos de T são os terminais. Procuraremos
representá-los por letras minúsculas (a, b, c, d, ...)
Os elementos de V são os não-terminais.
Procuraremos representá-los por letras maiúsculas
(A, B, C, D, ...)
As cadeias mistas, isto é, aquelas que contém
símbolos de V e símbolos de T (cadeias pertencentes
à (VT)* ) serão representadas por letras gregas (,
, , , ...)
TEORIA DA COMPUTAÇÃO

Exemplo:

G1 = ({S, A, B}, {a, b}, P, S) onde:
Prof. Yandre Maldonado - 8
• P = { 1) S  AB
2) A  a
3) B  b }

Quais as cadeias terminais geradas
por esta gramática?
TEORIA DA COMPUTAÇÃO

Descrição de linguagens:
G1 = ({A, B}, {a, b, c}, P, A) onde:
P = { 1) A  aB
2)B  bB
3)B  c }
Prof. Yandre Maldonado - 9


G2 = ({S, A, B, C}, {a, b, c}, P, S) onde:
P = { 1) S  A
2) A  BaC
3) B  bB
4) B  b
5) C  cC
6) C  c }
A linguagem gerada pela gramática G1 descrita acima,
poderia ser expressa da seguinte forma: L(G1)={abnc,
n 0}
A linguagem gerada pela gramática G2 descrita acima,
poderia ser expressa da seguinte forma: L(G2)={biacj,
i1, j 1}
TEORIA DA COMPUTAÇÃO

G2 (subconjunto da língua portuguesa)
Prof. Yandre Maldonado - 10
• V = {Sentença, Sn, Sv, Artigo, Verbo, Substantivo,
Complemento}
• T = {peixe, isca, mordeu, o, a}
• P = { 1) Sentença  Sn Sv
2) Sn  Artigo Substantivo
3) Sv  Verbo Complemento
4) Complemento  Artigo Substantivo
5) Artigo  o
6) Artigo  a
7) Substantivo  peixe
8) Substantivo  isca
9) Verbo  mordeu
}
• S = Sentença
TEORIA DA COMPUTAÇÃO

G3 - Eliminando os problemas de
concordância de gênero
Prof. Yandre Maldonado - 11
• V = {Sentença, Sn, Sv, ArtigoF, ArtigoM, Verbo,
SubstantivoF, SubstantivoM, Complemento}
• T = {peixe, isca, mordeu, o, a}
• P = { 1) Sentença  Sn Sv
2) Sn  ArtigoF SubstantivoF
3) Sn  ArtigoM SubstantivoM
4) Sv  Verbo Complemento
5) Complemento  ArtigoF SubstantivoF
6) Complemento  ArtigoM SubstantivoM
7) ArtigoF  a
8) ArtigoM  o
9) SubstantivoF  isca
10) SubstantivoM  peixe
11) Verbo  mordeu
}
• S = Sentença
TEORIA DA COMPUTAÇÃO

Prof. Yandre Maldonado - 12
BNF - Forma Normal de Backus
 Substitui o símbolo “” por “::=”;
 Os não-terminais são ladeados por “<” e “>”;
 É usada para regras que apresentam um único
símbolo não-terminal do lado esquerdo;
 Quando houverem repetições do lado esquerdo, do
tipo:
• <A> ::= 1
* Os símbolos <, >, :, = e | não
• <A> ::= 2
fazem parte da linguagem,
apenas ajudam a descrevê-la.
...
• <A> ::= n
escreve-se: <A> ::= 1 | 2 | ... | n
TEORIA DA COMPUTAÇÃO

G3 - Descrição em BNF
Prof. Yandre Maldonado - 13
1) <Sentença> ::= <Sn> <Sv>
2) <Sn> ::= <ArtigoF> <SubstantivoF>
| <ArtigoM> <SubstantivoM>
4) <Sv> ::= <Verbo> <Complemento>
5) <Complemento> ::= <ArtigoF> <SubstantivoF>
|<ArtigoM> <SubstantivoM>
7) <ArtigoF> ::= o
8) <ArtigoM> ::= a
9) <SubstantivoF> ::= peixe
10) <SubstantivoM> ::= isca
11) <Verbo> ::= mordeu
TEORIA DA COMPUTAÇÃO
BNF é um padrão muito utilizado para
a descrição sintática de linguagens;
 Principais aplicações de descrição
sintática de linguagens (BNF):

Prof. Yandre Maldonado - 14
Ajuda a entender como se escreve
programas sintaticamente corretos;
 Pode ser usada para determinar se
um programa está sintaticamente
correto (papel do compilador).

TEORIA DA COMPUTAÇÃO

BNF para expressões aritméticas:
Prof. Yandre Maldonado - 15
<expressão> ::= <valor> |
<valor><operador><expressão>
<valor> ::= <número> | <sinal><número>
<número> ::= <semsinal> |
<semsinal>.<semsinal>
<semsinal> ::= <dígito> | <dígito><semsinal>
<dígito>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<sinal> ::= + | <operador> ::= + | - | / | *
TEORIA DA COMPUTAÇÃO

Adaptação para o software PROSINTATIC:
Prof. Yandre Maldonado - 16
<expressão> ::= <valor> |
<valor><operador><expressão>
<valor> ::= <número> | <sinal><número>
<número> ::= cn | cn.cn
<sinal> ::= + | <operador> ::= + | - | / | *
TEORIA DA COMPUTAÇÃO

EBNF – Extended BNF

Notação que acrescenta metasímbolos adicionais à
notação BNF;
• [ ]  opcionalidade;
• {}  repetição;

Prof. Yandre Maldonado - 17
Seguindo esta notação, os Não-Terminais
<expressão>, <valor>, <semsinal> e <número> (do
slide 15) poderiam ter suas regras descritas da
seguinte forma:
• <expressão> ::= <valor> [<operador><expressão>]
• <valor> ::= [<sinal>] <semsinal> [.<semsinal>]
• <semsinal> ::= <dígito> {<dígito>}

Pascal simplificado em EBNF;
TEORIA DA COMPUTAÇÃO

PROSINTATIC
Ambiente computacional para auxílio
ao projeto sintático de linguagens
computacionais;
 Baseado no algoritmo de CockeYounger-Kasami;
 Introduz algumas facilidades para o
projeto de linguagens, tais como:

Prof. Yandre Maldonado - 18
• Analisador Léxico;
• Classificação de símbolos terminais
(símbolo/palavra reservada).
TEORIA DA COMPUTAÇÃO

Algoritmo de Cocke-Younger-Kasami
Reconhecedor de LLC´s;
 Só funciona para GLC´s que estejam
na Forma Normal de Chomsky (FNC);
 Uma GLC está na FNC quando todas
as suas regras são da forma:

Prof. Yandre Maldonado - 19
• ABC ou Aa, onde:
• A, B e C são Não-terminais e a é terminal.
TEORIA DA COMPUTAÇÃO

Exemplo de análise com o algoritmo
CYK:
Dada a Gramática:
Prof. Yandre Maldonado - 20
G({S,A,B},{a,b},P,S),
onde P:
S AA
S AS
S b
A SA
A AS
A a
S – Símbolo de partida no
topo: cadeia aceita
S, A
S, A
S, A
S, A
S
S, A
S, A
A
S
S, A
A
S
A
A
S
a
b
a
a
b
TEORIA DA COMPUTAÇÃO

Autômato com Pilha


Prof. Yandre Maldonado - 21


São formalismos (máquinas) capazes de
reconhecer as Linguagens Livres de
Contexto;
Maior poder que os Autômatos Finitos, pois
possuem um “espaço de armazenamento”
extra que é utilizado durante o
processamento de uma cadeia;
Possui uma pilha que caracteriza uma
memória auxiliar onde pode-se inserir e
remover informações;
Mesmo poder de reconhecimento das
GLC’s;
TEORIA DA COMPUTAÇÃO
Exemplo de LLC: {anbn | n0}
 Um AF não é capaz de reconhecer
este tipo de linguagem devido à sua
incapacidade de “recordar”
(memorizar) informação sobre a
cadeia analisada;
 Autômatos com Pilha (AP) possuem
uma pilha para armazenar
informação, adicionando poder aos
AF’s.

Prof. Yandre Maldonado - 22
TEORIA DA COMPUTAÇÃO

Definição:

AP é uma sextupla <,,S,S0,,B>, onde:
Prof. Yandre Maldonado - 23
•  é o alfabeto de entrada do AP;
•  é o alfabeto da pilha;
• S é o conjunto finito não vazio de estados do
AP;
• S0 é o estado inicial, S0  S;
•  é a função de transição de estados,
: S  ({})    conjunto de subconjuntos
finitos de S  *
• B é o símbolo da base da pilha, B  .
TEORIA DA COMPUTAÇÃO


Ao contrário da fita de entrada, a pilha pode ser lida e
alterada durante um processamento;
O autômato verifica o conteúdo do topo da pilha, retira-o e
substitui por uma cadeia   *.

Prof. Yandre Maldonado - 24


Se  = A, e A  , então o símbolo do topo é substituído por
A e a cabeça de leitura escrita continua posicionada no
mesmo lugar;
Se  = A1A2...An, n>1 então o símbolo do topo da pilha é
retirado, sendo An colocado em seu lugar, An-1 na posição
seguinte, e assim por diante. A cabeça é deslocada para a
posição ocupada por A1 que é então o novo topo da pilha;
Se  =  então o símbolo do topo da pilha é retirado,
fazendo a pilha decrescer.
TEORIA DA COMPUTAÇÃO


Prof. Yandre Maldonado - 25

A função de transição , é função do estado
corrente, da letra corrente na fita de entrada
e do símbolo no topo da pilha;
Além disso, esta função determina não só o
próximo estado que o AP assume, mas
também como o topo da pilha deve ser
substituído;
O AP inicia sua operação num estado inicial
especial denotado por S0 e com um único
símbolo na pilha, denotado por B.
TEORIA DA COMPUTAÇÃO
A configuração de um AP é dada por
uma tripla <s, x, > onde s é o estado
corrente, x é a cadeia da fita que falta
ser processada e  é o conteúdo da
pilha, com o topo no início de ;
 O AP anda ou move-se de uma
configuração para outra através da
aplicação de uma função de
transição.

Prof. Yandre Maldonado - 26
TEORIA DA COMPUTAÇÃO


Prof. Yandre Maldonado - 27

Se o AP está na configuração <s,ay,A> e
temos que (s,a,A)=<t,>, então o AP movese para a configuração <t,y, > e denotase <s,ay,A> |— <t,y, >.
Se o AP move-se de uma configuração
<s1,x1,1> para uma configuração
<s2,x2,2> por meio de um número finito de
movimentos, denotamos
<s1,x1,1>|—*<s2,x2,2>
Se o valor de  para uma determinada
configuração for  o AP pára.
TEORIA DA COMPUTAÇÃO
Note que AP’s não possuem estados
finais como os AF’s;
 Assim, um string x é aceito se, ao
chegar ao final da cadeia de entrada,
a pilha estiver vazia,
independentemente do estado em
que o AP se encontra;

Prof. Yandre Maldonado - 28
TEORIA DA COMPUTAÇÃO

Formalmente temos:
Dado o AP P = <,,S,S0,,B> e o
string x sobre , diz-se que x é aceito
por P sse existe s  S tal que
<S0,x,B>|—*<s,,  >. Caso contrário,
x é rejeitado.
 Dado o AP P = <,,S,S0,,B>, a
linguagem L(P) definida por P é
{x  *|  sS  <S0,x,B> |—*<s,,  >}

Prof. Yandre Maldonado - 29
TEORIA DA COMPUTAÇÃO

Exemplo de AP para a LLC {anbn |
n0}:
<b,A>/ 
Prof. Yandre Maldonado - 30
(S,a,B) = {<S,A>}
S
(S,a,A) = {<S,AA>}
(S,b,A) = {<R,>}
(R,b,A) = {<R, >}
<a,B>/A
(S,,B) = {<S, >} <a,A>/AA
<,B>/ 
R
<b,A>/ 
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 31
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
B
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 32
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
A
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 33
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
A
A
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 34
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
A
A
A
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 35
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
A
A
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 36
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
A
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaabbb
<b,A>/ 
S
Prof. Yandre Maldonado - 37
<a,B>/A
<a,A>/AA
<,B>/ 
R
<b,A>/ 
CADEIA
ACEITA
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo de AP para {x{a,b}*| |x|a=|x|b}:
Prof. Yandre Maldonado - 38
(S,a,C) = {<S,AC>}
(S,b,C) = {<S,BC>}
(S,,C) = {<S,>}
(S,a,A) = {<S,AA>}
(S,b,A) = {<S,>}
(S,a,B) = {<S,>}
(S,b,B) = {<S,BB>}
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 39
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
C
BASE DA PILHA: C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 40
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 41
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 42
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 43
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 44
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 45
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 46
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 47
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 48
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
A
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 49
S
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
C
PILHA
TEORIA DA COMPUTAÇÃO

Exemplo: processamento da cadeia aaaabbabbb
Prof. Yandre Maldonado - 50
S
CADEIA
ACEITA
<a,C>/AC
<b,C>/BC
<,C>/
<a,A>/AA
<b,A>/
<a,B>/
<b,B>/BB
PILHA
TEORIA DA COMPUTAÇÃO

Atividade Prática Nº 1

Prof. Yandre Maldonado - 51

Complemente a descrição em BNF da
linguagem LIAD, que será entregue
durante a aula.
Atividade Prática Nº 2

Resolva a lista de exercícios de
Autômato com Pilha.