\documentclass[a4paper]{article} \newif\ifshowcode \showcodetrue \usepackage{latexsym} \usepackage[portuges]{babel} \usepackage{a4wide} \usepackage[latin1]{inputenc} \parindent=0pt \parskip=2pt \newtheorem{questao}{Quest\~{a}o} \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{Processamento de Linguagens I\\ LESI + LMCC (3º ano)} \author{3º Ficha Pr\'{a}tica} \date{Ano Lectivo de 05/06} \begin{document} \pagenumbering{arabic} \maketitle \section{Objectivos} Este ficha pr\'{a}tica cont\'{e}m 1 exerc\'{i}cio para ser resolvido nas aulas te\'{o}rico-pr\'{a}ticas com vista a consolidar definitivamente os conhecimentos pr\'{a}ticos 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} Na medida em que esta ficha tem por objectivo refor\c car os conhecimentos e aptid\~{o}es que os alunos devem ter adquirido ao resolver a Ficha 2, come\c ca-se por relembrar os conceitos b\'{a}sicos a\'{i} introduzidos.\\ 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ê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ê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.\\ Tendo em vista o a consolida\c c\~{a}o da capacidade de desenvolver PLs com recurso a Geradores de Compiladores, prop\~{o}e-se para esta aula o recurso à ferramenta \textsf{Flex} para gerar o \textbf{Analisador L\'{e}xico (AL)}), e o recurso à 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 resolver o exerc\'{i}cio proposto, proceda em etapas: \begin{enumerate} \item escreva a GIC; identifique os s\'{i}mbolos terminais, descreva-os à custa de Express\~{o}es Regulares e gere o AL; 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 à 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 à GT anterior as Ac\c c\~{o}es Sem\^{a}nticas necess\'{a}rias para calcular e escrever o resultado desejado. \end{enumerate} %-------------------------------------------------------------------------- \subsection{Gerador de Indices Remissivos} Considere uma situa\c c\~{a}o em que se pretende gerar automaticamente, a partir de uma descri\c c\~{a}o como a que se ilustra abaixo, o \'{I}ndice Remissivo a inserir no fim de um determinado documento. Recorda-se que um \'{I}ndice Remissivo \'{e} uma lista, ordenada alfabeticamente, de todos os termos a destacar num documento, com a indica\c c\~{a}o das p\'{a}ginas do documento onde cada termo foi definido.\\ A descri\c c\~{a}o inicial, escrita de acordo com uma linguagem espec\'{i}fica que dever\'{a} ser definida para o efeito, permite indicar para cada p\'{a}gina (referida pelo seu número ou nome do apêndice) a lista de termos a destacar. Abaixo ilustra-se uma frase v\'{a}lida da dita Linguagem: @o exemplo.txt @{ INDICE 1 = processador, linguagem, compilador 2 = compilador, interpretador, gramatica 3 = gramatica, GR, GIC 4 = gramatica, linguagem, reconhecedor A = gramatica, YACC B = LRC, LISA FIM DO INDICE @} O \'{I}ndice que deve ser gerado para este exemplo \'{e} apresentado a seguir: \begin{verbatim} INDICE REMISSIVO processador: 1 linguagem: 1 4 compilador: 1 2 interpretador: 2 gramatica: 2 3 4 A GR: 3 GIC: 3 reconhecedor: 4 YACC: A LRC: B LISA: B \end{verbatim} No contexto desta aula o que se pretende \'{e}: que escreva a gram\'{a}tica que define a linguagem pretendida e que desenvolva, com aux\'{i}lio dos Geradores \textsf{Lex} e \textsf{Yacc} e seguindo os passos acima, o processador (reconhecedor+calculador e verificador) necess\'{a}rio, tomando por base essa gram\'{a}tica. %-------------------------------------------------------------------------- \newpage \section{Resolu\c c\~{a}o:} \subsection{Vers\~ao 1} \subsubsection{Lex} @o ex2_1f03.l @{ %{ #include "y.tab.h" %} integer [0-9] charI [aA-zZ] pal [aA-zZ]+ %% "FIM DO INDICE" { return FIM; } "INDICE" { return INDICE; } \=|\, { return yytext[0]; } {integer} { yylval.id = strdup(yytext); return IND_INT; } {charI} { yylval.id = strdup(yytext); return IND_CHAR; } {pal} { yylval.id = strdup(yytext); return PAL; } [ \n\t] %% int yywrap(void) { return 1;} @} \newpage \subsubsection{Yacc} @o ex2_1f03v1.y @{%{ #include #include "term.c" Term *newList; char *indexT; %} %union { char *id; } %token INDICE FIM %token IND_INT IND_CHAR %token PAL %start IndiceRemissivo %% IndiceRemissivo : INDICE ListaInd FIM { print(newList); } ; ListaInd : Elem | ListaInd Elem ; Elem : Ident '=' Termos ; Ident : IND_INT { indexT = strdup($1); } | IND_CHAR { indexT = strdup($1); } ; Termos : Termo | Termos ',' Termo ; Termo : PAL { newList = insert(newList,$1,indexT); } ; %% int yyerror(char* error) { fprintf(stdout,"Error: %s\n", error); return 0; } int main() { newList = initList(); yyparse(); return 0; } @} \newpage \subsection{C\'{o}digo \emph{C}} @o term.c @{ #include #define MAX 10 typedef struct termList { char *identifier; char *index[MAX]; struct termList *next; } Term; Term* initList() { return NULL; } Term* insert(Term *term, char *name, char* ind) { int i = 0; if (term == NULL) { term = (Term*) malloc(sizeof(Term)); term->identifier = name; term->index[0] = ind; } else { if (strcmp(name,term->identifier)==0) { while(term->index[i]!=NULL) i++; term->index[i]=ind; } else term->next=insert(term->next,name,ind); } return term; } void print(Term *term) { int i; printf("\n\nINDICE REMISSIVO\n"); while (term!=NULL) { printf("\t%s: ", term->identifier); for (i = 0; i < MAX; i++) if (term->index[i] != NULL) printf("%s ", term->index[i]); else break; printf("\n"); term = term->next; } printf("\n"); } @} \subsection{Vers\~{a}o 2} @o ex2_1f03v2.l @{ %{ #include "indice_remissivo.h" #include "indice.tab.h" int lineno = 1; %} %option noyywrap %% INDICE { return INIINDICE; } FIM[ ]+DO[ ]+INDICE { return FIMINDICE; } "=" { return IGUAL; } "," { return VIRGULA; } [0-9]+ { yylval.numero = atoi(yytext); return INDICE; } [A-Z][0-9]* { yylval.string = strdup(yytext); return APENDICE; } [a-zA-Z][a-zA-Z]+ { yylval.string = strdup(yytext); return TERMO; } [ \t\r] \n { lineno++; } %% @} \newpage @o ex2_1f03v2.y @{%{ #include "indice_remissivo.h" extern int lineno; extern char *yytext; listaEntradas *parse_result = NULL; void yyerror( const char *msg) { fprintf( stderr, "Erro linha %d: %s - %s\n", lineno, yytext, msg); } %} %union { int numero; char *string; seccao *s; listaPalavras *palavras; entrada *e; listaEntradas *l; } %token INIINDICE "INDICE" %token FIMINDICE "FIM DO INDICE" %token IGUAL "=" %token VIRGULA "," %token INDICE %token APENDICE %token TERMO %type seccao %type lstpalavras %type entrada %type lstentradas %% indice: "INDICE" lstentradas "FIM DO INDICE" { parse_result = $2; } ; lstentradas: entrada { $$ = listaEntradas_new( $1); } | lstentradas entrada { $$ = listaEntradas_insert( $1, $2); } ; entrada: seccao "=" lstpalavras { $$ = entrada_new( $1, $3); } ; seccao: INDICE { $$ = seccao_new_indice( $1); } | APENDICE { $$ = seccao_new_apendice( $1); } ; lstpalavras: TERMO { $$ = listaPalavras_new( $1); } | lstpalavras "," TERMO { $$ = listaPalavras_insert( $1, $3); } ; %% int main(void) { if( yyparse() == 0) { printf( "O ficheiro foi processado com sucesso!\n"); } prettyprint( parse_result); return 0; } @} \newpage @o indice_remissivo.h @{ #ifndef _INDICE_REMISSIVO_H_ #define _INDICE_REMISSIVO_H_ #include #include #include enum tipo_seccao { SECCAO_INDICE, SECCAO_APENDICE }; typedef struct _seccao_ { enum tipo_seccao tipo; union { int indice; char *apendice; } u; } seccao; typedef struct _listaPalavras_ { char *palavra; struct _listaPalavras_ *next; } listaPalavras; typedef struct _entrada_ { seccao *s; listaPalavras *lista; } entrada; typedef struct _listaEntradas_ { entrada *e; struct _listaEntradas_ *next; } listaEntradas; void prettyprint( listaEntradas *lst); listaEntradas *listaEntradas_new( entrada *e); listaEntradas *listaEntradas_insert( listaEntradas *lista, entrada *e); entrada *entrada_new( seccao *s, listaPalavras *lista); listaPalavras *listaPalavras_new( char *p); listaPalavras *listaPalavras_insert( listaPalavras *lista, char *p); void listaPalavras_print( listaPalavras *lista); seccao *seccao_new_indice( int i); seccao *seccao_new_apendice( char *s); #endif @} \newpage @o indice_remissivo.c @{ #include "indice_remissivo.h" void print_entrada( entrada *e); void print_seccao( seccao *s); void prettyprint( listaEntradas *lst) { printf( "INDICE\n"); for( ; lst != NULL; lst = lst ->next) { print_entrada(lst->e); } printf( "FIM DO INDICE\n"); } void print_entrada( entrada *e) { listaPalavras *lst = NULL; print_seccao(e->s); for(lst = e->lista; lst != NULL; lst = lst->next) { printf("%s", lst->palavra); if( lst->next != NULL) printf(", "); else printf("\n"); } } void print_seccao( seccao *s) { if(s->tipo == SECCAO_INDICE) { printf( "%d = ", s->u.indice); } else if( s->tipo == SECCAO_APENDICE) { printf( "%s = ", s->u.apendice); } } listaEntradas *listaEntradas_new( entrada *e) { listaEntradas *res = NULL; res = (listaEntradas *) calloc( 1, sizeof(listaEntradas)); if( res == NULL) return NULL; res->e = e; return res; } listaEntradas *listaEntradas_insert( listaEntradas *lista, entrada *e) { listaEntradas *res = NULL; res = listaEntradas_new(e); if( res == NULL) return NULL; res->next = lista; return res; } entrada *entrada_new( seccao *s, listaPalavras *lista) { entrada *res = NULL; res = (entrada *) calloc( 1, sizeof(entrada)); if( res == NULL) return NULL; res->s = s; res->lista = lista; return res; } listaPalavras *listaPalavras_new( char *p) { listaPalavras *res = NULL; res = (listaPalavras *) calloc( 1, sizeof(listaPalavras)); if( res == NULL) { return NULL; } res->palavra = strdup(p); return res; } listaPalavras *listaPalavras_insert( listaPalavras *lista, char *p) { listaPalavras *res = NULL; res = listaPalavras_new( p); if( res == NULL) { return NULL; } res->next = lista; return res; } void listaPalavras_print( listaPalavras *lista) { while( lista != NULL) { printf("%s\n", lista->palavra); lista = lista->next; } } seccao *seccao_new_indice( int i) { seccao *res = NULL; res = (seccao *) calloc( 1, sizeof(seccao)); res->tipo = SECCAO_INDICE; res->u.indice = i; return res; } seccao *seccao_new_apendice( char *s) { seccao *res = NULL; res = (seccao *) calloc( 1, sizeof(seccao)); res->tipo = SECCAO_APENDICE; res->u.apendice = strdup(s); return res; } @} \section{Ficheiros} @f \end{document}