Análise Lexical: Estrutura de um Compilador

O processo de compilação envolve diferentes fases:

A primeira delas é a análise léxica, que consiste na conversão da sequência de caracteres de entrada numa sequência de elementos lexicais (tokens).

A principal função da análise léxica é estruturar a sequência de carácteres da entrada numa sequência de tokens a serem processados pelo parser.

No entanto, o analisador léxico efectua outras operações como sejam: a exclusão de espaços em branco e de comentários do parser, e a correlação entre erros (léxicos e sintácticos) com o código fonte (e.g. número da linha).

A análise léxica pode ser feita recorrendo a gramáticas do tipo-3, ou seja, por gramáticas regulares, e a sua implementação computacional pode ser feita eficientemente recorrendo a autómatos finitos.

Análise Lexical: gramáticas regulares

Uma gramática é regular, sse existir um autómato finito que a reconhece.

Um autómato finito é uma máquina de estados com um estado inicial e um ou mais estados de aceitação (reconhecimento).

As transições são feitas apenas tendo em conta o estado actual e a entrada.

Um autómato finito para reconhecer a palavra reservada if será:

Outro autómato finito que reconheça um identificador pode ser: