\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{1 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 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 Express\~{o}es Regulares para definir (gerar) Linguagens Regulares; \item uso de Express\~{o}es Regulares para desenvolver programas eficientes, baseados em algoritmos standard guiados por Aut\'{o}matos Finitos Deterministas, para reconhecer Linguagens Regulares; \item uso de Aut\'{o}matos Deterministas Reactivos, para processar Linguagens Regulares, isto \'{e} para desencadear Ac\c c\~{o}es espec'{i}ficas ao reconhecer frases que derivam de Padr~{o}es (definidos com base em ERs) ---princ\'{i}pio da Programa\c c\~{a}o baseada em regras \emph{Condi\c c\~{a}o-Rea\c c\~{a}o}; \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{Flex}, dispon\'{i}vel em ambiente \textsf{Linux}, para gera\c c~{a}o autom\'{a}tica de processadores de linguagens regulares, nomeadamente para cria\c c~{a}o de \emph{Filtros de Texto} ou de \emph{Analisadores L\'{e}xicos}. \end{itemize} %-------------------------------------------------------------------------- \section{Filtros de Texto} Para introduzir a ferramenta de gera\c c\~{a}o de programas \textsf{FLex} baseada em especificacoes com Expressoes Regulares, e para sedimentar os conhecimentos que adquiriu sobre automatos deterministas reactivos como suporte a construcao de programas eficientes, prop\~{o}em-se alguns exerc\'{i}cios, para resolver dentro ou fora da aula, que visam a cria\c c\~{a}o de programas aut\'{o}nomos para filtrar textos (\textbf{FT}). \subsection{Processador de Question\'{a}rios} Suponha que ao fim de cada entrevista um Rep\'{o}rter produz um texto com as perguntas e respostas, distinguindo umas das outras porque as perguntas come\c cam com "EU:", no in\'{i}cio da linha, e as respostas come\c cam com "ELE:", tamb\'{e}m no in\'{i}cio da linha.\\ Nesse contexto, pretende-se desenvolver um \textsf{FT} para processar os question\'{a}rios que: \begin{description} \item[a)] simplesmente retire do texto original as tais marcas "EU:" e "ELE:", devolvendo todo o resto da entrevista sem qualquer altera\c c\~{a}o.\\ \textbf{Solu\c c\~{a}o:\\} @o ex2_1a1.l -i @{ EU EU: ELE ELE: %% ^{EU} { } ^{ELE} { } %% int yywrap(void) { return 1;} int main( int argc, char **argv ) { ++argv, --argc; /* skip over program name */ if ( argc > 0 ) yyin = fopen( argv[0], "r" ); else yyin = stdin; yylex(); } @} \begin{verbatim} \end{verbatim} Melhore o filtro, de modo a tratar as marcas, quer estejam escritas em mai\'{u}sculas, quer em min\'{u}sculas; \textbf{Solu\c c\~{a}o\\} Aqui a \'{u}nica altera\c c\~{a}o que se pretende \'{e} ao n\'{i}vel das express\~{o}es regulares definidas. Ou seja, @o ex2_1a2.l @{ EU [Ee][Uu]: ELE [Ee][Ll][Ee]: %% ^{EU} { } ^{ELE} { } %% int yywrap(void) { return 1;} int main( int argc, char **argv ) { ++argv, --argc; /* skip over program name */ if ( argc > 0 ) yyin = fopen( argv[0], "r" ); else yyin = stdin; yylex(); } @} Assim, com o seguinte teste: @o ex2_1.txt @{ eU: Porque se interessa tanto por esta area? ElE: Nao sei, desde pequeno tive um grande fascinio pela natureza. Eu: Ha quantos anos trabalha nisto? ELe: Cerca de 20 anos. @} \bigskip O resultado de execu\c c\~{a}o ser\'{a}: \begin{verbatim} Porque se interessa tanto por esta area? Nao sei, desde pequeno tive um grande fascinio pela natureza. Ha quantos anos trabalha nisto? Cerca de 20 anos. \end{verbatim} \item[b)] substitua a marca "EU:" pela palavra "Entrevistador" e a marca "ELE" por "Entrevistado"; @o ex2_1b.l @{ EU [Ee][Uu] ELE [Ee][Ll][Ee] %% ^{EU} { printf("Entrevistador"); } ^{ELE} { printf("Entrevistado"); } %% int yywrap(void) { return 1;} int main( int argc, char **argv ) { ++argv, --argc; /* skip over program name */ if ( argc > 0 ) yyin = fopen( argv[0], "r" ); else yyin = stdin; yylex(); } @} O resultado de execu\c c\~{a}o obtido (com o exemplo anterior): \begin{verbatim} Entrevistador: Porque se interessa tanto por esta area? Entrevistado: Nao sei, desde pequeno tive um grande fascinio pela natureza. Entrevistado: Ha quantos anos trabalha nisto? Entrevistado: Cerca de 20 anos. \end{verbatim} \item[c)] substitua a marca "EU" pelo nome do entrevistador e a marca "ELE:" pelo nome do entrevistado, supondo que no in\'{i}cio encontrar\'{a} as respectivas defini\c c\~{o}es (ordem irrelevante) na forma "EU=nome." ou "ELE=nome."\footnote{Al\'{i}nea proposta para pensar fora da aula.} \end{description} \textbf{Solu\c c\~{a}o} @o ex2_1c.l @{ %{ #include char *nomeEu; char *nomeEle; %} EU [Ee][Uu] ELE [Ee][Ll][Ee] %% {EU}"="[^.]+"." { yytext[yyleng-1]='\0'; nomeEu = (char*) strdup(&yytext[3]); } {ELE}"="[^.]+"." { yytext[yyleng-1]='\0'; nomeEle = (char*) strdup(&yytext[4]); } ^{EU}/":" { printf("%s", nomeEu); } ^{ELE}/":" { printf("%s", nomeEle); } %% int yywrap(void) { return 1; } int main(int argc, char **argv ) { ++argv, --argc; /* skip over program name */ if ( argc > 0 ) yyin = fopen( argv[0], "r" ); else yyin = stdin; yylex(); } @} Assim com o exemplo anterior, acrescentando apenas as duas defini\c c\~{o}es para os nomes no \'{i}nicio do texto: @o ex2_1c.txt @{ eu=Andreia. eLe=Ana. eU: Porque se interessa tanto por esta area? ElE: Nao sei, desde pequeno tive um grande fascinio pela natureza. Eu: Ha quantos anos trabalha nisto? ELe: Cerca de 20 anos. @} O resultado obtido \'{e}: \begin{verbatim} Andreia: Porque se interessa tanto por esta area? Ana: Nao sei, desde pequeno tive um grande fascinio pela natureza. Andreia: Ha quantos anos trabalha nisto? Ana: Cerca de 20 anos. \end{verbatim} %-------------------------------------------------------------------------- \subsection{Expansor de Abreviaturas} Quando se retiram apontamentos, ou de uma forma geral, se tem de escrever muito depressa, \'{e} h\'{a}bito usar abreviaturas que correspondam a uma ou mais palavras vulgares e longas.\\ Suponha que criou esse costume e resolveu inserir nos seus textos as ditas abreviaturas (2 ou mais letras) precedidas pelo car\'{a}cter "\verb!\!". Por exemplo: "\verb!\!qq" (qualquer), ou "\verb!\!mb" (muito bom), ou ainda "\verb!\!sse" (se e s\'{o} se).\\ Desenvolva, ent\~{a}o: \begin{description} \item[a)] um \textsf{FT} que lhe devolva o texto original mas com todas as abreviaturas (que definiu \`{a} partida) devidamente expandidas; \item[b)] melhore o seu filtro de modo a contemplar ainda o tratamento do car\'{a}cter "\verb!/!" no fim de uma palavra, representando o sufixo "mente", e o car\'{a}cter "\verb!~!" no in\'{i}cio de uma palavra, representando o prefixo "in". Uma palavra pode conter ambos os caracteres, um no in\'{i}cio e outro no fim (pense na abreviatura da palavra "infelizmente"); \item[c)] outra melhoria que poderia introduzir no seu filtro era contemplar a possibilidade de definir abreviaturas dentro do pr\'{o}prio texto, na forma "\verb!\!def:abrev=termo-expandido;". Pense como o fazer e nas implica\c c\~{o}es que tal requisito implicararia no seu filtro original.\footnote{Al\'{i}nea proposta para pensar fora da aula.} \end{description} \newpage \begin{description} \item[a) e b)] \textbf{Solu\c c\~{a}o} @o ex2_2.l @{ qq \\qq mtbom \\mb sse \\sse ft \\FT mente \/ in ~ letra [a-zA-Z] %% {qq} { printf("qualquer"); } {mtbom} { printf("muito bom"); } {sse} { printf("se e so se"); } {ft} { printf("filtro de texto"); } {in}/{letra}+ { printf("in"); } {letra}+{mente} { yytext[yyleng-1]='\0'; printf("%smente",yytext); } %% int yywrap(void) { return 1;} int main( int argc, char **argv ) { ++argv, --argc; /* skip over program name */ if ( argc > 0 ) yyin = fopen( argv[0], "r" ); else yyin = stdin; yylex(); } @} Consideremos o seguinte exemplo:\\ @o ex2_2.txt @{ Suponha que criou esse costume e resolveu inserir nos seus textos as ditas abreviaturas precedidas pelo caracter "\" - por exemplo: 1. \qq 2. \mb 3. \sse Assim \qq abreviatura devera ser expandida e com ctz sera \mb nao termos de nos preocupar com as abreviaturas mas \sse tivermos este \FT nos nossos arquivos... ~feliz/ se nao o tivermos nao poderemos fazer abreviaturas nos nossos documentos... Obvia/ teremos de saber utilizar lex. @} O resultado obtido \'{e}: \begin{verbatim} Suponha que criou esse costume e resolveu inserir nos seus textos as ditas abreviaturas precedidas pelo caracter "\" - por exemplo: 1. qualquer 2. muito bom 3. se e so se Assim qualquer abreviatura devera ser expandida e com ctz sera muito bom nao termos de nos preocupar com as abreviaturas mas se e so se tivermos este filtro de texto nos nossos arquivos... infelizmente se nao o tivermos nao poderemos fazer abreviaturas nos nossos documentos... Obviamente teremos de saber utilizar lex. \end{verbatim} \end{description} %----------------------------------------------------------------- \subsection{Normalizador de Emails} Os Emails escritos a moda PRH caracterizam-se por terem todas as palavras comecadas por letras minúsculas, \`{a} excep\c c\~{a}o dos nomes pr\'{o}prios e siglas.\\ Desenvolva, ent\~{a}o: \begin{description} \item[a)] um \textsf{FT} que normalize o texto, \emph{capitalizando} (escrevendo a letra inicial em maiscula) todas as palavras no inicio de cada frase. Alem da primeira palavra do texto, uma frase comeca depois de um '.', '?' ou '!', seguido de zero ou mais espacos, eventualmente um ou mais fim-de-linha; \item[b)] complete a especificacao anterior de modo a que o seu \emph{normalizador de emails prh} conte tambem todos os nomes pr\'{o}prios (palavras come\c cadas por maisc\'{u}la) e siglas (palavras formadas so por maisc\'{u}las, uma ou mais) encontradas no texto original. \end{description} \textbf{Solu\c c\~{a}o} \begin{description} \item[a) e b)] @o ex2_3.l @{ %{ #include int nProprios = 0, nSiglas = 0; %} ident [a-z]+ nproprio [A-Z][a-z]+ sigla [A-Z]+ pontuacao [.!?] %x IFrase @} @o ex2_3.l @{ %% {nproprio} { nProprios++; ECHO; } {sigla} { nSiglas++; ECHO; } {pontuacao}" "*\n* { ECHO; BEGIN IFrase; } {nproprio} { nProprios++; ECHO; BEGIN INITIAL; } {sigla} { nSiglas++; ECHO; BEGIN INITIAL; } {ident} { yytext[0] = toupper(yytext[0]); printf("%s", yytext); BEGIN INITIAL; } %% int yywrap(void) { return 1;} int main(int argc, char **argv ) { ++argv, --argc; /* skip over program name */ if ( argc > 0 ) yyin = fopen( argv[0], "r" ); else yyin = stdin; // enter in state that match with IFRASE BEGIN IFrase; printf("\n\t\t\t ------ Resultado do Filtro de Texto: ------\n\n"); yylex(); printf("\n\t\t\t ------ Fim de Filtro de Texto. ------ \n\n"); printf("Numero de siglas: %d\n", nSiglas); printf("Numero de nomes proprios: %d\n\n",nProprios); return 0; } @} Consideremos o seguinte exemplo:\\ @o ex2_3.txt @{ qualquer delas me agrada mas tendo dar uma resp, acho que o esquema que prefiro e PAG 5. mas talvez com a caixa de letras do PAG 6 e a cor azul final (no PAG 5 esta muito escuro, quase parece preto). dp podemos falar com Joao para acertar a versao final, mas iria tv mais para os tons de azul. @} O resultado obtido \'{e}:\\ \begin{verbatim} ------ Resultado do Filtro de Texto: ------ Qualquer delas me agrada mas tendo dar uma resp, acho que o esquema que prefiro e PAG 5. Mas talvez com a caixa de letras do PAG 6 e a cor azul final (no PAG 5 esta muito escuro, quase parece preto). Dp podemos falar com Joao para acertar a versao final, mas iria tv mais para os tons de azul. ------ Fim de Filtro de Texto. ------ Numero de siglas: 3 Numero de nomes proprios: 1 \end{verbatim} \end{description} %-------------------------------------------------------------------------- \section{Analisadores L\'{e}xicos} 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 (que se pretende \emph{transformar}, caso seja uma \emph{frase v\'{a}lida} da linguagem em causa) e converter todas as palavras correctas em s\'{i}mbolos terminais dessa linguagem.\\ Com esse fim em vista, prop\~{o}e-se para esta aula o recurso \`{a} ferramenta \textsf{Flex} para gerar um \textbf{Analisador L\'{e}xico (AL)} a partir da descri\c c\~{a}o dos s\'{i}mbolos terminais de uma linguagem e sua associa\c c\~{a}o aos respectivos c\'{o}digos internos. %-------------------------------------------------------------------------- \subsection{M\'{a}quina de Venda de Chocolates} Considere uma situa\c c\~{a}o em que se pretende simular o funcionamento de uma m\'{a}quina de vender chocolates. Dado o stock no in\'{i}cio do dia (nome, pre\c co e quantidade de cada produto dispon\'{i}vel), a quantia inicial de trocos e os registos das vendas di\'{a}rias (nome do chocolate escolhido e a quantia introduzida), o objectivo \'{e} calcular \emph{a evolu\c c\~{a}o do stock ao longo do dia e o dinheiro acumulado}. A anima\c c\~{a}o pretendida dever\'{a} mostrar atrav\'{e}s de desenhos o estado da m\'{a}quina (stock existente e dinheiro ganho) ap\'{o}s cada movimento.\\ No contexto desta aula o que se pretende \'{e}: que defina uma linguagem para descrever o estado inicial da m\'{a}quina e os registos de vendas efectuadas durante o dia; e que desenvolva um \textsf{AL} para reconhecer todos os s\'{i}mbolos terminais dessa linguagem e devolver os respectivos c\'{o}digos.\\ Melhore o seu \textsf{AL} suportando cada \emph{palavra-chave}, ou \emph{palavra-reservada}, da linguagem em \emph{mai\'{u}sculas} ou \emph{min\'{u}sculas} e permitindo a inser\c c\~{a}o de \emph{linhas de coment\'{a}rio} no meio de uma frase v\'{a}lida.\\ Consideremos a seguinte gram\'{a}tica para a linguagem pretendida: \begin{verbatim} G1 = (T,N,S,P) T = { '{', '}', ';', ',' '(', ')', '-', string, int, real, STOCK, TROCOS, VENDAS } N = { MVC, Stock, Descricao, Trocos, Moeda, Vendas, Nome, Preco, Quantidade, IdMoeda, QuantiaI } S = MVC P = { MVC ---> '(' STOCK '{' Stock '}' ';' TROCOS '{' Trocos '}' ';' VENDAS '{' Vendas '}' ')' Stock ---> Descricao Stock ',' Descricao Descricao ---> Nome '-' Preco '-' Quantidade Trocos ---> Moeda | Trocos ',' Moeda Moeda ---> IdMoeda '-' Quantidade Vendas ---> Nome '-' QuantiaI Nome ---> string Preco ---> real Quantidade ---> int IdMoeda ---> real QuantiaI ---> real } ----------------------------------------------------------- \end{verbatim} Consideremos agora um exemplo espec\'{i}fico para esta linguagem, obedecendo \`{a}s regras estabelecidas por esta gram\'{a}tica. @o ex3_1.txt @{ ( /- registo de stock STOCK { twix - 2.0 - 5, mars -3.5 - 7, dove -1.5- 10, kitkat -3.25- 9 } ; /- registo de trocos -/ TROCOS { 0.1 - 13, 0.2 - 8, 0.5 - 15, 1. - 20, 2. - 10 }; /- registo de vendas -/ 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} @o ex3_1.l @{%{ #define STOCK 1 #define TROCOS 2 #define VENDAS 3 #define STRING 4 #define INT 5 #define REAL 6 %} 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} { return(INT); } {real} { return(REAL); } {string} { return(STRING); } {separadores} { return(yytext[0]); } {comentarios}|[ \t] { ; } . { printf("Unrecognized symbol"); } %% int yywrap(void) { return 1;} int main() { int s; while (s=yylex()) { printf("%d ",s); } return 0; } @} Resultado obtido (utilizando o exemplo acima): \begin{verbatim} 40 1 123 4 45 6 45 5 44 4 45 6 45 5 44 4 45 6 45 5 44 4 45 6 45 5 125 59 2 123 6 45 5 44 6 45 5 44 6 45 5 44 6 45 5 44 6 45 5 125 59 3 123 4 45 6 44 4 45 6 44 4 45 6 44 4 45 6 44 4 45 6 44 4 45 6 44 4 45 6 125 41 \end{verbatim} %-------------------------------------------------------------------------- \subsection{Anu\'{a}rio dos Medicamentos brancos} Considere agora uma outra situa\c c\~{a}o em que, para auxiliar o Instituto Farmac\^{e}utico do Minist\'{e}rio da Sa\'{u}de na gest\~{a}o do novo lote de medicamentos brancos, se pretende criar um sistema de consulta a esses medicamentos acess\'{i}vel a qualquer farm\'{a}cia via um browser HTML. 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).\\ Sobre cada medicamento \'{e} fornecida a seguinte documenta\c c\~{a}o: nome, c\'{o}digo, classe, composi\c c\~{a}o qu\'{i}mica, pre\c co recomendado, fabricantes dispon\'{i}veis e lista de medicamentos de marca equivalentes (respectivo nome e fabricante).\\ No contexto desta aula o que se pretende \'{e}: que defina uma linguagem para descrever a informa\c c\~{a}o envolvida no lote de medicamentos a considerar (essa linguagem ter\'{a} que permitir definir inicialmente o ano a que o Symposium Terap\^{e}utico diz respeito e a lista das classes de medicamentos); e que desenvolva um \textsf{AL} para reconhecer todos os s\'{i}mbolos terminais dessa linguagem e devolver os respectivos c\'{o}digos.\\ Melhore o seu \textsf{AL} suportando cada \emph{palavra-chave}, ou \emph{palavra-reservada}, da linguagem em \emph{mai\'{u}sculas} ou \emph{min\'{u}sculas} e permitindo a inser\c c\~{a}o de \emph{linhas de coment\'{a}rio} no meio de uma frase v\'{a}lida.\\ Consideremos a seguinte gram\'{a}tica: \begin{verbatim} G2 = (T,N,S,P) T = {SYMPOSIUM, ano, string, int, real, '[',']','{','}',',','-'} N = {SymposiumT, Classes, Medicamentos, Medicamento, Fabs, Fab, MedEq, MedEq1, Ano, Nome, NomeC, Comp, NFab, Pr, Cod} S = SymposiumT P = { SymposiumT ---> SYMPOSIUM ':' Ano '[' Classes ']' '[' Medicamentos ']' 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 ---> string NomeC ---> string Comp ---> string NFab ---> string Pr ---> real Cod ---> int } \end{verbatim} Um exemplo para esta gram\'{a}tica poderia ser: @o ex3_2.txt @{ Symposium: 2006 [Analgesico,Antibiotico] [ /- Medicamento 1 -/ (Moment,1,Analgesico,Paracetemol,4.5,{Roche},{Qualquer-Bial}); /- Medicamento 2 -/ (Antigripine,2,Antibiotico,Acetalilico,6.,{Fabt,Faba},{Aga-Fabc,Agb-Fabh}) ] @} \textbf{Solu\c c\~{a}} @o ex3_2.l @{ %{ #define SYMP 1 #define STRING 2 #define ANO 3 #define INT 4 #define REAL 5 %} 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(STRING); } {ano} { return(ANO); } {codigo} { return(INT); } {preco} { return(REAL); } {sinais} { return(yytext[0]); } {comentarios}|[ \t] { ; } . { printf("Unrecognized symbol"); } %% int yywrap(void) { return 1;} int main() { int s; while (s=yylex()) { printf("%d ", s); } return 0; } @} O resultado seria (com o exemplo acima): \begin{verbatim} 1 58 3 91 2 44 2 93 91 40 2 44 4 44 2 44 2 44 5 44 123 2 125 44 123 2 45 2 125 41 59 40 2 44 4 44 2 44 2 44 5 44 123 2 44 2 125 44 123 2 45 2 44 2 45 2 125 41 93 \end{verbatim} %-------------------------------------------------------------------------- \subsection{Documento anotado em XML} Como sabe um Documento \textsf{XML} \'{e} um texto vulgar semeado de anota\c c\~{o}es, ou marcas, que s\~{a}o identificadores especiais (designados por \emph{elementos XML}) intercalados entre os caracteres "\verb!!". Num documento \textsf{XML} bem formado, a cada \emph{marca de abertura} corresponder\'{a} uma \emph{marca de fecho}, que tem o mesmo identificador, mas que come\c ca por "\verb!!".\\ Dentro de cada \emph{marca de abertura}, al\'{e}m do identificador do elemento, ainda podem aparecer triplos formados por um outro identificador (de atributo), pelo sinal "\verb!=!" e pelo respectivo valor que \'{e} qualquer texto entre aspas.\\ Cada fragmento do documento (texto livre) entre marcas deve ser considerado em bloco como sendo o s\'{i}mbolo PCDATA.\\ Desenvolva ent\~{a}o um \textsf{AL} que receba um documento \textsf{XML} e devolva todos os s\'{i}mbolos terminais encontrados, a seguir resumidos: "\verb!!", "\verb! some text @} Para resolver a primeira parte do exerc\'{i}cio (constru\c c\~{a}o do AL) consideremos ent\~{a}o a seguinte gram\'{a}tica que descreve um documento XML como o exemplificado acima: \begin{verbatim} G3 = (T,N,S,P) T = {id, val, pcdata, '<','/','>','='} N = {DocXML, MarcAbre, MarcFech, Conteud, Compon, Elem, Atribs, Atrib, IdEle, IdAtr} S = DocXML P = { DocXML ---> MarcAbre Conteud MarcFech MarcAbre ---> '<' Elem '>' MarcFech ---> '<''/' IdEle '>' Elem ---> IdEle Atribs Atribs ---> | Atribs Atrib Atrib ---> IdAtr '=' val Conteud ---> Compon | Conteud Compon Compon ---> MarcAbre | MarcFech | pcdata IdEle ---> id IdAtr ---> id } \end{verbatim} %-------------------------------------------------------------------------- \textbf{Solu\c c\~{a}o (Parte 1)} @o ex3_3.l @{ %{ #define BEA 1 #define BEF 2 #define BD 3 #define IG 4 #define ID 5 #define VAL 6 #define PCDATA 7 %} id [A-Z][a-z]+ string \"[^"]*\" %x FimMarca %% {id} { return(ID); } {string} { return(VAL); } \= { return(IG); } \/ { return(BEF); } \< { return(BEA); } \>/[ \t\n]*\< { return(BD); } \> { BEGIN FimMarca; return(BD); } \< { unput(yytext[0]); BEGIN INITIAL; return(PCDATA); } . { ; } %% @} @o ex3_3.l @{ int yywrap(void) { return 1;} int main() { int s; while (s=yylex()) { printf("%d ",s); } return 0; } @} \bigskip Considerando o exemplo anterior, o resultado obtido \'{e}: \begin{verbatim} 1 5 3 1 5 5 4 6 3 7 1 2 5 3 1 5 5 4 6 3 1 2 5 3 1 5 3 1 5 5 4 6 5 4 6 3 1 2 5 3 1 2 5 3 1 2 5 3 \end{verbatim} \textbf{Solu\c c\~{a}o para as al\'{i}neas a, b e c} \bigskip \textbf{Solu\c c\~{a}o a)} @o ex3_3a.l @{ %% "<""/"?[^>]*">" { ; } [ \t] { ; } %% int yywrap(void) { return 1;} int main() { yylex(); return 0; } @} \bigskip \textbf{Solu\c c\~{a}o b)} @o ex3_3b.l @{ %{ int contaA=0, contaF=0; %} %% "<""/" { contaF++; ECHO; } "<" { contaA++; ECHO; } %% int yywrap(void) { return 1;} int main() { int s; yylex(); if (contaA != contaF) { printf("\n\nERRO: marcas mal emparelhadas!!! \n "); printf("N. Marcas Abertas: %d\n", contaA); printf("N. Marcas Fechadas: %d\n", contaF); } return 0; } @} \bigskip \textbf{Solu\c c\~{a}o c)} ATENCAO: nesta resolucao simplificada \'{e} assumido que as marca de abertura so t\^{e}m identificador de elemento (nao h\'{a} atributos).\\ @o ex3_3c.l @{%{ %{ char * abre; char * list[50]; void initList() { int i = 0; for (i = 0; i < 50; i++) list[i] = NULL; } void addElem(char *pal) { int i=0; while(list[i]!=NULL && i < 50) { i++; } list[i] = pal; } char* deleteElem() { int i=0; char *aux; while(list[i]!=NULL && i < 50) { i++; } aux = list[i-1]; list[i-1]=NULL; return aux; } %} id [A-Z][a-z]+ %% "<"{id}">" { ECHO; yytext[yyleng-1]='\0'; addElem(&yytext[1]); } "<""/"{id}">" { ECHO; yytext[yyleng-1]='\0'; abre = deleteElem(); if (strcmp(abre,&yytext[2])!=0) { printf("Documento mal formado! \n"); exit(0); } } %% int yywrap(void) { return 1;} int main() { initList(); yylex(); return 0; } @} Por exemplo, consideremos o seguinte documento \textsf{XML} mal-formado:\\ @o ex3_3c.txt @{ some text some data @} O resultado obtido ser\'{a}:\\ \begin{verbatim} Moment 1 Analgesico Paracetamol 4.5 pcdata GenericoA GenericoB ERRO: marca de fecho nao esperada! \end{verbatim} %---------------------------------------------------------- \section{Makefile} \begin{verbatim} all1 : to_tex to_dvi to_pdf all2: to_tex to_dvi to_pdf to_compile to_tex: pl105f01resDCC.w nuweb pl105f01resDCC.w to_dvi: pl105f01resDCC.tex latex pl105f01resDCC.tex to_pdf: pl105f01resDCC.dvi dvipdf pl105f01resDCC.dvi to_compile: ex21a1 ex21a2 ex21c ex22 ex23 ex31 ex32 ex33 ex33a ex33b ex21a1: lex ex2_1a1.l gcc lex.yy.c -o ex2_1a1 ex21a2: lex ex2_1a2.l gcc lex.yy.c -o ex2_1a2 ex21c: lex ex2_1c.l gcc lex.yy.c -o ex2_1c ex22: lex ex2_2.l gcc lex.yy.c -o ex2_2 ex23: lex ex2_3.l gcc lex.yy.c -o ex2_3 ex31: lex ex3_1.l gcc lex.yy.c -o ex3_1 ex32: lex ex3_2.l gcc lex.yy.c -o ex3_2 ex33: lex ex3_3.l gcc lex.yy.c -o ex3_3 ex33a: lex ex3_3a.l gcc lex.yy.c -o ex3_3a ex33b: lex ex3_3b.l gcc lex.yy.c -o ex3_3b ex33c: lex ex3_3c.l gcc lex.yy.c -o ex3_3c clean: rm -f ex2_1a1 ex2_1a2 ex2_1c ex2_2 ex2_3 ex3_1 ex3_2 ex3_3 ex3_3a ex3_3b ex3_3c rm -f *.log *.dvi *.toc *.aux lex.yy.c \end{verbatim} \section{Ficheiros} @f \end{document}