Aula 10 - GLC

Prévia do material em texto

Linguagens livres de contexto 
(Gramáticas Livres de Contexto) 
Profa. Janne Oeiras Lachi 
UFGD 
Linguagens Formais 
Gramáticas livres de contexto (GLC) 
 É um método mais poderoso de descrever 
linguagens que os autômatos finitos e 
expressões regulares; 
 Tais gramáticas podem descrever certas 
características que têm uma estrutura 
recursiva; 
 As GLCs foram primeiramente utilizadas 
para o estudo da linguagem humana 
(formação de frases); 
Aplicações de GLCs 
 Em Ciência da Computação, uma aplicação 
importante das GLCs ocorre na especificação e 
compilação de linguagens de programação; 
 Uma gramática para uma linguagem de 
programação serve como referência para uma 
pessoa tentando aprender a sintaxe de tal 
linguagem; 
 Os designers de compiladores e interpretadores 
freqüentemente iniciam seu trabalho definindo 
uma gramática para a linguagem. 
Aplicações de GLCs 
Hopcroft et al. (pág. 205 a 219): 
 Analisadores sintáticos (componentes de 
tradutores de linguagens de programação); 
 O gerador de analisadores sintáticos YACC; 
 Linguagens de marcação (HTML); 
 XML e definições de tipos de documentos. 
Gramáticas livres de contexto 
 A coleção de linguagens associadas com GLC 
são chamadas de linguagens livres de contexto; 
 Essa coleção inclui todas as linguagens regulares 
e muitas outras linguagens (ver Hierarquia de 
Chomsky); 
 Estudo: 
 Gramáticas Livres de Contexto (gerador); 
 Autômatos com pilha (reconhecedor). 
Gramáticas livres de contexto 
 Suas produções são do tipo: 
A  
sendo que A  N e  (NT)* 
 
