%
% This file was written in Literate Programming
%    
% Authors: Pedro Henriques, Daniela da Cruz
% Date: November, 2005
% Second Update: December, 2005
% Last update: April, 2006 (ANTLR version) - Rodrigo Baptista
%

\documentclass[a4paper]{report}
\newif\ifshowcode
\showcodetrue

\usepackage{latexsym}
\usepackage{a4wide}
%\usepackage[latin1]{inputenc}
\usepackage[dvips]{epsfig}
\usepackage{epic}
\usepackage{eepic}
\usepackage{hyperref}

\parindent=0pt
\parskip=2pt
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0in}
\addtolength{\topmargin}{-\headheight}
\addtolength{\topmargin}{-\headsep}
\setlength{\textheight}{8.9in}
\setlength{\textwidth}{6.5in}
\setlength{\marginparwidth}{0.5in}

\title{Lavanda}
\author{Exercise with Attribute Grammar and its implementation in LISA}
\date{\today}

\begin{document}
\maketitle

\newpage

\tableofcontents

\newpage

\chapter{Problem}
\textsf{Lavanda} is a Domain Specific Language (\emph{DSL}) which main goal is drescribe 
the bags of clothes that Point of Gathering of a Laundry daily send to the Center to wash.
Each bag has a identification number, the client name and its content is divided in one or more items.
Each item have one or more clothe type (personal clothe or \emph{household linen}), tinged type (white or color) and line type (cotton, wool and fiber).
For each one of this items we keep in register the number of pieces that belongs to that item.
The Independent Context Grammar$G$, mentioned below, defines the language \textsf{Lavanda} intended.
The root is \texttt{Lavanda}, the terminal simbols are written is lowercase (pseudo-terminais), or uppercase (reserved-words),
ou between apostrophes (sinais de pontua\c c\~{a}o) and null string \'{is} noted by \verb"&";
the remaining simbols are Non-Terminals.
\begin{verbatim}
         p1:  Lavanda  -->  Cabec  Sacos
         p2:  Cabec    -->  data  IdPR
         p3:  Sacos    -->  Saco  '.'
         p4:             |  Sacos  Saco  '.'
         p5:  Saco     -->  num  IdCli  Lotes
         p6:  Lotes    -->  Lote  Outros
         p7:  Lote     -->  Tipo  Qt
         p8:  Tipo     -->  Classe  Tinto  Fio
         p9:  Outros   -->  &
         p10:            |  ';'  Lotes
         p11: IdPR     -->  id
         p12: IdCli    -->  id
         p13: Qt       -->  num
         p14,15:    Classe-->  corpo |  casa
         p16,17:    Tinto -->  br    |  cor
         p18,19,20: Fio   -->  alg   |  la    |  fib
\end{verbatim}
%---------------------------------------------------------------------------

After transform $G$ in a independent contex abstract grammar (you can reduce some productions that seems redundant), 
writte a \textbf{Attribute Grammar} for:
\begin{itemize}
    \item
    compute (and print) total of bags sended and total of items of each cliente.
    \item
    compute (and print) total of pieces of each 12 items types
    (since 'body/br/alg' until 'house/cor/fib') sended to wash at laundry.
    \item
    compute total cost of each bag; suppose initially is given a table with prices of each item type.\\

    The grammar should detect error situations: the identification number of bag is duplicated and should flag an error
    allways show up a bag for a client already finded.
\end{itemize}

%--------------------------------------------------------------------------
\chapter{Attribute Grammar - Solution}
The first step is writte the abstract grammar.\\
To do that we eliminate all terminals without semantic charge (reserved words and signs).
The grammarr will be simplified by eliminating productions without alternatives that in right side
just show up one terminal --- in this case: \texttt{p11, p12, p13}.
\begin{verbatim}
         p1a:  Lavanda  -->  Cabec  Sacos
         p2a:  Cabec    -->  data  id
         p3a:  Sacos    -->  Saco
         p4a:             |  Sacos  Saco
         p5a:  Saco     -->  num  id  Lotes
         p6a:  Lotes    -->  Lote  Outros
         p7a:  Lote     -->  Tipo  num
         p8a:  Tipo     -->  Classe  Tinto  Fio
         p9a:  Outros   -->  &
         p10a:            |  Lotes
         p11a:    Classe-->  corpo
         p12a:            |  casa
         p13a:    Tinto -->  br
         p14a:            |  cor
         p15a:    Fio   -->  alg
         p16a:            |  la
         p17a:            |  fib
