impressao (1)

Prévia do material em texto

COMPILADORES 
AULA 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Frank Coelho de Alcantara 
 
 
 
2 
CONVERSA INICIAL 
O processo de compilação começa no analisador léxico, um módulo 
dedicado à análise de palavras de uma determinada linguagem. No caso da 
compilação, estaremos sempre falando de linguagens formais. Veremos nesta 
aula as funcionalidades do analisador léxico, começando pela definição de 
linguagem formal; estudaremos depois o conceito de lexema e passaremos 
pelas técnicas que permitem sua identificação e classificação. 
Segundo Mogensen (2010), a palavra léxico tem o sentido original de 
“referente às palavras”; do ponto de vista da ciência da computação, é 
necessário entender palavras como sendo conjuntos de símbolos usados em um 
código, visando à execução de um determinado algoritmo. A análise léxica 
consiste na identificação de palavras e símbolos contidos no código-fonte. 
Existem duas técnicas importantes de reconhecimento de lexemas: o uso 
de máquinas de estado finito e o uso de expressões regulares. Nos dois casos, 
partiremos dos alicerces da linguística computacional e chegaremos a 
aplicações práticas, com base em experiência e eficiência. Aqui, quando 
estudamos o analisador léxico, precisaremos considerar um lexema como sendo 
qualquer conjunto de caracteres que tenha algum sentido em uma determinada 
linguagem de programação. Assim, se recorremos à linguagem C, a palavra 
chave for e o símbolo == serão lexemas. Caberá ao analisador léxico reconhecer 
e classificar esses lexemas, atendendo às regras criadas para a linguagem de 
programação, em tokens. 
Uma vez que as palavras e símbolos tenham sido corretamente 
identificados, cada token será composto de, no mínimo, duas informações: uma 
classe e um valor. As classes dividem os lexemas segundo sua funcionalidade. 
No caso da linguagem C, para não fugir do exemplo, os lexemas for e == serão 
de classes diferentes, já que um é um operador lógico e o outro é uma palavra 
reservada. Os valores atribuídos a cada token são opcionais, e serão utilizados 
apenas para completar a informação necessária. 
TEMA 1 – LINGUAGENS E STRINGS 
Uma linguagem de programação é uma linguagem formal. Será formal a 
linguagem que possa ser rígida e precisamente especificada (Bergmann, 2010). 
Definimos linguagens formais por meio do Teorema de Kleene. Esse teorema 
 
 
3 
afirma que, para que uma linguagem seja considerada formal, ela deve ser 
definida por expressões regulares e máquinas de estado finitas. Um dos mais 
importantes corolários deste teorema indica que qualquer máquina de estados 
finita pode ser transformada em uma expressão regular e vice-versa. A 
especificação de uma linguagem formal requer o uso de alguns conhecimentos 
importados da álgebra. O conceito de conjunto é o primeiro deles. Definimos um 
conjunto como sendo uma coleção de objetos únicos chamados de elementos. 
Os conjuntos serão representados por uma letra maiúscula em negrito e itálico 
e seus elementos por letras minúsculas, números ou símbolos, entre chaves, 
como podemos ver na Equação a seguir: 
 𝑨 = {a, b, c, e, g, h} 
Um conjunto pode conter um número infinito de elementos, elemento 
nenhum ou qualquer quantidade entre esses dois extremos. O conjunto que não 
têm elementos é um conjunto vazio, representado pelo símbolo ∅. O conjunto 
𝑩 = {∅} não é um conjunto vazio, é um conjunto com um único elemento, que 
por sua vez é um conjunto vazio. Observe que, ao listarmos os elementos de um 
conjunto, cada elemento deverá aparecer uma vez; é também permitido listar os 
elementos do conjunto na ordem que desejarmos sem que isso altere a 
informação que ele contém. Existem, do ponto de vista da linguística 
computacional, dois conjuntos de símbolos muito importantes: o alfabeto, 
doravante representado por 𝜮, e a string. 
O alfabeto é o conjunto finito de todos os símbolos possíveis em um 
determinado domínio do conhecimento. O código ASCII, com seus 255 símbolos, 
e o Unicode, contendo mais de 100.000, são exemplos de alfabetos (Aho et al., 
2007). Usando um pouco de formalidade algébrica, podemos exemplificar 
conjuntos da seguinte forma: 
 𝜮𝟏 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, alfabeto utilizado para escrever todos os 
números positivos inteiros; 
 𝜮𝟐 = {a, b, c, d, e … x, y. z}, alfabeto utilizado para escrever palavras em 
