Análise léxica

Prévia do material em texto

DESCRIÇÃO
Funcionamento do Analisador Léxico, como fazer a especificação da Linguagem Fonte e ferramentas para a sua construção.
PROPÓSITO
Compreender o funcionamento e as características da Análise Léxica, identificando a estrutura funcional do Analisador e as formas de implementação.
OBJETIVOS
MÓDULO 1
Descrever o Analisador Léxico e as formas de especificação e reconhecimento de tokens
MÓDULO 2
Identificar as características dos Autômatos Finitos e das Expressões Regulares para construção de um Analisador Léxico
MÓDULO 3
Identificar as formas de projetar os Analisadores Léxicos
INTRODUÇÃO
A Compilação abrange duas grandes etapas: A Análise (front-end) e a Síntese (back-end). A etapa de Análise implica em três passos internos: Análise
Léxica, Análise Sintática e Análise Semântica. Já a etapa de Síntese é composta pela Geração de Código Intermediário, Otimização e Geração de
Código de Montagem.
A fase de Análise depende de interpretar o código-fonte que foi escrito em uma determinada linguagem de programação. O Componente do
Compilador que entra em contato direto com o código-fonte é o Analisador Léxico (AL), também conhecido como Scanner. Ele é o responsável por
separar os elementos do programa, denominados tokens, que permitiram o prosseguimento do processo de tradução pelo compilador.
Neste tema, iremos apresentar as características do Analisador Léxico, as técnicas que são empregadas e formas de o implementar seja por
programação, seja utilizando ferramentas que o geram automaticamente.
MÓDULO 1
 Descrever o Analisador Léxico e as formas de especificação e reconhecimento de tokens
ANALISADOR LÉXICO
Conforme vocês devem saber, a etapa de Análise é o momento em que o compilador tenta entender o programa fonte. Esta etapa possui três passos,
como especificado na Figura 1.
 
 Figura 1: Etapa de Análise. 
Fonte: O Autor, 2020.
O primeiro desses passos é a Análise Léxica, também conhecida como scanning e o componente que a processa é o Analisador Léxico (AL), também
chamado scanner.
O Analisador Léxico faz a leitura de um fluxo de caracteres a partir do programa fonte e produz um fluxo de palavras. Para isso, ele faz a agregação
dos caracteres lidos e, a partir de um conjunto de regras, verifica se elas são ou não válidas na linguagem em que foi construído o programa fonte. Se
ela for válida, é lhe atribuída uma classe gramatical.
Cabe ressaltar que, de todos os passos do compilador, o scanner é o único que entra em contato direto com o programa fonte.
 COMENTÁRIO
Como sua funcionalidade é relativamente simples, agrupar caracteres para formar palavras, os analisadores léxicos podem ser implementados
rapidamente. Existem diversas ferramentas automáticas que permitem a sua geração a partir de uma descrição matemática da sintaxe léxica à
linguagem fonte.
TOKENS, LEXEMAS E PADRÕES
A função primordial do Analisador Léxico é receber um fluxo de caracteres e agregá-los em “palavras,” verificando se são válidas no alfabeto da
linguagem do programa fonte. Estas “palavras” são associadas então a uma classe gramatical, que se denomina tokens.
Os tokens são normalmente compostos de duas partes principais:
Tipo
Indica a classe da “palavra”, um inteiro, um identificador, um operador etc.
Valor (opcional)
Utilizado em alguns tipos para armazenar informação adicional.
Além destas duas partes, alguns compiladores acrescentam outras informações aos tokens, como a posição dele no arquivo de entrada (coluna e
linha) para facilitar o tratamento de erros.
Um exemplo de lista de tokens gerados em um scanner pode ser visto na Figura 2 extraída de um scanner gerado em GALS para o cálculo da área de
um paralelogramo.
 
 Figura 2: Tokens gerados em GALS. 
Fonte: O Autor, 2020.
De uma forma geral, existe mais de uma cadeia de entrada que corresponde ao mesmo token.
Na Figura 2, se você observar tanto AREA, quanto BASE e ALTURA foram associadas ao mesmo token denominado VARIAVEL.
Além disso, eles se constituem em LEXEMAS, que nada mais são que palavras que correspondem aos padrões de um token.
 EXEMPLO
