3 ExpressoesRegulares - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Linguagens Formais 
1 
Linguagens Formais 
• Conceitos 
• Gramática 
• Autômatos 
• Linguagem Regular 
• Linguagens Livres de Contexto 
• Resumo 
 
 
 
2 
Conceitos 
• Alfabeto (Σ): conjunto finito não vazio de símbolos. 
 Ex.: Σ = {a,b} 
 
• Palavra (string, word, cadeia): sequência finita de símbolos 
de Σ. 
 Ex.: a, b, aaa, bbb, ab 
 
• Tamanho de uma palavra: número de símbolos da palavra. 
Denotado por |x|. 
 
• Palavra vazia: λ 
 | λ |=0 
 3 
Conceitos 
• Linguagem sobre Σ: conjunto de palavras sobre Σ. 
 Σ* é o conjunto de todas as palavras sobre Σ. 
 
 Exemplo de linguagem sobre Σ = {0,1} 
 L = {w Є {0,1}* | w começa com 0} 
4 
Gramática 
• Gramática: 
– é um formalismo para definição de uma linguagem 
– é uma quádrupla (V, Σ, R, P), onde: 
 
 V (variáveis): um alfabeto 
 P Є V : variável de partida 
 Σ (terminais): um alfabeto 
 
 R (regras): uma relação do tipo u → v (u produz v), onde 
 u Є (V U Σ)+ 
 v Є (V U Σ)* 
 
 
 
5 
Gramática 
Exemplo: G = (V, Σ, R, P), em que: 
V = {A, B} 
Σ = {a,b} 
P = A 
 
Regras: 
A → aA | B 
B → bB | λ 
 
Esta gramática gera a linguagem 
L = {w Є {a,b}* | w = anbm , n ≥ 0 e m≥0 } 
 
 
6 
Autômatos 
• Autômato Finito: 
 
– é uma máquina de estados finitos do tipo reconhecedor de linguagem 
– é constituído por um alfabeto, um conjunto de estados e um conjunto 
de transições. 
 
– AFD (Autômato Finito Determinístico): 
• possui apenas um estado inicial e 
 
• cada par (estado,símbolo) é mapeado para um estado, ou seja, a 
partir de um dado estado, é possível atingir apenas um único 
estado para uma dada palavra na entrada. 
 
 
 
 
7 
Autômatos 
Exemplo de AFD: 
 
 
 
 
 
 
 
Reconhece a linguagem L= {w Є {0,1}* | |w| é par} 
 
2 1 
0,1 
0,1 
8 
Autômatos 
 
– AFN (Autômato Finito Não Determinístico): 
• pode possuir mais de um estado inicial e/ou 
• possuir algum par (estado,símbolo) mapeado para mais de um 
estado 
 
 
 1 2 
0,1 
0 
9 
Linguagem Regular 
 
• Linguagem Regular: são as linguagens reconhecidas por 
máquinas de estados finitos. 
 
• Especificação de linguagens regulares: expressões regulares e 
gramáticas regulares 
 
• Expressão Regular: 
 - φ, λ e a para qualquer a Є Σ são expressões regulares que denotam os 
conjuntos {φ} , {λ} e {a} respectivamente 
 - se r e s são expressões regulares, então (r + s), (rs) e (r)* também são 
expressões regulares 
 
 10 
Linguagem Regular 
 
Exemplos de expressões regulares: 
(0+1)* 
01* 
(a + b)*b(a+b)* 
 
 
Precedência: fecho de Kleene (*) - concatenação - união (+) 
 Exemplo: (0 + (10*)) equivale a 0 + 10* 
 
11 
Gramática Regular 
• Gramática Regular: em uma gramática regular, cada regra tem 
uma das formas: 
 
 X → a 
 X → aY 
 X → λ 
 
 Toda forma sentencial gerada por uma gramática regular é do 
tipo wA, onde w é constituído somente por símbolos 
terminais e A é uma variável. 
 
 
12 
Gramática Livre de Contexto 
• Gramática Livre de Contexto: em uma gramática livre de contexto, cada 
regra : 
– Tem do lado esquerdo apenas uma variável 
– Tem do lado direito uma palavra qualquer constituída por variáveis 
e/ou terminais 
 
Exemplo: P → 0P0 | 1P1 | 0 | 1 | λ 
Gera L= {w Є {0,1}* | w = wR} (palíndromos sobre {0,1}*) 
 
• Linguagem Livre de Contexto: uma linguagem é dita livre de contexto se 
existe uma gramática livre de contexto que a gere 
13 
Gramática Livre de Contexto 
• Ambiguidade: uma GLC (gramática livre de contexto) é ambígua se existe 
mais de uma árvore de derivação para alguma sentença que ela gera. 
 
 E → E + E | E * E | t 
 
 
 
E 
E E 
t 
+ 
E * 
t 
E 
t 
E 
E + 
t 
E 
t 
E 
* E 
t 
14 
Gramática Livre de Contexto 
• Linguagens de programação são especificadas por linguagens livres de 
contexto. 
 
• A remoção de ambiguidade é importante para a construção do analisador 
sintático, cuja operação baseia-se na construção de uma árvore de 
derivação a partir do programa fonte. 
 
• Há formas de se modificar uma gramática, sem alterar a linguagem 
gerada, por exemplo, eliminação de variáveis inúteis e de recursão à 
esquerda. 
 
• Este assunto será estudado mais profundamente em Análise Sintática 
 
 
15 
Gramática Livre de Contexto 
 
• Gramáticas livres de contexto são reconhecidas por Autômatos de Pilha. 
 
• Autômato de Pilha: é uma máquina similar a um autômato finito, porém 
possui uma pilha. 
 
Transições são do tipo: no estado e, se o próximo símbolo da entrada for a e 
o símbolo no topo da pilha for b, há uma transição de e para e’ , b é 
desempilhado e z é empilhado. 
 
 
 
 
e e’ 
a, b/z 
16 
Resumo 
 
• Linguagens são constituídas por símbolos de um alfabeto 
• Linguagens são especificadas por gramáticas 
• Autômatos são reconhecedores para linguagens 
• Linguagens Regulares são: 
– especificadas por gramáticas regulares ou expressões regulares 
– reconhecidas por autômatos finitos 
• Linguagens Livres de Contexto são: 
– especificadas por gramáticas livres de contexto 
– reconhecidas por autômatos de pilha 
 
 
 
 
 
17 
Referência Bibliográfica 
 Introdução aos Fundamentos da Computação – Linguagens e 
Máquinas 
Newton José Vieira – Ed. Thompson 
Capítulos 2 e 3 
 
18