idiomas latinos, se desconsiderarmos os acentos e sinais especiais. 
Note que o conjunto dos números inteiros (Ι = {0, 1, 2, 3, … }) não pode ser 
considerado um alfabeto, por ser infinito. Alfabetos são, obrigatoriamente, 
conjuntos finitos. O outro conjunto de símbolos igualmente importante para o 
 
 
4 
nosso estudo é o string. Diferindo dos conjuntos algébricos, em uma string a 
ordem em que os elementos são listados é importante. Observe que a string 𝑠 é 
um conjunto de símbolos de um determinado alfabeto 𝜮. Ressalte-se que uma 
string vazia ainda é uma string, sendo representada pelo símbolo 𝜺 (Bergmann, 
2010). 
Formalmente, podemos definir uma string como sendo uma sequência de 
símbolos 𝑠 de comprimento 𝑛 de um alfabeto 𝜮, representada pela função 
𝑠: [𝑛] → 𝜮 com domínio [𝑛] e contradomínio 𝜮. Dessa forma, podemos considerar 
a string 𝑠 = 𝑐𝑐𝑑𝑎 do alfabeto 𝜮 = {𝑎, 𝑏, 𝑐, 𝑑}, com 𝑛 = 4 e função 𝑠: [4] → 𝜮 
definida por: 𝑠(1) = 𝑐; 𝑠(2) = 𝑐; 𝑠(3) = 𝑑 𝑒 𝑠(4) = 𝑎. Seguindo essa definição, uma 
string vazia 𝑣 será definida pela função 𝑣: [0] → 𝜮. Podemos utilizar essa 
definição para exemplificar uma string 𝑠, do alfabeto 𝜮𝒕 = {a, b, c}. Nesse caso, 
podemos, por exemplo, definir as strings: 𝑎𝑏𝑐, 𝑎𝑎𝑏𝑐, 𝑐𝑎𝑏𝑏𝑎, … todas em relação 
ao alfabeto 𝜮𝒕 de comprimentos 𝑛 = 3, 𝑛 = 4, e 𝑛 = 5, respectivamente. 
É indispensável assim destacar que existe uma grande diferença entre 
uma string vazia, 𝜺 e uma string nula. Tomando, novamente a linguagem C como 
exemplo, poderíamos ter uma string contendo apenas o símbolo ‘\0’, uma string 
com um único caractere. Nesse caso, teríamos uma string vazia; como o ‘\0’ não 
existe no alfabeto da linguagem C, essa string não contém caractere algum. Já 
a string nula consiste de um ponteiro do tipo NULL. 
Definir uma linguagem a partir de suas strings não é uma tarefa trivial. 
Para tanto, podemos recorrer ao Teorema de Kleene, citado anteriormente, e 
nos ater a máquinas de estados finitos e a expressões regulares. 
TEMA 2 – MÁQUINA DE ESTADOS FINITOS 
O estudo das máquinas de estados é chamado de Teoria dos 
Autômatos. Consiste no estudo das regras de formação e comportamento de 
tais máquinas do ponto de vista da matemática e da lógica. Definimos uma 
máquina de estados finitos como sendo “um conjunto finito de estados 
submetidos a um número finito de transições entre estes estados” (Mogensen, 
2010). Cada estado é um momento específico no tempo; as condições internas 
da máquina estão estáveis, enquanto a transição é uma função que, recebendo 
dois argumentos, um estado e um símbolo de entrada, resulta em outro estado. 
Nesta disciplina, serão utilizadas, fundamentalmente, as Máquinas de Mealy, 
 
 
5 
cuja função de transição é relacionada com o estado da máquina e com o 
símbolo da entrada. 
No estado inicial, a máquina recebe um símbolo de uma string do alfabeto 
escolhido. Todas as vezes que um símbolo é lido, a máquina prossegue para um 
novo estado, indicado pela função de transição. Esse novo estado será 
determinado pela função de transição de acordo com o estado anterior e com o 
símbolo lido, atendendo às características da Máquina de Mealy. Ao terminar a 
leitura de todos os símbolos de entrada, a máquina ficará em um estado que 
indica o reconhecimento de uma sequência de símbolos (accepting state) ou não 
(non-accepting state). O conjunto de todas as strings aceitas pela máquina forma 
uma linguagem. 
Existem duas formas interessantes de se representar uma máquina de 
estados:a forma gráfica, ou diagrama de estados, e a forma tabular. Na forma 
gráfica, cada estado é representado por um círculo e as funções de transição 
são representadas por setas etiquetadas por um símbolo que representa a 
entrada da função. O estado inicial é representado por uma seta solta, sem 
nenhum estado em sua origem. Observe que, ao longo do funcionamento da 
máquina, os estados que estiverem em modo accepting state são representados 
por dois círculos concêntricos. Podemos sintetizar uma máquina de estados com 
cinco conceitos: 
1. Estados: pontos estáveis no processo de computação da máquina, 
representados por círculos; 
2. Estado inicial: estado onde a máquina inicia o processamento, indicado 
por um círculo com uma seta apontada para ele; 
3. Estados intermediários: todos os estados intermediários têm, no 
mínimo, duas setas: uma apontada para o círculo que o representa e outra 
deixando esse círculo; 
4. Estado final: se a string for corretamente processada, a máquina deverá 
assumir este estado, em geral indicando que está pronta para processar 
outra string (accepting state); o estado final é representado por dois 
círculos concêntricos. 
5. Transições: as transições são representadas por uma seta com origem 
em um estado e destino no estado seguinte; se a máquina permanecer no 
mesmo estado, a transição será representada por uma seta que deixa o 
estado e aponta para ele mesmo. 
 
 
6 
Uma máquina de estados comum em comunicação de dados é capaz de 
detectar a paridade de um conjunto de bits. Uma máquina de detecção de 
paridade começa pela definição do alfabeto 𝜮𝑨 = {0,1} e termina na 
especificação do diagrama de estados apresentado na figura. 
Figura 1 – Máquina de estados de um detector de paridade (números pares de 
uns) 
 
Todos os estados e transições desta máquina já estão definidos, e ela só 
pode receber informações pelo estado 𝑆0, e só estará em accepting state se o 
número de uns na string de entrada for par, incluindo a string nula (Holub, 1990). 
Um zero aplicado ao estado 𝑆0 manterá a máquina em accepting state, indicando 
zero uns. Ainda que zero não seja par, este conceito é usado em detectores de 
paridade. O primeiro número um da sequência de entrada leva a máquina para 
o estado 𝑆1. A partir desse momento, qualquer quantidade de zeros manterá a 
máquina em 𝑆1 e fora do accepting state. Ainda em 𝑆1, qualquer um levará a 
máquina para o estado 𝑆1 e para accepting state. Essa máquina reconhece 
qualquer número par de uns, inclusive um nenhum. 
A máquina apresentada na Figura 1 está perfeitamente determinada. 
Como o alfabeto possui apenas dois símbolos, e como cada um deles pode 
atingir um estado, cada estado tem exatamente duas setas de saída. As 
máquinas em que todas as transições são definidas e conhecidas são chamadas 
de determinísticas. Se existir uma única transição entre quaisquer dois estados 
que não possa ser diretamente relacionada a um dos símbolos do alfabeto, ela 
será denominada de 𝜖, e teremos como resultado uma máquina de estados 
finitos não determinística (Aho, 2007). 
 
 
7 
Existem duas diferenças formais muito importantes entre uma máquina de 
estados finitos não determinística e uma determinística. A inexistência de 
transições 𝝐 é uma delas, e a outra é a inexistência de transições múltiplas de 
saída para um mesmo símbolo. Ou seja, em uma máquina de estados finitos 
determinística cada estado terá uma, e somente uma transição para cada 
símbolo do alfabeto escolhido. 
Outra representação interessante das máquinas de estados finitos é a 
tabela. Nesse caso, cada linha é nomeada como um dos estados possíveis, cada 
coluna representa um dos símbolos do alfabeto e a interseção entre essas linhas 
e colunas representa o estado resultante da transição, como pode ser visto na 
tabela que segue. 
Tabela 1 – Tabela representação de uma máquina de paridade 
 
 
 
 
Como exercício, vamos desenvolver uma máquina de estados capaz de 
identificar uma string contendo um número ímpar de zeros, dado que 𝜮 = {0, 1}. 
Figura 2 – Solução 
 
 
TEMA 3 – EXPRESSÕES REGULARES 
Além das máquinas de estados finitos, podemos utilizar as expressões 
regulares, indicadas pelas letras 𝑟, 𝑠 𝑜𝑢 𝑡, para representar as strings de uma 
determinada linguagem 𝐿 derivada de um alfabeto finito 𝜮. O importante, nesse 
momento, é perceber que o alfabeto é o coração das expressões regulares. 
Dado um alfabeto 𝜮 qualquer, iremos descrever as strings, 𝑟, 𝑠 𝑜𝑢 𝑡, de uma 
linguagem 𝐿, por meio de um conjunto de expressões lógicas e matemáticas que, 
 0 1 
