View
108
Download
1
Category
Preview:
Citation preview
Expressões Regulares e Gramáticas
profa. Laís do Nascimento SalvadorE-mail: laisns@dcc.ufba.br
Grande parte dos slides foi gentilmente cedida pelo prof. Ivan Carlos Alcântara de Oliveira
Teoria dos AutômatosExpressões Regulares
• A expressão regular é a maneira mais compacta e mais simples de descrever conjuntos regulares, e é usada com essa finalidade em construção de compiladores, editores, sistemas operacionais, protocolos, etc.
• É um formalismo denotacional, também considerado gerador.
Teoria dos AutômatosExpressões Regulares
Definição: Uma Expressão Regular (ER) sobre um alfabeto é definida como segue:
é uma ER (linguagem vazia) é uma ER (linguagem contendo somente a
cadeia vazia )• para cada a , a é uma ER• se e são ER´s, então | é uma ER. ( OU –
alternância) • se e são ER´s, então é uma ER.
(concatenação)• se é uma ER, então ()* é uma ER
(exponenciação)
Teoria dos AutômatosExpressões Regulares
*: | | | |.....
+: | | |.....
+ = *
• ordem de precedência(decrescente): – exponenciação– concatenação – alternância
Teoria dos AutômatosExpressões Regulares
Expressão regular Linguagem representada
aa Somente a palavra aa
ba* Todas as palavras que começam com b, seguido por zero ou mais a´s
(a|b)* Todas as palavras sobre {a, b}
(a|b)* aa (a|b) * Todas as palavras que contém aa como subpalavra
a* ba* ba* Todas as palavras contendo exatamente 2 b´s
(a|b)* (aa| bb ) Todas as palavras que terminam com aa ou bb
(a| ) (b | ba)* Todas as palavras que não possuem 2 a´s consecutivos
Teoria dos AutômatosExpressões Regulares - ExercíciosExercícios:1. Indique se a cadeia 1011 pertence às linguagens
correspondentes a cada uma das expressões regularesa) __________ (10)*1011b) __________ 0*(10 | 11)*c) __________ 1(00)*(11)*d) __________ (1 |00)(01 |0)1*2) Escreva uma expressão regular para cada uma das
seguintes linguagens sobre o alfabeto {a,b}:a) O conjunto de todas as cadeias que começam e terminam
com a e contém no mínimo um bb) O conjunto de todas as cadeias que terminam em abc) O conjunto de todas as cadeias com comprimento maior
ou igual a 2
Teoria dos AutômatosExpressões Regulares - Exercícios
3) Especificar as linguagens representadas pelas seguintes e.r´s:
a) abb*cb) abb*aa*c) bb*(ab)*
4) Construa uma ER para cada uma das seguintes linguagens sobre o alfabeto {0, 1}
a) O conjunto de todas as cadeias terminando em 00.
b) O conjunto de todas as cadeias com 3 zeros consecutivos.
Gramáticas• Um exemplo inicial:<frase> <sujeito> <verbo> <predicado> <sujeito> O homem <sujeito> A mulher<verbo> leu <verbo> escreveu <predicado> um <adjetivo> livro <adjetivo> ótimo <adjetivo> péssimo <adjetivo>
Gramática - Definição Formal (1/6)
• Def. É um mecanismo gerador de cadeias de uma linguagem. Uma gramática formal é uma quádrupla:
G = ( N, T, P, S )onde:
N é um alfabeto finito, conhecido como vocabulário não terminal.
T é um alfabeto finito, conhecido como vocabulário terminal.
P é um conjunto finito de regras ou produções da forma w i com:
w (N U T )+ e i (N U T )*
S é o símbolo inicial ou axioma por onde as regras começam a ser aplicadas S N
• Observações Importantes: a) N T = b) N T = V (vocabulário de G) c) Notação que será utilizada:
T letras minúsculas N letras maiúsculas
d) Uma seqüência da forma: 1, 2, 3, ........, n,pode ser abreviada como uma única produção da forma: 1| 2 | 3| .... | n
e) Para descobrir se uma cadeia x T* é gerada pela gramática basta fazer um processo de derivação começando do símbolo inicial S até obter a cadeia desejada.
Gramática - Definição Formal (2/6)
• Exemplo 1: Gramática que gera números binários de qualquer tamanho.
G1 = (N, T, P, S), T = {0, 1}, N = {S}
P = {S 0 | 1 | 0S | 1S}
a) A cadeia x = 0 1 0 é gerada pela gramática G?
S 0S 01S 0 1 0 (É gerada!!!!)
b) A cadeia y = 0101000 é gerada pela gramática G?
S 0S 01S 010S 0101S 01010S 010100S 0101000 (É gerada!!!!)
c) A cadeia z = 0201000 é gerada pela gramática G? Não é gerada pois observa-se que o símbolo 2T.
Gramática - Definição Formal (3/6)
• Exemplo 2: Gramática que gera qualquer número inteiro positivo, incluindo o 0. Z+ = {0, 1, 2, ...}.
G2 = ( N, T, P, S ), T = {0, 1, 2, 3, ..., 9}, N = {NUMERO} S = NUMEROP = { NUMERO 0 | 1 | ... | 9 | 0 NUMERO | 1 NUMERO| ... | 9 NUMERO}
a) A cadeia x = 9 0 3 é gerada pela gramática G? NUMERO 9NUMERO 90NUMERO 9 0 3 (É gerada!!!!)
b) A cadeia y = 002551 é gerada pela gramática G? NUMERO 0NUMERO 00NUMERO 002NUMERO
0025NUMERO 00255NUMERO 002551 (É gerada!!!!)
Gramática - Definição Formal (4/6)
• Exemplo 3 - Solução 1: Desenvolver uma gramática que gera números inteiros, não permitindo números que começam com 0, exceção para o valor 0.
G3 = (N, T, P, S), T = {0, 1, 2, 3, ..., 9}, N = {Num ,D} S = NumP = { Num 0 | 1 | 2 | ... | 9 | 1D | 2D | ... | 9D D 0 | 1 | 2 | ... | 9 | 0D | 1D | ... | 9D}
a) A cadeia x = 9 0 3 é gerada pela gramática G?
Num 9D 90D 9 0 3 (É gerada!!!!)
b) A cadeia y = 0231 é gerada pela gramática G?
Num 0 ( Não é gerada ) OK!!! Pois não se aceita zeros a esquerda.
Gramática - Definição Formal (5/6)
• Exemplo 3- Solução 2: Desenvolver uma gramática que gera números inteiros, não permitindo números que começam com 0, exceção para o valor 0.
G4 = (N, T, P, S), T = {0, 1, 2, 3, ..., 9},N = { Num, D, DF}, S = NumP = { Num D| 1D | 2D| ... | 9D D 0 | 1 | 2 | ... | 9 | 1DF | ... | 9DF DF 0 | 1 | 2 | ... | 9 | 0DF | 1DF | ... | 9DF }
a) A cadeia x = 9 0 3 é gerada pela gramática G?
Num D 9DF 90DF 903 (É gerada!!!!)
b) A cadeia y = 0231 é gerada pela gramática G?
Num D 0 ( Não é gerada ) OK!!! Pois não se aceita zeros a esquerda.
Gramática - Definição Formal (6/6)
1) Seja a gramática abaixo
G = {N, T, P, S}, N = {S, A, B}, T = {a, c, d} P = {S AB, A AA, A B, A a, B Bcd,B a}
Pede-se: G gera x = a a a c d, y = aaaacdcdaacd, z = aaaaaaacdaaacdcdcd, k=aacdcdcdaacdaacdcd?
2) Seja G2 o conjunto das seguintes produções: P = { ID a | b | c ID a | ID 0 | ID 1 }
Escrever VN, VT. Mostrar as derivações possíveis para gerar as sentenças a, cba0, a0, a1, ccaaa.
3) Construir uma gramática que gera números inteiros divisíveis por 5 (negativos ou positivos). Exemplo: 0, 5, -10, 15, -225, ... )
Gramática - Exercícios (1/3)
4) Construir urna gramática cujas sentenças sejam cadeias com igual número de 0's e 1's.
5) Criar uma gramática que gera números binários palíndromos: Exemplo: 0, 1, 010, 00100, 111, 101, 01010.
6) Construir urna gramática que gera {a (bn) a | am0, n>=0, m >=2}
Gramática - Exercícios (2/3)
7) Desenvolver uma gramática que gere expressões aritméticas com parênteses balanceados, dois operadores (representado por * e +) e um operando representado por x.Exemplo: x, x* (x + x) e ((((x))))
8) Escrever uma gramática cuja linguagem seja o conjunto dos números inteiros pares positivos sem zeros à esquerda.
9) Escrever uma gramática que seja capaz de gerar qualquer identificador da linguagem JAVA.
Gramática - Exercícios (3/3)
• Exemplo:a) Qual a L(G)? L(G) = {a bn c, n>= 0}
b) Encontrar G' equivalente a G
Basta encontrar um conjunto de produções diferentes que satisfaz L(G') = L(G). G' = ( N, T, P, S )
T = { a, b, c }, P = { A aBc, B bB | }, N = { A, B}, S = A, L(G') = {a bn c, n>= 0}
Observa-se que L(G) = L(G’) G' G
Gramática - Outros Conceitos
• Def. Árvore de derivação sintática:É um tipo de árvore voltada a análise sintática de
sentenças que utilizaremos para montar as possíveis derivações de uma dada sentença e, com isto, verificar se ela pertence ou não a uma determinada gramática G. A montagem de uma árvore de derivação a partir de uma gramática G = (N, T, P, S) é realizada da seguinte maneira:
a) A raiz da árvore é o símbolo inicial.b) Os vértices interiores pertencem ao N.c) Os nós folhas pertencem ao T.
Gramática - Outros Conceitos
• Exemplo:Seja a gramática G = (N, T, P, S) como
definida abaixo:
T = { a, b, c }, N = { A, B }, S = AP = {A aB, B bB | c }
• Verificar se x = abbbc, y = ac, z = abbca, w = a são sentenças de L(G).
Gramática - Outros Conceitos
• Árvore de derivação sintática - Exemplos:c) Verificar se x = abbbc, y = ac, z = abbca, w = a são
sentenças de G. Para isto basta verificar se realizando algumas derivações é possível obter a sentença solicitada.
Logo, x e y são sentenças de G, z e w não são.
x yz w
|c
b
Gramática - Outros Conceitos
• Def. Gramáticas Ambíguas: Uma gramática é ambígua se gera uma sentença para a qual existem duas ou mais árvores de derivação sintática.
Exemplo: Seja G = (N, T, P, S) a gramática definida abaixo:T = { a, c, d }, N = { S, A, B },P = { S AB, A AA | B | a, B Bcd | a }
Pede-se:
a) Qual é a L(G) ? b) G é ambígua?c) Se G for ambígua, encontrar G' equivalente a G não ambígua.
Gramática - Outros Conceitos
a) Qual é a L(G) ? Como esta gramática é um pouco complexa,
vamos por partes:• As produções B Bcd | a geram sentenças no
formato: a(cd)*
• As produções A AA | B | a geram formas sentenciais no formato A+, onde cada A gera um B ou um a. Logo estas regras geram sentenças no formato: (a(cd)*|a)+
• A regra inicial, por sua vez, é SAB, então temos que L(G) = (a(cd)*|a)+a(cd)*
Gramática - Outros Conceitos
b)Para a sentença x = aaacd encontra-se duas árvores de derivação como ilustrado abaixo:
Logo G é ambígua.
Gramática - Outros Conceitos
c) Se G for ambígua encontrar G' equivalente a G não ambígua.
• Sabemos que L(G) = (a(cd)*|a)+a(cd)* . Observa-se que esta própria expressão é ambígua (por exemplo: há duas formas de se gerar a sentença aa).
• Ao simplificar a e.r. chegamos em: (a(cd)*)+a(cd)* . Com base nesta 2a. e.r. podemos retirar a produção Aa, observe que ela é uma fonte de ambigüidade, e a linguagem gerada continua a mesma. Logo temos a seguinte gramática modificada:
P = { S AB, A AA | B , B Bcd | a }
Porém esta gramática ainda é ambígua. Onde está o problema?
Gramática - Outros Conceitos
• Observe que a produção A AA também é uma fonte de ambigüidade, por quê?
• Logo devemos substituir a produção por outra, que não gere sentenças ambíguas, sem prejuízo da linguagem gerada. Assim, chegamos na seguinte gramática:
P = { S AB, A BA | B, B Bcd | a }
• Ainda podemos simplificar e chegar numa outra solução:
P = { S BS | BB, B Bcd | a }
• Observe que ambas gramáticas não são ambíguas.
Gramática - Outros Conceitos
1) Dada a linguagem:L(G) = {an bm ek, n >= 2, m>=0, k>=1}
Encontrar a gramática G
2) Dadas as produções de duas gramáticas G1 e G2 determinar a linguagem gerada:
a) G1 P = {S a S a S |}
b) G2 P = {S a S a | }
Pede-se: São ambíguas?Justifique a sua resposta.
Gramática - Exercícios (1/4)
3) Produzir uma gramática G tal que a) L(G) = {abn c com n >= 0}
b) L(G) = {an bm com n <= m; n, m>=1}
4) Encontre gramáticas não ambíguas que gerem os seguintes conjuntos:a) números binários múltiplos de 4, sem zeros não significativos.c) números inteiros pares, positivos ou negativos, com sinal (exceto o zero), sem zeros não significativos.
Gramática - Exercícios (2/4)
5) Dadas as produções de 3 gramáticas
a) Quais as linguagens geradas? Descrever informalmente se for impossível formalizar.
b) Quais gramáticas são ambíguas? Por quê?
(G2) S [S]S | | a | b S S[S]
(G1) S aBC | a BC bcS |
(G3) S 01ZY | ZY 0DC | S DC 1CC | CC 1DC |
Gramática - Exercícios (3/4)
6) Seja uma gramática G dada pelas produções abaixo:
P: {S AB | C, A aAb | ab, B cBd | cd, C aCd | aDb, D bDc | bc }
Pede-se:a) Qual a linguagem gerada pela gramática?b) Ela é ambígua? c) Encontrar uma G1 equivalente a G.
Gramática - Exercícios (4/4)
• Extremamente úteis;• Usadas na construção de compiladores;• Exemplos de Gramáticas Livres de Contexto:
G = (N,T,P,S)onde N = {S}T = {a,b}P = { S aSb
S } L(G) = ?
Gramática para expressão com parênteses balanceados:G’ : P = { S (S)
S }
Gramáticas Livres de Contexto
Exemplos de Gramáticas Livres de Contexto:
Vamos construir uma definição recursiva para expressões aritméticas:
. x é uma expressão aritmética• Assumindo que e seja uma expressão
aritmética então:• (e) é uma expressão aritmética;• e + e é uma expressão aritmética;• e * e é uma expressão aritmética;
Gramáticas Livres de Contexto
Exemplos de Gramáticas Livres de Contexto:
A partir desta definição é fácil construir a gramática para esta linguagem,
G1 = (N,T,P,S) onde N = {E}, T = {+,*,(,),x},
S = E
P = { E E+E | E*E | (E) | x}
G1 é ambígua. Por quê?
Gramáticas Livres de Contexto
• Analise a sentença: x+x*x
• Quantas árvores de derivação podem ser construídas para esta sentença, com base em G1?
Gramáticas Livres de Contexto
E * E
E
E + E x
x x
Outra árvore de derivação para a sentença: x+x*x
Gramáticas Livres de Contexto
+E
E
x
E
E * E
x x
Uma outra gramática para expressões aritméticas:
G1’ = (N, T, P, S) onde N = {T, F, E} T = {x, +, *, (, )} S = E
P = { E E + T, (1) L(G1´) ?
E T, (2) G1´ é ambígua ? T T * F, (3) T F, (4) F (E), (5) F x, (6) }
Gramáticas Livres de Contexto
Uma gramática para comandos condicionais aninhados:
<programa> ... <comando> ...
<comando> <condicional>
<condicional> if < condição > then <comando>
<condicional> if < condição > then <comando> else <comando>
< condição > ...
Provar que esta gramática é ambígua.
Gramáticas Livres de Contexto
Gramáticas Livres de Contexto
<condicional>
if <condição> then <comando> else <comando>
<condicional>
if <condição> then <comando>
Gramáticas Livres de Contexto
<condicional>
if <condição> then <comando>
<condicional>
else <comando>if <condição> then <comando>
Atividade:
1- Pesquise um gramática para a linguagem objeto de implementação do projeto de compiladores.
2- Verifique se ela é ambígua.
Gramáticas Livres de Contexto
Recommended