Uma especificação de tokens poderia ser a seguinte:
:[\s]+
variavel: [A-Za-z]*
multiplicacao: "*"
igual: "="
fim:";"
Onde:
Uma variável é definida como uma sequência de caracteres maiúsculos ou minúsculos. (linha 2).
Os operadores de igualdade e multiplicação pelos seus símbolos tradicionais (linhas 3 e 4).
O marcador de fim de comando pelo “;” ponto e vírgula (linha 5).
Você deve notar, porém, que existe outra especificação na linha 1, ela corresponde a ignorar os espaços em branco (\s), desta forma o AL irá descartar
estes espaços durante o seu processamento.
Veja no quadro 1 um exemplo de descrição de padrão de tokens.
TOKEN LEXEMA EXEMPLO DESCRIÇÃO INFORMAL DO PADRÃO
Var Var Variável
Const Const Constante
Cont Cont Contador
Se Se Comando Se
Senao Senao Clausula senão do comando Se
OpRela <,>,==,<>,<=,>= Operadores Relacionais ou < ou > ou == ou <> ou <= ou >=
OpArit +,-,/,*, Operadores Aritméticos ou + ou – ou / ou *
Id Área, lado Pelo menos uma letra seguida por outras
Atrib = Atribuição
NumInt 10 21 35 Número Inteiro
ParDir ) Parêntese direito
ParEsq ( Parêntese esquerdo
TermCom ; Terminador de Comando
{ { Início bloco de comando
} } Fim bloco de comando
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Quadro 1– Exemplo de descrição de Tokens. 
Fonte: O Autor, 2020.
Considere agora a seguinte expressão:
Valor = (A + 35) * 5
Com base na descrição do quadro 1, como seriam os lexemas da expressão?
O quadro 2 responde à pergunta:
LEXEMA TIPO VALOR
VALOR ID VALOR
= ATRIB Atribuição
( ParEsq Parêntese Esquerdo
A ID A
+ OpArit Soma
35 NumInt 35
) Parêntese Direito
* OpArit Multiplicação
5 NumInt 5
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Quadro 2 – LEXEMAS da Expressão. 
Fonte: O Autor, 2020.
Conforme já foi dito, os espaços em branco são eliminados, bem como marcadores de retorno de carro, nova linha e nova página. Então, do ponto de
vista do scanner, a sequência de caracteres a ser analisada seria:
Valor=(A+35)*5
Isto gera uma situação que pede cuidado. Observe esta nova expressão:
A3 = 6 + B
Pelo que vimos na descrição do quadro 1, A3 não seria um identificador válido, pois identificadores (id) são formados apenas por letras. Porém, do
ponto de vista do léxico, esse erro não será percebido, somente o será na Análise Sintática, na qual a gramática é avaliada, já que os lexemas aqui
seriam os constantes no quadro 3.
LEXEMA TIPO VALOR
A ID A
3 NumInt 3
= ATRIB Atribuição
6 NumInt 6
+ OpArit Soma
B ID B
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Quadro 3 – LEXEMAS da Expressão. 
Fonte: O Autor, 2020.
Outro detalhe importante é que, apesar de ignorar os brancos, estes devem ser preservados para permitir que uma eventual mensagem de erro tenha
mais legibilidade.
TRATAMENTO E RECUPERAÇÃO DE ERROS
Considere a seguinte expressão:
Es (A == B) 
A = A + 1
O Analisador Léxico não tem como saber se Es é um identificador, já que atende aos padrões dos tokens, ou o comando ‘Se’ escrito invertido, neste
caso ele prossegue normalmente gerando os lexemas ‘Es’ como identificador e deixa para o Analisador Sintático tratar o problema.
Já a seguinte expressão correspondente ao cálculo da área de um quadrado:
AREA = LADO ^2
Ela gera um efetivo erro léxico já que, apesar de normalmente as especificações das linguagens de programação definirem o circunflexo (^) como o
operador de exponenciação, no quadro 1 ele não foi comtemplado.
 ATENÇÃO
Isso gera o seguinte problema: O AL não pode simplesmente interromper a análise e reportar o erro, ele deve anotá-lo de alguma forma e prosseguir.
A estratégia mais simples, que normalmente é adotada, consiste em remover todos os caracteres não reconhecíveis como tokens, até que se encontre
um bem formado.
 EXEMPLO
Considere a sequência de caracteres a seguir:
AABC =@@@@123
Ao fazer sua análise, o AL agiria da seguinte forma:
Identifica inicialmente o lexema AABC como sendo um identificador.
Identifica = como o operador de atribuição.
Ignora os quatro @ seguidos.
Identifica 123 como um inteiro.
Essa solução eventualmente exigiria um tratamento mais cuidadoso pelo Analisador Sintático, mas permitirá que o scanner prossiga em seu trabalho.
Outras formas possíveis de fazer a recuperação de erros são:
Remover um caractere estranho.
Inserir um caractere ausente.
Substituir um caractere incorreto por um correto.
Transpor dois caracteres adjacentes.
Essas estratégias tentam consertar a entrada tornando-a um lexema válido através de uma única transformação. Neste caso, assume-se que a maioria
dos erros léxicos são resultado de um único erro de digitação, o que apesar de ser verdade em grande parte dos casos, nem sempre ocorre.
RECONHECENDO TOKENS
O processo de reconhecimento de tokens começa com o Analisador Léxico lendo caractere a caractere do programa fonte. Considere, por exemplo, o
seguinte trecho escrito em uma linguagem que segue o padrão estabelecido no quadro 1:
AT = B + 10; 
Se (AT== C( AT= D ^ 2;
O processo começa retirando as quebras de linhas, páginas, retorno de carro e espaços em branco, esses últimos desde que não sejam uma string
delimitada por “ ”.
Desta forma, o programa a ser analisado fica assim:
AT=B+10;Se(AT==C(AT=D^2;
Para facilitar a visualização, vamos colocar em uma tabela numerando as posições dos símbolos:
Posição 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1
Símbolo A T = B + 1 0 ; S E ( A T = = C ( A T
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
A seguir, ele recupera o primeiro caractere no caso A, mas não pode parar por aí, pois, apesar de esta letra atender ao padrão de um identificador,
pode ser seguida de outras de forma que o scanner deve ler até que encontre um símbolo que não corresponda mais ao padrão de identificador.
No nosso exemplo, ele irá ler o T e juntar ao A como identificador, mas ao ler o terceiro símbolo (=), como ele não pode pertencer a um identificador,
ele considera reconhecido o primeiro token, ficando, então, da seguinte forma o processamento da tabela de símbolos:
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
A seguir, ele verifica que o terceiro símbolo (=) também corresponde a um padrão que é a atribuição, mas ele pega o próximo para ver se não seria o
operador de igualdade (==). Como não é outro = ele reconhece o segundo token.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
A seguir, serão reconhecidos o B e o operador de soma, seguindo sempre o mesmo método.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Chegamos, então, ao símbolo 1, ele corresponde ao padrão de um inteiro, mas o AL tem que verificar se não é um inteiro com vários dígitos. Desta
forma, ele continua a leitura até encontrar um símbolo que não seja um dígito e gera um novo token.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
O próximo token facilmente reconhecido é o terminador de comando (;).
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
O próximo símbolo é o “S” que irá corresponder a um token de identificador, porém, o processador, o símbolo seguinte ao AL notará que forma a
palavra reservada SE, que corresponde a um comando e lança este token na tabela.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
SE SE Comando Se 9
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Os próximos dois tokens a serem reconhecidos serão a abertura de parênteses e o id AT.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
SE SE Comando Se 9
( ParEsq Parêntese esquerdo 11
AT ID AT 12
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
No processamento do próximo símbolo, novamente veremos uma interpretação inicial do token ser modificada, pois ao ler o caractere =, ele casa com
o padrão do comando de atribuição, mas ao prosseguir lendo o próximo, é encontrado um novo =, o que significa que o token real é o operador de
comparação de igualdade quando ele gera um novo token.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
SE SE Comando Se 9
( ParEsq Parêntese esquerdo 11
AT ID AT 12
== OpRela igualdade 14
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
A seguir, como você deve deduzir, ao continuar analisando o extrato do programa, são reconhecidos os tokens C (identificador) e ( (ParEsq).
Aqui, você pode estar se perguntando, mas abrir um novo parêntese não seria um erro a ser reportado?
No caso do scanner não é um erro, pois este símbolo corresponde ao padrão de um token.
 COMENTÁRIO
Caberá ao Analisador Sintático, no passo de compilação seguinte, verificar que, no caso do comando SE, ali deveria ter sido fechado o parêntese e
não aberto um novo.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
SE SE Comando Se 9
( ParEsq Parêntese esquerdo 11
AT ID AT 12
== OpRela igualdade 14
C ID C 16
( ParEsq Parêntese esquerdo 17
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Os próximos reconhecimentos, que ocorrerão sem problemas, serão dos tokens AT, = e D.
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
SE SE Comando Se 9
( ParEsq Parêntese esquerdo 11
AT ID AT 12
== OpRela igualdade 14
C ID C 16
( ParEsq Parêntese esquerdo 17
AT ID AT 18
= ATRIB Atribuição 20
D ID D 21
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Ao continuar a interpretação, ao ler o símbolo ^ teremos um problema: o AL não o consegue associar a nenhum token, portanto a alternativa mais
comum é ignorá-lo, fazer a anotação de um erro e continuar até o final do programa, gerando dois novos tokens correspondendo ao 2 e ao “;”
LEXEMA TIPO VALOR POSIÇÃO
AT ID AT 1
= ATRIB Atribuição 3
B ID B 4
+ OpArit soma 5
10 NumInt 10 6
; TermCom Terminador de comando 8
SE SE Comando Se 9
( ParEsq Parêntese esquerdo 11
AT ID AT 12
== OpRela igualdade 14
C ID C 16
( ParEsq Parêntese esquerdo 17
AT ID AT 18
= ATRIB Atribuição 20
D ID D 21
2 NumInt 2 23
; TermCom Terminador de comando 24
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Teríamos ainda uma anotação de erro correspondente à posição 22, o “^”, de símbolo não reconhecido.
Veja mais sobre reconhecimento de tokens no vídeo a seguir:
VERIFICANDO O APRENDIZADO
1. CONSIDERE A DESCRIÇÃO DE UMA LINGUAGEM ESPECIFICADA NO QUADRO1. ELA ESPECIFICA OS PADRÕES
DOS TOKENS QUE SERVEM PARA IDENTIFICAR OS LEXEMAS. 
 
SE FOSSE SUBMETIDO AO SCANNER O PROGRAMA ABAIXO, QUANTOS LEXEMAS E TIPOS DE TOKENS
DIFERENTES SERIAM ENCONTRADOS? 
 
 
AT = B + 20; 
CD = A – 3;
A) 15 lexemas e 15 tipos de tokens
B) 12 lexemas e 12 tipos de tokens
C) 12 lexemas e 5 tipos de tokens
D) 5 lexemas e 12 tipos de tokens
2. CONSIDERE A DESCRIÇÃO DE UMA LINGUAGEM ESPECIFICADA NO QUADRO1. ELA ESPECIFICA OS PADRÕES
DOS TOKENS QUE SERVEM PARA IDENTIFICAR OS LEXEMAS. SE FOSSE SUBMETIDOAO SCANNER O
PROGRAMA ABAIXO, EM QUE POSIÇÃO OCORRERIA UM ERRO LÉXICO? 
 
ES )B == C ) A != B + C;
A) 1
B) 3
C) 9
D) 14
GABARITO
1. Considere a descrição de uma linguagem especificada no quadro1. Ela especifica os padrões dos tokens que servem para identificar os
lexemas. 
 
Se fosse submetido ao scanner o programa abaixo, quantos lexemas e tipos de tokens diferentes seriam encontrados? 
 
 
AT = B + 20; 
CD = A – 3;
A alternativa "C " está correta.
 
Os programas possuem um total de 15 caracteres, sendo que alguns deles se juntam em um único lexema.
Os Lexemas são AT,=,B,+,20,;,CD, =, A, -, 3, ; totalizando 12.
Estes lexemas correspondem aos seguintes tipos de token:
ID : AT, B, CD e A
TermCom : ; e ;
OpArit : - e +
Atrib : = e =
NumInt: 20 e 3
Portanto, temos 5 tipos de tokens no programa.
2. Considere a descrição de uma linguagem especificada no quadro1. Ela especifica os padrões dos tokens que servem para identificar os
lexemas. Se fosse submetido ao scanner o programa abaixo, em que posição ocorreria um erro léxico? 
 
ES )B == C ) A != B + C;
A alternativa "C " está correta.
 
Inicialmente, o programa será compactado, eliminando os brancos. Desta forma, ele ficaria assim:
ES)B==C)A!=B+C;
Para melhor visualização, vamos colocar em uma tabela:
Posição 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Símbolo E S ) = = C ) A ! = B + C ;
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Na posição 1, percebemos que ocorreu a inversão do comando SE, mas o AL não consegue lidar com esse erro que será tratado no Analisador
Sintático.
Na posição 3, temos a inversão dos parênteses, mas da mesma forma o AL não consegue lidar com esse erro que também será tratado no Analisador
Sintático.
Na posição 9 temos o ! que não é um símbolo válido na linguagem gerando, portanto, um erro léxico.
A posição 16 é onde está o erro no programa original, mas ele foi compactado com a eliminação dos brancos.
MÓDULO 2
 Identificar as características dos Autômatos Finitos e das Expressões Regulares para construção de um Analisador Léxico
ANALISADOR LÉXICO COMO UM AUTÔMATO FINITO
Agora que vimos o funcionamento básico de um scanner, vamos estudar seu funcionamento em mais detalhes. Considere o seguinte algoritmo que
nos permitiria identificar a palavra reservada VAR, conforme a descrição da linguagem do quadro 1 do módulo 1.
L ← proximocaracter(); 
Se (L == ‘v’) 
{ 
L ← proximocaracter(); 
Se (L == ‘a’) 
{ 
L ← proximocaracter(); 
Se (L == ‘r’) 
Retornatoken(‘var’) 
Senao tenteoutrotoken(); 
} 
Senão tenteoutrotoken(0; 
} 
Senão tenteoutrotoken();
 ATENÇÃO
Observações retornatoken(), proximocaracter() e tenteoutrotoken() correspondem a subprogramas implementados para respectivamente retornar um
token, pegar o próximo caractere no programa fonte e reiniciar a análise para outro token.
Este algoritmo poderia ser perfeitamente implementado a partir de um Autômato Finito correspondente aos seguintes estados:
 
 Figura 3: Autômato Finito para identificar “VAR”. 
Fonte: O Autor, 2020.
Por sinal, a utilização de Autômatos Finitos é uma das formas mais utilizadas de implementar o Analisador Léxico.
AUTÔMATOS FINITOS
Um Autômato Finito, também chamado de máquina de estados finitos, diz respeito a formas eficientes de implementar determinados algoritmos
quando temos limitação de recursos no hardware da máquina.
Nos Autômatos Finitos os estados são geralmente representados por círculos e as transições de estados representadas por setas conforme pode ser
visto na Figura 3, sendo que o estado final é representado por uma borda dupla no círculo.
Quando o autômato recebe um símbolo de entrada, no nosso exemplo um caractere, ele faz uma transição, também chamada salto, para outro estado
de acordo com as regras estabelecidas em sua função de transição.
 ATENÇÃO
A função de transição é a função que define o funcionamento do autômato, ou seja, é o mapeamento de todas as ligações de cada estado, com
determinado símbolo de entrada, resultando em um próximo estado.
Formalmente, um Autômato Finito é representado por uma quíntupla (Q,Ʃ,δ,q0,F):
Q – É o conjunto finito de estados.
Ʃ – É o conjunto finito de símbolos de entrada.
δ – É a função de transição.
q0 – É o estado inicial (q0 ∈ Q - o estado inicial é apontado por uma seta).
F – O conjunto de estados finais ou de aceitação (um estado inicial também pode ser final).
 EXEMPLO
Por exemplo, o nosso autômato de reconhecimento do token VAR poderia ser definido da seguinte forma:
Q = Número de estados = {S0, S1, S2, S3}
Ʃ = Símbolos de entrada = {V, A, R}
δ = Transições =
δ (S0, V) = S1
δ (S1, A) = S2
δ (S2, R) = S3
q0 = Estado inicial = {S0}
F = Conjunto de estados finais = {S3}
Tudo bem que o autômato apresentado é muito simples e você deve estar se perguntando:
O que aconteceria se, por exemplo, depois do V viesse um caractere não aceito?
Nos autômatos, normalmente, não representamos os estados de erro. Mas em um scanner, obviamente, teríamos que desviar para uma rotina de
tratamento de erro.
Enriquecendo um pouco mais a nossa discussão, imagine agora que se deseja definir um autômato para reconhecer VAR, SE, CONST e CONT. Como
ele seria?
Vamos começar criando o grafo que o representa:
 
 Figura 4: Autômato Finito para identificar TOKENS. 
Fonte: O Autor, 2020.
A quíntupla deste autômato seria então:
 EXEMPLO
Q = Número de estados = {S0, S1, S2, S3, S4, S5, S6, S7, S8, S8, S10, S11}
Ʃ = Símbolos de entrada = {V, A, R, S, E, C, O, N, T}
δ = Transições =
δ (S0, V) = S1
δ (S0, S) = S4
δ (S0, C) = S6
δ (S1, A) = S2
δ (S2, R) = S3
δ (S4, E) = S5
δ (S6, O) = S7
δ (S7, N) = S8
δ (S8, S) = S9
δ (S8, T) = S11
δ (S9, T) = S10
q0 = Estado inicial = {S0}
F = Conjunto de estados finais = {S3, S10, S11}
AUTÔMATO FINITO DETERMINÍSTICO (AFD)
Um Autômato Finito Determinístico é um autômato no qual para cada estado e para cada entrada só há zero ou uma transição possível.
Propriedades de um Autômato Finito Determinístico (AFD):
As transições estão completas.
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 transição possível.
É definida pela propriedade do determinismo.
A sua definição formal também corresponde à quíntupla (Q,Ʃ,δ,q0,F), sendo que o autômato pode ser representado como um diagrama, conforme a
figura 3; ou na forma tabular onde:
As linhas correspondem aos estados.
As colunas correspondem às entradas.
O estado inicial é marcado com uma seta.
Os estados de aceitação são marcados com asterisco.
Vejamos a representação do autômato na forma tabular logo abaixo:
V A R S E C O N S T
→S0 S1 - - S4 -- S6 - - - -
S1 - S2 - - - - - - - -
S2 - - S3 - - - - - - -
*S3 - - - - - - - - - -
S4 - - - S5 - - - - - -
*S5 - - - - - - - - - -
S6 - - - - - - S7 - - -
S7 - - - - - - - S8 - -
S8 - - - - - - - - S9 S11
S9 - - - - - - - - - S10
*S10 - - - - - - - - - -
*S11 - - - - - - - - - -
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
ACEITAÇÃO DE LINGUAGEM
O AFD aceita como entrada uma cadeia de caracteres chamada de w, porém, a aceitação somente ocorre se existe uma sequência de transições
correspondentes aos símbolos do alfabeto de entrada (w) que conduza de um estado inicial a um estado final.
No processo de leitura, estando em um estado qualquer, o controle do Autômato Finito lê a entrada e verifica:
Se não existir uma transição para esse estado e essa entrada no AFD, a sequência de caracteres não é aceita.
Se ele passa para outro estado qualquer e busca o próximo caractere.
A sequência será aceita se:
For atingido o final da lista de símbolos, mostrando que w todo foi lido.
O autômato estiver em um estado final.
O passo a passo resumido será então:
O autômato recebe uma cadeia de entrada.
Processa a cadeia e produz uma saída: Aceita ou rejeita.
Começa no estado inicial.
Lê símbolos da esquerda para a direita.
Após ler um símbolo, move-se de um estado para outro, de acordo com a função detransição.
Quando lê o último símbolo, produz a saída.
Se o autômato estiver em estado de aceitação, a saída será aceita.
Caso contrário, será rejeitada.
Vejam que este funcionamento se adequa perfeitamente a um Analisador Léxico. Vamos traduzir como seriam os passos para este último caso:
Recebe um programa fonte.
Elimina os brancos e os comentários e processa a cadeia gerada da esquerda para a direita, produzindo um token de saída se a cadeia
corresponder a alguma especificação ou a rejeita, gerando um erro.
Começa no Estado Inicial, passando o primeiro símbolo.
Lê os próximos símbolos e move-se pelos estados a partir das regras de transição.
Quando atinge um estado terminal aceitável gera um token, senão gera um erro.
Após a recuperação do erro, retoma a varredura da cadeia de entrada buscando um novo token.
EXPRESSÕES REGULARES (REGEX)
Os Autômatos Finitos, e de forma similar os Analisadores Léxicos, fazem suas transições, no caso dos autômatos, e o reconhecimento de tokens no
caso dos scanners, a partir de regras estabelecidas. Tanto um quanto os outros podem ter suas regras definidas a partir de expressões regulares.
Uma Expressão Regular provê uma forma flexível e concisa de definir cadeias de caracteres de interesse, por exemplo, os tokens de uma linguagem
de programação.
Elas possuem um formalismo que permite a sua interpretação por um processador de Regex, que, portanto, pode ser utilizado como um Analisador
Léxico.
 VOCÊ SABIA
O termo Expressão Regular deriva do trabalho de Stephen Cole Kleene que as desenvolveu como uma notação da álgebra de conjuntos regulares,
tendo seu trabalho servido de base para os primeiros algoritmos computacionais de busca e de processamento de texto na plataforma Unix.
STEPHEN COLE KLEENE (1909-1994)
Foi um matemático norte-americano reconhecido como um dos fundadores da ramificação da lógica matemática conhecida por Teoria da
Computabilidade.
Vejamos como podemos escrever Regex. Inicialmente, seria interessante vocês acessarem o site da Regex. Ele faz a validação de Expressões
Regulares e em todos os nossos exemplos vamos utilizá-lo para validação.
Imagine que você deseja encontrar o nome Carvalho nos dados abaixo:
CARLOS DA SILVA; RUA ROSAS, 25; 11111-111; (99)9999-9999
MÁRCIO CARVALHO; RUA HORTÊNCIAS, 40; 12123111; (88)8888-8888
Você poderia simplesmente definir a Regex como Carvalho, como exemplificado na Figura 5.
javascript:void(0)
 
 Figura 5: Expressões Regulares. 
Fonte: O Autor, 2020.
Note que o valor que corresponde a Regex aparece em azul.
Vamos complicar um pouco. Imagine agora que você deseja identificar o CEP. Uma expressão possível seria:
\d\d\d\d\d-\d\d\d
Esta expressão define que devemos encontrar 5 dígitos, o \d indicando um dígito, a seguir um hífen e, finalmente, mais 3 dígitos (ver Figura 6).
 
 Figura 6: Expressões Regulares. 
Fonte: O Autor, 2020.
Note que o primeiro CEP foi localizado, mas o segundo não. Isso se deve a termos colocado o “-“ na expressão e o segundo não possuir esse
caractere. Agora, vamos mudar a Regex para:
\d\d\d\d\d-?\d\d\d
Note que temos um “?” após o hífen dizendo que ele é opcional. Agora, os dois retornam como você pode notar na Figura 7.
 
 Figura 7: Expressões Regulares. 
Fonte: O Autor, 2020.
 ATENÇÃO
Você pode estar se perguntando: Tudo bem, funcionou, mas porque “\d” é dígito e o “?” é opcional? Bem, estes são os meta-caracteres que dão um
extremo poder às Regex.
META-CARACTERES
Vejamos agora os principais Meta-caracteres.
O CIRCUNFLEXO “^”
Ele simboliza o início de uma linha, por exemplo, a expressão ^Car retorna todo início de linha que tem Car. Note na Figura 8 que Car de Carvalho não
foi reconhecido porque não está no início da linha.
 
 Figura 8: Expressões Regulares. 
Fonte: O Autor, 2020.
Já se movermos Carvalho para o início de linha ele será reconhecido (Figura 9):
 
 Figura 9: Expressões Regulares. 
Fonte: O Autor, 2020.
O CIFRÃO $
Ele simboliza o fim de uma linha. Por Exemplo, 88$ retorna a linhas terminadas por 88 (Figura 10):
 
 Figura 10: Expressões Regulares. 
Fonte: O Autor, 2020.
A LISTA “[]”
O uso de colchetes nos permite definir um conjunto de valores que desejamos que retornem. Por exemplo, para encontrar as letras C e R, podemos
utilizar a expressão [CR] (Figura 11):
 
 Figura 11: Expressões Regulares. 
Fonte: O Autor, 2020.
Note que retornaram apenas os C e R maiúsculos. Regex são case sensitive. Para retornar os dois, mude a expressão para [CRcr] (Figura 12):
 
 Figura 12: Expressões Regulares. 
Fonte: O Autor, 2020.
Para definir um intervalo, coloque um hífen entre os símbolos. Por exemplo, para recuperar todas as letras minúsculas, a expressão seria [a-z] (Figura
13):
 
 Figura 13: Expressões Regulares. 
Fonte: O Autor,2020.
LISTA NEGADA [^...]
O uso do circunflexo no início da lista significa que os componentes da lista devem ser ignorados na busca. Por exemplo, a lista negada [^a-zA-Z]
indica que queremos ignorar todas as letras conforme se pode ver na Figura 13.
 
 Figura 14: Expressões Regulares. 
Fonte: O Autor, 2020.
O PONTO “.”
Muitas vezes, precisamos de um curinga para permitir qualquer caractere em uma posição. Por exemplo, para pegarmos as palavras que possuem r
na terceira posição, poderíamos utilizar a expressão “..r” (ver Figura 15):
 
 Figura 15: Expressões Regulares. 
Fonte: O Autor, 2020.
Note que retornaram duas vezes Car e uma vez Hor.
O ponto na realidade significa qualquer coisa, inclusive números, símbolos, tab etc.
Veja a figura 15 com “..1”. Foi identificado 5;1, 111, 1-1, 0;1 e 231. Desta forma, podemos resumir assim:
O ponto casa com qualquer coisa.
O ponto casa com o ponto.
O ponto é um curinga para casar um caractere.
 
 Figura 16: Expressões Regulares. 
Fonte: O Autor, 2020.
AS CHAVES {}
Um número entre chaves "{}", indica uma quantidade de repetições do caractere (ou meta-caractere) anterior. Por exemplo, a expressão: “.{5}”
reconhece os caracteres de 5 em 5 (Figura 17):
 
 Figura 17: Expressões Regulares. 
Fonte: O Autor, 2020.
CLASSES DE CARACTERES
Podemos definir a classe de caracteres que desejamos buscar em nossas Regex. Uma forma seria a seguinte:
[a-z] - Todas as letras minúsculas.
[A-Z] - Todas as letras maiúsculas.
[A-z] - Todas as letras maiúsculas e minúsculas.
[A-Za-z0-9] - Todas as letras e dígitos.
[0-9] – Todos os dígitos.
Porém, existem atalhos que nos permitem definir estas classes de uma forma mais simples. Eles são:
Atalho Classe
\d [0-9]
\D [^0-9]
\w [A-Za-z0-9]
\W [^A-Za-z0-9]
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Veja o exemplo da Figura 18 que reconhece todos os dígitos.
 
 Figura 18: Expressões Regulares. 
Fonte: O Autor, 2020.
Note agora a Figura 19. O W maiúsculo, da mesma forma que o D maiúsculo nega a classe retornando quem não pertence à classe.
 
 Figura 19: Expressões Regulares. 
Fonte: O Autor, 2020.
QUANTIFICADORES
Quantificadores são uma classe de Meta-caracteres que permite informar se a presença do caractere é obrigatória e se pode ou não existir mais de
um.
Os mais importantes são:
? - Pode aparecer uma vez ou não aparecer.
+ - Aparece no mínimo 1 vez, mas pode aparecer várias vezes.
* - Pode não aparecer ou aparecer várias vezes.
Vejamos um exemplo: A expressão [A-Z]* casa com os caracteres que tenham letras maiúsculas, mas também podem não ter estas letras (Figura 20).
 
 Figura 20: Expressões Regulares. 
Fonte: O Autor, 2020.
Note que foram encontradas 109 correspondências devido a letras e caracteres que não atendem, porém, se mudarmos para + ficando [A-Z]+, só
retornam 7 letras maiúsculas (Figura 20).
 
 Figura 21: Expressões Regulares. Fonte: O Autor, 2020.
BARRA VERTICAL – OPÇÃO
Quando usamos uma barra vertical “|” indica opção, ou seja, pode ser um ou outro. Por exemplo, a expressão a | r retorna os a ou r minúsculos.
 
 Figura 21: Expressões Regulares. 
Fonte: O Autor, 2020.
OUTROS META-CARACTERESFinalmente, vejamos alguns outros Meta-caracteres que são muito importantes:
\s Espaço em branco
\r Retorno de carro
\n Nova linha
\t Marcada de tabulação
/ Caractere de escape
 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Veja mais sobre autômatos e expressões regulares no vídeo a seguir:
VERIFICANDO O APRENDIZADO
1. AUTÔMATOS FINITOS PODEM SER REPRESENTADOS DE FORMA GRÁFICA OU TABULAR. CONSIDERANDO O
AUTÔMATO DEFINIDO PELA SEGUINTE ESTRUTURA TABULAR: 
 
V A R S E C O N S T
→S0 S1 - - S4 -- S6 - - - -
S1 - S2 - - - - - - - -
S2 - - S3 - - - - - - -
*S3 - - - - - - - - - -
S4 - - - S5 - - - - - -
*S5 - - - - - - - - - -
S6 - - - - - - S7 - - -
S7 - - - - - - - S8 - -
S8 - - - - - - - - S9 S11
S9 - - - - - - - - - S10
*S10 - - - - - - - - - -
*S11 - - - - - - - - - -
� ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM HORIZONTAL
QUAL SERIA O ESTADO FINAL DO AUTÔMATO SE ENTRASSEM OS CARACTERES NA SEGUINTE ORDEM: C O N T?
A) S3e
B) S5
C) S10 Análise Semântica
D) S11
2. EXPRESSÕES REGULARES SÃO UMA FORMA FLEXÍVEL DE ESTABELECER PADRÕES PARA O
RECONHECIMENTO DE CADEIAS DE CARACTERES. ELAS POSSUEM UM FORTE FORMALISMO QUE NOS PERMITE
DEFINIR COM PRECISÃO AS REGRAS DE PESQUISA NO TEXTO. A EXPRESSÃO QUE DETERMINA QUE DEVEMOS
ENCONTRAR LETRAS MAIÚSCULAS OU DÍGITOS É:
A) [A-Za-z]|[0-9]
B) [A-Z]|[0-9]
C) \w
D) \W
GABARITO
1. Autômatos Finitos podem ser representados de forma gráfica ou tabular. Considerando o autômato definido pela seguinte estrutura
tabular: 
 
