Analisador Léxico e Expressões Regulares

Prévia do material em texto

Editado por Aleardo Manacero Jr.
Capítulo 2 - Analisador Léxico
1. Expressões regulares 
2. Autômatos de estado finito 
3. AEF's e expressões regulares 
4. Implementação do analisador léxico 
O compilador tem no seu analisador léxico o primeiro componente a entrar em contato com o código fonte. Sua função basica é
identificar os tokens presentes no código fonte e passar essa informação para o parser. Isso significa que ele vai ocupar uma grande
parte do tempo de execução do compilador, obrigando-nos a implementá-lo de modo bastante eficiente para que o processo de
compilação possa ocorrer de forma rápida. O procedimento de análise léxica consiste em ler os caracteres de entrada e agrupa-los em
conjuntos que tenham sentido para os demais componentes do compilador. Estes conjuntos são os tokens da linguagem e na realidade
são os identificadores e símbolos especiais de uma linguagem de computação. A seguir trataremos das expressões regulares e dos
autômatos de estado finito, para depois estudarmos como os AEF's podem ser construídos automaticamente a partir de uma gramática
regular e como os analisadores léxicos podem ser representados através de um AEF. 
1. Expressões regulares
Expressão regular é uma forma compacta de denotar todos os possíveis strings que compõe uma determinada linguagem, usando para
isso a chamada notação estrela (*) de Kleene para representar a ocorrência de zero ou mais instâncias de um determinado símbolo ou
conjunto de símbolos terminais. 
O que a notação * de Kleene faz é apenas indicar que uma sequência de um determinado caracter "c" é expressa pelo símbolo "c*",
representando uma sequência de pelo menos zero ocorrências do caracter "c". Assim, um número inteiro pode ser representado por
"dd*", em que "d" representa um dos algarismos entre 0 e 9. Da mesma forma, um identificador em pascal ou modula-2 pode ser
representado por "a(a|d)*", em que "a" representa uma letra entre a e z enquanto "d" é um algarismo entre 0 e 9. 
Uma expressão regular pode ser expressa através de uma gramática livre de contexto da seguinte forma: 
gramática ER = ( {'|', '(', ')', '*', '+', '?', \sigma}, 
 {ExpReg, Termo, Fator, Primario}, 
 ExpReg, 
 P ) 
Na qual P: 
 1. ExpReg -> ExpReg '|' Termo (alternação) 
 2. ExpReg -> Termo 
 3. Termo -> Termo Primario (concatenação) 
 4. Termo -> Primario 
 5. Primario -> Fator '*' (iteração) 
 6. Primario -> Fator 
 7. Fator -> '(' ExpReg ')' (agrupamento) 
 8. Fator -> \sigma 
Observações: 1. '(', ')', '*', '|', '+' e '?' são chamados meta-símbolos. 
 2. O meta-símbolo '+' significa que o Fator associado a ele pode ser repetido uma ou mais vezes. Logo, "a+" = "aa*" 
 3. O meta-símbolo '?' significa que o Fator associado a ele pode ser repetido zero ou uma vez. Logo, "a?" = a |
