Escola Politécnica da
Universidade de São Paulo
PCS2056 - Linguagens e Compiladores
Compilador
Analisador Léxico
Alexandre Minoru Sugano
Renato Dias Kavai
1. Quais são as funções do analisador léxico nos compiladores/interpretadores?
O analisador léxico é a interface de entrada para os compiladores/interpretadores, atuando como
tradutor do texto-fonte. Sua função primária é realizar a leitura de um arquivo, fragmentá-lo em
componentes léxicos básicos (conhecidos como lexemas), classificar estes componentes em uma
estrutura (conhecidos como átomos ou token) e retornar esta estrutura ao analisador léxico. Assim,
o analisador léxico tem a função de Extrair e Classificar os Átomos. O analisador léxico possui
outras funcionalidades que não são diretamente relacionados à análise léxica, mas que são
importantes para o processo de compilação. Abaixo estão listadas as outras funcionalidades do
analisador léxico:
•
•
•
•
•
•
•
•
•
Descartar delimitadores e comentários: comentários e delimitadores melhoram a legibilidade
do código, mas não possuem valores sintáticos e não são utilizados em outras etapas de
compilação.
Conversão numérica: transformar as cadeias de caracteres numéricos em uma representação
interna de números com tamanho conhecido, como por exemplo, um int ou um float.
Tratamento de Identificadores: transforma uma identificação em uma representação de
tamanho conhecido. No caso dos identificadores é utilizada uma tabela de símbolos para
auxiliar esta tarefa. Nesta tabela é guardado o nome do identificador e atribui um índice, o qual
é utilizado no átomo como referencia ao nome.
Identificação de palavras reservadas: verifica se o identificador é uma palavra chave da
linguagem. Para isso, o identificador é comparado com todas as palavras de uma tabela de
palavras reservadas (pré-determinada pela linguagem).
Recuperação de Erros:trata casos de leitura de uma estruturas ou de um símbolos inesperados,
para não perder a sincronia entre o que está sendo lido e o que está sendo analisado. Os
mecanismos de tratamento são diversos, seja ignorando o que está sendo lido até achar um
delimitador ou avisar que aquele átomo está mal formado e continuar com a execução.
Listagens e Gerar tabelas de referência cruzada: como o analisador léxico possui contato direto
com o texto-fonte, é possível criar listagens de átomos. As tabelas de referencia cruzada é uma
listagem que facilitar a localização de alguns átomos no texto-fonte, informando a linha e a
coluna.
Definição e Expansão de macros: algumas linguagens permitem o uso de macros e é de
responsabilidade do compilador realizar os devidos tratamentos com relação as macros. As
macros funcionam como abreviaturas de código. A sua substituição pode ocorrer em um préprocessamento de arquivo ou durante a análise sintática, sendo que neste ultimo método é
necessário uma forte comunicação entre o analisador léxico e o analisador sintático.
Interagir com o sistema de arquivos: considerando que o analisador léxico é a interface de
entrada para textos-fonte e sendo estes comumente arquivos,a interação do analisador léxico
com os sistemas de arquivos é natural.
Compilação Condicional: alguns compiladores permitem alguns comandos de controle para
configurar a compilação de trechos de um conjunto de texto-fonte de acordo com os
1
•
parâmetros. Assim o analisador léxico possui forte participação na compilação neste modo
através do chaveamento de arquivos e da seleção de trechos de texto.
Controle de listagens: a partir dos comandos decontrole do compilador é possível configurar
diversos tipos de coletas para as listagens, assim como habilitar ou desabilitar tal recurso.
2. Quais as vantagens e desvantagens da implementação do analisador léxico como uma fase
separada do processamento da linguagem de programação em relação à sua implementação
como sub-rotina que vai extraindo um átomo a cada chamada?
O analisador léxico é muito requisitado ao realizar a tradução do texto-fonte, logo é um potencial
gargalo para o compilador. Separando o analisador léxico do processamento da linguagem, torna-se
possível uma melhor avaliação da eficiência do analisador léxico com relação a tradução do textofonte, facilitando também na otimização do desempenho deste processo.
A implementação do analisador léxico em fase separada utiliza um arquivo intermediário, onde
será preenchido com o átomo extraído do texto-fonte, servindo como entrada para o analisador
sintático. Enquanto que na implementação como sub-rotina, o analisador léxico responde por meio
de alguma área de memória convencionada (pode ser um parâmetro a ser preenchido, por
exemplo) o átomo extraído do texto-fonte. O analisador sintático realiza o consumo do átomo
juntamente com a produção, sem a necessidade de um arquivo intermediário e viabilizando a
compilação em passo único.
3. Defina formalmente, através de expressões regulares sobre o conjunto de caracteres ASCII, a
sintaxe de cada um dos tipos de átomos a serem extraídos do texto-fonte pelo analisador
léxico, bem como de cada um dos espaçadores e comentários.
Foram definidos seis tipos de átomos. A seguir está uma breve descrição de cada átomo, seguido de
sua definição e sua expressão regular:
•
Inteiro: representa um número inteiro. É definido como um ou mais caracteres de números.
Inteiro: [0-9]+
•
Float: representa um número racional. É definido como uma cadeia de caracteres de números
tendo o caractere ponto [.] como separador entre números inteiros e números decimais, sendo
que o ponto pode aparecer no inicio da cadeia de caracteres.
Float: ([0-9])*\.([0-9])+
•
Identificador: representa um nome genérico sem sentido especial para a linguagem. É definido
como uma cadeia de caracteres de letras, números e underscore(_), sendo que o início desta
cadeia não pode ser um número.
Identificador: ([a-z]|[A-Z]|_)([a-z]|[A-Z]|_|[0-9])*
2
•
Char: representação de um caractere na linguagem. É definido como uma cadeia de caracteres
delimitados por aspas simples [‘].
Char: ‘(\\’|[^’])+’
•
String: representação de uma palavra na linguagem. É definida como uma cadeia de caracteres
delimitados por aspas duplas [“].
String: “(\\”|[^”])+”
•
Palavras reservadas: representam símbolos e palavras com sentido especial para a linguagem.
É definido como um identificador ou como um conjunto de símbolos que podem estar
compostos (como por exemplo >= e ||) ou simples (como por exemplo / e +).
PalavraReservada: (([a-z]|[A-Z]|_)([a-z]|[A-Z]|_|[0-9])*)| == |
&& | \|\| | != | >= | <= | [^([a-z]|[A-Z]|_|[0-9])]
Nem todos os caracteres lidos pelo analisador léxico são considerados átomos. Abaixo estão outras
duas classificações que são ignoradas pelo analisador léxico:
•
Espaçadores: são definidos como espaços em branco, tabulações e quebra de linha
Espaçadores: \t|\n|\x20
•
Comentários: são definidos de duas formas. A primeira é um conjunto de caracteres delimitados
por /* e */. A segunda é um conjunto de caracteres delimitados por // e por uma quebra de
linha.
Comentários: (/\*([^*]|[\r\n]|(\*+([^*/]|[\r\n])))*\*+/)|(//.*)
4. Converta cada uma das expressões regulares, assim obtidas, em autômatos finitos
equivalentes que reconheçam as correspondentes linguagens por elas definidas.
Figura 1 - Autômato finito para átomos do tipo inteiro
3
Figura 2 - Autômato finito para átomos do tipo float
Figura 3 - Autômato finito para átomos do tipo identificador
Figura 4 - Autômato finito para átomos do tipo caractere
4
Figura 5 - Autômato finito para átomos do tipo string
Figura 6 - Autômato finito para átomos do tipo palavra reservada
5
Figura 7 - Autômato finito para espaçadores
Figura 8 - Autômato finito para comentários
6
5. Crie um autômato único que aceite todas essas linguagens a partir de um mesmo estado
inicial, mas que apresente um estado final diferenciado para cada uma delas.
7
6. Transforme o autômato assim obtido em um transdutor, que emita como saída o átomo
encontrado ao abandonar cada um dos estados finais para iniciar o reconhecimento de mais
um átomo do texto.
O transdutor possui um diagrama de estados muito semelhante ao item anterior, com a diferença
de que os estados finais do diagrama anterior possuem uma transição vazia para estado inicial,
emitindo como saída o átomo devidamente extraído e classificado. A única exceção para esta regra
é o estado de comentário, o qual não emite nenhum átomo.
8
7. Converta o transdutor assim obtido em uma sub-rotina, escrita na linguagem de programação
de sua preferência. Não se esqueça que o final de cada átomo é determinado ao ser
encontrado o primeiro símbolo do átomo ou do espaçador seguinte. Esse símbolo não pode
ser perdido, devendo-se, portanto, tomar os cuidados de programação que forem necessários
para reprocessá-los, apesar de já terem sido lidos pelo autômato.
Para implementar o transdutor foi adotada a linguagem em C, já que o compilador deve ser
desenvolvido nesta linguagem. As transições do transdutor foram definidas a partir de uma tabela
de estados. A tabela é um mapeamento entre o estado atual com o tipo do caractere lido
relacionado com o próximo estado. Assim, o estado vai sendo atualizado para cada caractere lido
até retornar ao estado inicial, fechando um ciclo para a extração de um átomo. Terminado um ciclo
de leitura para a formação de um átomo, é verificado o estado exatamente anterior ao inicial,
determinando assim o tipo do átomo de acordo com o estado encontrado. Caso o primeiro
caractere lido seja um espaço, ou uma tabulação ou uma quebra de linha, ele é ignorado e o
programa pega o próximo caractere. Caso seja atingido o estado de comentário, o conteúdo lido é
descartado e inicia-se um novo átomo. Ao final de cada ciclo de leitura (sendo que o ciclo não passe
pelo estado de comentário), o transdutor monta um átomo com tipo e valor, assim como
referencias do início do átomo ao texto-fonte a partir de coordenadas de linha e a coluna. Além
disso, átomos do tipo identificadores, char e strings possuem seus valores adicionados as
respectivas tabelas.
8. Crie um programa principal que chame repetidamente a sub-rotina assim construída, e a
aplique sobre um arquivo do tipo texto contendo o texto-fonte a ser analisado. Após cada
chamada, esse programa principal deve imprimir as duas componentes do átomo extraído (o
tipo e o valor do átomo encontrado). Faça o programa parar quando o programa principal
receber do analisador léxico um átomo especial indicativo da ausência de novos átomos no
texto de entrada.
O programa principal cria as tabelas necessárias (símbolo, string e palavras reservadas) e chama a
função getNextToken() do analisador léxico enquanto o átomo recebido não seja um End Of
File. Quando esse átomo é recebido, o programa principal limpa a memória utilizada pelas
tabelas e pelo átomo recebido, antes de finalizar por completo.
9
9. Relate detalhadamente o funcionamento do analisador léxico assim construído, incluindo no
relatório: descrição teórica do programa; descrição da sua estrutura; descrição de seu
funcionamento; descrição dos testes realizados e das saídas obtidas.
O programa foi dividido em duas partes: programa principal (Main.c e Main.h) e analisador
léxico(Léxico.h e Léxico.c). Também foi definida uma simples estrutura de lista ligada (LinkedTable.c
e LinkedTable.h) para auxiliar na manipulação de tabela.
As estruturas de lista ligada são utilizadas para montar a Tabela de Símbolos, Tabela de Strings e
Tabela de Palavras Reservadas. A estrutura de lista ligada possui dois ponteiros para outras duas
estruturas de lista ligada, sendo um ponteiro representando o elemento anterior (ponteiro prev) e
o outro ponteiro representando um elemento posterior (ponteiro next). Caso a estrutura seja
extremidade de uma lista ligada, o ponteiro da extremidade apontará para o NULL, ou seja, se a
estrutura for o primeiro da lista, o ponteiro anterior aponta para NULL. A estrutura ligada
armazena os dados em um atributo chamado value, sendo que o conteúdo depende da tabela
representada pela esta estrutura. Na tabela de string é armazenado o valor do átomo do tipo string.
Na tabela de símbolos é armazenado o valor do átomo do tipo identificador. Na tabela de palavras
reservadas são armazenadas símbolos e palavras com sentido especial para a linguagem. Cada valor
armazenado possui um índice representado pelo atributo id. A lista ligada ainda conta com dois
métodos: iniciaLinkedTable() e liberaMemoriaLinkedTable(). A primeira função
inicializa a estrutura de uma lista com os ponteiros NULL e o id -1, representando uma estrutura de
lista vazia. A segunda função percorre todos os elementos da lista para liberar a memória ocupada
por cada estrutura de lista ligada.
O programa principal é o programa que chama a função de conseguir novos átomos do Léxico.c. O
programa principal possui uma função main(), que inicia as três tabelas, populando a tabela de
palavras reservadas e começa a chamar Átomos utilizando a função do analisador léxico. Ela chama
átomos até que venha um átomo do tipo EOF. Ao receber este átomo, ela libera a memória
utilizada e finaliza o programa. Esses arquivos também possuem uma função auxiliar chamada
createReservedWordsTable(), que é a função que popula a tabela de palavras reservadas. A
partir do arquivo "reservedWords.txt", as palavras são lidas e adicionadas na LinkedTable. Se a
LinkedTable esta vazia (id = -1), o primeiro elemento é apenas atualizado. Caso não esteja vazio, é
buscado o último elemento (next = NULL) e um novo elemento é criado e linkado a tabela, com Id e
Value setados. A função vai adicionando elementos na tabela até alcançar o EOF do arquivo.
O analisador léxico é o core do programa. A primeira função deles é criar a Struct Token. Essa struct
possui um atributo type, que é composto por três caracteres, e representa os tipos de átomos que
o analisador léxico pode identificar, que são: INT, FLT, IDN, RWD, CHA, STR, ERR e EOF. O segundo
atributo da tabela é o value_i, que representa o valor de fato do átomo, que pode ser o valor
real de um int (no caso do tipo INT), um id (no cado de IDN, RWD, CHA, STR), -1 (no caso de ERR) e 0
(no caso de EOF). O tipo FLT não utiliza value_i, e sim um similar, value_f, que é do tipo float e
representa o valor real dele. Por último, o átomo possui os atributos lin e col, que representam
a linha e a coluna onde o átomo começa no texto-fonte. Quanto as funções, os arquvios possuem
10
diversas para poder executar a analise léxica. A função principal é a getNextToken(), que vai
chamar as funções de mudança de estado e de montagem do átomo, para poder manda-lo para o
programa principal. E na função principal também que a tabela de estados é criada. A função
atualizaStatus() é a função responsável por verificar em qual estado o programa se encontra
após ler um átomo. A função começa lendo char por char, ignorando os primeiros espaços em
branco, tabs e quebras de linha até achar um char que comece um átomo. A partir dai os estados
vão sendo atualizados, os chars lidos são salvos na variável lida e a linha e a coluna são salvas
também. No fim, caso o estado seja um comentário, o programa recomeça a leitura do próximo
átomo. Caso seja qualquer outra coisa, a função devolve as informações obtidas e o estado que
tinha sido alcançado antes de retornar ao zero para o léxico poder fazer a montagem do átomo. A
função que cuida disso é a montaToken(). Esta função trata diferentemente o que foi lido de
acordo com o estado recebido. Caso seja um INT ou um FLT, ela transforma o valor lido no
respectivo valor em int ou float. Caso seja uma String ou um Char, eles são buscados na tabela de
Strings e o identificador deles é salvo. Caso não estejam lá, são adicionados a tabela. Caso seja um
símbolo, a mesma coisa acontece com a tabela de palavras reservadas. Caso tenha sido lido um
potencial identificador, ele é buscado primeiro na tabela de palavras reservadas, é só depois que
não é encontrado, é buscado ou adicionado na tabela de símbolos. A função também monta o
átomo de erro caso um estado desse tipo tenha sido encontrado. Para átomos INT, a função
trataInteiro() é utilizada. Ela analisa cada digito lido e soma-o ao int resultante,
multiplicando-o por 10 a cada iteração. Caso o número estoure 999999999, o valor passado é -1. De
um modo semelhante, a função trataFloat() trata os átomos FLT. De um modo semelhante a
anterior, ela monta a parte inteira do número, até chegar no ‘.’, onde ela passa a montar a parte
decimal do número. A função trataErro() por enquanto retorna apenas -1. Uma função
importante para a mudança de estados é a readFile(), que cuida da leitura de chars do códigofonte. Essa função vai lendo char por char do arquivo quando é chamada, ou, se o arquivo tiver
terminado, a função retorna EOF. A função createStateTable() é responsável pela criação da
tabela de estados, indicando qual é o estado alcançado a partir de um estado e de uma classe de
char lido. Por último existem duas funções de manipulação de lista ligada. A primeira,
buscaTabela(), busca um valor na tabela escolhida e devolve o id se ele for encontrado, e FALSE
(-1), caso não seja encontrado. A segunda, adicionaNaTabela(), adiciona o valor na tabela,
criando se necessário um novo elemento e fazendo as ligações necessárias, e devolve o novo id.
O analisador léxico desenvolvido realiza diversas funções de um analisador léxico: ele identifica e
classifica os átomos, descarta delimitadores e comentários, faz conversão numérica de int e float,
trata os identificadores, identifica as palavras reservadas, recupera alguns erros e interage com o
sistema de arquivos. Outras funções descritas na primeira questão não foram implementadas.
Os testes foram realizados com diversos tipos de combinações de entradas para testar o
funcionamento da transição de estados e se os átomos estavam sendo montados de forma correta.
No fim, foi escrito um programa que utiliza as principais combinações possíveis do programa.
Algumas observações são feitas. Primeiro, mesmo que um símbolo (como -, * ou &) caia no estado
de palavra reservada, ele será considerado uma palavra não reconhecida se não estiver no arquivo
11
reserverdWords.txt, e será enviado com o Id -1 para o programa principal. De mesmo modo, ao se
deparar com algo parecido 1.b, ou seja um float que depois do ponto tem algo estranho que não
seja um número, ele será enviado como uma palavra reservada desconhecida (por causa do ., que é
uma palavra reservada). O token de erro é utilizado para 4 tipos de erros: algo na forma 1a (número
inteiro seguido de letra ou _), na forma 1.1a (número float seguido de letra ou _, ou então o não
fechamento de um ‘ ou de um “ antes do fim do arquivo. Por enquanto o analisador léxico trata
esses erros de forma igual (um átomo do tipo ERR de valor -1). Contudo, a medida que o analisador
sintático precisar de erros mais especificos esses erros ganharam uma identificação melhor
(separando “números mal formados” de “final inesperado de arquivo”).
O código-fonte abaixo foi o programa escrito para os testes finais:
int main() {
int a; //variavel teste
float b; /*outra variavel*/
a = a + 1;
b = b + 1.2;
printf("A casa e bonita");
char c = 'c';
if (a == 1)
printf("oi");
else
b = b * b;
return 0;
}
Como saída do programa, é esperado que o Léxico.c imprima o que foi lido e considerado um
átomo separado. Logo após a montagem do átomo, o programa principal imprime na tela o tipo do
átomo, seu valor e a linha e a coluna onde o átomo começa. Isso ocorre até chegarmos no átomo
EOF, que recebe o mesmo tratamento, menos a impressão do que foi lido, porque de fato nada foi
lido. Abaixo temos um exemplo da saída do programa rodando o código-fonte acima:
TOKEN int
valor = 6
tipo
= RWD
linha = 1
coluna = 1
TOKEN )
valor =
tipo
=
linha =
coluna =
11
RWD
1
10
TOKEN a
valor =
tipo
=
linha =
coluna =
1
IDN
2
8
TOKEN main
valor = 0
tipo
= IDN
linha = 1
coluna = 5
TOKEN {
valor =
tipo
=
linha =
coluna =
12
RWD
1
12
TOKEN ;
valor =
tipo
=
linha =
coluna =
1
RWD
2
9
TOKEN (
valor =
tipo
=
linha =
coluna =
TOKEN int
valor = 6
tipo
= RWD
linha = 2
coluna = 4
10
RWD
1
9
TOKEN float
valor = 14
tipo
= RWD
linha = 4
coluna = 4
12
TOKEN b
valor =
tipo
=
linha =
coluna =
2
IDN
4
10
TOKEN ;
valor =
tipo
=
linha =
coluna =
1
RWD
4
11
TOKEN a
valor =
tipo
=
linha =
coluna =
1
IDN
6
4
TOKEN =
valor =
tipo
=
linha =
coluna =
2
RWD
6
6
TOKEN a
valor =
tipo
=
linha =
coluna =
1
IDN
6
8
TOKEN +
valor =
tipo
=
linha =
coluna =
3
RWD
6
10
TOKEN 1
valor =
tipo
=
linha =
coluna =
1
INT
6
12
TOKEN ;
valor =
tipo
=
linha =
coluna =
1
RWD
6
13
TOKEN b
valor =
tipo
=
linha =
coluna =
2
IDN
7
4
TOKEN =
valor =
tipo
=
linha =
coluna =
2
RWD
7
6
TOKEN b
valor = 2
tipo
= IDN
linha = 7
coluna = 8
TOKEN +
valor =
tipo
=
linha =
coluna =
3
RWD
7
10
TOKEN 1.2
valor = 1.200000
tipo
= FLT
linha = 7
coluna = 12
TOKEN ;
valor =
tipo
=
linha =
coluna =
1
RWD
7
15
TOKEN printf
valor = 18
tipo
= RWD
linha = 9
coluna = 4
TOKEN (
valor =
tipo
=
linha =
coluna =
10
RWD
9
10
TOKEN "A
valor =
tipo
=
linha =
coluna =
casa e bonita"
0
STR
9
11
TOKEN )
valor =
tipo
=
linha =
coluna =
TOKEN ;
valor =
tipo
=
linha =
coluna =
11
RWD
9
28
1
RWD
9
29
TOKEN char
valor = 3
tipo
= RWD
linha = 10
coluna = 4
TOKEN c
valor = 4
tipo
= IDN
linha = 10
coluna = 9
TOKEN =
valor =
tipo
=
linha =
coluna =
2
RWD
10
11
TOKEN 'c'
valor = 1
tipo
= CHA
linha = 10
coluna = 13
TOKEN ;
valor =
tipo
=
linha =
coluna =
1
RWD
10
16
TOKEN if
valor =
tipo
=
linha =
coluna =
15
RWD
11
4
TOKEN (
valor =
tipo
=
linha =
coluna =
10
RWD
11
7
TOKEN a
valor =
tipo
=
linha =
coluna =
1
IDN
11
8
TOKEN ==
valor =
tipo
=
linha =
coluna =
0
RWD
11
10
TOKEN 1
valor =
tipo
=
linha =
coluna =
1
INT
11
13
TOKEN )
valor =
tipo
=
linha =
coluna =
11
RWD
11
14
TOKEN printf
valor = 18
tipo
= RWD
linha = 12
coluna = 2
13
TOKEN (
valor =
tipo
=
linha =
coluna =
10
RWD
12
8
TOKEN "oi"
valor = 2
tipo
= STR
linha = 12
coluna = 9
TOKEN )
valor =
tipo
=
linha =
coluna =
TOKEN ;
valor =
tipo
=
linha =
coluna =
11
RWD
12
13
1
RWD
12
14
TOKEN else
valor = 16
tipo
= RWD
linha = 13
coluna = 4
TOKEN b
valor = 2
tipo
= IDN
linha = 14
coluna = 2
TOKEN =
valor =
tipo
=
linha =
coluna =
TOKEN b
valor =
tipo
=
linha =
coluna =
TOKEN *
valor =
tipo
=
linha =
coluna =
TOKEN b
valor =
tipo
=
linha =
coluna =
2
RWD
14
4
2
IDN
14
6
4
RWD
14
8
2
IDN
14
10
TOKEN ;
valor = 1
tipo
= RWD
linha = 14
coluna = 11
TOKEN return
valor = 17
tipo
= RWD
linha = 16
coluna = 4
TOKEN 0
valor =
tipo
=
linha =
coluna =
0
INT
16
11
TOKEN ;
valor =
tipo
=
linha =
coluna =
1
RWD
16
12
TOKEN }
valor =
tipo
=
linha =
coluna =
13
RWD
17
1
valor
tipo
linha
coluna
0
EOF
0
0
=
=
=
=
10. Explique como enriquecer esse analisador léxico com um expansor de macros do tipo #DEFINE,
não paramétrico nem recursivo, mas que permita a qualquer macro chamar outras macros, de
forma não cíclica. (O expansor de macros não precisa ser implementado).
Para o analisador léxico tratar a expansão de macros, é necessário que o analisador léxico
administre uma tabela de macros, relacionando um identificador a um macro. Quando o analisador
léxico encontrar um átomo de identificação, este átomo será primeiramente analisado na tabela de
macros. Caso o identificador é encontrado, substitui o átomo de identificação pelo macro.
Considerando os macros não paramétricos e não recursivos, existe outro método para tratar a
expansão de macros. O método realiza um pré-processamento no texto-fonte, fazendo uma cópia
temporária do texto-fonte com as devidas substituições de macros antes de iniciar o processo
analítico.
14