V A R S E C O N S T
→S0 S1 - - S4 -- S6 - - - -
S1 - S2 - - - - - - - -
S2 - - S3 - - - - - - -
*S3 - - - - - - - - - -
S4 - - - S5 - - - - - -
*S5 - - - - - - - - - -
S6 - - - - - - S7 - - -
S7 - - - - - - - S8 - -
S8 - - - - - - - - S9 S11
S9 - - - - - - - - - S10
*S10 - - - - - - - - - -
*S11 - - - - - - - - - -
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Qual seria o estado final do autômato se entrassem os caracteres na seguinte ordem: C O N T?
A alternativa "D " está correta.
 
Como o estado de Entrada é S1, ao receber a letra C, ela fará a transição para S6.
S6 ao receber a letra O fará a transição para S7.
S7 ao receber N fará a transição para S8.
S8 ao receber T fará a transição para S11, que é um estado de aceitação.
2. Expressões Regulares são uma forma flexível de estabelecer padrões para o reconhecimento de cadeias de caracteres. Elas possuem um
forte formalismo que nos permite definir com precisão as regras de pesquisa no texto. A expressão que determina que devemos encontrar
letras maiúsculas ou dígitos é:
A alternativa "B " está correta.
 
[A-Za-z]|[0-9] A expressão pega todas as letras maiúsculas e minúsculas e os dígitos, e foram solicitadas
[A-Z]|[0-9]- Pega as maiúsculas e os dígitos e atende ao solicitado.
\w equivale a [A-Za-z]|[0-9] e pega também as minúsculas.
\W ignora todas as letras e dígitos.
MÓDULO 3
 Identificar as formas de projetar os Analisadores Léxicos