\end{verbatim}
The next step is choose the attributes.\\

\begin{itemize}

\item
For first item, we will need two sinthesized attributes:
\texttt{nSacos: int} associated at axiom \texttt{Lavanda} and
\texttt{nLotes: int} associated at symbol \texttt{Saco}.\\
To compute each one will be necessary associate:
\texttt{nSacos: int} at symbol  \texttt{Sacos} and
\texttt{nLotes: int} at symbol \texttt{Lotes} and at symbol \texttt{Outros}.\\

The computation and translate rules are:
\begin{verbatim}
         p1a:  Lavanda  -->  Cabec  Sacos
               -- Lavanda.nSacos = Sacos.nSacos
               -- escreve( Lavanda.nSacos )
         p3a:  Sacos    -->  Saco
               -- Sacos.nSacos = 1
         p4a:             |  Sacos  Saco
               -- Sacos0.nSacos = Sacos1.nSacos + 1
         p5a:  Saco     -->  num  id  Lotes
               -- Saco.nLotes = Lotes.nLotes
               -- escreve( Saco.nLotes )
         p6a:  Lotes    -->  Lote  Outros
               -- Lotes.nLotes = Outros.nLotes + 1
         p9a:  Outros   -->  &
               -- Outros.nLotes = 0
         p10a:            |  Lotes
               -- Outros.nLotes = Lotes.nLotes
\end{verbatim}


\item
	To this item will be needed 3 attributes: 
	\begin{enumerate}
		\item
		\texttt{inEnv: HashTable} --- \texttt{Saco}, \texttt{Lotes} and \texttt{Lote};
		\item
		\texttt{outEnv: HashTable} --- \texttt{Lavanda}, \texttt{Sacos}, \texttt{Saco},
		\texttt{Lotes}, \texttt{Lote} and \texttt{Outros};
		\item
		\texttt{name: string} --- \texttt{Tipo}, \texttt{Classe}, \texttt{Tinto} and \texttt{Fio}.
	\end{enumerate}


The computation and translate rules are:
\begin{verbatim}

         p1a:  Lavanda  -->  Cabec  Sacos
               -- escreveT( Sacos.outEnv )
         p3a:  Sacos    -->  Saco
               -- Saco.inEnv = Sacos.inEnv
               -- Sacos.outEnv = Saco.outEnv
         p4a:             |  Sacos  Saco
	       -- Saco.inEnv = Sacos1.outEnv
               -- Sacos1.inEnv = Sacos0.inEnv
               -- Sacos0.outEnv = Saco.outEnv
         p5a:  Saco     -->  num  id  Lotes
               -- Lotes.inEnv = Saco.inEnv
               -- Saco.outEnv = Lotes.outEnv
         p6a:  Lotes    -->  Lote  Outros
               -- Lote.inEnv = Lotes.inEnv
	       -- Outros.inEnv = Lote.outEnv
	       -- Lotes.outEnv = Outros.outEnv
         p7a:  Lote    -->  Tipo num
               -- Lote.outEnv = updateTablePrice(Lote.inEnv, Tipo.name, num)
         p8a:  Tipo    -->  Classe Tinto Fio
               -- Tipo.name = Classe.name + Tinto.name + Fio.name
         p9a:  Outros   -->  &
               -- Outros.outEnv = Outros.inEv;
         p10a:            |  Lotes
               -- Lotes.inEnv = Outros.inEnv;
               -- Outros.outEnv = Lotes.outEnv;
         p11a: Classe  -->  corpo
	       -- Classe.name = "corpo"
         p12a: Classe  -->  casa
	       -- Classe.name = "casa"
         p13a: Tinto  -->  br
	       -- Tinto.name = "br"
         p14a: Tinto  -->  cor
	       -- Tinto.name = "cor"
         p15a: Fio  -->  alg
	       -- Fio.name = "alg"
         p16a: Fio  -->  la
	       -- Fio.name = "la"
         p17a: Fio  -->  fib
	       -- Fio.name = "fib"