Exemplo: 
G1 = ({A,B}, {0,1,#}, P, A) 
 
 P: {A 
A 
 } 
 
Qual a linguagem gerada por G1? 
Derivação 
 Efetuando sucessivos passos de 
derivação poderemos verificar que a 
linguagem de G1 é: 
 L(G1)= {0n#1n | n>=0} 
 
 Exemplo: 000#111 
 A  0A1  00A11  
 000A111  000B111 
  000#111 
 
P: {A 
A 
 } 
 
Derivação mais à esquerda 
 Para restringir o número de escolhas que 
temos na derivação de uma palavra, 
muitas vezes é útil exigir que em cada 
etapa da derivação seja substituído o não-
terminal mais à esquerda (leftmost); 
 Este tipo de derivação é chamado de 
derivação mais à esquerda; 
 Utiliza-se o símbolo  ou 

lm lm 
* 
Exemplo: derivação mais à esquerda 
 Dada a gramática abaixo, derivar a 
palavra 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 
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) 
 
lm 
lm 
lm 
lm 
lm lm 
lm 
lm 
lm lm lm 
Podemos resumir a derivação mais à esquerda 
dizendo que E  a * (a + b00) ou 
representar várias etapas por meio de expressões como 
E * E  a * (E) 
lm 
* 
lm 
* 
Derivação mais à direita 
 Em cada etapa da derivação é substituído 
o não-terminal mais à direita (rightmost); 
 Utiliza-se o símbolo  ou 

rm rm 
* 
Derivação mais à direita 
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 
E  E*E  E * (E)  E * (E+E)  E *(E+I)  
 
E *(E+I0)  E *(E+I00)  E *(E+b00) 
 
E *(I+b00)  E *(a+b00)  I *(a+I00)  a *(a+b00) 
 
rm 
rm 
rm 
rm 
rm rm 
rm 
rm 
rm rm rm 
 Dada a gramática abaixo, derivar a 
palavra a * (a + b00) 
Árvore de análise sintática 
 Também serve para representar a 
derivação de uma palavra de forma 
gráfica; 
 Na literatura, também são chamadas de 
árvores de derivação (Menezes, 2005); 
parser tree (Sipser, 2006). 
Revisão da terminologia de árvores 
Hopcroft et al. (p. 194) 
 Árvores são coleções de nós, com um 
relacionamento pai-filho. Um nó tem no máximo 
um pai, colocado acima do nó, e zero ou mais 
filhos, colocados abaixo dele. Linhas (arestas) 
conectam os pais a seus filhos, colocados abaixo 
deles. 
E E 
E 
E × E 
a 
a 
+ 
a 
Hopcroft et al. (p. 194) 
 Existe um nó, a raiz, que não tem pai e esse nó 
aparece no alto da árvore. Nós sem filhos são 
chamados folhas. Nós que não são folhas são 
nós internos. 
E E 
E 
E E 
a 
a 
+ 
a 
× 
Revisão da terminologia de árvores 
Hopcroft et al. (p. 194) 
 Um filho de um filho de um... nó é um 
descendente desse nó. Um pai de pai de um... é 
um ancestral. De modo trivial, os nós são 
ancestrais e descendentes deles próprios. 
E E 
E 
E E 
a 
a 
+ 
a 
× 
Revisão da terminologia de árvores 
Hopcroft et al. (p. 194) 
 Os filhos de um nó são ordenados “a partir da 
esquerda” e traçados dessa forma. Se o nó N 
está a esquerda do nó M, então todos os 
descendentes de N são considerados à 
esquerda de todos os descendentes de M. 
E E 
E 
E E 
a 
a 
+ 
a 
× 
Revisão da terminologia de árvores 
Árvore de análise sintática 
 Dada uma gramática G=(N, T, P, S), árvores de 
análise sintática para G são árvores com as 
seguintes condições: 
 O nó mais alto é a raiz da árvore (símbolo inicial); 
 Cada nó interior é rotulado por um símbolo não-
terminal; 
 Cada folha é rotulada por um símbolo terminal ou 
pela palavra vazia (neste caso, esta folha é o único 
filho de seu pai); 
 Se um nó interno é rotulado por A e seus filhos são 
rotulados por X1, X2, ..., Xn respectivamente, a partir 
da esquerda, então A  X1X2 ... Xn é uma produção 
em P. 
Árvore de análise sintática 
 Exemplo: 000#111 
 
 
A 
A 
A 
A 
B 
# 1 1 1 0 0 0 
A  0A1  00A11  000A111  
000B111  000#111 
 
Concatenando-se os nós folhas da 
esquerda para direita, obtemos o 
resultado da árvore sintática. 
 
A 
A 
 
 
EXEMPLO 2 
 G2, descreve um fragmento da língua Inglesa: 
SENTENCE NOUN-PHRASE VERB-PHRASE
NOUN-PHRASE CMPLX-NOUN | CMPLX-NOUN PREP-PHRASE
VERB-PHRASE CMPLX-VERB | CMPLX-VERB PREP-PHRASE
PREP-PHRASE PREP CMPLX-NOUN
CMPLX-NOUN ARTICLE NOUN
CMPLX-VERB VERB | VERB NOUN-PHRASE
ARTICLE a | the 
NOUN boy | girl | flower 
VERB touches | likes | sees 
PREP with 
 
EXEMPLO 2 
 a boy sees 
SENTENCE  NOUN-PHRASE VERB-PHRASE
 CMPLX-NOUN VERB-PHRASE
 ARTICLE NOUN VERB-PHRASE
 a NOUN VERB-PHRASE
 a boy VERB-PHRASE
  a boy CMPLX-PHRASE
  a boy VERB
  a boy sees 
Gere a árvore de análise sintática para esta sentença 
EXEMPLO 3 
 G4 = (N, T, P, EXPR) 
 N = {EXPR, TERM, FACTOR} 
 T = {a, +, x, (, )} 
 P = { EXPR EXPR + TERMTERM
 TERM TERM x FACTORFACTOR
 FACTOR (EXPR ) | a 
 } 
Para as palavras abaixo: 
 1) mostre a derivação de cada uma delas e 
 2) gere árvores de análise sintática 
 a+axa 
 (a+a)xa 
EXEMPLO 3 (cont.) 
 A gramática G4 descreve um fragmento de uma 
linguagem de programação preocupada com 
expressões aritméticas; 
 Note que a precedência de operadores é considerada 
( x tem maior precedência que +) 
 Também é considerado o uso de parênteses para dar 
maior precedência a uma determinada operação 
como a adição em (a+a) x a 
Exercício 
 Obtenha a árvore de análise sintática de 
sentença “bbabaaabbaba” na gramática: 
 G = ({S, A}, {a, b}, P, S) 
 P: S  bAS | a 
 A  SaA | SS | ab 
Design de GLCs 
 Assim como o design de autômatos, o design 
de GLCs é um processo criativo; 
 Existem algumas técnicas que podem auxiliar 
nesse processo quando estivermos com 
dúvidas; 
 
Design de GLCs 
 1. Muitas Linguagens Livres de Contexto (LLC) são a 
união de LLCs mais simples. 
 Assim para construir uma GLCpara uma linguagem, você 
pode quebrá-la em “pedaços” menores e construir 
gramáticas individuais para cada “pedaço”; 
 Estas gramáticas individuais podem ser facilmente juntadas 
em uma gramática para a linguagem original por meio da 
combinação das suas regras e pela adição de uma nova 
regra S S1 | S2 | ... | SK 
Design de GLCs 
 1. Muitas Linguagens Livres de Contexto (LLC) são a 
união de LLCs mais simples. 
 Exemplo: {0n1n| n>=0}  {1n0n| n>=0} 
 Primeiro, construa a gramática para a linguagem {0n1n| 
n>=0}: S1  0S11|
 Segundo, construa a gramática para a linguagem {1n0n| 
n>=0}: S2  1S20|
 Adicione a regra S  S1|S2 para conseguir a gramática: 
S  S1|S2 
S1  0S11|
S2  1S20|
Design de GLCs 
 2. Construir uma GLC para uma linguagem regular é 
mais fácil se antes construirmos um AFD e depois o 
convertemos para uma GLC equivalente. 
 Crie um não-terminal Ri para cada estado qi do seu AFD; 
 Adicione a regra Ri aRj a GLC se (qi,a)= qj é uma 
trasição no AFD; 
 Adicione a regra Ri  se qi é um estado de aceitação no 
AFD; 
 Faça R0 o símbolo inicial da gramática, onde q0 é o estado 
inicial do AFD. 
Design de GLCs 
 3. Certas GLCs contem palavras com duas 
subpalavras que são “linkadas” no sentido que uma 
máquina para reconhecer tal linguagem deveria 
lembrar uma quantidade ilimitada de informação 
sobre uma das subpalavras para verificar que esta 
corresponde apropriadamente a outra subpalavra. 
 Exemplo: {0n1n| n>=0} 
 Usar regras da forma R uRv, que gera palavras com a 
parte contendo u’s corresponde à parte que contém v’s. 
Design de GLCs 
 4. Em linguagem mais complexas, as palavras podem 
conter certas estruturas que aparecem 
recursivamente como parte de outras (ou da mesma) 
estruturas. 
 Exemplo: 
EXPR EXPR + TERMTERM
 TERM TERM x FACTORFACTOR
 FACTOR (EXPR ) | a 
 Toda vez que o símbolo a aparece, pode aparecer também 
recursivamente uma expressão “parentizada”. Para isso, 
devemos colocar o símbolo não-terminal que gera aquela 
estrutura no devido lugar nas regras onde a estrutura deve 
recursivamente aparecer. 
Ambiguidade 
 Uma gramática pode gerar a mesma 
palavra de diferentes maneiras; 
 Tal palavra terá diferentes árvores de 
análise sintática e portanto vários e 
diferentes significados; 
 Este resultado pode ser indesejável para 
várias aplicações como o desenvolvimento 
de linguagens de programação, pois um 
programa deve ter uma interpretação 
única 
Ambiguidade 
 Se uma gramática gera a mesma palavra 
de diferentes maneiras, dizemos que a 
palavra é derivada ambiguamente; 
 Se uma gramática gera alguma palavra 
ambiguamente, então dizemos que essa 
gramática é ambígua. 
Ambiguidade: exemplo 
 Dada a gramática G5: 
 E E + EE x E | (E ) | a 
 A palavra a+axa é gerada ambiguamente; 
 
E E 
E 
E × E 
a 
a 
+ 
a 
E 
E 
E 
E 
× E 
a a 
+ a 
Ambiguidade: exemplo 
 Comparando G5 com G4, nota-se que G5 não 
captura relações de precedência usuais e 
podemos agrupar o + antes do x e vice-
versa; 
 
 
 
 G5 e G4 geram a mesma linguagem, mas G5 
é ambígua e G4 não é. 
G5 
E E + EE x E | (E ) | a 
G4 
EXPR EXPR + TERMTERM
TERM  TERM x FACTOR | FACTOR
 FACTOR  (EXPR ) | a 
Ambiguidade: definição 
 Dizemos que uma gramática gera uma palavra ambiguamente, 
quando a palavra possui duas árvores de análise sintática 
diferentes e não duas derivações diferentes; 
 exemplo: 
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 
Derivar a palavra a + b 
E  E+E  I + E  a + E  a + I  a + b 
 
E  E+E  E + I  I + I  I + b  a + b 
Duas derivações podem ser 
diferentes quanto à ordem pela 
qual são substituídos os não-
terminais; 
Ambiguidade: definição 
 Uma palavra w é derivada ambiguamente por 
uma GLC G se ela possui duas ou mais 
derivações à esquerda; 
 Uma gramática G é ambígua se ela gera 
alguma palavra ambiguamente. 
 Infelizmente não há um algoritmo para determinar 
(detectar) se uma gramática é ambígua. 
 Também não há algoritmo genérico para remover a 
ambiguidade de uma gramática. Existem técnicas. Ver 
Hopcroft et al. seção 5.4.2 
Ambiguidade: exemplo 
 Derivar a palavra a + a * a 
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 
Linguagens Inerentemente 
Ambíguas 
 É uma linguagem que só pode ser gerada por 
GLCs ambíguas. 
 Exemplo: 
L = { ai bj ck | i=j ou j=k} 
 
POSCOMP 2003