% % Este ficheiro contem um texto em Literate Haskell % Partes do ficheiro são texto em LaTeX e outras em Haskell % % Processamento de Linguagens e Compiladores % 2005/2006 % \documentclass[12pt]{article} \usepackage{a4wide} \usepackage{graphics} \usepackage{graphicx} \usepackage{color} \usepackage{alltt} \usepackage{noweb} % noweb LaTeX style \usepackage[portuges]{babel} \usepackage[latin1]{inputenc} \usepackage[dvips]{epsfig} \usepackage{epic} \usepackage{eepic} \newtheorem{exercicio}{}[section] \title{\sf Processamento de Linguagens e Compiladores \\ \begin{tabular}{c} {\small LMCC}, {\small Universidade do Minho} \\ {\small Ano lectivo 2005/2006} \\ {\small João Saraiva} \\ {\small Ficha Teórico-Prática N$º$6} \\ \end{tabular} } \author{} \date{} %-------------------- Inicio do Documento ------------------------------- \begin{document} \maketitle Este texto está escrito no sistema de \textbf{literate programming} \textit{noweb}\footnote{\texttt{http://www.eecs.harvard.edu/nr/noweb/}}. Um documento em \textit{noweb} pode ser interpretado como um documento \LaTeX\ ou como um programa \textit{numa qualquer linguagem de programação}. Isto é, o sistema \textit{noweb} é um sistema de literate programming genérico que pode ser utilizado para documentar/desenvolver software em qualquer linguagem de programação. Por exemplo, podemos utilizar o sistema \textit{noweb} para documentar programas em Java, C, Haskell, etc. Nesta ficha o sistema \textit{noweb} é utilizado no desenvolvimento de especificações/programas em \textit{Lex}. \section{Lex: Um Gerador de Analisadores Léxicos} Expressões regulares são uma notação simples e concisa para definir linguagens regulares. Como vimos nas fichas teórico-práticas anteriores, a construção de funções de aceitação para linguagens regulares é feita eficientemente se considerarmos a sua construção baseada num autómato finito determinista. A construção de autómatos finitos é uma tarefa mecânica que pode ser feita facilmente por um computador. Assim, e como vimos nas fichas teórico-práticas n$º4$ e n$º5$ é possível construirmos programas, chamados \textit{gerador de analisadores léxicos}, que convertem automaticamente expressões regulares em autómatos finitos deterministas. O sistema \textit{Lex} é um gerador de analisadores léxicos que produz um programa C, que modela um autómato finito deterministas, a partir de uma especificação léxica, baseada em expressões regulares. Antes de apresentarmos o sistema \textit{Lex} vamos primeiro mostrar a notação de expressões regulares que este ssistema utiliza. \subsection{Expressões Regulares na Notação Unix} \label{sec:er} Expressões regulares são a base de várias ferramentas incluídas no sistema operativo Unix, tais como \texttt{grep}, \texttt{awk}, \texttt{vi}, etc. Todas estas ferramentas utilizam a mesma notação para definir expressões regulares que se tornou um \textit{standard de facto} para expressões regulares. Na tabela seguinte descreve-se brevemente esta notação. \bigskip \begin{tabular}{|l|l|} \hline \texttt{a} & concorda com o caracter $a$ \\ \texttt{.} & qualquer caracter excepto \textit{newline} \\ \texttt{*} & zero ou mais cópias da expressão regular precedente \\ \texttt{+} & uma ou mais cópias da expressão regular precedente \\ \texttt{?} & zero ou uma cópia da expressão regular precedente \\ \texttt{a|b} & concorda com $a$ ou $b$ \\ \texttt{ab} & concorda com $a$ seguido de $b$ \\ \texttt{[xyz]} & concorda com a classe de caracteres $[xyz]$ \\ & neste caso concorda com $x$, $y$ e $z$ \\ \texttt{\^{ }xyz} & negação da classe de caracteres $[xyz]$ \\ & neste caso concorda com todos os caracetres menos os da classe \\ \texttt{(r)} & concorda com $r$: os parentesis são usados para \\ & redefinir prioridades dos operadores \\ \texttt{\^{ }r} & concorda com $r$ mas apenas no início de uma linha \\ \verb@$r@ & concorda com $r$ mas apenas no fim de uma linha\\ \verb@"a|b"@ & concorda com a string $"a|b"$ \\ \hline \end{tabular} \begin{exercicio} \label{exerc:er} Escreva expressões regulares na notação Unix/Linux para modelar as seguintes linguagens regulares: \begin{enumerate} \item Frases constituídas por zero ou mais símbolos $a$ seguidos por um ou mais símbolos $b$. \item Linguagem cujas frases são os digitos. \item Linguagem dos números inteiros. \item Linguagem dos espaços. \item Linguagem cuja única frase é a palavra reservada \textit{WHILE}. \item Linguagem que define todas as combinações de letras maiúculas e minúsculas para escrever a palavra \textit{WHILE}. \item Comentários \textit{a la} Haskell. Isto é, frases que começam pela sequência \texttt{--} e terminam por \textit{newline} \end{enumerate} \end{exercicio} \section{Especificações em Lex} Expressões regulares por si só permitem definir de uma forma concisa e clara padrões de texto. Para se obterem ferramentas úteis é no entanto necessário associar acções (ou, \textit{reacções}) a essas mesmas expressões regulares. Isto é, para cada expressão regular é necessário especificar como os nossos programas devem reagir assim que uma parte do texto concorda com a expressões regular em causa. Uma especificação é constituída por três secções, separadas por \texttt{\%\%}, tal como se apresenta a seguir. \begin{verbatim} definições %% regras %% código do programador \end{verbatim} O primeiro separador \texttt{\%\%} tem sempre de existir pois a secção \texttt{rules}, onde se definem as expressões regulares e respectivas acções tem sempre de ser definida. \begin{itemize} \item \texttt{definições}: secção onde se incluem algumas definições de código C (por exemplo, definição de variáveis globais, \textit{include} de módulos, etc) ou de expressões regulares que são depois usadas na secção de regras. \item \texttt{regras}: secção onde se definem as regras, isto é, pares constituídos pela expressão regular e respectiva acção. As expressões regulares são definidas na notação Unix (ver secção~\ref{sec:er}) e tem de começar na primeira coluna do ficheiro. A expressão regular é seguida por um espaço (isto é, espaço, \textit{tab} ou \textit{newline}) e uma acção (opcional) associada à expressão regular. Um acção é um \textit{statement} C ou um bloco de \textit{statements} delimitado por \texttt{\{} e \texttt{\}}. \item \texttt{código do programador}: secção onde o programador pode incluir funções em C necessárias para definir as acções que associa às expressões regulares. Uma função que deve também ser aqui definida éa função \texttt{main}, pois é obrigatória em qualquer programa C. Tipicamente, a função \texttt{main} chama apenas a função \texttt{yylex()} que é função C que o \textit{Lex} produz e que modela a aceitação no autómato finito determinista construída de acordo com as expressões regulares deinidas na secção das regras. Uma outra função que aqui deve ser definida éa função \texttt{yywrap()} que o \textit{Lex} assume como pre-definida e que indica se se já chegou ao fim do input ou não\footnote{As funções \texttt{main} e \texttt{yywrap} estão habitualmente definidas na biblioteca \texttt{libl.a} e não é necessário escrevê-las em cada especificação \textit{Lex}. Porém, e um vez que existem distribuições do sistema \textit{Lex} que não trazem essa biblioteca e para tornar o código C mais portável (podemos portar o código C para computadores sem o \textit{Lex}, preferimos incluir sempre a definição destas funções.}. \end{itemize} De seguida apresentamos uma especificação \textit{Lex} que sinaliza sempre que uma sequência de caracteres da entrada concorda com a expressão regular \texttt{hello}. Nesse caso a acção desencadeada é enviar para a saída a frase \verb@"Matched the word "hello"!\n"@. Todos os outros caracteres concordam com a expressão regular \verb@.|\n@ e uma vez que a acção não faz nada, logo nada é enviado para a saída. @ <>= /* Não existem definições */ %% hello { printf("Matched the word \"hello\"!\n"); } .|\n ; %% int yywrap (void) {return 1; } /* função executada após EOF */ int main() /* função main usual */ { yylex(); return 0; } @ \subsection{Executar o Sistema Lex} A partir de uma especificação válida o sistema \textit{Lex} produz um programa C. Historicamente, este programa tem nome \texttt{lex.yy.c} (mas pode ser actualmente facilmente renomeado utilizando uma opção do sistema \textit{Lex}). Assim, para gerar uma função de aceitação para a especificação apreentada anteriomente efectue: \begin{verbatim} lex primeiro.l \end{verbatim} Verifique que o ficheiro \texttt{lex.yy.c} foi gerado e está no sistema de ficheiros\footnote{Se tiver curiosidade em ver como a função \textit{dfaaccpet} escrita em Haskell na ficha teórico-prática nº2 se escreve (muito) eficiente e (muito) complicadamente em C, edite esse mesmo ficheiro...}. Após produzir o programa C pode facilmente produzir um programa executável compilando esse programa: \begin{verbatim} gcc -Wall lex.yy.c \end{verbatim} O programa gerado (\texttt{a.out}) recebe as frases do \textit{standard input}. Assim, utilize o texto apresentado a seguir para executar o programa fazendo: \begin{verbatim} a.out < frase.txt \end{verbatim} @ <>= Isto é um teste para ver se o lex funciona! hello?! Estás aí? humm!!! @ \begin{exercicio} Escreva uma especificação em \textit{Lex} para testar as todas as expressões regulares definidas no exercício~\ref{exerc:er}. Isto é, defina uma única especificação em \textit{Lex} que contém todas as expressões regulares e cujas (re)acções indicam qual expressão regular utilizada. \end{exercicio} @ <>= %% a*b+ { printf("Encontrei As seguidos de Bs \n"); } ... { printf("Encontrei um digito \n"); ... %% int yywrap (void) {return 1; } int main() { yylex(); return 0; } @ \subsection{Inclusão de Código C} O programador pode definir código C nas secções de \texttt{definições} e \texttt{código do programador}. Por exemplo, em \textit{Lex} podemos definir facilmente um programa similar ao \texttt{wc} existente em Unix. Isto é um programa que conta o número de linhas e caracteres de um ficheiro. Na especificação seguinte, definem-se duas variáveis globais \texttt{linhas} e \texttt{caract} na secção de definições. Estas variáveis não podem ser declaradas na primeira coluna para não se confundirem com definições de expressoes regulares. Na secção de regras definem-se as expressºões regulares que concordam com o \textit{newline} e com qualquer outro caracter e incrementam-se os contadores. A função \texttt{main} envia os valores finais dos contadores paraa saída, @ <>= int linhas = 0, caract = 0; %% \n { ++linhas; ++caract; } . { ++caract; } %% int yywrap (void) {return 1; } int main() { yylex(); printf( "# of lines = %d, # of chars = %d\n",linhas, caract ); return 0; } @ \begin{exercicio} Escreva uma especificação em \textit{Lex} para construir um histograma que indica as ocorrências da cada caracter Ascii num ficheiro de texto recebido do \textit{standard input}. \end{exercicio} @ <>= /* declarar estrutura de dados para definir o histograma */ %% %% int yywrap (void) {return 1; } int main() { /* iniciar o histograma */ yylex(); /* mostrar as ocorrências de cada caractere ascii */ return 0; } @ Na secção de definições e de modo a não termos a preocupação em iniciar o código C na primeira coluna, este pode ser incluído entre os delimitadores \verb@%{@ e \verb@%}@. Nesta secção de definições pode-se ainda definir expressões regulares que são posteriormente usadas na secção de regras. Neste caso as expressões regulares tem um nome que é depois referido nas regras através de delimitar o nome entre chavetas. No exemplo seguinte mostramos o uso destas caracteristicas. @ <>= %{ #include int contaNat = 0; /+ conta numero de naturais */ int contaDig = 0; /* conta numero de digitos */ int somaNat = 0; /* somatorio de naturais */ %} digito [0-9] %% {digito}+ { somaNat += atoi(yytext); ++contaNat; conaDig += yyleng; } .|\n ; %% int yywrap (void) {return 1; } int main() { yylex(); printf( "# de naturais = %d, # de digitos = %d , somatorio = %d\n" ,contaNat,contaDig,somaNat); return 0; } @ Como podemos verificar neste exemplo existem variáveis predefinidas em \textit{Lex}: \begin{itemize} \item \textbf{yytext}: Apontador para a string que concordou com a expressão regular; \item \textbf{yyleng}: comprimento da string que concordou com a expressão regular; \end{itemize} \subsection{Regras de Escolha da Expressão Regular} Em caso uma string (ou sub-string) concordar com mais de que uma expressão regular definida numa especificação \textit{Lex}, então para definir qual das duas expressões regulares é preferida o \textit{Lex} utiliza as seguintes regras: \begin{enumerate} \item Se duas uma string concordas com duas expressões regulares então a expressão regular que concordar com mais símbolos é preferida. \item No caso de ambas as expressões regulares concordarem com o mesmo número de caracteres então a primeira expressão regular que ocorre na especificação \textit{Lex} é preferida. \end{enumerate} \begin{exercicio} Utilize a especificação apresentada de seguida para constatar que o \textit{Lex} utiliza estas regras. Apresente o texto de entrada que utilizaria para fazer essa constactação. \end{exercicio} @ <>= %% prefer { printf("prefiro a expressão regular que ocorre primeiro\n"} [a-zA-Z]+ { printf("prefiro a 2ª expressão regular\n"} . ; %% int yywrap (void) {return 1; } int main() { yylex(); return 0; } @ \section{Filtros de Texto em Lex} \begin{exercicio} Na escrita de textos em Português é ferquente utilizarmos abreviatura de modo a podermos escrever os nossos textos de uma foram mais rápida. Por exemplo, a abreviatura \textit{qd} significa \textit{quando}, enquanto \textit{fds} significa \textit{fim de semana}. Considere as abreviaturas definidas na seguinte tabela: \bigskip \begin{center} \begin{tabular}{|l|l|} \hline qdo & quando \\ qto & quanto \\ pq & porque \\ tb & também \\ cqd & como queriamos dizer \\ fds & fim de semana \\ \hline \end{tabular} \end{center} Considere ainda que \verb@\@ antes de uma palavra estende a palavra com \textit{in} e que no fim estende com \textit{mente}. Isto é, \verb@\formal@ estende para \textit{informal}, enquanto \verb@formal\@ estende para \textit{formalmente}. Por último, \verb@\formal\@ estende para \textit{informalmente}. \end{exercicio} \section{Contextos em Lex} Considere que se pretende desenvolver um programa em \textit{Lex} que dado um texto conta todos os números (inteiros) que aparecem dentro de uma lista (na sua notação usual) e deverão ignorar os restantes números que aprecem no texto. \begin{verbatim} Este texto, com o numero 24, pretende mostrar a utilizacao de contextos em Lex. Assim, o pocessador a desenvolver em Lex devera somar as listas [4,6,-5,6] e [7,3,6] e produzir o resultado 27. \end{verbatim} @ <>= %{ int contador = 0; %} inteiro [+-]?[0-9]+ %S CONTADOR %% "[" BEGIN CONTADOR ; {inteiro} contador++ ; "]" BEGIN 0; . ; . ; %% int yywrap() { printf (" Res: %d ",contador); } @ \section{Analisadores Lexicos em Lex} @ <>= %{ #include "token.h" extern int yylval; %} inteiro [-+]?[0-9]+ %% {inteiro} { yylval = atoi(yytext) ; return NUMBER; } [\(\);] return yytext[0]; [ \t\n] ; /* ignorar espaços */ . { fprintf(stderr," Erro lexico: Simbolo %c não é do vocabulário",yytext[0]); exit(0); } %% @ \end{document}