\end{verbatim}


\item

To this item will be needed 5 attributes: 

\begin{enumerate}
		\item
		\texttt{inTable: HashTable} --- \texttt{Sacos}, \texttt{Saco}, \texttt{Lotes}, 
                \texttt{Lote} and \texttt{Outros};\\ Price table (inherited attribute).
		\item
		\texttt{inIds: Vector} --- \texttt{Sacos} and \texttt{Saco};\\
                Clients identifiers (Array --- inherited attribute).
		\item
		\texttt{outIds: Vector} --- \texttt{Sacos} and \texttt{Saco};\\
                 Clients identifiers (Array --- sinthesized attribute).
		\item
		\texttt{custoTotal: int} --- \texttt{Saco}, \texttt{Lotes}, \texttt{Lote} and
		\texttt{Outros};\\
                Cost of each bag (sinthesized attribute).
		\item
		\texttt{name: string} ---- \texttt{Tipo}, \texttt{Classe}, \texttt{Tinto} and \texttt{Fio}.
                Name of each attribute associated at Tipo (sinthesized attribute).


\end{enumerate}

The computation and translate rules are:

\begin{verbatim}
	 p1a : Lavanda -> Cabec Sacos
               -- Sacos.inTable = initTable()
	       -- Sacos.inIds   = initIds()
         p3a:  Sacos    -->  Saco
               -- Saco.inTable = Sacos.inTable
               -- Saco.inIds = Sacos.inIds
               -- Sacos.outIds = Saco.outIds
	       -- escrevePreco( Saco.custoTotal )
         p4a:             |  Sacos  Saco
	       -- Saco.inTable  = Sacos0.inTable
               -- Sacos1.inEnv = Sacos0.inEnv
	       -- Saco.inIds = Sacos1.outIds
	       -- Sacos1.inIds = Sacos0.inIds
	       -- Sacos0.outIds = Saco.outIds
	       -- escrevePreco( Saco.custoTotal )
         p5a:  Saco     -->  num  id  Lotes
	       -- Saco.outEnv = novoId( Saco.inIds, num.value() )
	       -- if ( pertence( num,Saco.inIds ) )
               --    erro("Cliente ja existente!")
               -- Lotes.inTable   = Saco.inTable
	       -- Saco.custoTotal = Lotes.custoTotal
         p6a:  Lotes    -->  Lote  Outros
               -- Lote.inTable = Lotes.inTable
               -- Outros.inTable = Lotes.inTable
               -- Lotes.custoTotal = Lote.custoTotal + Outros.custoTotal
         p7a:  Lote    -->  Tipo num
               -- Lote.custoTotal = lookupPreco( Lote.inEnv, Tipo.name ) * num.value()
         p8a:  Tipo    -->  Classe Tinto Fio
               -- Tipo.name = Classe.name + Tinto.name + Fio.name
         p9a:  Outros   -->  &
               -- Outros.custoTotal = 0
         p10a:            |  Lotes
               -- Outros.custoTotal = Lotes.custoTotal
         p11a: Classe  -->  corpo
	       -- Classe.name = "corpo"
         p12a: Classe  -->  casa
	       -- Classe.name = "casa"
         p13a: Tinto  -->  br
	       -- Tinto.name = "br"
         p14a: Tinto  -->  cor
	       -- Tinto.name = "cor"
         p15a: Fio  -->  alg
	       -- Fio.name = "alg"
         p16a: Fio  -->  la
	       -- Fio.name = "la"
         p17a: Fio  -->  fib
	       -- Fio.name = "fib"
\end{verbatim}

\end{itemize}

\newpage

\chapter{\textsf{LISA} implementation}