\lambda 
1.1 Álgebra de expressões regulares
Uma vez definida uma expressão regular, temos que saber como manipula-la de modo a torna-la o mais legível possível, isto é, como
uma expressão regular define todos os strings de uma linguagem, gostaríamos de poder ler através dela quais são os strings admissíveis
para a dada linguagem sem muitos transtornos. 
Isto é possível através de manipulações algébricas feitas a partir de propriedades do tipo associativa, comutativa, distributiva e de
identidade aplicadas às expressões regulares. Por exemplo, fica fácil de perceber que a propriedade comutativa pode ser aplicada sobre
uma alternação pois r|s = s|r e não sobre uma concatenação pois rs != sr. A seguir temos uma lista das propriedades algébricas para
expressões regulares. 
1. r|s = s|r (comutativa para alternação) 
2. r|(s|t) = (r|s)|t (associativa para alternação) 
3. r(st) = (rs)t (associativa para concatenação) 
4. r|r = r (absorção para alternação) 
5. r(s|t) = rs|rt (distributiva a esquerda) 
6. (r|s)t = rt|st (distributiva a direita) 
7. r \lambda = \lambda r = r (identidade para concatenação) 
8. r*r* = r* (absorção de fechamento) 
9. r* = \lambda | r | rr | ... (fechamento de Kleene) 
10.(r*)* = r* 
11.rr* = r*r = r+ 
12.(r*|s*)* = (r*s*)* 
13.(r*s*)* = (r|s)* 
14.(rs)*r = r(sr)* 
15.(r|s)* = (r*s)*r* 
1.2 Transformações entre gramáticas e expressões regulares
Uma linguagem regular pode ser definida ou através de uma gramática regular ou através de uma expressão regular. Ambas as formas
são suficientes, isto é, definindo-se uma delas a linguagem fica automaticamente definida também. As diferenças entre a gramática e a
expressão que definem uma linguagem regular se devem ao formato em que definimos estas duas entidades. 
Enquanto uma gramática usa o conjunto de produções para reescrever o símbolo inicial nos strings da linguagem, a expressão regular
vai descrever os mesmos strings através de uma única sentença na forma descrita em 2.1. Portanto a descrição de uma linguagem
através de uma expressão regular permite uma identificação mais clara dos strings que compõem a dada linguagem, enquanto que a
gramática é mais útil no momento de se formular as regras de formação da linguagem. 
Logo, é interessante que tenhamos alguma estratégia para converter uma gramática numa expressão regular e vice-versa, para que
tenhamos como definir as regras e visualizar a linguagem nas formas adequadas para ambos os casos. 
A) Conversão de expressão regular para gramática: 
Dada a expressão regular \omega: 
1. Cria-se a "produção" S -> \omega 
2. Aplica-se uma das regras a seguir até não existirem produções vazias nem meta-símbolos 
Regra Para as produções Criam-se as produções
R1 A -> xy A -> xB e B -> y
R2 A -> x*y A -> xB | y e B -> xB |
y 
R3 A -> x | y A -> x e A -> y
R4 A -> B e B -> x A -> x e B -> x
R5 A -> \lambda e B -> xA B -> xA e B -> x
R6 S -> \lambda (S é o símbolo
inicial) 
G -> \lambdaG -> S 
Exemplo: 
a(a|d)* ==> S -> a(a|d)* 
 (R1) S -> aA A -> (a|d)* 
A -> (a|d)* <=> A -> (a|d)*\lambda 
(R2) A -> (a|d)B | \lambda 
 B -> (a|d)B | \lambda 
(R3) A -> (a|d)B A -> \lambda 
 A -> aB A -> dB 
(R3) B -> (a|d)B B -> \lambda 
 B -> aB B -> dB 
 
Com isso temos: 
S -> aA 
A -> aB A -> dB A -> \lambda
B -> aB B -> dB B -> \lambda
Eliminando-se as produções vazias e fazendo as simplificações necessárias temos a gramática final dada por: 
S -> aA S -> a
A -> aA A -> dA
A -> a A -> d
B) Conversão de gramática para expressão regular: A conversão neste sentido também é simples, bastando fazer o procedimento
inverso ao anterior usando para tanto as regras dadas a seguir: 
R1 Produções da gramática Expressão
regular 
R1 A -> xB B -> y A -> xy
R2 A -> xA | y A -> x*y
R3 A -> x A -> y A -> x|y
 
Exemplo: 
A partir da gramática G abaixo teremos: 
S-> aA S -> a 
A -> aA A -> a ===> a(a|d)*(a|d)|a ===> a(a|d)* 
A -> dA A -> d 
2. Autômatos de estado finito
Como foi dito no capítulo anterior, um autômato é uma entidade capaz de reconhecer se uma string está ou não corretamente definida
dentro de uma dada gramática. Pela classificação de Chomsky vimos também que uma gramática regular pode ser reconhecida pelo
que chamamos de autômato de estado finito (AEF), o qual é descritopelos cinco objetos discriminados a seguir: 
M = (\SIGMA, Q, \DELTA, q0, F) 
Em que 
\SIGMA é o alfabeto compreendido pelo autômato, 
Q é o conjunto de estados definidos para o autômato, 
\DELTA é o seu conjunto de regras de transição, 
q0 é o seu estado inicial e 
F é o conjunto de estados finais para o autômato. 
Um autômato pode ter suas regras de transição representadas de forma gráfica ou tabular. Na forma gráfica temos também a
representação visual dos estados do AEF, o que facilita o entendimento de como o autômato passa de um estado a outro. Já a forma
tabular se presta bem ao armazenamento das transições num computador, o que vai ser muito interessante durante o projeto de um
analisador léxico. A figura a seguir ilustra a representação gráfica de um AEF, enquanto que a tabela depois da figura representa as
transições do mesmo autômato em sua forma tabular. 
 
