\documentclass[a4paper]{article} \usepackage{latexsym} \usepackage[portuges]{babel} \usepackage{a4wide} \usepackage[latin1]{inputenc} \usepackage{epsf} \parindent=0pt \parskip=2pt \begin{document} \title{Processamento de Linguagens I\\ LESI + LMCC (3º ano)} \author{2ª Ficha Pr\'{a}tica} \date{Ano Lectivo de 05/06} \maketitle %-------------------------------------------------------------------------- \section{Objectivos} Este ficha pr\'{a}tica cont\'{e}m exerc\'{i}cios para serem resolvidos nas aulas te\'{o}rico-pr\'{a}ticas com vista a sedimentar os conhecimentos relativos a: \begin{itemize} \item uso de Gram\'{a}ticas Independentes de Contexto (GIC) para definir a sintaxe de Linguagens; \item uso de Gram\'{a}ticas Tradutoras (GT) para definir a sem\^{a}ntica est\'{a}tica e din\^{a}mica de Linguagens; \item uso de GT para desenvolver programas eficientes, baseados em algoritmos standard guiados por Tabelas de Decis\~{a}o (constru\'{i}das a partir de Aut\'{o}matos Finitos Deterministas com stack), para reconhecer e processar Linguagens, desencadeando Ac\c c\~{o}es Sem\^{a}nticas espec\'{i}ficas ao reconhecer as produ\c c\~{o}es da gram\'{a}tica; \item gera\c c\~{a}o autom\'{a}tica de programas a partir de especifica\c c\~{o}es formais; \item uso da ferramenta \textsf{Yacc}, dispon\'{i}vel em ambiente \textsf{Linux}, para gera\c c\~{a}o autom\'{a}tica de processadores de linguagens, nomeadamente para cria\c c\~{a}o de \emph{Tradutores Dirigidos pela Sintaxe} (\emph{Analisadores Sint\'{a}cticos} e \emph{Analisadores Sem\^{a}nticos}). \end{itemize} %-------------------------------------------------------------------------- \section{Tradutores Dirigidos pela Sintaxe} No contexto do desenvolvimento de Compiladores, ou mais genericamente de Processadores de Linguagens, o primeiro n\'{i}vel, ou tarefa a implementar, \'{e} a \textbf{an\'{a}lise l\'{e}xica} que tem por miss\~{a}o ler o texto fonte e converter todas as palavras correctas em s\'{i}mbolos terminais dessa linguagem. O segundo n\'{i}vel \'{e} a \textbf{an\'{a}lise sint\'{a}ctica} que pega nos s\'{i}mbolos recebidos do AL e verifica se a sequ\^{e}ncia em causa respeita as regras de deriva\c c\~{a}o, ou produ\c c\~{o}es, da gram\'{a}tica. O terceiro n\'{i}vel \'{e} a \textbf{an\'{a}lise sem\^{a}ntica} que calcula o valor, ou significado, exacto da frase e, ent\~{a}o, valida se a sequ\^{e}ncia de s\'{i}mbolos sintacticamente correcta cumpre todas as condi\c c\~{o}es de contexto que a tornam semanticamente v\'{a}lida. O quarto n\'{i}vel \'{e} a \textbf{tradu\c c\~{a}o} que pega no significado exacto da frase v\'{a}lida e constr\'{o}i, ou calcula, o resultado final.\\ Com esse fim em vista e assumindo que o 1º n\'{i}vel j\'{a} est\'{a} implementado (gra\c cas ao uso do \textsf{Flex} para gerar o \textbf{Analisador L\'{e}xico (AL)}), prop\~{o}e-se para esta aula o recurso \`{a} ferramenta \textsf{Yacc} para gerar os \textbf{Analisadores Sint\'{a}ctico e Sem\^{a}ntico} e o \textbf{Tradutor} a partir da Gram\'{a}tica Tradutora da Linguagem a processar.\\ Para cada um dos exerc\'{i}cios, proceda em tr\^{e}s etapas: \begin{enumerate} \item escreva a GIC e gere o \emph{Parser} (Analisador Sint\'{a}ctico) que lhe permitir\'{a}, apenas, verificar a correc\c c\~{a}o sint\'{a}ctica das frases; \item escreva, depois, uma primeira vers\~{a}o da GT, acrescentando \'{a} GIC anterior as Ac\c c\~{o}es Sem\^{a}nticas necess\'{a}rias para, apenas, validar a correc\c c\~{a}o sem\^{a}ntica das frases; \item escreva, a seguir, uma vers\~{a}o final da GT, acrescentando \'{a} GT anterior as Ac\c c\~{o}es Sem\^{a}nticas necess\'{a}rias para calcular e escrever o resultado desejado. \end{enumerate} %-------------------------------------------------------------------------- \subsection{M\'{a}quina de Venda de Chocolates} Retome o problema 3.1 da Ficha 1, em que se pretende simular o funcionamento de uma m\'{a}quina de vender chocolates dado o stock no in\'{i}cio do dia, a quantia inicial de trocos e os registos das vendas di\'{a}rias.\\ O objectivo, para esta aula, \'{e} calcular \emph{o stock final e o dinheiro acumulado}, considerando todos os pedidos v\'{a}lidos ao longo do dia. O sistema deve ainda assinalar todos os pedidos que n\~{a}o puderam ser satisfeitos, por o chocolate pedido n\~{a}o existir em stock, ou a quantia n\~{a}o ser suficiente.\\ Concretamente, o que se pretende \'{e}: que desenvolva, com aux\'{i}lio do Gerador \textsf{Yacc}, o processador (reconhecedor+calculador e verificador) pedido, tomando por base a gram\'{a}tica da linguagem para descrever o estado inicial da m\'{a}quina e os registos de vendas efectuadas durante o dia---criada na aula anterior (Ficha Pr\'{a}tica 1); utilize o AL desenvolvido tamb\'{e}m nessa aula.\\ Comecemos por considerar o seguinte exemplo (j\'{a} referido na ficha anterior):\\ \textbf{Exemplo} @o exemplo2_1f02.txt @{( STOCK { twix - 0.70 - 5, mars - 0.50 - 1, dove - 0.65- 10, kitkat - 0.60 - 9 } ; TROCOS { 0.1 - 13, 0.2 - 8, 0.5 - 15, 1. - 20, 2. - 10 }; VENDAS { dove - 1.0, mars - 0.7, kitkat - 0.8, kitkat - 0.9, mars - 0.5, dove - 1., twix - 7. } ) @} \textbf{Solu\c c\~{a}o} \begin{description} \item[-] Lex @o ex2_1f02.l @{ %{ #include "y.tab.h" %} stock [Ss][Tt][oO][cC][kK] trocos [tT][rR][oO][cC][oO][sS] vendas [vV][eE][nN][dD][aA][sS] string [a-zA-Z]+ int [1-9][0-9]* real [0-9]+"."[0-9]* separadores [{}(),;-] comentarios "/-"[^-]*"-/"|"/-"[^\n]* %% {stock} { return(STOCK); } {trocos} { return(TROCOS); } {vendas} { return(VENDAS); } {int} { yylval.qt=atoi(yytext); return(INT); } {real} { yylval.pr=atof(yytext); return(REAL); } {string} { yylval.name=strdup(yytext); return(ID); } {separadores} { return(yytext[0]); } {comentarios}|[ \n\t] { ; } . { printf("Unrecognized symbol"); } %% int yywrap(void) { return 1;} @} \item[-] Yacc @o ex2_1f02.y @{ %{ #include #include "mvc.c" MVC *mvc; float money=0.0; %} %union { char *name; int qt; float pr; } %type Nome %type Quantidade %type QuantiaI IdMoeda Preco %token STOCK TROCOS VENDAS %token ID %token REAL %token INT %% MVC : '(' STOCK '{' Stock '}' ';' TROCOS '{' Trocos '}' ';' VENDAS '{' Vendas '}' ')' ; Stock : Descricao | Stock ',' Descricao ; Descricao : Nome '-' Preco '-' Quantidade { mvc = insert(mvc,$1,$3,$5); } ; Trocos : Moeda | Trocos ',' Moeda ; Moeda : IdMoeda '-' Quantidade { money += $1*$3; } ; Vendas : Venda | Vendas ',' Venda ; Venda : Nome '-' QuantiaI { if (lookupQt(mvc,$1) != 0) { money += lookupPrice(mvc,$1); update(mvc,$1); } else printf("\nATENCAO!!! Pedido de %s nao satisfeito!\n",$1); } ; Nome : ID { $$ = $1; } ; Preco : REAL { $$ = $1; } ; Quantidade : INT { $$ = $1; } ; IdMoeda : REAL { $$ = $1; } ; QuantiaI : REAL { $$ = $1; } ; %% int yyerror(char* error) { fprintf(stdout,"Error: %s\n", error); return 0; } int main() { mvc = init(mvc); yyparse(); printf("\n\n\t----------------------------------------------\n"); printf("\t|\tDinheiro Acumulado: %.2f\t |\n",money); printf("\t----------------------------------------------\n"); print(mvc); return 0; } @} \item[-] C\'{o}digo \emph{C} @o mvc.c @{ typedef struct mvc { char *nome; int quantity; float price; struct mvc *next; } MVC; MVC* init(MVC *mvc) { mvc = NULL; return mvc; } MVC* insert(MVC *mvc, char *nome1, float pr, int qt) { if (mvc == NULL) { mvc = (MVC*) malloc(sizeof(MVC)); mvc->nome = nome1; mvc->price = pr; mvc->quantity = qt; } else mvc->next=insert(mvc->next,nome1,pr,qt); return mvc; } float lookupPrice(MVC *mvc,char *nome1) { while (strcmp(nome1,mvc->nome)!=0) mvc = mvc->next; return mvc->price; } int lookupQt(MVC *mvc,char *nome1) { while (strcmp(nome1,mvc->nome)!=0) mvc = mvc->next; return mvc->quantity; } @} @o mvc.c @{ void update(MVC *mvc,char *nome1) { while (strcmp(nome1,mvc->nome)!=0) mvc = mvc->next; mvc->quantity = mvc->quantity-1; } void print(MVC *stock) { printf("\n\n\t---------- Estado final da maquina -----------\n"); printf("\t|\t\t\t\t\t |\n"); printf("\t|\tChocolate |\t Quantidade\t |\n"); printf("\t----------------------------------------------\n"); while(stock!=NULL) { printf("\t|\t%s\t |\t\t%d\t |\n",stock->nome,stock->quantity); stock=stock->next; } printf("\t----------------------------------------------\n"); printf("\n\n"); } @} \end{description} \newpage %-------------------------------------------------------------------------- \subsection{Anu\'{a}rio dos Medicamentos brancos} Considere agora de novo o problema da Ficha 1, desta vez o 3.2, em que se pretende criar um sistema de consulta a esses medicamentos acess\'{i}vel a qualquer farm\'{a}cia via um browser HTML. Como ent\~{a}o foi explicado, esse sistema deve mostrar a informa\c c\~{a}o agrupada por: classe de medicamentos no Symposium Terap\^{e}utico (uma p\'{a}gina por classe, com os medicamentos ordenados alfabeticamente); ou por fabricante (uma p\'{a}gina \'{u}nica, com os medicamentos agrupados por fabricante).\\ No contexto desta aula o que se pretende \'{e}: que desenvolva, com aux\'{i}lio do Gerador \textsf{Yacc}, o processador (reconhecedor+calculador e verificador) pedido, tomando por base a gram\'{a}tica da linguagem para definir o ano a que o Symposium Terap\^{e}utico diz respeito, a lista das classes e de fabricantes v\'{a}lidos, e descrever a informa\c c\~{a}o envolvida no lote de medicamentos a considerar---criada na aula anterior (Ficha Pr\'{a}tica 1); utilize o AL desenvolvido tamb\'{e}m nessa aula. N\~{a}o se esque\c ca que o seu sistema deve detectar e sinalizar todas as situa\c c\~{o}es em que a classe do medicamento ou os fabricantes indicados n\~{a}o sejam v\'{a}lidos (n\~{a}o fa\c cam parte da lista inicial). \textbf{Exemplo} @o exemplo2_2f02.txt @{ Symposium: 2006 [Analgesico,Antibiotico] [ (Moment,1,Analgesico,Paracetemol,4.5,{Roche},{Qualquer-Bial}); (Antigripine,2,Antibiotico,Acetalilico,6.,{Fabt,Faba},{Aga-Fabc,Agb-Fabh}) ] @} \textbf{Solu\c c\~{a}o} \begin{description} \item[-] Lex @o ex2_2f02.l @{ %{ #include "y.tab.h" %} symposium [Ss][Yy][mM][pP][oO][sS][iI][uU][Mm] string [A-Z][a-z]+ ano [0-2][0-9][0-9][0-9] codigo [1-9][0-9]* preco [0-9]+"."[0-9]* sinais [\[\](),;{}:-] comentarios "/-"[^-]*"-/"|"/-"[^\n]* %% {symposium} { return(SYMP); } {string} { return(ID); } {ano} { return(ANO); } {codigo} { return(INT); } {preco} { return(REAL); } {sinais} { return(yytext[0]); } {comentarios}|[ \n\t] { ; } . { printf("Unrecognized symbol"); } %% int yywrap(void) { return 1;} @} \item[-] Yacc @o ex2_2f02.y @{ %{ #include %} %token SYMP ANO ID REAL INT %% SymposiumT : SYMP ':' Ano '[' Classes ']' '[' Medicamentos ']' { printf("Texto reconhecido!"); } ; Classes : Nome | Classes ',' Nome ; Medicamentos : Medicamento | Medicamentos ';' Medicamento ; Medicamento : '(' Nome ',' Cod ',' NomeC ',' Comp ',' Pr ',' '{' Fabs '}' ',' '{' MedEq '}' ')' ; Fabs : NFab | Fabs ',' NFab ; MedEq : MedEq1 | MedEq ',' MedEq1 ; MedEq1 : Nome '-' NFab ; Ano : ANO ; Nome : ID ; NomeC : ID ; Comp : ID ; NFab : ID ; Pr : REAL ; Cod : INT ; %% int yyerror(char* error) { fprintf(stdout,"Error: %s\n", error); return 0; } int main() { return yyparse(); } @} \end{description} \newpage %-------------------------------------------------------------------------- \subsection{Documento anotado em XML} Neste caso pretende-se processar Documentos \textsf{XML}---textos vulgares semeados de anota\c c\~{o}es, ou marcas, tal como descrito no exerc\'{i}cio 3.3 da Ficha 1.\\ Tomando por base a descri\c c\~{a}o de Documento \textsf{XML} a\'{i} apresentada, pretende-se desenvolver um programa que valide se toda a marca que abre fecha, pela ordem correcta (uma marca aberta dentro de outra, ter\'{a} de fechar antes da primeira), e que liste todas as marcas encontradas indicando a frequ\^{e}ncia de cada uma (n\'{u}mero de ocorr\^{e}ncias sobre o total de marcas). O processador tamb\'{e}m deve verificar que a mesma marca abre sempre associada ao mesmo conjunto de atributos. Se o documento-fonte for v\'{a}lido, deve ent\~{a}o ser gerada uma vers\~{a}o \LaTeX\ em que cada fragmento de texto marcado \'{e} assinalado entre chavetas precedidas por um comando \LaTeX\ cujo nome \'{e} igual ao nome do elemento.\\ % No contexto desta aula o que se pretende \'{e}: que desenvolva, com aux\'{i}lio do Gerador \textsf{Yacc}, o processador (reconhecedor+calculador e verificador) pretendido, tomando por base a gram\'{a}tica de um Documento \textsf{XML} criada na aula anterior (Ficha Pr\'{a}tica 1); utilize o AL desenvolvido tamb\'{e}m nessa aula. \newpage \textbf{Solu\c c\~{a}o - 1a Parte} \begin{itemize} \item Lex @o ex2_3f02.l @{ %{ #include #include "y.tab.h" %} id [A-Z][a-z]+ string \"[^"]*\" %x FimMarca %% {id} { yylval.name=strdup(yytext); return ID; } {string} { return VAL; } \>/[ \t\n]*\< { return(BD); } \< { return BEA; } \> { BEGIN FimMarca; return BD; } \= { return IG; } \/ { return BEF; } \< { unput(yytext[0]); BEGIN INITIAL; } . { yylval.name=strdup(yytext); return PCDATA; } [ \n] { ; } %% int yywrap() { return 1; } @} \newpage \item Yacc @o ex2_3f02.y @{%{ #include #include "list.c" int open = 0, close = 0; char * abre; %} %union { int number; char *name; } %token ID VAL PCDATA %token IG BEA BEF BD %type IdEle %start DocXML @} @o ex2_3f02.y @{ %% DocXML : MarcAbre Conteud MarcFech { printf("Marcas Abertura: %d.\n", open); printf("Marcas Fecho: %d.\n\n", close); } ; MarcAbre : BEA Elem BD { open++; } ; MarcFech : BEA BEF IdEle BD { close++; abre = pop(); if (strcmp(abre,$3)!=0) { printf("Documento mal formado!\n"); exit(0); } } ; Elem : IdEle Atribs { push($1); } ; Atribs : Atribs Atrib | ; Atrib : IdAtr IG VAL ; Conteud : Compon | Conteud Compon ; Compon : MarcAbre | MarcFech | PCDATA ; IdEle : ID ; IdAtr : ID ; %% int yyerror(char* error) { fprintf(stdout,"Error: %s\n", error); return 0; } int main() { initList(); return yyparse(); } @} \newpage \item C\'{o}digo \emph{C} @o list.c @{ char * list[50]; void initList() { int i = 0; for (i = 0; i < 50; i++) list[i] = NULL; } void push(char *pal) { int i=0; while(list[i]!=NULL && i < 50) i++; list[i] = pal; } char* pop() { int i=0; char *aux; while(list[i]!=NULL && i < 50) { i++; } aux = list[i-1]; list[i-1]=NULL; return aux; } @} \item Exemplo de teste @o exemplo2_3f02.txt @{ some text @} \end{itemize} %-------------------------------------------------------------------------- \section{Makefile} @o makefile @{# ex2_1 ex21: lex ex2_1f02.l yacc -d ex2_1f02.y gcc lex.yy.c y.tab.c -o ex21 # ex2_2 ex22: lex ex2_2f02.l yacc -d ex2_2f02.y gcc lex.yy.c y.tab.c -o ex22 # ex2_3 ex2_3: lex ex2_3.l yacc -d ex2_3.y gcc lex.yy y.tab.c -o ex23 # clean clean: rm -f y.tab.c y.tab.c lex.yy.c rm ex21 ex22 ex23 @} \section{Ficheiros} @f \end{document}