Computabilidade e Linguagens Formais

Gramáticas e linguagens sem contexto
Gabriel David / Cristina Ribeiro
1
Gramáticas sem contexto

Notação que define linguagens mais gerais que linguagens
regulares
–
–

Compiladores (desde 1960’s)
DTDs em XML
Exemplo: palindroma
–
–
–
w=wR adamada (“capicua”)
0110, 11011, 
Não é regular




CFL
(CFG, PDA)
LR
(ER, DFA,
NFA, NFA)
Lema da bombagem
Para ser regular existe autómato com n estados
Escolhido n, seja w=0n10n=xyz
Fazendo y igual a um ou mais zeros da 1ª parte de w, xz também é
reconhecida pelo autómato mas, como x tem menos 0’s que z, não é um
palindroma e contradiz a hipótese de ser o autómato da linguagem
Gramáticas-2
Exemplo do palindroma

Definição recursiva
–
–

Notação alternativa: produções
–
–
–
–
–
–

Base: 0, 1 e  são palindromas
Indução: se w é um palindroma, 0w0 e 1w1 também o são; nada mais é um
palindroma
(para P, variável que representa a linguagem dos palindromas)
1. P  
2. P  0
3. P  1
4. P  0P0
5. P  1P1
1,2,3 constituem a base; 4,5 são recursivas
–
Interpretação da regra 4: Se w está em P então 0w0 também está
Gramáticas-3
Definição de CFG

CFG G=(V, T, P, S)
–
–
–
–
T são os terminais, símbolos usados nas cadeias da linguagem
V são as variáveis (de linguagem), os não terminais ou categorias
sintáticas
S é o símbolo de arranque, a variável da linguagem definida (as
outras são linguagens auxiliares)
P é um conjunto finito de produções ou regras da forma



–
H  B1B2…Bn
definição parcial de H, a cabeça, sendo B1B2…Bn, o corpo, uma sequência
de terminais e não terminais
As cadeias da linguagem são as que se obtém substituindo os não
terminais Bi por cadeias que se saiba pertencerem à linguagem Bi
Exemplo: G = ({P}, {0,1}, A, P)
Gramáticas-4
Exemplo das expressões

Representar as expressões aritméticas com +, ×, parênteses e
identificadores
–
–
–

Alfabeto identificadores: ‘a’, ‘b’, ‘0’, ‘1’ Outros terminais: ‘(‘, ‘)’, ‘+’, ‘×’
Identificadores: começa com letra seguida por um número qualquer de
letras e dígitos
ER: (a+b)(a+b+0+1)*
Usa-se uma variável E para as expressões e outra I para os
identificadores
–
–
–
–
–
–
1.
2.
3.
4.
EI
E  E+E
E  E×E
E  (E)
5. I  a
6. I  b
7. I  Ia
8. I  Ib
9. I  I0
10. I  I1
Produções mais compactas
E  I | E+E | E×E | (E)
I  a | b | Ia | Ib | I0 | I1
Gramáticas-5
Inferência

Inferência recursiva
Da base para cima; dos corpos para as cabeças das regras
Começa-se com as conhecidas e aplicam-se as regras para descobrir
novas; acaba-se por chegar a todas, numa pesquisa em largura
–
–
Cadeia
Linguagem
Produção usada Cadeias usadas
i
a
I
5
ii
b
I
6
iii
b0
I
9
ii
iv
b00
I
9
iii
v
a
E
1
i
vi
b00
E
1
iv
vii
a+b00
E
2
v, vi
viii (a+b00)
E
4
vii
ix
E
3
v, viii
a×(a+b00)
Gramáticas-6
Derivação

Derivação
–
–

Passo de derivação: 
–
–
–



Do topo para baixo; das cabeças para os corpos das regras
Começa-se com o objectivo, a linguagem alvo e aplicam-se as
regras, substituindo variáveis pelos respectivos corpos, até só haver
uma cadeia de terminais; chega a todas, pesquisa em profundidade
CFG G=(V,T,P,S)
α, β  (V  T)* A  V Aγ  P
αAβ G αγβ
* significa derivação em 0 ou mais passos
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)
Gramáticas-7
Derivação

No exemplo anterior, escolheu-se em cada passo a variável
mais à esquerda
*

– Derivação mais à esquerda
lm
–

Derivação mais à direita
Exemplo:
*

rm
E  E  E  E  (E)  E  (E  E) 
rm
rm
rm
rm
 E  ( E  I )  E  ( E  I 0)  E  ( E  I 00)  E  ( E  b00) 
rm
rm
rm
rm
rm
E  ( I  b00)  E  (a  b00)  I  (a  b00)  a  (a  b00)
rm
rm
rm
*
E  a  (a  b00)
rm
Gramáticas-8
Linguagem de uma gramática

