Os Compiladores com Lex e Yacc

Compiladores com Lex e Yacc

Um compilador é um programa de sistema que traduz um programa em uma linguagem de alto nível para um programa equivalente em código de máquina para um processador. Em geral, um compilador não produz diretamente o código de máquina, mas sim um programa em linguagem simbólica (assembly) semanticamente equivalente ao programa de alto nível.

Para desempenhar suas tarefas, um compilador deve executar dois tipos de atividade, sendo a primeira, a análise do código fonte em que a estrutura e o significado do programa de alto nível são reconhecidos. A segunda atividade é a síntese do programa equivalente em linguagem simbólica. Embora conceitualmente seja possível executar toda a análise e apenas então iniciar a síntese, estas duas atividades ocorrem em praticamente paralelo.

Assim sendo, os compiladores Lex/Flex servem para executar a primeira atividade mencionada, ou seja, gerar automaticamente programas (usualmente em linguagem C) fazendo a leitura de uma entrada de modo a varrer um texto e/ou programa (“scanner”) com o objetivo de obter uma sequência de unidades léxicas (“tokens”). Os tokens gerados pelo Lex/Flex serão usualmente processados posteriormente pelo Yacc/Bison, um programa que realizará a análise sintática.

A estrutura de um arquivo Lex é similar aos de um arquivo Yacc e são divididos em três seções, separados por linhas que contém somente dois símbolos de porcentagem (“%”) como mostrado no exemplo a seguir.

definições

%%

regras

%%

sub-rotinas

Na seção de definições são definidas as macros e são importadas as bibliotecas escritas em C. É também possível escrever código C na mesma seção.

Já a seção de regras associa padrões om instruções C os quais são escritos na forma de expressões regulares. Quando o analisador léxico identifica algum texto da entrada relacionada com algum padrão definido no arquivo fonte, é executado o código C associado e, no aso de dois padrões distintos estiverem relacionados com a mesma entrada, será utilizado para análise o maio desse padrões, pois é o que consome o ais número de caracteres de entrada. Em casos de ambiguidade, ou seja, dois padrões consumirem a mesma quantidade de caracteres, é utilizado o padrão definido no arquivo.

A seção de sub-rotinas contém blocos de código C que serão apenas copiados ao arquivo final. Portanto, assume-se que tal código será invocado a partir das regras da seção de regas.

A seguir, um exemplo de um arquivo Lex que reconhece inteiros de entrada de dados e os imprime na saída padrão.

[pic 1]

Utilizando o código acima, é possível realizar a conversão para um arquivo C para a seguinte entrada.

[pic 2]

        Imprimindo a seguinte saída.

[pic 3]

        O gerador de análise léxica Lex e o gerador de análise sintática Yacc são geralmente utilizados em conjunto.

        O Yacc utiliza uma gramática formal para analisar sintaticamente uma entrada, algo que o Lex realizar somente com expressões regulares por ser limitado a simples máquinas de estado finito). Entretanto Yacc não realiza leituras a partir de uma simples entrada de dados, sendo assim, necessário uma série de tokens geralmente fornecidos pelo analisador léxico.

        Segue baixo dois diagramas do relacionamento entre Lex e Yacc:

[pic 4]

        A partir do diagrama 1, é possível perceber que o Le gera a sub-rotina yylex() a partir de regras léxicas e que o Yacc gera a sub-rotina yyparse() a partir de regras gramaticais.

...