𝑺𝟎 𝑆0 𝑆1 
𝑺𝟏 𝑆1 𝑆0 
 0 1 
𝑆0 𝑆1 𝑆0 
∗ 𝑆1 𝑆0 𝑆1 
 
 
8 
deste momento em diante, chamaremos de expressões regulares. Contudo, é 
necessário destacar que, para que nossa álgebra atenda às necessidades 
propostas, é necessário considerar que os símbolos 𝜺, ∅, |, (, ) 𝒆 ∗ não fazem 
parte do alfabeto 𝜮 escolhido. 
Vejamos um exemplo simples de expressões regulares, considerando o 
alfabeto 𝜮 composto de todas as letras latinas em minúsculo. A expressão 
regular pode ser representada por 𝑎. Trata-se da representação de todos as 
strings que atendam ao conjunto {𝑎}. Considerando que essa expressão regular 
está relacionada a um conjunto de strings da linguagem 𝐿 de alfabeto 𝜮 =
{𝑎, 𝑏, 𝑐, … , 𝑥, 𝑦, 𝑧}, a expressão regular representa o conjunto de todas as strings 
que possuem apenas um caractere, o caractere 𝑎. Com o auxílio do Teorema de 
Kleene, é possível representar essa expressão regular na forma de uma máquina 
de estados finitos. 
Para entendermos o potencial das expressões regulares, precisamos 
definir três operações importantes: a união, a concatenação e uma operação 
especial chamada de Kleene star ou closure. Elas definem todas as operações 
necessárias para a criação de expressões regulares. 
3.1 União 
Em linguística computacional, a união é definida exatamente da mesma 
forma que na teoria dos conjuntos. Tomando dos conjuntos 𝑳𝟏 =
{a, b, c, eg, hf} e 𝑳𝟐 = {ea, af}, temos que 𝑳𝟏 ∪ 𝑳𝟐 = {a, b, c, eg, hf, ea, af}. Observe 
que, em alguns textos técnicos, principalmente em inglês, o símbolo algébrico 
da união (∪) é substituído pelo símbolo da soma (+) ou por uma barra vertical 
(|). Precisamos ressaltar ainda que a união de um conjunto com um conjunto 
vazio é o próprio conjunto. Por fim, podemos representar um conjunto vazio 𝑨 de 
duas formas: 𝑨 = ∅ ou 𝑨 = {}. A operação de união é tão poderosa que, em 
alguns textos de linguística computacional, dizemos que a linguagem 𝐿1 é 
autocontida na operação de união. 
3.2 Concatenação 
Do ponto de vista intuitivo, o resultado da concatenação de duas strings é 
uma string formada pelas duas strings originais, em sequência. Assim, a 
concatenação de “um belo dia” e “ começa cedo” será “um belo dia começa 
 
 
9 
cedo”. Observe que, para que a operação de concatenação seja perfeita, é 
preciso que as strings tenham os valores desejados. Se tirarmos o espaço que 
existe no começo de “começa cedo”, o resultado seria: “um belo diacomeça 
cedo”. Considerando um pouco de formalidade matemática, devemos expandir 
o conceito de que a concatenação é uma operação a ser realizada entre duas 
linguagens 𝐿1 𝑒 𝐿2. Nesse caso, definimos a concatenação 𝐿 entre 𝐿1 e 𝐿2 como 
sendo: 
 𝐿 = 𝐿1 ⋅ 𝐿2 = {𝑥𝑦 |𝑥 ∈ 𝐿1, 𝑦 ∈ 𝐿2} 