Existem duas formas básicas para a construção de um Analisador Léxico:
Realizar sua programação.
Utilizar um gerador de Analisador Léxico.
CONSTRUINDO O SCANNER
Como você deve lembrar, a principal função do AL é ler os caracteres de entrada e produzir uma lista de tokens.
Cada token representa um símbolo válido na linguagem fonte e são representados internamente por uma estrutura que terá, normalmente, dois
campos:
LEXEMA
Sequência de caracteres que formam o token.
SÍMBOLO
Representação interna para o token.
 ATENÇÃO
Vários scanners acrescentam um terceiro campo correspondente à posição do lexema na cadeia de entrada.
O scanner cria, então, uma estrutura de dados correspondendo ao encadeamento dos diversos tokens, conforme se pode ver na Figura 22:
 
 Figura 22: Encadeamento dos tokens. 
Fonte: O Autor, 2020.
O reconhecimento dos tokens será realizado a partir da especificação da linguagem. Conforme vimos, esta especificação pode ser realizada a partir de
expressões regulares.
 COMENTÁRIO
Apesar de muito eficiente para o processamento automático, este tipo de especificação pode ser de difícil entendimento por um ser humano no
momento de realizar a programação. Uma representação mais legível seria a partir de Diagramas de Sintaxe.
DIAGRAMAS DE SINTAXE
Estes diagramas são representações gráficas das Expressões Regulares e permitem um entendimento simplificado do padrão.
Considere a seguinte Regex correspondente a um identificador:
<letra>{ [ <letra> | <dígito> ] }
Considere que letra corresponde a [A-Za-z] e dígito a [0-9].
Em BNF, definiríamos o token identificador como:
BNF
javascript:void(0)
javascript:void(0)
javascript:void(0)
A notação inicialmente criada por John Backus e Noam Chomsky, foi modificada posteriormente por Peter Naur dando origem à forma de
Backus-Naur ou BNF. BNF é uma metalinguagem para descrever as LP.
<identificador>::= <letra>{ [ <letra> | <dígito> ] }
Que especifica que um identificador é composto por uma letra seguida de letras ou dígitos.
O Diagrama de Sintaxe correspondente é o apresentado na Figura 23.
 
 Figura 23: Diagrama de Sintaxe do Identificador.