Forma gráfica para representação de um AEF.
 a b c
A B B C
B C B -
C A - D
D - - -
Forma tabular para representação das transições num AEF.
Um autômato reconhece ou aceita um string para uma dada linguagem se, ao final do string, parar num estado pertencente ao
conjuntode estados finais F. Caso isso não ocorra diz-se que o autômato rejeita o string. Além disso, diz-se que um autômato aceita
uma linguagem se e somente se todos os strings definidos para aquela linguagem são aceitos pelo autômato, isto é, para qualquer string
pertencente à linguagem o autômato irá parar num de seus estados finais. Partindo da definição da aceitação de uma linguagem
podemos comparar dois autômatos sobre suas condições de equivalência, isomorfismo, etc. Assim, diz-se que dois autômatos são
EQUIVALENTES quando eles aceitam a mesma linguagem. Já quando, além de aceitarem a mesma linguagem, eles também tiverem
os mesmos estados, diz-se que eles são ISOMORFOS. Por outro lado, quando um autômato tem o menor número de estados entre
todos os seus equivalentes dizemos que ele é REDUZIDO. 
Um AEF ainda pode ser classificado segundo o tipo de regras de transição que o mesmo apresenta. Por este critério ele pode ser
determinístico ou não-determinístico. 
Um AEF não-deterministico é aquele em que pode ocorrer a transição vazia, que é aquela em que o AEF pode passar de um estado a
outro sem que ocorra a entrada de um caracter do string. Além disso, num AEF não-determinístico podem ocorrer indeterminações na
ação do AEF, isto é, determinados estados podem ter mais do que uma transição possível para um dado caracter. 
O AEF determinístico é aquele em que transições vazias não ocorrem e também em que não existam indeterminismos no momento de
transitar de um estado a outro após a leitura de um caracter, ou seja, é todo aquele que não for não-determinístico. 
2.2.1 Transformação de uma gramática regular num AEF
Como um AEF é um dispositivo capaz de reconhecer os strings de uma linguagem e uma gramática é um meio formal de definir uma
linguagem, devemos ter mecanismos para a partir de uma gramática especificar o AEF que reconheça tal linguagem. Isto é feito de
forma bastante simples, seguindo-se as regras a seguir: 
 
