Lex & Yacc

  1. lex
  2. yacc

1. lex

O trabalho de geração automática do front-end de um compilador é possível apenas com a utilização dos chamados compiladores de compiladores. Nessa categoria uma das mais famosas ferramentas é, na prática, constituída por um par de aplicativos, dos quais o lex é encarregado de fazer a geração do analisador léxico.

Basicamente o lex necessita da especificação da linguagem na forma de expressão regular e de um conjunto de funções adicionais para a manipulação dos tokens gerados, em particular de funções que trabalhem com a tabela de símbolos.

A geração do código do scanner é feita com a execução do comando
lex arquivo_fonte

O arquivo com o fonte do lex é dividido em três partes, todas separadas pelo token "%%". Elas são:

  1. Preâmbulo, em que se faz a inclusão de bibliotecas e de definições de agrupamentos de caracteres, como no exemplo a seguir:

    2. %{
    #include "stdio.h"
    #include "parser.h" /* onde estariam definidos os headers do parser */
    %}
    delimitador  [ \t\n]
    brancos  {delimitador}+
    letra_maiusc  [A-Z]
    letra_minusc  [a-z]
    letra  {letra_maiusc}|{letra_minusc}
    digito  [0-9]
    identificador  {letra}({letra}|{digito})*
    numero  {digito}+
  1. Corpo, em que estão definidas as expressões regulares para a linguagem, assim como as ações semânticas a serem disparadas no eventual reconhecimento de cada token (expressão). Assim, o exemplo a seguir mostra como é especificado o corpo de um arquivo lex:

    2.  
    while  { return (WHILE); }
    {identificador}                 { mkname(); return IDENT; }
    {numero}  { mkval(); return INTNUM; }
  1. Funções adicionais, em que surgem as funções chamadas a partir do corpo do arquivo lex, tais como mkname() e mkval(). É aqui que devem vir as funções que manipulam a tabela de símbolos.

    2.  

     

    void mkname ( )
    { do do do do
    }

    void mkval ( )
    { da da da da
    }

Esse arquivo apresenta um exemplo mais complexo de arquivo lex.

2. yacc

O segundo aplicativo indicado no início desse texto é o yacc, que significa yet another compiler-compiler. Ele é o responsável pela geração do parser e, implicitamente já espera funções geradas pelo lex para o percorrimento do texto fonte a ser compilado.

No ambiente unix existem outros pares que podem substituir o lex-yacc, sendo que a melhor escolha recai no par flex-bison, em que o flex substitui o lex, enquanto o bison substitui o yacc. Em particular, a implementação do scanner a partir do flex é muito superior âgrave; obtida pelo lex, sendo totalmente compatível com o yacc. Assim, mesmo usando o yacc é preferível que se use o lex. De qualquer forma, os dois pares aceitam os mesmos arquivos fonte para a definição da linguagem, de modo que não é preciso escolher um deles a priori.

O formato de um arquivo yacc é mais complexo do que o do lex. Ele também é composto por partes de definição, corpo e adicionais, com uma sintaxe bastante diferenciada no corpo, mesmo porque enquanto no lex a gramática é uma gramática regular, no yacc temos uma gramática de atributos (que é uma gramática livre de contexto acrescida de atributos para a manipulação semântica de contexto).

O problema na especificação do corpo de um arquivo yacc é o fato de uma gramática exibir derivações bastante distintas a partir de um mesmo símbolo não-terminal. Todas essas derivações devem aparecer no corpo, sendo que a ordem em que as mesmas aparecem acaba influenciando a forma como o yacc determina as possíveis construções da linguagem. Isso demanda um cuidado grande no momento de construir a gramática da linguagem, caso não se queira perder um tempo considerável eliminando ambiguidades inexistentes.

Aqui voce vê um exemplo de arquivo de definicao do yacc.