Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Compiladores: Análise Léxica

Compiladores: Análise Léxica

Apresentação de Análise Léxica de Compiladores que realizei no curso de graduação em Ciência da Computação (UFMA) na cadeira de Compiladores I (Setembro de 2009).

Almir Filho

May 24, 2010
Tweet

More Decks by Almir Filho

Other Decks in Programming

Transcript

  1. - Fase em que o compilador lê o programa-fonte como

    uma sequência de caracteres à procura de certos padrões e a organiza em unidades lógicas denominadas de tokens. - Cada token pode ser representado por uma determinada sequência de caracteres. - Cada token representa uma unidade de informação do programa-fonte. ANÁLISE LÉXICA
  2. - Tokens tendem a se enquadrar em diversas categorias. -

    Categorias estas que são padronizadas para as diferentes linguagens de programação. - Exemplos de categorias são: - palavras reservadas (if, while, etc.); - símbolos especiais (operadores aritméticos, atribuição, etc.); - identificadores (geralmente sequência de caracteres composta de letras e dígitos iniciadas por uma letra); - literais ou constantes (contantes numéricas, cadeias de caracteres) TOKENS
  3. Na linha de código abaixo, por exemplo, em C: var

    = 3; temos 4 tokens: var : representa um identificador; = : operação de atribuição; 3 : valor numérico; ; : final de instrução. EXEMPLO DE TOKENS
  4. - Como a tarefa efetuada pela análise léxica é basicamente

    um reconhecimento de padrões, mostraremos um pouco dos métodos usados para execução deste processo. Estes métodos são basicamente: - Expressões Regulares - Autômatos Finitos MÉTODOS PARA ANÁLISE LÉXICA
  5. - Descreveremos aqui algumas expressões regulares típicas para algumas categorias

    de tokens. EXPRESSÕES REGULARES - Números natural = [0-9]+ naturalComSinal = (+|-)? natural numero = naturalComSinal(“.”natural)?(E naturalComSinal)? - Identificadores letra = [a-zA-Z] digito = [0-9] identificador = letra( letra | digito )*
  6. - Há uma forte relação entre autômatos finitos e expressões

    regulares. A seguir, um exemplo elucidativo: AUTÔMATOS FINITOS - Identificadores: Como foi definido anteriormente uma expressão regular, representaremos agora a mesma expressão com um autômato finito determinístico (DFA): identificador = letra( letra | digito )*
  7. - Notemos que o diagrama anterior permite ao DFA passar

    para o estado de aceitação em qualquer ponto durante a leitura de uma cadeia identificadora. - Como esses algoritmos deverão ser traduzidos em código, precisamos saber quando chegamos ao final de cada token, ou seja, quando achamos um delimitador. - Eis um DFA que representa esta idéia ([outro] é qualquer coisa que não seja nem letra nem digito): VERIFICAÇÃO À FRENTE
  8. - Há muitas maneiras de traduzir autômatos finitos em código,

    porém poucos algoritmos são úteis. - Algoritmos dessa natureza tendem a ser exponencialmente mais complexos devido ao número de estados que determinado autômato pode assumir. IMPLEMENTAÇÃO
  9. - Expressões Regulares são compactas, por essa razão são preferíveis

    como descrições de tokens. - A construção de tal algoritmo começa geralmente com expressões regulares e segue pela construção de um DFA até o programa final para Análise Léxica. ALGORITMO DE TRADUÇÃO DE UMA EXPRESSÃO REGULAR PARA DFA
  10. Os seguintes passos são executados: - Tradução de uma expressão

    regular para um NFA; - Conversão de um NFA para um DFA; - Minimização do número de estados de um DFA; - Construção de um algoritmo à partir de um DFA minimizado. ALGORITMO DE TRADUÇÃO DE UMA EXPRESSÃO REGULAR PARA DFA
  11. - Vamos ilustrar um pequeno autômato para - uma resumida

    - análise léxica da linguagem TINY. É importante observar que este exemplo só diz respeito a identificação de comentários, literais numéricos, identificadores, atribuições e espaços em branco. EXEMPLO: ALGORITMO DE UM SISTEMA DE ANÁLISE LÉXICA PARA TINY