GRAMÁTICA AEF
alfabeto \SIGMA alfabeto \SIGMA
Para todo símbolo não-terminal em
N 
cria-se um estado q pertencente a Q
cria-se um estado final qf
S q0
Para toda produção A -> xB cria-se uma transição \delta(A,x) = 
B
Para toda produção A -> x cria-se uma transição \delta(A,x) = 
qf
3 AEF's e expressões regulares
Como já vimos, gramáticas e expressões regulares são apenas duas formas distintas de representar uma linguagem. Logo, também
podemos construir um AEF partindo-se de uma expressão regular. Uma forma bastante simples de se fazer isto é através da
representação gráfica de um AEF, em que uma expressão regular ER seria colocada dentro de uma caixa-preta com um estado de
entrada A e outro de saída B, como mostrado a seguir: 
A seguir acrescentaria-se um estado inicial S e outro final F, quando teríamos as transições \delta(S,\lambda) = A e \delta(B,\lambda) =
F. A partir daí seguiríamos com a transformação usando as cinco regras a seguir, até que não existam mais caixas-pretas. 
REGRAS: 
Exercício: 
Encontre o AEF que reconheça a expressão \omega = a(a|d)* 
Como se pode observar, o número de transições vazias no AEF encontrado é bastante elevado, o que nos faz pensar em reduzir o
número destas ocorrências. Entretanto, é bastante perigoso fazer isso sem um critério muito bem definido, pois podemos acabar
alterando a linguagem reconhecida por um AEF se retirarmos expressões vazias que fossem realmente necessárias. O exemplo a seguir
ilustra bem este problema. 
Exemplo (exercício): 
1. Construa o AEF para a expressão \omega = (a*b)* usando as regras dadas anteriormente. 
2. Após isso repita a construção do AEF, porém trocando a regra R3 pela regra F3 dada a seguir. Verifique que neste segundo
caso é possível a aceitação do string "a", que não é aceita por \omega. 
3.1 - Obtenção de um AEF determinístico a partir de um não-determinístico
A redução do número de transições vazias num AEF, bem como a eliminação de transições ambíguas, pode ser feita de forma segura
quando se faz a redução de um AEF não-determinístico para um determinístico. Este processo é realizado em quatro etapas, "remoção
de ciclos vazios", "eliminação de transições vazias", "remoção de não-determinismos" e "redução do autômato", que estão descritas a
seguir. 
1. Remoção de ciclos vazios: 
O primeiro passo na obtenção do AEF determinístico é identificar ciclos nos quais, partindo-se de um dado estado pode-se
chegar ao mesmo passando apenas por transições vazias. Como se percebe, tais ciclos implicam em que os estados
intermediários não necessariamente precisam ser percorridos, desde que se garanta a manutenção das transições não-vazias
ligadas aos estados do ciclo. 
Para eliminarmos estes ciclos sem que haja prejuízo de consistência ao AEF basta que se crie um novo estado que irá assumir o
lugar de todos os estados que fazem parte do ciclo. As transições de entrada do novo estado são as transições de entrada de cada
um dos estados do ciclo, enquanto que as transições de saída são todas as transições de saída dos estados em substituição. Nesse
processo, caso um dos estados do ciclo for final, então o novo estado também será final. 
Efetuar isto de forma gráfica é possível, bastando tomar cuidado para, a cada passo, não deixar de lado nenhuma transição dos
estados que compõe o ciclo. Entretanto, quando estamos fazendo isso de forma automatizada fica difícil conseguir um
algoritmo que trabalhe de forma visual eficientemente. O que se faz é usar a forma tabular de representação das transições do
AEF, passando então a ser necessário um algoritmo de deteção de ciclos vazios na tabela em questão. 
Fica como exercício a especificação dos algoritmos para a eliminação dos ciclos vazios no AEF não-determinístico, o que
significa um algoritmo para a deteção do ciclo e outro para a união dos estados pertencentes ao ciclo. 
 
 
2. Eliminação de transições vazias: 
Após a eliminação dos ciclos vazios ainda teremos transições vazias que não pertenciam a nenhum ciclo. A eliminação de tais
transições pode ser feita de forma semelhante à eliminação dos ciclos vazios, isto é, através da união dos estados envolvidos
numa transição vazia, tanto de forma gráfica quanto de forma algoritmica através da tabela de transições. 
No caso da eliminação de transições vazias, o que se faz é copiar o estado destino da transição vazia sobre o estado origem da
mesma, sem remover o estado destino entretanto. No processo o que se faz é copiar todas as transições que partem do estado
destino para o estado origem, pois são estas as transições que passam a ser possíveis quando partindo do estado origem com a
transição vazia para o estado destino, no qual teríamos as novas transições de partida possíveis. Aqui também, o novo estado
(aquele do qual partia a transição vazia) passará a ser final caso o estado destino seja final. 
Na forma tabular, teríamos algo como nastabelas seguintes, nas quais estamos eliminando a transição vazia \delta(A, \lambda)
= B. 
a b \lambda a b \lambda
S B A S B A 
A B A A,B F G
B A,B F G B A,B F G
F ===> F 
G F H,J G F H,J
H F H F
J A J A 
Observem que o algoritmo pode ser otimizado se forçarmos com que o processo se inicie a partir de um estado destino que não
tenha transições vazias entre as suas transições de partida, pois assim eliminamos a possibilidade de ter que eliminar transições
recursivamente. 
 