A linguagem da CFG G=(V,T,P,S) é o conjunto de cadeias
terminais que têm derivações a partir do símbolo inicial S
*
L(G)  {w  T * | S  w}
G

Teorema: L(Gpal) é o conjunto dos palindromas sobre {0,1}
–
–
Prova: w  {0,1}* está em L(Gpal) se e só se w é palindroma w=wR
[se] hipótese: w é palindroma; indução em |w|




Base: |w|=0 ou |w|=1, isto é, w=, w=0, w=1
*
como existem as produções P, P0, P1 então P  w
Indução: supondo |w|2, como w=wR, w tem que começar e acabar com* o
mesmo símbolo, w=0x0 ou w=1x1.Além disso, x=xR. Por hipótese, P  x
*
Então P  0P0  0 x0  w e para 1x1 é semelhante. w está em L(G pal).
Gramáticas-9
Continuação da prova
–
*
[só se] hipótese: w está em Gpal, P  w indução no número de
passos de uma derivação de w a partir de P






Base: derivação só com 1 passo: usar regras não recursivas. Obtém-se , 0,
1 que são todos palindromas
Indução: supõe-se que a derivação tem n+1 passos e que a afirmação é
*
verdadeira para todas as derivações com n passos, P  x em n passos
então x é um palindroma x=xR
Uma derivação com n+1 passos só pode ser
*
*
ou
P 1P1 1x1  w
P 0 P0 0 x 0  w




Como wR=(0x0)R=0xR0=0x0=w então w é um palindroma
Se as produções envolverem vários símbolos de linguagem,
temos indução mútua, com várias afirmações em simultâneo
Gramáticas-10
Formas frásicas

Formas frásicas são derivações a partir do símbolo inicial
–
–

*
S 
G
Forma frásica esquerda (direita)
–

CFG G=(V,T,P,S)
  (V  T)* é forma frásica se
Derivação mais à esquerda (direita)
L(G) é constituída pelas formas frásicas que pertencem a T*,
só têm terminais
Gramáticas-11
Árvores de análise

Estrutura de dados mais usada para representar um programa
fonte num compilador
–

Facilita a escrita de funções recursivas para a geração de código
Seja G=(V,T,P,S); uma árvore de análise para G é uma
árvore que
–
–
–
A etiqueta de cada nó interior é uma variável
A etiqueta de cada folha é uma variável, um terminal ou  (neste
caso, filho único)
Se um nó interior tiver etiqueta A e os seus filhos etiquetas X1… Xk
então A  X1…Xk é uma produção em P
Gramáticas-12
Exemplos de árvores de análise

Uma árvore de análise representa uma derivação
Derivação P  0110
 A derivação pode ser parcial
P
 Derivação E  I  E
*

*
0
P
E
0
E
1
P


+
E
1
I
Cada nó interior da árvore corresponde a uma produção
Gramáticas-13
Colheita de uma árvore de análise



Colheita de uma árvore de análise é a cadeia obtida pela
concatenação de todas as folhas, lidas da esquerda para a
direita
Todas as colheitas das árvores cuja raiz é o símbolo inicial
de G são formas frásicas de G
As colheitas destas árvores que são terminais (folhas só com
terminais e ) são cadeias da linguagem
Gramáticas-14
Uma árvore de análise de a×(a+b00)
E
E
×
E
I
(
E
)
a
E
+
E
I
I
a
I
0
I
0
b
Gramáticas-15
Equivalências

Dada uma gramática G=(V,T,P,S) são equivalentes:
–
O processo de inferência recursiva determina que a cadeia terminal
w está na linguagem da variável A
*
–
–
A w
*
A w
lm
–
*
A w
rm
–

Existe uma árvore de análise com raiz A e colheita w
As equivalências são verdadeiras mesmo que w contenha
variáveis (não está definido para a inferência recursiva)
Gramáticas-16
Analisadores (parsers)

Gramáticas formais propostas por Noam Chomsky
–
–

Linguagem de programação
–
–

Descrever linguagens naturais – resultados limitados
Muito úteis para descrever linguagens “artificiais”
Alguns aspectos podem ser definidos por expressões regulares
Mas o emparelhamento de parêntesis e de estruturas if-else não são
regulares – exigem CFG
Existem programas (YACC, Bison, …) que, a partir de uma CFG de
uma dada linguagem L, geram automaticamente um programa capaz de
construir uma árvore de análise para programas escritos em L
–
Dispensa o programador de fazer esse programa, habitualmente incluído
nos tradutores (compiladores, interpretadores)
Gramáticas-17
Uso das CFG
programa
em L
CFG
de
L
parse
r
YAC
C
E
E
+
E
I
Gramáticas-18
As RE não chegam

Exemplo dos parênteses:
–
–
–

Se, dado um programa, se abstrair de tudo o que não são parênteses,
fica-se com cadeias do tipo (()())(). Nunca se obtém, por exemplo,
(() ou ())(, porque os parênteses devem estar emparelhados.
a) Mostrar que a linguagem destas cadeias não é regular
b) Definir uma CFG para a linguagem
Resposta:
–
–
a) a linguagem implícita na cadeia w= (((…()…))) de comprimento
2n é homomórfica da definida por 0n1n que já vimos ser não regular
b) B  BB | (B) | 



BB: a concatenação de duas cadeias emparelhadas é emparelhada
(B): parênteses em volta de uma cadeia emparelhada mantém o carácter
 é o caso base
Gramáticas-19
Escolha

Exemplo do if-else:
–
–
–

Numa linguagem de programação, a construção if pode aparecer
isolada ou então emparelhada com else, à semelhança dos parênteses;
é recursiva. Exemplos: i, ie, ieie, iiee. Não: ei, iee
a) defina uma CFG para essa linguagem
b) apresente todas as árvores de análise de iie; qual a correcta, em C?
Resposta:
–
–
else liga-se ao if mais próximo
a) S   | SS | iS | iSeS
b) (i)(ie)
(i(ie))
S
S
S
i
S

S
i S e S


i
(i(i)e) S
i S e S
S
i S e S


i
S


Gramáticas-20
Linguagens de anotação: HTML

As cadeias nestas linguagens são documentos com marcas
para estruturar o texto e controlar a sua apresentação
<P>A avaliação de <B>CLF</B> inclui:
<OL><LI>Miniteste
<LI>Exame
<LI>Exercícios
</OL>
Char  a | A | …
Elemento  Texto |
Texto   | Char Texto
<P> Doc |
Doc   | Elemento Doc
<B> Doc </B> |
<OL> Lista </OL>
Lista   | ItemLista Lista
ItemLista  <LI> Doc
Gramáticas-21
XML

Alguns aspectos do HTML não exigem o poder das CFG
–
–

Em HTML, a gramática está predefinida
–

A 1ª e 2ª linhas dizem que Texto se exprime pela RL (a+A+…)*
Os elementos <B> e <OL>, são como parênteses, exigem CFG
Os navegadores incluem um parser de HTML para analisar os
documentos de entrada, produzir uma árvore e mostrar o resultado
Em XML, dá-se aos utilizadores a capacidade de definirem a
própria gramática, num DTD (Document Type Definition)
–
–
Os documentos explicitam o DTD que especifica a sua estrutura
Os navegadores têm que incluir a capacidade de processar a
gramática para poderem validar os respectivos documentos
Gramáticas-22
Navegador HTML
documento
HTML
navegador
Parser
HTML
Doc
P
OL
Texto
B
Gramáticas-23
Navegador XML
documento
tipo Curso
navegador
DTD
Curso
Gera
parse
r
Parse
r
Curs
o
Curso
Cadeira Cadeira
Cnome
…
Gramáticas-24
Sintaxe dos DTDs
<!DOCTYPE nome-do-DTD [
lista de definições de elementos
]>
<!ELEMENT nome-do-elemento (descrição)>

Descrição é uma expressão regular
–
–
Base: outros elementos ou #PCDATA (texto sem marcas)
Operadores:





–
“|” reunião
“,” concatenação
“*” fecho, zero ou mais
“+” fecho, um ou mais
“?” fecho, zero ou um
Podem usar-se parênteses
Gramáticas-25
DTD Curso
<!DOCTYPE CURSO [
<!ELEMENT CURSO (GRAU, CADEIRA+)>
<!ELEMENT CADEIRA (CNOME, PROF, ALUNO*,
ASSISTENTE?)>
<!ELEMENT GRAU (L | M | D)>
<!ELEMENT CNOME (#PCDATA)>
<!ELEMENT PROF (#PCDATA)>
<!ELEMENT ALUNO (#PCDATA)>
<!ELEMENT ASSISTENTE (#PCDATA)>
]>
Gramáticas-26
Documentos XML
<CURSO>
<GRAU>L</GRAU>
<CADEIRA>
<CNOME>Lógica</CNOME>
<PROF>Francisco</PROF>
</CADEIRA>
</CURSO>
<CURSO>
<GRAU>M</GRAU>
<CADEIRA>
<CNOME>Matemática</CNOME>
<PROF>Francisco</PROF>
<ALUNO>Zé</ALUNO>
<ALUNO>Rui</ALUNO>
<ASSISTENTE>Luis
</ASSISTENTE>
</CADEIRA>
<CADEIRA>
<CNOME>Redes</CNOME>
<PROF>Antonio</PROF>
</CADEIRA>
</CURSO>
Gramáticas-27
XML e CFG

Reescrever DTD na notação das CFG
–


Converter CFG com expressões regulares no corpo das regras para
CFG normais
Base: se o corpo for uma concatenação, já está na forma
CFG normal
Indução: cinco casos
–
A  E1, E2
(concatenação, E1 e E2 permitidas nos DTD)
A  BC
B  E1
C  E2
(inventar variáveis B e C novas, permitida em CFG)
(E1 pode ainda não estar na CFG, mas é menor)



–
A  E1 | E 2


A  E1
A  E2
Gramáticas-28
XML e CFG
–
A  (E1)*



–
(B é nova)
A  (E1)+



–
A  BA
A 
B  E1
A  BA
A B
B  E1
A  (E1)?


A 
A  E1
Gramáticas-29
Converter o DTD Curso
CURSO  GRAU, CAD
CAD  CADEIRA
CAD  CADEIRA CAD
CADEIRA  CNOME PROF AL ASS
AL  B AL | 
B  ALUNO
ASS  ASSISTENTE | 
GRAU  L | M | D
CNOME  #PCDATA
PROF  #PCDATA
ALUNO  #PCDATA
ASSISTENTE  #PCDATA
ou AL  ALUNO AL | 
X
Gramáticas-30
Ambiguidade de uma CFG

Exemplo da instrução de selecção: análise da cadeia iie
–

Exemplo das expressões aritméticas: análise de a+b
–
–
–
–

Derivação 1: E  E+E  I+E  a+E  a+I  a+b
Derivação 2: E  E+E  E+I  I+I  I+b  a+b
As derivações são diferentes
Mas árvore de análise é a mesma, mesmo significado
Uma CFG G=(V,T,P,S) é ambígua se
–

3 árvores de análise, com significados diferentes
E
+
E
E
I
I
a
b
Existir uma cadeia w em T* para a qual existam duas árvores de
análise diferentes com raiz S e colheita w
Se não existir nenhuma dessas cadeias é não ambígua
Gramáticas-31
Precedência dos operadores
E
a + (a × a)

E
E
+
E
I
E
×
a
E ×
E
+
I
E
E
I
I
I
I
a
a
a
a
E
a
(a + a) × a
Cadeia a + a × a tem 2 árvores de análise – gramática ambígua
–
Para desambiguar pode-se usar regras de precedência


× tem precedência relativamente a +, tem prioridade superior, aplica-se antes
do + tanto à esquerda como à direita (1ª árvore respeita esta regra, a 2ª não)
a + a × a = a + (a × a)  (a + a) × a
Gramáticas-32
Associatividade
E
a + (a + a)

E
E
+
E
I
E
+
a
E +
E
+
I
E
E
I
I
I
I
a
a
a
a
E
a
(a + a) + a
Cadeia a + a + a tem 2 árvores de análise – gramática ambígua
–
Para desambiguar usa-se regra de associatividade



Sequências de operadores com a mesma precedência são associativos à
esquerda (2ª árvore respeita esta regra, a 1ª não)
a + a + a = (a + a) × a
Como a adição é associativa, o resultado é o mesmo nas duas análises
Gramáticas-33
Remoção da ambiguidade de CFG


Na gramática, a ambiguidade remove-se introduzindo mais
variáveis, para distinguir níveis de precedência e regras de
associatividade
Conceitos
–
–
–
Factor: expressão que não pode ser fraccionada por operadores (+
ou ×) adjacentes – identificadores e expressões entre parênteses
Termo: expressão que não pode ser fraccionada por +
Expressão: outras expressões – uma expressão é assim uma soma de
um ou mais termos
Gramáticas-34
Gramática não ambígua

I  a | b | Ia | Ib | I0 | I1
F  I | (E)
TF|T×F
ET|E+T

Construir árvore de a+a×a



Gramáticas-35
Ambiguidade e derivações


Teorema: para cada gramática e cada cadeia w de terminais,
w tem duas árvores de análise diferentes se e só se w tem
duas derivações mais à esquerda de S diferentes
Exemplo: derivações mais à esquerda das árvores de a+a×a
Gramáticas-36
Ambiguidade na linguagem




Uma linguagem sem contexto L é ambígua se todas as suas
gramáticas forem ambíguas
Exemplo: L= {anbncmdm | n1, m1}  {anbmcmdn | n1,
m1}
Definir CFG
Construir 2 árvores de análise para w=aabbccdd
Gramáticas-37