% % 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 LRC} \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{LRC} implementation} \section{Context Free Grammar} @o CFG.ssl @{ /*********************************** Scanner ***********************************/ WHITESPACE : < [\ \t\n]+ >; DM : < [0-3][0-9] >; YEAR : < [0-2][0-9][0-9][0-9] >; NUMBER : < [0-9]+ >; CORPO : < "corpo" >; CASA : < "casa" >; COR : < "cor" >; BR : < "br" >; ALG : < "alg" >; FIB : < "fib" >; LA : < "la" >; IDENTIFIER : < [a-z]+ >; /******************************** Parser ********************************/ lavanda { syn Lavanda ast; }; lavanda ::= (cabec sacos ) { $$.ast = RootLavanda( sacos.ast ); } ; cabec { syn Cabec ast ; }; cabec ::= (data IDENTIFIER) { $$.ast = NoSyn(); } ; @} @o CFG.ssl @{ data { syn Cabec ast; }; data ::= (DM '-' DM '-' YEAR) { $$.ast = NoSyn(); }; sacos { syn Sacos ast ; } ; sacos ::= ( saco moreSacos ) { $$.ast = ConsSacos(saco.ast,moreSacos.ast); }; moreSacos { syn Sacos ast; }; moreSacos ::= () { $$.ast = NoSacos(); } | ( sacos ) { $$.ast = sacos.ast; }; saco { syn Saco ast ; } ; saco ::= (NUMBER IDENTIFIER '(' lotes ')' ) { $$.ast = ConsSaco(IDENTIFIER,STRtoINT(NUMBER),lotes.ast); } ; lotes { syn Lotes ast; }; lotes ::= ( lote outros ) { $$.ast = ConsLotes(lote.ast,outros.ast); }; lote { syn Lote ast; }; lote ::= ( tipo NUMBER ) { $$.ast = ConsLote(tipo.ast,STRtoINT(NUMBER)); }; @} @o CFG.ssl @{ outros { syn Lotes ast; }; outros ::= () { $$.ast = NoLotes(); } | ( ',' lotes ) { $$.ast = lotes.ast; }; tipo { syn Tipo ast; }; tipo ::= (classe '-' tinto '-' fio ) { $$.ast = ConsName(classe.ast,tinto.ast,fio.ast); }; classe { syn Name ast; }; classe ::= ( CORPO ) { $$.ast = ConsStr("corpo"); } | ( CASA ) { $$.ast = ConsStr("casa"); }; tinto { syn Name ast; }; tinto ::= ( COR ) { $$.ast = ConsStr("cor"); } | ( BR ) { $$.ast = ConsStr("br"); }; fio { syn Name ast; }; fio ::= ( FIB ) { $$.ast = ConsStr("fib"); } | ( LA ) { $$.ast = ConsStr("la"); } | ( ALG ) { $$.ast = ConsStr("alg"); }; @} \newpage \section{Abstract Syntax Tree} @o AST.ssl @{ Lavanda ~ lavanda.ast ; root Lavanda; Lavanda : RootLavanda (Sacos) ; Cabec : NoSyn () ; Sacos : NoSacos () | ConsSacos (Saco Sacos) ; Saco : NoSaco() | ConsSaco (STR INT Lotes) ; Lotes : NoLotes() | ConsLotes ( Lote Lotes) ; Lote : ConsLote ( Tipo INT) ; Tipo : ConsName(Name Name Name); Name : ConsStr(STR); @} \newpage \section{Semantics} @o Semantics.ssl @{ /*************** Attributes ***************/ /***** b) *****/ list tableLotes; tableLotes : Empty() | ConsTableLotes ( STR INT tableLotes); tableLotes: Empty [ \at ::= "" ] | ConsTableLotes [ \at ::= "\t" \at "\t\t" \at "\n" \at ]; /***** c) *****/ list tablePrice; tablePrice: EmptyPrice() | ConsTablePrice( STR REAL tablePrice); tablePrice: EmptyPrice [ \at ::= ""] | ConsTablePrice [ \at ::= "\t" \at "\t\t" \at "\n\n" \at]; list idSacos; idSacos: EmptyIds() | ConsIdSacos (INT idSacos); idSacos: EmptyIds [ \at ::= "" ] | ConsIdSacos [ \at ::= "\t" \at "\n\n" \at]; /******/ Lavanda { syn INT nSacos; syn tableLotes tLotesOut; } ; @} @o Semantics.ssl @{ Lavanda : RootLavanda { local STR numSacos; local tableLotes tLotes; numSacos = "\n\nNumero de sacos: " # INTtoSTR($$.nSacos) # "\n\n"; $$.nSacos = Sacos.nSacos; /* b) */ tLotes = $$.tLotesOut; Sacos.tLotesIn = initEnv(Empty()); $$.tLotesOut = Sacos.tLotesOut; /* c) */ Sacos.tPriceIn = initEnvPrice(EmptyPrice()); Sacos.inIds = EmptyIds(); }; Sacos { syn INT nSacos; /* b) */ inh tableLotes tLotesIn; syn tableLotes tLotesOut; /* c) */ inh tablePrice tPriceIn; inh idSacos inIds; syn idSacos outIds; }; Sacos : NoSacos { $$.nSacos = 0; $$.tLotesOut = $$.tLotesIn; /* c) */ $$.outIds = $$.inIds; } | ConsSacos { $$.nSacos = Sacos$2.nSacos + 1; /* b) */ Saco.tLotesIn = $$.tLotesIn; Sacos$2.tLotesIn = Saco.tLotesOut; $$.tLotesOut = Sacos$2.tLotesOut; /* c) */ Saco.tPriceIn = $$.tPriceIn; Sacos$2.tPriceIn = $$.tPriceIn; Saco.inIds = $$.inIds; Sacos$2.inIds = Saco.outIds; $$.outIds = Sacos$2.outIds; }; @} @o Semantics.ssl @{ Saco { syn INT nLotes; /* b) */ inh tableLotes tLotesIn; syn tableLotes tLotesOut; /* c) */ inh tablePrice tPriceIn; syn REAL custoTotal; inh idSacos inIds; syn idSacos outIds; }; Saco : NoSaco { /* b) */ $$.nLotes = 0; $$.tLotesOut = $$.tLotesIn; /* c) */ $$.custoTotal = 0.0; $$.outIds = $$.inIds; } | ConsSaco { local STR infLotesPrice; local STR erro; infLotesPrice = "\nNumero de lotes no saco n. " # INTtoSTR(INT) # ": " # INTtoSTR($$.nLotes) # "\nPreco total: " # REALtoSTR($$.custoTotal); $$.nLotes = Lotes.nLotes; /* b) */ Lotes.tLotesIn = $$.tLotesIn; $$.tLotesOut = Lotes.tLotesOut; /* c) */ Lotes.tPriceIn = $$.tPriceIn; $$.custoTotal = Lotes.custoTotal; $$.outIds = joinId($$.inIds,INT); erro = belongId($$.inIds,INT) ? "Erro: saco ja existente!" : ""; }; Lotes { syn INT nLotes; /* b) */ inh tableLotes tLotesIn; syn tableLotes tLotesOut; /* c) */ inh tablePrice tPriceIn; syn REAL custoTotal; }; @} @o Semantics.ssl @{ Lotes: NoLotes { /* a) */ $$.nLotes = 0; /* b) */ $$.tLotesOut = $$.tLotesIn; /* c) */ $$.custoTotal = 0.0; } | ConsLotes { $$.nLotes = Lotes$2.nLotes + 1; /* b) */ Lote.tLotesIn = $$.tLotesIn; Lotes$2.tLotesIn = Lote.tLotesOut; $$.tLotesOut = Lotes$2.tLotesOut; /* c) */ Lote.tPriceIn = $$.tPriceIn; Lotes$2.tPriceIn = $$.tPriceIn; $$.custoTotal = Lote.custoTotal + Lotes$2.custoTotal; }; Lote { /* b) */ inh tableLotes tLotesIn; syn tableLotes tLotesOut; /* c) */ inh tablePrice tPriceIn; syn REAL custoTotal; }; Lote: ConsLote { /* b) */ $$.tLotesOut = changeTableLotes($$.tLotesIn,Tipo.name,INT); /* c) */ $$.custoTotal = lookupPrice($$.tPriceIn,Tipo.name) * INTtoREAL(INT); }; @} @o Semantics.ssl @{ Tipo { syn STR name; }; Tipo : ConsName { $$.name = Ident(Name$1) # "-" # Ident(Name$2) # "-" # Ident(Name$3); }; /***** b) **********/ tableLotes initEnv(tableLotes table) { with(table) ( Empty() : ConsTableLotes("corpo-br-la",0, ConsTableLotes("corpo-br-fib",0, ConsTableLotes("corpo-br-alg",0, ConsTableLotes("corpo-cor-la",0, ConsTableLotes("corpo-cor-fib",0, ConsTableLotes("corpo-cor-alg",0, ConsTableLotes("casa-br-la",0, ConsTableLotes("casa-br-fib",0, ConsTableLotes("casa-br-alg",0, ConsTableLotes("casa-cor-la",0, ConsTableLotes("casa-cor-fib",0, ConsTableLotes("casa-cor-alg",0,Empty())))))))))))) , * : Empty() ) }; @} @o Semantics.ssl @{ tableLotes changeTableLotes(tableLotes table,STR name, INT num) { with(table) ( Empty() : Empty(), ConsTableLotes(name1,num1,tail) : (name1 == name) ? ConsTableLotes(name,num+num1,tail) : ConsTableLotes(name1, num1, changeTableLotes(tail,name,num)) ) }; STR Ident(Name s) { with(s) (ConsStr(s1): s1, * : "" ) }; /******** c) ********/ tablePrice initEnvPrice(tablePrice table) { with(table) ( EmptyPrice() : ConsTablePrice("corpo-br-la",1.0, ConsTablePrice("corpo-br-fib",2.2, ConsTablePrice("corpo-br-alg",3.4, ConsTablePrice("corpo-cor-la",4.5, ConsTablePrice("corpo-cor-fib",1.9, ConsTablePrice("corpo-cor-alg",3.7, ConsTablePrice("casa-br-la",2.6, ConsTablePrice("casa-br-fib",7.1, ConsTablePrice("casa-br-alg",5.3, ConsTablePrice("casa-cor-la",3.5, ConsTablePrice("casa-cor-fib",2.3, ConsTablePrice("casa-cor-alg",2.5,EmptyPrice())))))))))))) , * : EmptyPrice() ) }; @} @o Semantics.ssl @{ REAL lookupPrice(tablePrice table,STR name) { with(table) ( EmptyPrice() : 0.0, ConsTablePrice(name1,num1,tail) : (name1 == name) ? num1 : lookupPrice(tail,name) ) }; idSacos joinId(idSacos ids, INT numSaco) { with(ids) ( EmptyIds() : ConsIdSacos(numSaco,EmptyIds()), ConsIdSacos(num,tail) : ConsIdSacos(num,joinId(tail,numSaco)) ) }; BOOL belongId(idSacos ids, INT numSaco) { with(ids) ( EmptyIds() : false, ConsIdSacos(num,tail) : (num == numSaco) ? true : belongId(tail,numSaco) ) }; @} \newpage \section{Unparsing} @o Unparsing.ssl @{ Lavanda : RootLavanda [ \at ::= \at numSacos "Tabela Lotes:\n\t -Descricao- \t -N. Lotes-\n" tLotes] ; Cabec : NoSyn [ \at ::= ""] ; Sacos : ConsSacos [ \at ::= \at " " \at ] ; Saco : ConsSaco [ \at ::= infLotesPrice " " erro] ; @} \section{Makefile} @o makefileLRC @{ RUNLRC=perl -S -w /usr/local/lrc/bin/runlrc.pl SSL_SOURCES = LavandaCFG.ssl attributes.ssl LRC_OPTIONS = -no_warnings -remove_deadends -v2c_code eva : code.ivr bcode.ieq $(RUNLRC) +4 -4 $(LRC_OPTIONS) bcode.ieq code.ivr : $(SSL_SOURCES) $(RUNLRC) -3 $(LRC_OPTIONS) $(SSL_SOURCES) clean : $(RUNLRC) -clean rm -f eva rm -f bcode.* rm -f code.* rm -f Save.* @} \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} \begin{verbatim} [_localhost_LavandaLRC]$ ./eva -O Teste.test entering output descriptor: attr='(null)' view='BASEVIEW' file='(null)' /**** processing file Teste.test ****/ Unparse decorated term Numero de lotes no saco n. 1: 2 Preco total: 9.5 Numero de lotes no saco n. 2: 1 Preco total: 28.4 Numero de lotes no saco n. 3: 6 Preco total: 40.6 Numero de sacos: 3 Tabela Lotes: -Descricao- -N. Lotes- corpo-br-la 0 corpo-br-fib 0 corpo-br-alg 0 corpo-cor-la 4 corpo-cor-fib 1 corpo-cor-alg 2 casa-br-la 0 casa-br-fib 4 casa-br-alg 0 casa-cor-la 3 casa-cor-fib 1 casa-cor-alg 4 \end{verbatim} \newpage \newpage \chapter{Files} @f \end{document}