@o Lavanda.lisa
@{
language Lavanda
{
   lexicon
	 {
	 	  ReservedWord corpo | casa | br | cor | alg | fib | la
	 	  Number     [0-9]+
		  Data 	     [0-2][0-9]\-[0-9][0-9]\-[0-2][0-9][0-9][0-9]
		  Identifier [a-z]+
		  separa \( | \) | \, | \> | \-
		  ignore      [\0x09\0x0A\0x0D\  ]+
	 }


attributes int       LAVANDA.nSacos, CABEC.nSacos, SACOS.nSacos, 
                     SACO.nLotes, LOTES.nLotes, LOTE.nLotes, OUTROS.nLotes;
           String    TIPO.name, CLASSE.name, TINTO.name, FIO.name, 
                     LAVANDA.output, SACOS.output, SACO.output;
           // b)
           Hashtable SACOS.inTable, SACO.inTable, OUTROS.inTable, 
                     LOTE.inTable, LOTES.inTable,
		     SACOS.outTable, SACO.outTable, OUTROS.outTable, 
                     LOTE.outTable, LOTES.outTable;
	  // c)
	  Hashtable  SACOS.inTablePrice, SACO.inTablePrice, LOTES.inTablePrice, 
                     LOTE.inTablePrice, OUTROS.inTablePrice;  
	  Vector     SACOS.inIds, SACO.inIds, 
                     SACOS.outIds, SACO.outIds;
	  double     SACO.custoTotal, LOTES.custoTotal, OUTROS.custoTotal, LOTE.custoTotal;

@}

@o Lavanda.lisa
@{

  rule Lavanda {
	LAVANDA ::= CABEC SACOS compute {
		LAVANDA.nSacos = SACOS.nSacos;
		LAVANDA.output = "\n\nSACOS:" + escreve( LAVANDA.nSacos, "sacos" ) + 
		                 "\n\nLOTES: " + SACOS.output + "\n" +
		                "TABELA LOTES: " + printTable(SACOS.outTable);
		
		// b)
		SACOS.inTable = initNLotes();
		
		// c)
		SACOS.inTablePrice = initTablePrice();
		SACOS.inIds        = initIds();
				      };
	}

rule Cabec {
        CABEC ::= #Data #Identifier compute {
        	CABEC.nSacos = 0;	
        	};
            }


   rule Sacos1 {
        SACOS ::= SACO compute {
        	SACOS.nSacos = 1;
        	SACOS.output = SACO.output + writePrice( SACO.custoTotal );
        	
        	// b)
        	SACO.inTable   = SACOS.inTable; 
        	SACOS.outTable = SACO.outTable;
        	
        	// c)
        	SACO.inTablePrice = SACOS.inTablePrice;
        	SACO.inIds        = SACOS.inIds;
        	SACOS.outIds      = SACO.outIds;
        	};
            }
            
            
  rule Sacos2 {
        SACOS ::= SACOS SACO compute {
        	SACOS[0].nSacos = SACOS[1].nSacos + 1;
        	SACOS[0].output = SACOS[1].output + SACO.output + writePrice( SACO.custoTotal );
        	
        	// b)
        	
        	SACO.inTable      = SACOS[1].outTable;
        	SACOS[1].inTable  = SACOS[0].inTable;
        	SACOS[0].outTable = SACO.outTable;
        	
        	// c)
        	SACO.inTablePrice      =  SACOS[0].inTablePrice;
        	SACOS[1].inTablePrice  =  SACOS[0].inTablePrice;
        	SACO.inIds             =  SACOS[1].outIds;
        	SACOS[1].inIds         =  SACOS[0].inIds;
        	SACOS[0].outIds        =  SACO.outIds;
   		        	    	
        	};
  }
                  
   rule Saco {
        SACO ::= #Number #Identifier \( LOTES \) compute {
        	SACO.nLotes = LOTES.nLotes;
        	SACO.output = escreve( SACO.nLotes, "lotes" );
        	
        	// b)
        	LOTES.inTable  = SACO.inTable;
        	SACO.outTable  =  LOTES.outTable;
        	
        	// c)
        	SACO.outIds         = newId( SACO.inIds, Integer.valueOf( #Number.value()).intValue() );
        	LOTES.inTablePrice  = SACO.inTablePrice;
        	SACO.custoTotal     = LOTES.custoTotal;
    		if ( inIds.contains( Integer.valueOf(#Number.value()).intValue() ))
			throw new Exception("Cliente already exists!");
        	};
            }

@}

@o Lavanda.lisa
@{
  rule Lotes {
  	LOTES ::= LOTE OUTROS compute {
  		LOTES.nLotes = OUTROS.nLotes + 1;
  		
  		// b)
  		LOTE.inTable    =  LOTES.inTable;
  		OUTROS.inTable  =  LOTE.outTable;
  		LOTES.outTable  =  OUTROS.outTable;
  		
  		// c)
  		
  		LOTE.inTablePrice    =  LOTES.inTablePrice;
  		OUTROS.inTablePrice  =  LOTES.inTablePrice;
  		LOTES.custoTotal     =  LOTE.custoTotal + OUTROS.custoTotal;
  		
  		};
  	}
        
  rule Lote {
       LOTE ::= TIPO #Number compute {
                LOTE.nLotes = 0;
                
                // b)
                LOTE.outTable = updateTablePrice(LOTE.inTable, TIPO.name, 
                                Integer.valueOf(#Number.value()).intValue());
                
                // c)
                LOTE.custoTotal = lookupPrice( LOTE.inTablePrice, TIPO.name ) *
                                  (Integer.valueOf(#Number.value()).intValue());
                
                };
              }
    
  rule Tipo {
       TIPO ::= CLASSE \- TINTO \- FIO compute {
                TIPO.name = CLASSE.name + "/" + TINTO.name + "/" + FIO.name;
                };
               }
               
               
 rule Outros {
       OUTROS ::= compute {
                OUTROS.nLotes = 0;
                
                // b)
                OUTROS.outTable = OUTROS.inTable;
                
                // c) 
                OUTROS.custoTotal = 0;
                
                }
              | \, LOTES compute {
                OUTROS.nLotes = LOTES.nLotes;
                                
                // b)
                LOTES.inTable = OUTROS.inTable;
                OUTROS.outTable = LOTES.outTable;
                
                // c) 
                OUTROS.custoTotal = LOTES.custoTotal;
                LOTES.inTablePrice = OUTROS.inTablePrice;
                };
               }
  
@}
             
@o Lavanda.lisa
@{                             
   rule Classe {
       CLASSE ::= corpo compute {
                CLASSE.name = "corpo";
                }
               |  casa compute {
                  CLASSE.name = "casa";
               };
               }         
               
               
   rule Tinto {
       TINTO ::= br compute {
                TINTO.name = "br";
                }
               | cor compute {
                TINTO.name = "cor";
                };
               }
                                
   rule Fio {
       FIO ::= alg compute {
                FIO.name = "alg";
                }
              | la compute {
                FIO.name = "la";
                }
              | fib compute {
                FIO.name = "fib";
                };
               }
               
                                   
   method Print
	 {
		import java.util.*;

		
		public String escreve(int num, String descripton)
		{
			String str = "\n\nNumero de " + descripton + ": " + num;
			return str;
		}
		
		
		// b)

@}
		
@o Lavanda.lisa
@{		
		public Hashtable initNLotes()
		 { 
			Hashtable env = new Hashtable();
		        env.put("corpo/br/la",0);
       		        env.put("corpo/br/alg",0);
       		        env.put("corpo/br/fib",0);
       		        env.put("corpo/cor/la",0);
       		        env.put("corpo/cor/alg",0);
       		        env.put("corpo/cor/fib",0);
		        env.put("casa/br/la",0);
       		        env.put("casa/br/alg",0);
       		        env.put("casa/br/fib",0);
       		        env.put("casa/cor/la",0);
       		        env.put("casa/cor/alg",0);
       		        env.put("casa/cor/fib",0); 
       		        
       		        return env;
		  }	
		  
		  
		  public Hashtable updateTablePrice(Hashtable inTable, String name, int number)
		 { 
		        inTable = (Hashtable)inTable.clone();
		        int pieces = ((Integer)inTable.get(name)).intValue();
		 	inTable.remove(name);
		 	inTable.put(name,number+pieces);
		 	return inTable;
		 }
		  
		  public String printTable(Hashtable inTable)
		  {
		    String out="\n\n", str="";
		    
		    for (Enumeration et = inTable.keys(); et.hasMoreElements();)
		    {
		      str = (String)et.nextElement();
		      int pieces = ((Integer)inTable.get(str)).intValue();
		      out +=  str + " ----> " + pieces + "\n";
		    }
		    
		    return out;
		  }	 
@}
		
@o Lavanda.lisa
@{	 
		  // c)
		  
		  public Hashtable initTablePrice()
		 { 
			Hashtable env = new Hashtable();
		        env.put("corpo/br/la",1.0);
       		        env.put("corpo/br/alg",2.2);
       		        env.put("corpo/br/fib",3.4);
       		        env.put("corpo/cor/la",4.5);
       		        env.put("corpo/cor/alg",3.7);
       		        env.put("corpo/cor/fib",1.9);
		        env.put("casa/br/la",2.6);
       		        env.put("casa/br/alg",5.3);
       		        env.put("casa/br/fib",7.1);
       		        env.put("casa/cor/la",3.5);
       		        env.put("casa/cor/alg",2.5);
       		        env.put("casa/cor/fib",2.3); 
       		       
       		        return env;
		  }	
		
		public double lookupPrice ( Hashtable in, String name )
		{
		        return ( ((Double)in.get(name)).doubleValue() );
		}
		
                public Vector initIds()
                {
                	return ( new Vector() );
                }
                
		public Vector newId(Vector old, int num)
                {
                	old.addElement(num);
                	return ( (Vector)old.clone() );
                }
                
		public String writePrice(double num)
		{
			return ( "\n\nPreco Total: " + num + "\n" );
		}
		
		
	}
@}

\newpage


\chapter{Example test}

@o Test.txt
@{
10-11-2005 today  1 dani   (corpo-cor-la 1 , casa-cor-alg 2)
                  2 pedro  (casa-br-fib 4)
                  3 celina (corpo-cor-alg 2, corpo-cor-la 3, corpo-cor-fib 1, 
                            casa-cor-alg 2, casa-cor-la 3, casa-cor-fib 1)

@}

\newpage

\chapter{Results}

Before we show some results that we obtain with example mentioned we could show some functionality
that \textsf{LISA} give us, and that help us to understand the compiler to our little language.


\begin{enumerate}

\item

\texttt{Automata:} The automata produced by \textsf{LISA} for \emph{Lavanda} is:\\


\centerline{\includegraphics[width=0.9\linewidth]{automato}}

\item

\texttt{BNF}

\centerline{\includegraphics[width=1\linewidth]{bnf}}


\item

\texttt{Inherited and sinthesized attributes}

See, for example, the tree of inherited and sinthesized attributes for some productions of our grammar.

Consider the follow production:\\

\begin{verbatim}
p1a:  Lavanda  -->  Cabec  Sacos
\end{verbatim}

The inherited and sinthesized attributes are:\\

\centerline{\includegraphics[width=1\linewidth]{prod1}}


Now, consider the follow production:\\

\begin{verbatim}
p3a:  Sacos    -->  Saco
\end{verbatim}


\centerline{\includegraphics[width=1\linewidth]{prod3}}

\item

\texttt{Firs/Follow}

\textsf{LISA} allow us calculate \emph{first} and \emph{follow} of productions.\\

\centerline{\includegraphics[width=1\linewidth]{first_follow}}

\end{enumerate}

So, after this analyse we could show the \emph{output} produced by compiler:

\centerline{\includegraphics[width=0.65\linewidth]{res_lisa}}

\newpage

\chapter{Files}
@f

\end{document}