No caso mais comum de concatenação, visto diariamente na construção 
de programas, consideramos as linguagens 𝐿1 e 𝐿2 como sendo conjuntos de 
uma única string; sendo assim, podemos extrapolar a definição de concatenação 
para esse caso específico. Dadas duas strings representadas pelas funções 
𝑠1: [𝑚] → 𝜮 e 𝑠2: [𝑛] → 𝚺, é possível definir a concatenação como sendo a função 
𝑠1 ⋅ 𝑠2: [𝑚 + 𝑛] → 𝜮 de comprimento 𝑙 = 𝑚 + 𝑛, para todos os 𝑖, se e somente se: 
 𝑠1(𝑖) ⋅ 𝑠2(𝑖) = {
𝑥(𝑖), 𝑠𝑒 𝑖 ≤ 𝑚
𝑦(𝑖−𝑚), 𝑠𝑒 𝑖 > 𝑚 
 
Destaforma, se tivermos 𝑠1 = “cbba” e 𝑠2 = “ac”, teremos 𝑠1 ⋅ 𝑠2 =
“𝑐𝑏𝑏𝑎𝑎𝑐”; ou, em formato de tabelas e correndo todos os valores de 𝑖 em cada 
string (Rangel, 2013), como pode ser visto na tabela abaixo. 
Tabela 2 – Concatenação de strings pelo método formal de concatenação 
𝒊 𝒔𝟏(𝒊) 𝒊 𝒃𝟐(𝒊) 𝒊 (𝒔𝟏 ⋅ 𝒔𝟐)(𝒊) 
𝟏 c 𝟏 a 𝟏 c 
𝟐 b 𝟐 c 𝟐 b 
𝟑 b 𝟑 b 
𝟒 a 𝟒 a 
 𝟓 a 
 𝟔 c 
Podemos ainda usar uma notação algébrica um pouco mais refinada para 
indicar a concatenação de duas strings. Se assim for, podemos dizer que dadas 
as strings 𝑠1 e 𝑠2, a concatenação será um conjunto representado por 𝜮
∗ que 
indica um conjunto finito de strings relativas ao alfabeto 𝜮, de tal forma que: 𝑠1 ⋅
 
 
10 
𝑠2 = 𝜮
∗. Podemos exemplificar considerando que 𝑠1 = 𝑎𝑏, 𝑠2 = 𝑟𝑎, 𝑠3 = 𝑐𝑎𝑑. 
Teremos: 𝑠2 ⋅ 𝑠1 = 𝑟𝑎𝑎𝑏, 𝑠1 ⋅ 𝑠1 = 𝑎𝑏𝑎𝑏 e 𝑠3 ⋅ 𝑠2 = 𝑐𝑎𝑑𝑟𝑎. Importante lembrar que 
a concatenação pode ser realizada entre várias strings (Pitts, 2013), mas sempre 
dois a dois, dessa forma: 
 𝑠1 ⋅ 𝑠2 ⋅ 𝑠3 ⋅ 𝑠1 ⋅ 𝑠2 = (((𝑠1 ⋅ 𝑠2) ⋅ 𝑠3) ⋅ 𝑠1) ⋅ 𝑠2 = 𝑎𝑏𝑟𝑎𝑐𝑎𝑑𝑎𝑏𝑟𝑎 
Além disso, é preciso destacar que o comprimento (length) da string 
concatenada é a soma dos comprimentos das strings, ou seja: 
 𝑙𝑒𝑛𝑔𝑡ℎ(𝑠1 ⋅ 𝑠2) = 𝑙𝑒𝑛𝑔𝑡ℎ(𝑠1) + 𝑙𝑒𝑛𝑔𝑡ℎ(𝑠2) 
O comprimento da string concatenada é importante em linguagens de 
programação, porque define o espaço de memória necessário ao manuseio da 
string. Vejamos alguns exemplos do uso da concatenação (Pitts, 2013): 
a. Se 𝜮 = {𝑎} então Σ∗ = {𝜺, 𝑎, 𝑎𝑎, 𝑎𝑎𝑎, … }; 
b. Se 𝜮 = {𝑎, 𝑏} então Σ∗ = {𝜺, 𝑎, 𝑎𝑎, 𝑏, 𝑎𝑏, 𝑏𝑎, 𝑏𝑏, 𝑎𝑎𝑎, 𝑎𝑎𝑏, … }; 
c. Se 𝜮 = ∅ então Σ∗ = {𝜺}. 
3.3 Kleene star 
A operação Kleene star, frequentemente chamada de closure, é uma 
operação unária representada por um ∗ e similar ao processo de exponenciação, 
de tal forma que Kleene de 𝐿, representada por 𝐿∗, é a linguagem 𝐿 repetida zero 
ou mais vezes. A operação Kleene star é uma sequência de concatenações de 
uma linguagem com ela mesmo (Hel-or, 2010). Por exemplo, se 𝐿 contém 
apenas um símbolo, 𝐿∗ será este símbolo repetido zero ou mais vezes. Sendo 
assim, se tomarmos uma linguagem 𝐿 podemos definir: 
a. 𝐿0 = 𝜺; 
b. 𝐿1 = 𝐿; 
c. 𝐿2 = 𝐿 ⋅ 𝐿; 
d. 𝐿𝑛 = 𝐿 ⋅ 𝐿𝑛−1; 
e. 𝐿∗ = 𝐿0 + 𝐿1 + 𝐿2 + 𝐿3 + ⋯. 
Observe que, aplicada sobre uma linguagem que seja um conjunto vazio, 
ou seja, que não possui nenhuma string, o resultado da closure será uma string 
 
 
11 
vazia: 𝐿 = ∅ ∴ ∅∗ = 𝜺. Podemos definir a operação Kleene star de forma 
algébrica por: 
 𝐿∗ = ⋃ 𝐿𝑖
∞
𝑖=0
 
Vejamos um exemplo: se 𝐿1 = {𝑎} e 𝐿2 = {𝑏}, então: 
𝐿1
∗ ⋅ 𝐿2 = {𝑏, 𝑎𝑏, 𝑎𝑎𝑏, 𝑎𝑎𝑎𝑏 … }. É possível aqui perceber a propagação Kleene do 
símbolo 𝑎 de zero ao infinito, sendo concatenado, repetidamente, ao símbolo 𝑏, 
que não está sujeito à operação Kleene star. Podemos exemplificar a Kleene 
star considerando a linguagem L = {0,1}. Dessa forma: 
 𝐿0 = {𝜺} 
 𝐿1 = {0,1} 
 𝐿2 = 𝐿 ⋅ 𝐿1 = {00,01,10,11} 
 𝐿3 = {000, 001, 010, 011, 100, 101, 110, 111} 
 𝐿∗ = {𝜺, 000, 001, 010, 011, 100, 101, 110, 111, 1000 … } 
Estudamos as três operações que usaremos para definir as expressões 
regulares: uma unária, a Kleene star, e duas binárias, a concatenação e a união. 
Com essas operações, podemos definir qualquer expressão regular para 
identificar qualquer string de qualquer alfabeto dado. A procedência será definida 
pelo uso de parênteses. Se não forem utilizados parênteses para definir a 
precedência entre as operações, Kleene star irá tomar a precedência sobre a 
concatenação e esta terá precedência sobre a união. Vamos ver o seguinte 
exemplo: 
 𝑎|𝑎𝑏∗ = (𝑎|(𝑎 ⋅ 𝑏∗)) 
Como dito anteriormente, as suas expressões regulares serão escritas 
com uma combinação das três operações básicas. Talvez isso não fique claro, 
até que você dê uma olhada na tabela abaixo. Ela apresenta algumas 
expressões regulares básicas para fixação dos conceitos, e introduz algumas 
alterações na simbologia utilizada, o que facilitará o uso das expressões 
regulares em ambiente de programação. 
 
 
12 
Tabela 3 – Concatenação de strings pelo método formal de concatenação 
Regex Álgebra Descrição 
𝒙 {“𝑥”} Um conjunto contendo apenas a string 𝑥 
𝜺 {““} Um conjunto contendo nenhuma string, a string 
vazia 
𝒔|𝒓 𝐿(𝑠) ∪ 𝐿(𝑟) A união de strings de ambas as linguagens 
𝒔 + 𝒓 𝐿𝑠 ∪ 𝐿(𝑟) A união de strings de ambas as linguagens 
𝒔 ⋅ 𝒓 = 𝒔𝒓 {𝑥𝑦|𝑥 ∈ 𝑠, 𝑦 ∈ 𝑟} Strings construídas com a concatenação das 
strings em 𝑠1 com as strings em 𝑠2 
𝒔∗ 𝜺 ∪ {𝑥𝑦|𝑥 ∈ 𝐿𝑠, 𝑦 ∈ 𝐿𝑠∗} Cada string é a concatenação de um número 
qualquer de strings da linguagem de 𝑠 
 
No último caso, a operação 𝑠∗ é definida de forma recursiva; consiste da 
string vazia 𝜺 mais aquilo que poderá ser obtido por intermédio da concatenação 
das linguagens 𝐿𝑠 e 𝐿𝑠∗. Equivale a dizer que a linguagem 𝐿𝑠∗ consiste de strings 
que podem ser obtidas pela concatenação de zero ou mais strings de 𝐿𝑠. 
Suponha que 𝐿𝑠 = { 𝑎, 𝑏}. Então, 𝐿𝑠∗ = {𝜺, 𝑎, 𝑏, 𝑎𝑎, 𝑏𝑏, 𝑎𝑏, 𝑏𝑎, … }, ou seja, qualquer 
string composta unicamente das combinações entre 𝑎 e 𝑏, incluindo a string 
vazia. 
Analisando a Tabela 3, é possível concluir que existe um símbolo qualquer 
𝑥 | 𝑥 ∈ 𝜮; assim, 𝑥 é uma expressão regular. Da mesma forma, a string vazia 𝜺 
também é uma expressão regular. É possível inferir algumas regras básicas do 
uso de expressões regulares para o reconhecimento de strings de uma 
linguagem 𝐿 sobre um alfabeto 𝜮. Podemos dizer que, dada uma expressão 
regular 𝑟: 
Tabela 4 – Condições de reconhecimento entre strings e expressões regulares 
Condições de concordância (reconhecimento) 
𝒓 reconhece 𝒂 ∈ 𝜮 se e somente se 𝒓 = 𝒂 
𝒓 reconhece 𝜺 ∈ 𝜮 se e somente se 𝒓 = 𝜺 
Nenhuma string será reconhecida por ∅ 
𝒓 reconhece 𝒂|𝒃 se e somente se 𝒓 = 𝒂 ou 𝒓 = 𝒃 
 
Neste ponto, estamos prontos para definir expressões regulares 
algébrica, formalmente, por seus quatro axiomas: 
1. ∅ é uma expressão regular que indica um conjunto vazio. 
 
 
13 
2. 𝜺 é uma expressão regular que indica um conjunto contendo uma string 
vazia; 
3. Para cada símbolo 𝑎 ∈ 𝜮 existe uma expressão regular 𝑎 que indica o 
conjunto {𝑎}. 
4. Se 𝑟 e 𝑠 são expressões regulares referentes as linguagens 𝑅 e 𝑆, então 
(𝑠𝑟), (𝑠|𝑟) 𝑒 𝑠∗ são expressões regulares que indicam as linguagens 𝑆 ⋅ 𝑅,
𝑆𝑈𝑅 e 𝑆∗ respectivamente. 
Algumas propriedades, apresentadas na Tabela 5, são derivadas desses 
axiomas e do que vimos sobre as operações união, concatenação e Kleene star. 
Tabela 5 - Propriedades das operações União, Concatenação e Kleene Star 
Propriedades 
1 ∅𝑠 = 𝑠∅ = 𝑠 
2 𝜀𝑠 = 𝑠𝜀 = 𝑠 
3 𝑠|∅ = 𝑠 + ∅ = ∅ + 𝑠 = 𝑠 
4 𝑠|𝑠 = 𝑠 + 𝑠 = 𝑠 
5 𝑟 + 𝑠 = 𝑠 + 𝑟 
6 𝑟(𝑠 + 𝑡) = 𝑟𝑠 + 𝑟𝑡 
7 (𝑟 + 𝑠)𝑡 = 𝑟𝑡 + 𝑠𝑡 
8 𝑟(𝑠𝑡) = (𝑟𝑠)𝑡 
9 ∅∗ = 𝜀 
10 𝜀∗ = 𝜀 
11 (𝜀 + 𝑟)+ = 𝑟∗ 
12 (𝜀 + 𝑟)∗ = 𝑟∗ 
13 𝑟∗(𝜀 + 𝑟) = (𝜀 + 𝑟)𝑟∗ = 𝑟∗ 
14 𝑟∗𝑠 + 𝑠 = 𝑟∗𝑠 
15 𝑟(𝑠𝑟)∗ = (𝑟𝑠)∗𝑟 
16 (𝑟 + 𝑠)∗ = (𝑟∗𝑠)∗𝑟∗ = (𝑠∗𝑟)∗𝑠∗ 
 
Podemos utilizar o conhecimento já adquirido para escrever uma 
expressão regular capaz de reconhecer qualquer número positivo do conjunto 
dos números inteiros, desde que nos lembremos que os números desse conjunto 
são representados por um ou mais dos seguintes algarismos: 
0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Sendo assim, podemos escrever a seguinte expressão 
regular: 
 
 
14 
Eq.1 (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ 
A Eq. 1 mostra a concatenação entre um conjunto e seu Kleene, já que 𝑠∗ 
indica zero ocorrências ou mais de cada um dos algarismo. Se consideramos 
que o conjunto vazio está implícito na operação Kleene, essa expressão regular 
representa, entre outros, os seguintes números:0 ,1, 10, 1000, 1234000, etc. 
podendo ser utilizada para representar qualquer um deles (Mogensen, 2010). 
Podemos também excluir outros símbolos do alfabeto para escrever uma 
notação mais amigável. Podemos excluir os símbolos . ? * + ^ $ | [ ] { } ( ) da 
nossa linguagem de exemplo e usá-los para definir um conjunto de símbolos de 
controle, ou metacaracteres. Se fizermos isso, a Eq. 1 poderia ser representada 
por: [0 − 9][0 − 9]∗. Usando essa notação nesse intervalo, poderíamos 
representar todas as combinações de letras do alfabeto português, menos os 
acentos e caracteres especiais pela concatenação de dois intervalos: [𝑎 − 𝑧𝐴_𝑍]. 
Para simplificar ainda mais a notação, podemos também excluir os símbolos +, ? 
e determinar que 𝑠+ representa uma ou mais ocorrência, e também que 𝑠 = 𝑠|𝜺 
representa a união de uma string com a string vazia. Se fizermos isso, a 
representação de um número inteiro positivo qualquer pode ser simplificada para 
[0 − 9]+. Agora é possível expandir esses conceitos para a representação de 
algumas das classes de lexemas mais utilizadas em linguagens formais, 
notadamente no universo das linguagens de programação. Vamos assim tentar 
explicar as expressões regulares que podem ser utilizadas para seu 
reconhecimento (Mogensen, 2010). Por fim, de forma muito simplificada: 
a. Palavras-chaves, ou Keywords. Devem ser reconhecidas por 
expressões regulares exatamente iguais às palavras chaves. Em C, por 
exemplo, a palavra-chave if será reconhecida pela expressão regular if. 
b. Nomes de variáveis. Neste caso, depende-se das regras de formação de 
cada linguagem. Em C, por exemplo, podemos escrever qualquer nome 
de variável, desde que ele comece com uma letra, contenha números e o 
caractere “_” e não utilize nenhum caractere excluído do alfabeto. Estes 
nomes de variáveis podem ser reconhecidos por: [𝑎 − 𝑧𝐴 − 𝑧_][𝑎 − 𝑧𝐴 −
𝑍0 − 9_]∗. 
c. Inteiros. Para a representação de inteiros positivos, podemos usar 
[0 − 9]+; porém, na linguagem C, por exemplo, precisamos representar 
 
 
15 
inteiros positivos e negativos. Assim, a expressão mais correta seria: 
[+|−]? [0 − 9]+, indicando qualquer número inteiro e podendo ter ou não 
os sinais + e – na frente1. 
d. Números de ponto flutuante. Números de ponto flutuante têm uma 
quantidade indefinida de algarismos antes e depois da vírgula (ponto nas 
linguagens de programação). Podem ter os símbolos de + e – e ainda 
podem estar em notação especial, representados por uma mantissa e um 
expoente. Talvez, uma forma de representar esses números seja a 
expressão regular: [+−]? (([0 − 9]+(. [0 − 9]∗)? [0 − 9]+)([eE][+−]? [0 −
9]+)? ) (Mogensen, 2010). 
e. Strings constantes. Neste caso, também precisamos entender as regras 
de formação da linguagem de programação. Na linguagem C, podemos 
representar as strings por: “([a-zA-z0-9]\[a-zA-Z])*” (Mogensen, 2010). 
Sem dúvida, o uso das expressões regulares fugiu do controle da álgebra 
e hoje pertence ao domínio das linguagens de programação; como tal, acaba 
tendo uma sintaxe própria, dependendo do padrão. Por exemplo, o padrão Posix, 
utilizado em máquinas Unix, Linux e Windows, é comum em várias linguagens 
de programação e merece que você pesquise sobre isso. 
Vamos finalizar esta seção com um exercício. Considerando o que vimos 
sobre expressões regulares, vamos escrever a expressão regular capaz de 
identificar um endereço IPv4. Solução: [0-9]{3}\.[0-9]{3}\.[0-9]{3}\.[0-9]{3}. 
TEMA 4 – LEXEMAS E TOKENS 
Devemos considerar o código, texto completo do programa, como sendo 
uma única string composta de strings que denominaremos lexemas. A função do 
analisador léxico será distinguir e identificar esses lexemas e classificá-los em 
tokens. O conceito de lexema em computação deriva da ciência da linguística, e 
representa apenas uma sequência de caracteres, ou símbolos, que juntos 
formam uma unidade sintática que tenha algum significado. Nesta disciplina, 
consideraremos token como sendo uma estrutura de dados que represente um 
lexema e explicite, além de sua classe e valor, informações que auxiliem no 
processo de análise léxica. Considerando a linguagem C, o analisador léxico 
 
1 De fato, para que isso fosse algebricamente correto, precisaríamos de um símbolo para indicar 
que, entre [, ], os símbolos + e – fazem parte do alfabeto utilizado. 
 
 
16 
deverá ser capaz de classificar lexemas diferentes em diversas classes de 
tokens, descritas por sua própria máquina de estados finito, ou expressão 
regular. Entre as classes diferentes da linguagem C, é possível destacar 
(Banahan; Brady; Doran, 1991): 
1. Palavras-chaves, keywords. São palavras que possuem um significado 
específico na linguagem; geralmente definem um comando ou processo 
específico. As keywords fazem parte da linguagem, e não podem ser 
utilizadas pelo programador como identificadores. 
2. Identificadores, identifiers. Palavras que podem ser utilizadas para 
identificação de variáveis e constantes. Em geral, as linguagens de 
programação apresentam apenas uma regra de formação dessas 
palavras. 
3. Operadores, operators. Símbolos utilizados para a realização de 
operações lógicas, aritméticas ou entre caracteres, os quais podem ser 
constituídos de um ou mais caracteres. Assim, o ! =, símbolo que 
representa diferente, na linguagem C, é formado por dois caracteres 
ASCII {!, =}; 
4. Valores numéricos. Valores que representam números inteiros, ou de 
ponto flutuante, positivos ou negativos, nas diversas notações possíveis 
– e, em muitas linguagens, em várias bases. Em C, é possível incluir 
números em decimal, hexadecimal e octal, mas não em binário. 
5. Caracteres especiais. Geralmente usados para limitar comandos, blocos 
ou caracteres. Entre outros, podemos citar: {, }, ,, . , (, ), 𝑒𝑡𝑐. 
6. Caracteres constantes. Caracteres especiais, não gráficos, utilizados 
para funções especiais dentro de strings e declarações. 
7. Comentários. Geralmente são identificados na fase de análise léxica, 
mas são ignorados pelo analisador léxico. Ou seja, precisam ser 
identificados, mas não são transformados em tokens e não são enviados 
para a próxima fase. 
8. Espaços, tabulações e novas linhas. Em geral, esses caracteres são 
ignorados e não são transformados em tokens, nem passados à próxima 
fase do processo de compilação. 
Esta lista não representa todas as possiblidades de classe utilizadas em 
linguagens de programação. Não é sequer a lista completa da linguagem C e 
está longe de ser a única solução possível. Para cada lexema identificado, será 
 
 
17 
preciso gerar uma estrutura de dados para armazenamento. Essencial, porém 
não exclusivamente, são necessárias duas informações: uma classe e um valor, 
de forma que teremos um par que, em geral, será composto por dois valores 
inteiros. Um token na linguagem de programação C/C++ poderia ser 
representado por uma struct: 
typedef struct 
{ 
 int nome; 
 int valor; 
} *Token; 
Não é raro que essa estrutura tenha informações referentes à linha e 
coluna onde aquele determinado token foi localizado no código. Essa informação 
é útil, entre outras coisas, para a identificação de erros. Se assim for, poderíamos 
ter duas estruturas para acrescentar a informação, como pode ser visto no 
fragmento de código a seguir: 
typedef struct { 
 int linha; 
 int coluna; 
} Position; 
 
typedef struct { 
 int nome; 
 int valor; 
 Position posicao; 
} Token; 
Estes tokens identificados e classificados serão armazenados na tabela 
de símbolos. 
4.1 Identificação de tokens 
Do ponto de vista didático, podemos remover um pouco da complexidade 
formal das máquinas de estados finitos determinística e criar um diagrama mais 
objetivo, que chamaremos de diagrama de transição. Usaremos os diagramas 
de transição para representaro processo de reconhecimento de um token. A 
vantagem do uso deste diagrama irá surgir no processo de transformação em 
 
 
18 
código. Geralmente, será possível converter o diagrama de transição em código 
usando apenas uma estrutura switch-case, comum em muitas linguagens de 
programação. 
Representaremos os diagramas de transição por um grafo formado por 
um conjunto de nós. Cada nó representa uma condição específica do processo 
de reconhecimento, e cada transição representa um caractere ou um conjunto 
de caracteres. Para simplificar, vamos representar apenas as transições que 
provocam mudanças de estado. O reconhecimento de lexemas provocará a 
criação do token correspondente, que deverá ser armazenado em uma estrutura 
de dados qualquer. Vamos usar como exemplo a figura abaixo, adaptada do 
trabalho e Aho et al. (2007). 
Figura 3 – Diagrama de transição para reconhecimento de <, >, =, <= e <= 
 
Nesse diagrama, cada estado de reconhecimento está representado por 
dois círculos concêntricos, um par ordenado com a classe do token e seu valor. 
Tanto a classe como o valor são constantes inteiras que, em um compilador real, 
poderiam estar definidas em diretivas de pré-processamento ou em uma tabela 
de valores constantes. O código pode ser muito simples se você fizer uma função 
para cada estado e passar como argumento desta função os símbolos. 
4.2 A complexidade da identificação 
 À primeira vista, o processo de reconhecimento de lexemas, para a 
criação de tokens é simples e depende apenas da capacidade de criação de 
expressões regulares e de máquinas de estado finitas. Entretanto, existem 
4 
0 
< 
1 2 
3 
= 
𝒐𝒖𝒕𝒓𝒐𝒔 
= 
5 6 
7 
> 
𝒐𝒖𝒕𝒓𝒐𝒔 
= 
< 𝒐𝒑, 𝑬𝑸 > 
< 𝒐𝒑, 𝑳𝑬 > 
< 𝒐𝒑, 𝑳𝑻 > 
< 𝒐𝒑, 𝑮𝑻 > 
< 𝒐𝒑, 𝑮𝑬 > 
 
 
19 
algumas considerações que precisam ser feitas. Tome como exemplo a seguinte 
declaração na linguagem C: 
typedef struct { 
 int linha; 
 int coluna; 
} Position 
Tanto o lexema typedef quanto o struct são palavras reservadas da 
linguagem C. Contudo, o typedef, para todos os efeitos, cria uma nova palavra-
chave, no caso Position. Neste caso, o analisador léxico terá que tratar o lexema 
Position como sendo da classe palavra-chave e não da classe identificador 
(Holub, 1990). Estruturas de dados complexas, como funções, objetos, arrays e 
structs, também requerem cuidado extra do analisador léxico. Todos esses tipos 
podem ser utilizados para a criação de novos escopos e de novos lexemas que 
poderão ou não ser identificados como palavras-chave ou identificadores. 
Na identificação de lexemas, ainda precisamos considerar o escopo. Isso 
quer dizer que existem blocos de códigos nos quais determinadas variáveis são 
visíveis. Na maior parte das linguagens, duas regras simples definem o 
mecanismo de escopo: (a) se um nome é declarado dentro de um bloco 𝑥 
qualquer, o nome só é válido neste bloco 𝑥; (b) se um bloco 𝑦 existe aninhado a 
um bloco 𝑥, qualquer nome declarado no bloco 𝑥 será valido no bloco 𝑦, a não 
ser que o nome também seja declarado no bloco 𝑦. Veja, por exemplo, o 
fragmento de código a seguir, em que temos dois lexemas i em escopos 
diferentes: 
#include <stdio.h> 
#include <stdlib.h> 
int main() { 
 int i = 35; 
 for (int i = 0; i < 10; i++){ 
 printf( "%d\n", i ); 
 } 
 printf( "%d\n", i ); 
 system( "pause" ); 
} 
 
 
20 
Se você executar esse código, terá uma contagem de zero até nove, 
seguida do número 35. A primeira declaração int i = 35; cria a variável i em 
memória e lhe atribui o valor 35; esta variável existe, e pode ser acessada dentro 
do bloco definido por int main() {...}. Mas, dentro desse mesmo bloco de código, 
usamos novamente o lexema i, dessa vez para definir uma variável i que só 
existe dentro do bloco definido por for (int i = 0; i < 10; i++){...}. O analisador 
léxico deve registrar os dois lexemas i como identificadores e diferenciar o 
escopo de cada um de acordo com o uso. O analisador léxico ainda terá que 
considerar o escopo estático, quando uma variável é definida antes do tempo de 
execução, e o escopo dinâmico, caso em que a variável será definida em tempo 
de execução. 
Uma das técnica utilizadas para resolver o problema do escopo é criar um 
conjunto de tabelas de símbolos, uma para cada escopo ativo durante o 
processo de compilação. Sempre que um bloco novo é encontrado, uma nova 
tabela de símbolos será criada. Nesse caso, é possível utilizar tanto a binary 
search tree quanto a linked list; muitas vezes a seleção é feita levando-se em 
consideração o tamanho do bloco. 
TEMA 5 – A TABELA DE SÍMBOLOS 
As tabelas de símbolos são estruturas de dados complexas utilizadas 
pelos compiladores para o armazenamento de informações referentes aos 
artefatos utilizados para a construção do programa (Aho et al., 2007). Esses 
artefatos serão relacionados ao código-fonte, ao modelo clássico de tabela de 
símbolos, ou à otimização e eficiência do código, modelo que vem sendo 
adotado em compiladores na segunda década do século XXI. 
A informação armazenada na tabela de símbolos é resultado do processo 
de compilação, de modo que, a cada novo passo, as informações são 
armazenadas, alteradas ou removidas, sempre com vistas a atender melhor o 
passo seguinte. Tradicionalmente, os principais módulos envolvidos nesse 
processo são o analisador léxico, que estamos estudando agora, e os 
analisadores sintático e semântico, que veremos nas próximas rotas. 
Atualmente, as tabelas de símbolos contêm informações sobre tempo de 
execução de blocos de código, pontos de entrada e saída de funções em 
memória e outras informações que podem ser úteis para a melhorar a eficiência 
 
 
21 
do código em execução. Com isso em mente, vamos rever o modelo do processo 
de compilação apresentado na Figura 4. 
Não é difícil perceber que, devido à sua importância, a tabela de símbolos 
requer alguma atenção e deve atender a requisitos de velocidade e eficiência. 
Nesse caso, a velocidade de acesso é indispensável, já que a tabela verdade 
deverá ser acessada; com muita frequência, a melhor solução é que toda a 
tabela esteja armazenada em memória. Isso provoca a necessidade de termos 
uma estrutura de armazenamento que seja de manutenção fácil e também 
flexível. Chega-se a uma estrutura na qual os registros podem ser facilmente 
removidos e em que a ordem e a hierarquia de armazenamento podem ser 
alteradas sem custos exagerados de processamento. 
Figura 4 - Modelagem do processo de compilação 
Existem diversas estruturas de dados que se valem da tabela de símbolos. 
Talvez a estrutura mais simples seja um array de structs. Podemos montar uma 
pilha, usando o array e controlando o tipo e a quantidade de dados em cada 
registro, valendo-se dos campos da structs. Um array é uma estrutura lenta. Uma 
alternativa é o uso das chamadas listas encadeadas, ou linked lists em inglês. 
Nesse caso, cada registro terá o endereço do próximo. Essa estrutura facilita a 
inserção de novos registros, ou até mesmo de blocos de registros, sem grandes 
custos computacionais extras. Também resolve o problema de remoção de 
Analisador 
Léxico 
Analisador 
Sintático 
Analisador 
Semântico 
Gerador de Código 
Intermediário 
Front-end 
 
Otimizador 
de Código 
Gerador d
e Código 
Final 
Back-end 
Tabela 
de 
Símbolos 
 
 
 
22 
blocos de registros, independentemente do seu tamanho. Contudo, não resolve 
o problema da busca reversa, que continua sendo computacionalmente cara. 
O problema da busca de informações na tabela de símbolos pode ser 
resolvido se utilizarmos uma estrutura chamada árvore binária de buscas, em 
inglês binary search tree. Nesse caso, o tempo de busca será praticamente igual 
ao tempo de inserção e não perderemos nenhuma das funcionalidades da lista 
encadeada. Essa estrutura também pode serconstruída a partir de structs; nesse 
caso, tudo que precisamos é garantir a existência de um ponteiro apontado para 
o nó da esquerda e outro apontando para o nó da direita. Considerando os 
fragmentos de código que usamos até o momento, teríamos que fazer a seguinte 
mudança nas nossas structs: 
typedef struct { 
 int linha; 
 int coluna; 
} Position; 
 
struct Token { 
 int ID; 
 int valor; 
 Position posicao; 
 struct Token *esquerda; 
 struct Token *direita; 
}*head; 
Já entendemos os problemas básicos do analisador léxico. Agora nos 
falta apenas aprofundar o processo de identificação. 
FINALIZANDO 
Estudamos as características do analisador léxico, que é o módulo do 
compilador responsável por identificar cada lexema do código fonte. Para 
entender esse processo, analisamos como definir uma linguagem formal a partir 
do Teorema de Kleene. Por sua vez, o Teorema de Kleene nos conduziu ao 
estudo das máquinas de estado determinísticas e das expressões regulares. São 
duas tecnologias que, além de servirem de base para a definição das linguagens 
formais, fundamentais para a programação, também se caracterizam como duas 
 
 
23 
formas eficientes de localizar e categorizar os lexemas em tokens. Uma vez que 
os tokens tenham sido criados, chegamos à tabela de símbolos. 
As máquinas de estado finito determinísticas se destacam nesse processo 
graças à sua facilidade de codificação. Contudo, muitas linguagens de 
programação adotaram algum tipo de expressão regular para a identificação de 
strings, dispensando a necessidade de codificar o processo de identificação de 
strings. Vimos inclusive que existem alguns padrões para o uso de expressões 
regulares em codificação, como o que é adotado no Posix. 
Durante o processo de compilação clássico, os módulos trocam 
informações entre si por meio da tabela de símbolos. Observando a necessidade 
de velocidade no processo de compilação, percebemos que a tabela de símbolos 
deve ser uma estrutura de dados rápida e flexível. Analisando um pouco mais 
detalhadamente o problema de identificar os lexemas, destacamos a existência 
de escopo, de funções e objetos e, principalmente, de comandos, como o typedef 
da linguagem C, os quais permitem que o programador crie novas palavras-
chaves, o que produz um nível extra, dinâmico, de complexidade para o 
processo. Resta-nos observar que, uma vez que todos os lexemas tenham sido 
identificados, essa informação será enviada para o próximo módulo, o analisador 
sintático, que será objeto da nossa próxima rota de aprendizagem. 
 
 
 
24 
REFERÊNCIAS 
AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2. ed. 
Boston: Pearson Education Inc., 2007. 
HOLUB, A. I. Compiler design in C. Englewood Cliffs: Prentice Hall Software 
Series, 1990. 
MOGENSEN, T. Æ. Basics of Compiler Design. Copenhagen: Department of 
Computer Science University of Copenhagen, 2010. 
PITTS, A. M. Regular Languages and Finite Automata for Part IA of the 
Computer Science Tripos. Cambridge University Computer Laboratory, 
Cambridge, 2013, p. 58. 
STEPHEN Cole Kleene. In: Wikipédia, a enciclopédia livre. Disponível em: 
<https://pt.wikipedia.org/wiki/Stephen_Kleene> Acesso em: 6 fev. 2018.