% % Este ficheiro contem um texto em Literate Programming % 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[latin1]{inputenc} \usepackage[portuges]{babel} \usepackage{latexsym} \usepackage{noweb} \usepackage[dvips]{epsfig} \usepackage{epic} \usepackage{eepic} \usepackage{hyperref} \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 Trabalho Prático N$º$1} \\ \textbf{\small Um Processador de Gramáticas} \end{tabular} } \author{\small Grupo: \begin{tabular}[t]{lll} 55436 & LESI & Ana \\ 40000 & MCC & Tó \\ 33333 & MCC & Zé \\ \end{tabular} } \date{} %-------------------- Inicio do Documento ------------------------------- \begin{document} \maketitle Neste trabalho prático pretende-se que os alunos construm um processador para uma notação de gramáticas independentes do contexto. O programa a desenvolver deverá utilizar as técnicas leccionadas nesta cadeira, nomeadamente: modelação de um analisador léxico via expressões regulares, gramáticas independentes do contexto, classe LL(1), construção de um parser recursivo descendente, e a análise semântica de linguagens. \bigskip \noindent \begin{tabular}{rl} \hline \\ \textbf{Entrega da Trabalho:} & 8 de Maio \\ \\ \textbf{Constituição dos Grupos:} & Os grupos terão obrigatoriamente \textbf{3 elementos} \\ \\ \textbf{Linguagem de Programação.:} & qualquer \\ \\ \hline \end{tabular} \bigskip Este trabalho prático consta de duas partes distintas: uma parte obrigatório que todos os grupos devem resolver (secções 1 a 6) e uma parte opcional (secção 7) em que são propostos três extras ao trabalho prático para os grupos que pretendem tirar uma melhor nota. \textit{Na aula teórica do dia 11 de Maio, realizar-se-á um teste individual escrito de 15 minutos de duração sobre o trabalho prático.} O enúnciado do trabalho prático está escrito em \textbf{literate Programming} usando o sistema \textbf{NoWeb}\footnote{O Sistema NoWeb está disponível no seguinte endereço: \texttt{http://www.eecs.harvard.edu/~nr/noweb/.}}. Isto é, pode ser interpretado como um documento \LaTeX\ ou como um programa numa qualquer linguagem de programação. Resolva este trabalho prático neste mesmo ficheiro de modo a implementar o programa e a sua documentação. \section{A Linguagem de Gramáticas} A linguagem, ou notação, de gramáticas independentes do contexto que vamos considerar é a notação \textit{formal} que tem vindo a ser utilizada nas aulas teóricas e teórico-práticas desta disciplina. Por exemplo, uma frase desta linguagem apresenta-se de seguida: \medskip \begin{verbatim} G = (T,N,S,P) T = {a,b,c}lazy : Save.agt $(HASKELL_VGEN) -1 -X -H -O -w -h -y Save N = {X,Y,Z} S = X P = { p0 : X -> a Y Z , p1 : Y -> b Y , p2 : Y -> , p3 : Z -> c } \end{verbatim} \medskip Nesta notação, os símbolos terminais escrevem-se em letras minúsculas e os não terminais em maiúsculas. As produções tem um nome e utiliza-se o símbolo \texttt{->} para denotar o operador \textit{deriva em} da notação BNF. A produção \texttt{p2} é uma produção nula e é denotada pela não existência de qualquer símbolo do lado direito. Esta mesma gramática pode também ser escrita de uma forma mais concisa, como se mostra a seguir: \medskip \begin{verbatim} G = ({a,b,c},{X,Y,Z},X,P) P = { p0 : X -> a Y Z , p1 : Y -> b Y , p2 : | , p3 : Z -> c } \end{verbatim} \medskip Em que os conjuntos de símbolos terminais, não terminais e axioma são definidos na própia definição de gramática. Note ainda, que as produções com o mesmo lado esquerdo utilizam o operador \textit{ou} do BNF. \subsection{Regras Semânticas} De acordo com a própria definição formal de gramáticas independentes do contexto, existem regras que temos de ter em conta quando se define uma gramática, nomeadamente: \begin{itemize} \item Não podem existir símbolos terminais e não terminais repetidos nos respectivos onjuntos. \item $T \cap N = \emptyset$ \item O axioma tem de ser um símbolo de $N$. \item Os símbolos que ocorrem nas produções de P tem de estar definidos em $T \cup N$. \item Os lados esquerdos de uma produção tem de ser elementos de $N$. \item Não podem existir duas produções com o mesmo nome. \end{itemize} Neste projecto pretende-se desenvolver um programa, isto é, um processador de gramáticas, que verifica se uma dada gramática está sintáctica e semanticamente bem formada. Pretende-se que o processador avise o programador da existência de qualquer erro na definição das suas gramáticas. Pretende-se ainda, e caso a gramática esteja bem formada, que o programa produza uma representação \textit{pretty printed} da gramática, por exemplo em Html ou LaTeX. \section{Gramática Independente do Contexto} Para formalizar a notação da linguagem anterior apresentamos uma gramática independente do contexto que a define: \texttt{...} \medskip \( \begin{array}{l} G = (T,N,S,P), com \\ T = \{ '(',')', ...\}, \\ N = \{ GIC , ... \}, \\ S = seja, \\ \begin{array}[t]{lclccl} P = & \{ & p_0: & GIC & \rightarrow & ... \\ & , & p_1: & ... & \rightarrow & ... \\ & , & ... & & & \\ & \} \end{array} \\ \end{array} \) \medskip \subsection{Condição LL(1)} Uma vez que pretendemos construir um parser recursivo descendente, vamos povar nesta secção que a gramática definida na secção anterior pertence à classe LL(1). \texttt{...} \section{Desenvolvimento do Projecto} Na realização deste projecto, utilizamos a linguagem de programação \texttt{X} pela seguintes razões: \begin{itemize} \item \texttt{...} \item \texttt{...} \end{itemize} Para realizar a análise léxica do texto fonte utilizamos \texttt{...} \subsection{Estrutura de Dados para Representar Gramáticas} Para podermos representar gramáticas independentes do contexto na linguagem \texttt{X}, definimos a seguinte estrutura de dados: @ <>= @ \section{Parsing da Notação de Gramáticas} Tendo provado que a gramática é LL(1), um parser recursivo descendente escreve-se facilmente em \texttt{X}. @ <>= @ Para efectuar a análise léxica, ou scanning, do texto fonte uilizamos o sistema \texttt{Y} @ <>= @ \section{Analisado Semântico} Após termos feito parsing de um texto fonte, isto é, uma gramática, precisamos construir uma função que verifique se as regras semânticas são respeitadas. Esta função apresenta-se a seguir. @ <>= @ \section{A Makefile} A makefile para produzir o programa desejado apresenta-se a seguir @ <>= COMP = gram : ... $(COMP) -o gram ... ... doc : tp1.tex pdflatex tp1.tex tp1.tex : tp1.nw noweb tp1.nw @ \section{Extras ao Trabalho Prático} \subsection{Pretty Printing} Nesta secção apresenta-se um função que gera uma representação mais \textit{alindada} das gramaticas. Esta função produz uma representação em Html?/\LaTeX?. @ <>= @ \subsection{Gramáticas Bem Definidas} Uma condiçãonecessária (embora, não única) para uma gramática independente do contexto estar \textit{bem definida} é o facto de todos os símbolos terminais e não terminais da gramática estarem acessíveis a partir do seu exioma. Um símbolo que não está acessível a partir do axioma nunca poderá ser usado na derivação de uma frase da linguagem e designa-se de \textit{símbolo não útil}. Considere a gramática seguinte: \begin{verbatim} G = (T,N,S,P) T = { .... } ... \end{verbatim} Esta gramática tem os seguinte símbolos anuláveis: .... De seguida apresentamos a função que dada uma gramática indica quais os símbolos anuláveis. Re-definimos ainda a função de \textit{pretty printing} de modo a não mostrar esse símbolos (e respectivas produções) na sua representação alindada. @ <>= @ \subsection{Fichas Teórico-Práticas} Em anexo apresentamos a resolução da fichas teórico-práticas nº1, nª2, \texttt{...} \end{document}