Fonte: O Autor, 2020.
Vejamos agora sua construção passo a passo:
Passo 1 – Inicialmente, representamos o fato de um identificador iniciar com uma letra.
 
Passo 2 - Representar que pode receber uma letra ou um dígito ou nenhum símbolo.
 
Passo 3 - Vamos representar agora que existe um loop na entrada das letras e dígitos e, se não digitar nada, vai para o final.
 
Passo 4 – Finalmente, juntamos o diagrama do primeiro passo com o do passo 3 e o identificamos.
 
ALGORITMOS BÁSICOS
Vista uma forma mais legível de representação da especificação da linguagem, vamos passar a discutir o algoritmo básico.
 ATENÇÃO
A primeira coisa que temos que fazer é receber o código-fonte, abri-lo e eliminar os comentários e espaços indesejados, como brancos, retorno de
carro, nova linha etc. e, a seguir, processar a cadeia resultante.
Um exemplo de lógica seria:
Algoritmo Scanner 
Inicio 
Abre fonte 
Prepara Arquivo() 
Fecha arquivo fonte 
Enquanto não acabou a cadeia 
Faça { 
PegaToken() 
ArmazenaToken() 
} 
Fim 
Observando o código, devemos atentar que Prepara arquivo() é um subprograma que trata os comentários e consome os espaços indesejáveis.
Poderíamos dizer que é um subprograma que receberia o código-fonte e o devolveria limpo, como uma única cadeia de caracteres.
A partir daí, seria processada a cadeia de caracteres onde seriam chamados os subprogramas PegaToken(), que retorna um token e o retorno seria
colocado na estrutura de tokens pelo ArmazenaToken()
Este loop se repete até o final da cadeia de caracteres.
A lógica do ArmazenaToken() é relativamente simples porque implica apenas no encadeamento em um lista de ponteiros das informações do token.
Entretanto, o PegaToken() é extremamente complexo, pois as linguagens possuem diversos tipos de token, identificadores, literais, palavras
reservadas, operadores aritméticos, de comparação, atribuição, valores etc.
Vejamos um exemplo simplificado de PegaToken() que trata dígitos e caracteres.
Algoritmo PegaToken() 
Inicio 
Se caracter é digito 
Então Trata Digito 
Senão Se caracter é letra 
Então TrataIdentificador 
Fim
Cabe observar que o tratamento de caractere teria que lidar com o fato de ele representar o início de uma palavra reservada, que neste exemplo não
foi tratado.
Apenas como exemplo, vejamos a lógica que poderia ser utilizada por uma sub-rotina de TrataIdentificador a partir do Diagrama de Sintaxe gerado
apresentado na Figura 23.
Algoritmo Trata Identificador
Def id: Palavra 
Inicio 
id <- caracter 
Ler(caracter) 
Enquanto caracter é letra ou dígito 
Faça {id <- id + caracter 
Ler(caracter) 
} 
token.lexema <- id 
token.símbolo <- identificador 
Fim. 
IMPLEMENTANDO COMO AUTÔMATO FINITO
Outra forma de implementação do scanner seria construí-lo como um Autômato Finito Determinístico que funcionariaa partir da especificação em
Linguagem Regular.
A nossa ideia é automatizar a derivação de AL a partir de um conjunto de Expressões Regulares (RE). Para tal, seguiremos um ciclo de construção
conforme mostrado na Figura 24:
 
 Figura 24: Ciclo de construção de um AFD para gerar scanner. 
Fonte: Cooper & Torczon, 2014.
Vejamos agora passo a passo o método.
Considere as seguintes Regex:
C* E CD
Os Autômatos Finitos correspondentes a elas seriam:
 
Supondo que a duas expressões pertencem à mesma especificação, iríamos juntá-los em um Autômato só correspondente à expressão c*cd.
 
Note o símbolo em vermelho Ɛ. Ele representa uma transição vazia (Ɛtransição), ou seja, ele faz uma transição para o próximo estado sem avançar no
processamento da cadeia de caracteres de entrada.
Com esta Ɛtransição, temos duas formas de transição em S0 em relação à letra C:
S0 → S0 se a próxima letra for c.
S0→S1 S1→S2 e S2 → S3 se a próxima letra for d.
O que gera uma certa complexidade na construção do autômato e o caracteriza como um Autômato Finito Não Determinístico (AFND).
O AFD sempre tem que possuir a mesma função de transição. Efetivamente, um AFD é um caso particular de AFND e eles não aceitam Ɛtransição.
Para tornarmos o nosso autômato AFND em um AFD, temos que eliminar a transição vazia. Uma possível solução seria este autômato:
 
 COMENTÁRIO
A primeira parte da solução quando criamos o Autômato Não Determinístico se chama Algoritmo de Thompson e a segunda parte, quando o
transformamos em um AFD, denominamos construção do subconjunto. Foge ao escopo de nosso tema entrar em maiores detalhes dessas técnicas,
mas se você se interessar, pode pesquisar na internet a respeito.
Uma vez criado o AFD, ele deve ser minimizado, pois em situações reais ele será bem grande e complexo e, a partir deste ponto, pode ser gerado um
código que implemente o AFD e desta forma ser utilizado como Analisador Léxico.
GERADORES DE ANALISADORES LÉXICOS
A outra forma para gerar um Analisador Léxico é empregar um programa com essa finalidade. Existem vários geradores de Analisadores Léxicos, por
exemplo, o LEX e o Gals. Eles funcionam recebendo como entrada as Expressões Regulares que especificam a linguagem e, a partir destas, geram o
scanner que fará a análise do programa fonte e irá gerar os tokens (Figura 25).
 
 Figura 25: Funcionamento de Geradores de Analisadores Léxicos. 
Fonte: O Autor, 2020.
EXTLEX
O EXTLex adota uma abordagem diferente, ele não gera um AL. Ele é um scanner configurável que pode ser utilizado com qualquer linguagem de
programação.
Na realidade, a partir da definição de um Autômato Finito Determinístico e do conjunto de palavras reservadas, ele faz a Análise Léxica da fonte
(Figura 26).
 
 Figura 26: Funcionamento do EXTLex. 
Fonte: O Autor, 2020.
Constituído de um programa Java que não precisa ser instalado, sua configuração é realizada a partir de dois arquivos de texto chamados automata e
reserved que correspondem, respectivamente, à especificação do AFD e ao conjunto de palavras reservadas da linguagem a ser analisada.
 SAIBA MAIS
Você pode baixá-lo diretamente da internet na página Gustavo Henrique Paetzold ou então aqui na disciplina, a partir deste arquivo.
No arquivo, você possui os seguintes elementos que aparecem na Figura 27:
 
 Figura 27: Componentes do Pacote EXTLex. 
Fonte: O Autor, 2020.
javascript:void(0);
Nele se destacam o leia-me e, particularmente, o arquivo Creating a Language for EXTLex, que explica como criar os arquivos de configuração
automata e reserved.
Na pasta EXTLEX, temos uma pasta com arquivos de configuração e de código de exemplo, os códigos-fontes do aplicativo e o arquivo .jar (Figura
28):
 
 Figura 28: Conteúdo da Pasta EXTLex. 
Fonte: O Autor, 2020.
Para executar o programa, você deve:
 
Colocar em uma mesma pasta o arquivo EXTLex.jar, o automata, que faz a configuração do autômato, reserved com as palavras reservadas e code
com o programa fonte a ser analisado.
 
Navegar até o diretório dos arquivos utilizando o prompt de comando e digitar
java -jar extlex.jar
 
Após submeter o comando, a análise é realizada e o relatório gerado.
 
Além dos lexemas, são gerados os erros encontrados.
 COMENTÁRIO