3. Remoção de não-determinismos: 
Como se pode ver das tabelas apresentadas no passo 2 ainda teremos indeterminismos em algumas transições, como por
exemplo \delta(A, a) = A ou \delta(A, a) = B. O último passo para a obtenção de um AEF determinístico é a eliminação de tais
transições, o que pode ser feito através da alteração dos estados do autômato. Muito embora isso também possa ser feito de
forma gráfica, apenas realizamos este passo pela forma tabular, uma vez que a complexidade da alteração dos estados é tal que
seria muito fácil cometer pequenos enganos no processo, o que levaria a uma linguagem diferente da original. 
O processo pela forma tabular é o seguinte: 
1. partindo-se do estado inicial, para cada transição com múltiplas opções cria-se um novo estado, cujo nome é a união dos
nomes dos estados destinos da transição. 
2. Cria-se uma nova linha na tabela, com o novo estado, em que as transições são dadas pela união entre as transições de
cada um dos estados agora aglutinados. 
3. Repete-se o processo até que não existam mais estados a serem aglutinados. 
 
4. Redução do autômato: 
Muito embora o autômato obtido no passo 3 já seja determinístico, o mesmo contém muitos estados que poderiam ser
eliminados por um processo de redução no tamanho do autômato. Esta redução se dá pela identificação dos estados
equivalentes em classe, que são os estados para os quais se aceitariam as mesmas strings caso eles fossem os estados iniciais
para as strings. 
Uma vez identificados os estados de uma classe de equivalência, os mesmos são substituidos por apenas uma instância,
alterando-se o seu nome e atualizando a tabela de transições para conter este novo nome. O processo se repete até que não seja
mais possível identificar novas classes de equivalência, o que significa que o autômato dado pela tabela atual é o autômato
reduzido para a linguagem em questão. 
O algoritmo a seguir deixa explícito o processo de minimização dos estados de um autômato determinístico: 
1. Dividir os estados em duas classes, uma contendo todos os estados que sejam finais e outra contendo os não-finais. 
2. Em qualquer das classes, separar também os estados que bloqueiam num determinado caracter do alfabeto numa nova
classe. 
3. Estados dentro de uma mesma classe que levem até estados em diferentes classes para um mesmo caracter, também
podem ser divididos em duas classes. 
4. O processo continua até que mais nenhuma nova classe possa ser criada. Nesse momento, cada uma das classes pode
ser considerada como sendo um estado único. 
 A aplicação desse processo no autômato a seguir mostra bem como isso pode ser feito: 
Ou seja, de início separamos os estados finais dos não-finais. Depois, vemos que os estados B e BE bloqueiam para o caracter
"a" e devem, portanto, serem separados do estado A. A seguir, vemos que o estado CF leva ao estado A, numa classe diferente
da classe a que pertence o estado CF, enquanto que os demais estados levam ao estado BE, que está numa classe diferente de A.
Assim, podemos separar o estado CF numa classe diferente da que pertencem os outros estados finais. A seguir, não teríamos
mais classes para separar, quando então poderíamos juntar todos os estados de uma dada classe num estado único, resultando
no autômato indicado na última tabela da sequência.
3.2- Transformação de AEF's em gramáticas regulares
O processo aqui é bastante simples, bastando fazer a aplicação das regras de transformação de forma reversa, isto é, para toda transição
 \delta(A,x) = B 
acrescenta-se a produção 
 A -> xB 
e para todo estado final "F" acrescenta-se a produção F -> \lambda 
Após a criação de todas as produções deve-se fazer a eliminação das produções vazias através dos mecanismos apresentados
anteriormente. Portanto percebe-se que a transformação é trivial, levando-nos a conseguir mais uma passagem entre as várias formas
de se representar a gramática para um analisador léxico. 
3.3- Gramática linear a esquerda
Quando examinamos o processo de transformação de uma gramática num AEF construímos todas as regras baseando-nos numa
gramática linear a direita, isto é, com produções do tipo A -> xB e A -> x. Entretanto, nem sempre temos uma gramática deste tipo em
mãos. Uma forma de se obter tal gramática é usar expressões regulares como uma forma intermediária no processo de transformação
de uma gramática linear a esquerda em outra a direita. Como já temos as regras de transformação entre ER's e gramáticas lineares a
direita, resta-nos apenas determinar as regras de transformação entre gramática linear a esquerda e expressões regulares. 
As regras de produção são as seguintes: 
 
Produções: Expressão
regular:
A -> Bx e B -> y A -> yx
A -> Ax e A -> y A -> yx*
A -> x e A -> y A -> x | y
4. Implementação do analisador léxico
Um analisador léxico pode ser implementado ou através do AEF que o representa ou através de sua gramática regular. Embora o
resultado de ambas as técnicas deva ser o mesmo, estas formas tem diferenças fundamentais quanto à implementação. Se partirmos do
AEF para a implementação do scanner, o trabalho de manipulação é maior do que se partirmos de sua gramática regular, que é um
processo que pode ser feito de forma automática. 
A seguir descrevemos estas duas abordagens, apresentando também os problemas envolvidos na especificação do analisador léxico,
tais como a implementação da tabela de símbolos, tamanho do alfabeto de entrada e tratamento da passagem de valores (tokens) ao
analisador sintático, entre outros. 
4.1 Implementação via AEF
A implementação do scanner através de um AEF é bastante simples. Basicamente o que é feito é usar um par de comandos do tipo
CASE (switch em C) para representar os estados e os caracteres sendo lidos pelo autômato. 
Assim, por exemplo, um primeiro CASE faz sua decisão a partir do estado atual do autômato (que está guardado numa variável
atualizada a cada transição), enquanto que o segundo CASE tomará a sua decisão a partir do caracter que acaba de ser lido. A ordem
em que estes dois cases são realizados pode ser alterada segundo a conveniência do processo de busca, isto é, caso seja mais
conveniente primeiro selecionar pelo caracter de entrada e depois pelo estado, podemos fazê-lo assim sem maiores complicações. A
decisão sobre qual ordem a ser adotada é deixada então a cargo do implementador. 
Como pode ser visto, uma vez definido o AEF temos que a sua implementação é trivial se o mesmo puder ser expresso por um
conjunto reduzido de estados e de caracteres de entrada. Entretanto isso não é o que ocorre num compilador, fazendo com que a
implementação do AEF se torne trabalhosa devido ao grande número de estados e do tamanho do alfabeto existentes numa gramática
regular real. A solução para este problema é o uso de geradores automáticos de scanners, tais como o lex ou o flex presentes no
ambiente UNIX. 
4.2 Implementação via gramática
O scanner pode ser implementado usando-se um gerador automático, tal como o lex. Para tanto, usamos gramáticas reescritas na forma
de expressões regulares, que devidamente arranjadas segundo a sintaxe do lex podem gerar de forma automática o código do scanner. 
Esta abordagem tem enormes vantagens com relação à implementação direta a partir do autômato pois, como a gramática (e as
expressões regulares que a representam) tem que ser definida de qualquer maneira, uma vez que é a partir dela que sabemos quais são
os strings permitidos paraa dada linguagem, torna-se desinteressante tranformarmos a gramática num autômato que teria que ser
implementado manualmente, se sabemos que existem geradores automáticos de scanners a partir das produções da própria gramática.
Entretanto, em ambos casos existem problemas que precisam ser resolvidos para que a implementação seja funcional, tanto quanto à
sua correção como quanto à sua eficiência. A seção seguinte faz um tratamento destes problemas. 
4.3 Problemas de implementação
1. Tamanho do alfabeto de entrada: Como o autômato usa dois cases aninhados, em que um deles é decidido pelos diferentes
caracteres do alfabeto de entrada, torna-se necessário que o alfabeto não seja muito extenso, uma vez que em geral temos cerca de 50
estados diferentes na gramática de um compilador normal. 
O alfabeto ASCII tem 128 caracteres (muitos não imprimíveis), logo se o estamos usando, precisamos de algo para reduzir o seu
tamanho. Uma tática é usar subconjuntos que tenham uma característica em comum para que possam ser representados por apenas um
único símbolo, tais como todas as letras (maiúsculas e minúsculas) serem representadas pelo conjunto [A-Za-z]. 
2. Critérios de parada: Um outro problema é a determinação de quando uma certa sequência de entrada representa um token válido
ou não. Por exemplo, para expressão regular d*d* fica impossível determinar se a sequência de entrada 12345 representa os strings "1"
e "2345" ou "123" e "45". 
Para este problema temos duas soluções. Na primeira a estratégia é antecipar sempre a leitura do próximo caracter quando estivermos
trabalhando com um dado caracter. Assim, se estivermos num estado final que tenha transições de saída, usamos o próximo caracter
para decidir se ele permite uma transição ou não. 
A outra solução simplesmente ignora os estados finais até que o autômato bloqueie. Neste caso ele verifica se o bloqueio ocorreu num
estado final. Caso isso seja verdade ele aceita o token, caso contrário o token é rejeitado. Nos dois casos o scanner reinicia seu
funcionamento a partir do caracter que causou o seu bloqueio. 
3. Eliminação de espaços e comentários: Outro aspecto a ser cuidado é a eliminação de espaços em branco e de comentários da
sequência de entrada. A finalidade de sua existência é dar mais clareza ao texto fonte mas, durante a compilação, não existe mais
nenhuma razão para que os mesmos sejam mantidos, uma vez que o scanner já separa todos os tokens a serem trabalhados pelo
analisador sintático. 
Aliás, se os espaços e comentários fossem mantidos após a passagem pelo scanner, teríamos que aumentar a quantidade de tokens
aceitáveis pela linguagem do parser, o que o tornaria muito mais complexo. Assim, temos que fazer com que o scanner reconheça
espaços e comentários e os descarte após detectar algo diferente de espaço ou comentário, o que é obtido modificando a sua gramática
de forma que suas expressões regulares incluam agora espaços e comentários. 
4. Passagem de valores: Como o scanner existe apenas para fazer a separação dos tokens de entrada do parser (que é quem ativa o
scanner), temos que encontrar uma forma de fazê-lo passar valores para o parser. 
Uma forma elegante de fazer isso é através da adição de ações semânticas às produções da gramática regular. Uma ação semântica é
simplesmente uma atribuição de valor de retôrno que o scanner faria no instante em que chegasse em um bloqueio num estado final. 
Isto pode ser implementado de várias formas, mas a mais simples é através de atribuições diretas dentro dos comandos case criados
(tanto manualmente como de forma automática) para fazer a análise léxica. No caso do uso do lex isto é feito diretamente em cada
expressão regular. 
5. Tabela de símbolos: Dentro do processo de identificação de tokens da gramática surge o problema de como identificar
individualmente cada variável ou constante definida no programa. Essa tarefa é resolvida pelo uso de uma tabela de símbolos, em que
são armazenadas todas as informações sobre cada variável (tratada aqui como um símbolo), tais como seu nome, seu escopo, endereço
lógico, tipo, etc.
Um grande problema envolvido na implementação do scanner é a forma em que a tabela de símbolos é criada e manipulada. Isto se
deve ao fato de que a tabela de símbolos tem que ser consultada, e atualizada, cada vez que um token é identificado. Logo, temos que
ter mecanismos que façam isso de forma bastante eficiente. 
Dentre as possíveis estratégias temos a implementação da tabela como sendo uma tabela hash, em que através de uma função hash
pudessemos encontrar símbolos dentro da tabela de forma bastante rápida. Esta forma é ao mesmo tempo eficiente e econômica em
termos de memória, desde que dentro de cada posição da tabela não tenhamos que percorrer listas extensas para identificar um token de
forma única. 
Uma possível melhoria é obtida ao custo de um aumento no espaço ocupado na memória, fazendo-se com que cada caracter de cada
token ocupe um nó de uma árvore de busca. Tal árvore é chamada "trie" (de re"trie"val) e consiste basicamente em fazer com que cada
nó seja um vetor que aponte para n possíveis caracteres que seguiriam ao nó em questão. 
Para efeito de comparação temos a seguir uma tabela apresentando o espaço ocupado e tempo de busca para tabelas de símbolos
implementadas através de busca linear, tabela hash e árvore trie: 
 
Algoritmo 
Tamanho da tabela
(bytes) Tempo de scan
50 ident. 500 ident. 
50
ident. 
500
ident. 
Busca
linear 600 6000 2960 29600
Tabela
Hash 1400 10400 250 540
Árvore trie 5720 36000 250 250