As capturas acima correspondem aos arquivos que estão na pasta example do pacote do EXTLex. Seria muito interessante você baixar os arquivos,
analisá-los e executar a análise léxica.
Seria muito interessante você baixar os arquivos, analisá-los e executar a análise léxica.
GALS
O GALS é um gerador de Analisadores Léxicos que funciona a partir da especificação da linguagem fonte submetida ao programa e que pode gerar o
AL em Java, C++ ou Delphi.
 SAIBA MAIS
Ele é composto de um arquivo .jar, portanto, não precisa ser instalado. Você pode obtê-lo na internet a partir do site Gals.Sourceforge ou baixando
diretamente aqui
O GALS trabalha internamente a partir de um Autômato Finito que é gerado automaticamente a partir da especificação dos tokens utilizando
expressões regulares.
Para acessar o GALS, basta dar um duplo clique no arquivo gals.jar que ele irá executar e apresentar a interface gráfica (Figura 29). Obviamente, você
precisa ter o Java instalado na sua máquina.
 
 Figura 29: Interface Gráfica do GALS.. 
Fonte: O Autor, 2020.
Clicando em opções, irá abrir a janela de configuração:
 
Na janela aberta, você deve escolher Analisador Léxico, linguagem C++ e clicar em Aplicar:
javascript:void(0);
 
Note que a interface irá mudar em relação à da figura 29, pois ficaram apenas os espaços do Analisador Léxico.
 
 Figura 30: Interface Gráfica do GALS para AL. 
Fonte: O Autor, 2020.
Para a definição do scanner, temos dois espaços:
As Definições Regulares.
Os tokens.
As Definições Regulares são opcionais, podemos fazer tudo no tokens, mais seu uso facilita as especificações posteriores.
Veja mais sobre a utilização do GALS no vídeo a seguir:
VERIFICANDO O APRENDIZADO
1. O SCANNER OU ANALISADOR LÉXICO É O RESPONSÁVEL PELO PRIMEIRO PASSO DA ETAPA DE ANÁLISE DA
COMPILAÇÃO. ELE PODE SER PROJETADO E IMPLEMENTADO DE VÁRIAS FORMAS, POR EXEMPLO, PELA
ESCRITA DO CÓDIGO PELO PROGRAMADOR OU ATRAVÉS DE GERADORES DE ANALISADORES LÉXICOS. A
FORMA MAIS COMUM DOS GERADORES TRABALHAREM É IMPLEMENTANDO UM(A):
A) Autômato Finito Não Determinístico
B) Autômato Finito Determinístico
C) Autômato de Pilha
D) Máquina de Moore
2. GALS É UM GERADOR DE ANALISADORES LÉXICOS A PARTIR DA DEFINIÇÃO DA LINGUAGEM POR
EXPRESSÕES REGULARES. CONSIDERE A ESPECIFICAÇÃO APRESENTADA NA FIGURA ABAIXO:
A SER AVALIADO ESTE CONJUNTO DE EXPRESSÕES, UM ERRO LÉXICO OCORREU. 
 
A := B / D; 
 
C := 5; 
 
POR QUE O ERRO ACONTECEU?
A) Porque existem espaços em branco entre os itens.
B) Porque na segunda linha está sendo realizada uma atribuição sem operação.
C) Porque existem identificadores com letra minúscula.
D) Porque são duas linhas e o retorno de carro e passagem para a próxima linha não estão sendo tratados.
GABARITO
1. O scanner ou Analisador Léxico é o responsável pelo primeiro passo da Etapa de Análise da Compilação. Ele pode ser projetado e
implementado de várias formas, por exemplo, pela escrita do código pelo programador ou através de Geradores de Analisadores Léxicos. A
forma mais comum dos geradores trabalharem é implementando um(a):
A alternativa "B " está correta.
 
Autômatos Finitos se prestam muito bem para a realização de Análise Léxica a partir da definição de regras estabelecidas pelas expressões regulares.
Apesar de Autômatos Não Determinísticos também poderem processar essas expressões, Autômatos Determinísticos evitam vários problemas
associados às Ɛtransições e, portanto, são utilizados na geração de Analisadores Léxicos.
2. GALS é um gerador de Analisadores Léxicos a partir da definição da linguagem por expressões regulares. Considere a especificação
apresentada na figura abaixo:
A ser avaliado este conjunto de expressões, um erro léxico ocorreu. 
 
A := b / D;C := 5; 
 
Por que o erro aconteceu?
A alternativa "D " está correta.
 
Quanto à opção A, ela está errada, pois o espaço está sendo tratado com o [s]+.
Quanto à opção B, ela está errada, já que nada amarra que uma atribuição somente pode ser feita após uma operação.
Quanto à opção C, ela está errada, já que identificadores aceitam que letras sejam maiúsculas ou minúsculas da forma que a especificação foi
realizada.
Quanto à opção D, ela está correta, deveria ser acrescida a especificação da primeira linha \r\t\n.
CONCLUSÃO
CONSIDERAÇÕES FINAIS
Ao longo deste tema, fizemos uma viagem pelos conceitos relacionados à Análise Léxica.
Iniciamos estudando o que é o Analisador Léxico, o que são os tokens e as técnicas para os reconhecer.
Nossa próxima parada foi nos Autômatos Finitos, vimos seu funcionamento e como podem ter suas regras estabelecidas a partir das Expressões
Regulares. Nas Expressões Regulares, vimos como as escrever.
A seguir, tratamos especificamente da construção de Analisadores Léxicos, tanto a partir de programação quanto da utilização de Autômatos Finitos a
partir do EXTLex.
Finalmente, em nossa parada final, estudamos o GALS, um Gerador de Analisadores Léxicos.
AVALIAÇÃO DO TEMA:
REFERÊNCIAS
AHO, A. V. et al. Compiladores: Princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson, 2008.
COOPER, K. D.; TORCZON, L. Construindo compiladores. 2. ed. Rio de Janeiro: Elsevier, 2014.
LOUDEN, K. C. Compiladores: Princípios e práticas. São Paulo: Cengage Learning, 2004.
SANTOS, P. R.; LANGLOIS, T. Compiladores: Da teoria à prática. Rio de Janeiro: LTC, 2018.
SEBESTA, R. W. Conceitos de linguagens de programação. 11. ed. Porto Alegre: Bookman, 2018.
TANENBAUM, A. S. Organização Estruturada de Computadores. 5. ed. São Paulo: Pearson, 2006.
EXPLORE+
Para saber mais sobre os assuntos tratados neste tema, pesquise na internet:
Sobre o projeto GALS, para se familiarizar com este gerador de compiladores.
Leia:
O livro Expressões Regulares, de Aurelio Marinho Jargas.
CONTEUDISTA
Sidney Nicolau Venturi Filho
 CURRÍCULO LATTES
javascript:void(0);