Resumo:
Há sempre um primeiro passo nas jornadas de dez mil milhas. Provérbio Chinês
Com esta primeira fase do trabalho prático da disciplina de Processamento de Linguagens I, pretendia-se implementar um processador genérico de documentos estruturados, tipo á la XML.
Processador engloba os analisadores léxico, sintáctico e semântico, e através desta análise constrói uma representação para o conhecimento representado no documento estruturado. A estrutura utilizada para essa representação foi o chamado grove . Apartir desta estrutura pode-se gerar a informação, nela contida, em vários formatos, que podem ou não preservar a informação. Neste trabalho gera-se o conhecido formato internacional ESIS.
O trabalho foi elaborado num sistema Linux RedHat 6.1 kernel 2.2.12, usando o editor vi, o utilitário de reconstrução de programas - GNU Make versão 3.77. Para gerar os reconhecedores/tradutores baseados em autómatos reactivos, utilizou-se o utilitário flex - fast lexical analyzer generator - versão 2.5. Para a construção do parser utilizou-se a ferramenta Yacc - an LALR(1) parser generator. O relatório foi elaborado em LaTeX versão 3.3.1 para Linux, com o auxílio do pli-doc.
O relatório começa por resumir os objectivos pretendidos com o trabalho.
De seguida no capítulo 1, apresenta-se uma introdução ao trabalho, definindo o ambiente de trabalho, objectivos mais específicos e definições importantes para a compreensão do trabalho.
Análise Léxica
Análise Sintáctica
Análise Semântica
Representação estrutural de docs-Grove
Apresentação de uma conclusão.
Apresentação de anexos com o código fonte.
Pretende-se criar um reconhecedor dos símbolos terminais para a linguagem dos documentos anotados.
Os símbolos terminais dos documentos anotados são os seguintes:
identicador: nome de uma tag ou de um atributo, tem a expressão regular [a-zA-Z][a-zA-Z0-9]+.
numero: representa um valor do tipo número. expressão regular Num [+-]?[0-9]+(\.[0-9]+)?
str: uma string, ie um conjunto de carcteres dentro de aspas.Str \"[^"]*\"
caracter menor : inicio de uma tag.
caracter maior : fim de uma tag.
caracter frontslash : identifica uma tag de fecho
caracter e-comercial : inicio de abreviatura.
caracter ponto-e-vírgula : fim de abreviatura.
outros caracter : todos os caracteres que não foram identificados anteriormente.
De seguida apresenta-se a implementação encontrada para o problema.
O código fonte para a ferramenta flex gerar o reconhecedor pretendido é oseguinte:
%{
#include <string.h>
extern Ponto p;
%}
Id [A-Za-z][A-Za-z0-9-]*
Str \"[^"]*\"
Num [+-]?[0-9]+(\.[0-9]+)?
%x MARCA ATRIB ABREV FIM
%%
\< {
BEGIN MARCA;
incC(1,&p); /* + 1 coluna */
return('<');
}
\& {
BEGIN ABREV;
incC(1,&p);
return('&');
}
\\[-<>&] {incC(2,&p);yylval.caracter = *yytext;return(car);}
. {incC(1,&p);yylval.caracter = *yytext;
/*mostra(p,car)*/;return(car);}
\n BEGIN(FIM);
<MARCA,ABREV>{Id} {
incC(strlen(yytext),&p);
yylval.nome=strdup(yytext);
return(id);
}
<MARCA>\/ {incC(1,&p);return('/');}
<MARCA>\= {incC(1,&p);return('=');}
<MARCA>{Num} {
yylval.valor = (void *)calloc(1,sizeof(int));
*((int *)(yylval.p)) = atoi(yytext);
incC(yyleng,&p);
return(num);}
<MARCA>{Str} {
char *s;
nodoS(yytext,&s);
yylval.p = (void *)s;
incC(yyleng,&p);
return(str);}
<MARCA>\> {
BEGIN INITIAL;
incC(1,&p);
return('>');
}
<ABREV>\; {
BEGIN INITIAL;
incC(1,&p);
return(';');
}
<ABREV,MARCA,ATRIB>[ \n\t] {
switch(*yytext){
case ' ':incC(1,&p);
break;
case '\t': incC(TAB,&p);
break;
default:incL(1,&p);
break;
}
}
<ABREV,MARCA,ATRIB>. {
printf("(%d,%d) Erro léxico\"%s\"\n",p.l,p.c,yytext);
exit(1);
}
<FIM>.|\n {
BEGIN(INITIAL);
yyless(0);
incL(1,&p);
yylval.caracter = '\n';
return(car);/* o último \n reconhecido */
}
<FIM><<EOF>> yyterminate();
%%
[gauss@localhost parser]$ flex xml.l
[gauss@localhost parser]$ gcc -o xml lex.yy.c -lfl
[gauss@localhost parser]$ cat y.tab.h
#define id 257
#define num 258
#define str 259
#define car 260
[gauss@localhost parser]$ cat ../textos/texto2.txt
<a b=1>
</a>
[gauss@localhost parser]$ xml < ../textos/texto2.txt
60 257 257 61 258 62 260 260 260 260 [gauss@localhost parser]$
[gauss@localhost parser]$ cat ../textos/texto3.txt
<a b = "str">
Subsec,c~oes n'ivel 1:
<c>
Subsec,c~oes n'ivel 2.1:
<c1 x = y u = v>
<c1>
</c1>
<c2 o=0 p="letra p" /
>
</c>
<d>
<d1 f="etiqueta de declara,c~oes"/ >
</d>
</a>
[gauss@localhost parser]$
[gauss@localhost parser]$ xml < ../textos/texto3.txt
60 257 257 61 259 62 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 60 257 62 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 260 60 257 257 61 257 257 61
257 62 260 260 260 260 260 260 260 260 260 60 47 257 62 260 260 60 257 257 61 258 257 61 259 47 62 260 60 47 257 62 260 60 257 62 260 260 60 257 257 61 259 47 62 260 60 47 257 62 260 260 260 260 [gauss@localhost parser]$
Pretende-se criar um analisador sintáctico para a linguagem dos documentos anotados, ie pretende-se um programa que dada uma frase, constituída por símbolos terminais da linguagem, verificar se a frase é válida na linguagem.
As frases que estão sintácticamente correctas são as frases reconhecidas pela gramática apresentada no código fonte destinado a ser processado pelo yacc, com ofim de gerar o parser para a linguagem.
Pretende-se implementar um reconhecedor de frases semânticamente correctas na linguagem dos documentos anotados.
Essencialmente esta análise trata uma frase sintáctica e lexicamente correcta, e verifica se os nomes das tags de abertura e fecho de cada secção coincidem.
Pretende-se construir, apartir de um documento anotado, uma estrutura de dados que corresponda à anotação do texto, ie essa estrutura deve manter a integralmente o documento anotado.
A estrutura de dados utilizada foi o grove.
Ficheiro destinado a ser processado pelo yacc, que construirá o reconhecedor para a linguagem dos documentos anotados.
/*****************
xml.y (* 00-04-11 *)
*************/
%{
#include "xml.c"
int i=0;
extern int yyparse();
extern char *yytext;
Grove *g = NULL;
%}
%union{
char *nome;
char caracter;
void *p;
Valor *valor;
Grove *grove;
Child *child;
Txt *texto;
Atrib *atrib;
}
%token <nome> id
%token <p> num str
%token <caracter> car
%type <grove> Abertura AberturaFecho Abrev Elems Elem Txt
%type <nome> Fecho
%type <atrib> Atrib Atribs
%type <valor> Valor
%start DocXML
%%
DocXML : Abertura Elems Fecho { ar1x1($1,$2,$3,&(g)); }
;
Elems : Elems Elem { ar2x1(&($$),$1,$2);}
| Elems Elem Txt { ar2x2(&($$),$1,$2,$3);}
| Elem Txt { ar2x3(&($$),$1,$2);}
| Elem { ar2x4(&($$),$1);}
| Txt { ar2x5(&($$),$1);}
Elem : Abrev { ar3x1(&($$),$1);}
| AberturaFecho { ar3x2(&($$),$1); }
| Abertura Elems Fecho { ar3x3(&($$),$1,$2,$3); }
;
Abrev : '&' id ';' { ar4x1(&($$),$2); }
;
Atribs : Atribs Atrib { ar5x1(&($$),$1,$2); }
| { ar5x2(&($$)); }
;
Atrib : id '=' Valor { ar6x1(&($$),$1,$3); }
;
Abertura: '<' id Atribs '>' { ar7x1(&($$),$2,$3); }
;
Fecho : '<' '/' id '>' { ar8x1(&($$),$3); }
;
AberturaFecho: '<' id Atribs '/' '>' { ar9x1(&($$),$2,$3); }
;
Valor : id { ar10x1(&($$),$1); }
| num { ar10x2(&($$),$1); }
| str { ar10x3(&($$),$1); }
;
Txt : Txt car { ar11x1(&($$),$1,$2); }
| car { ar11x2(&($$),$1); }
;
%%
#include "lex.yy.c"
int yyerror(char *s)
{
printf("(%d,%d) %s \"%s\"\n",p.l,p.c,s,yytext);
exit(1);
}
int main()
{
yyparse();
geraESIS(g,0);
return(0);
}
header do ficheiro auxiliar xml.c.
#include <stdio.h>
#include <string.h>
#include "./grove/grove.c"
#define TAB 5
typedef struct{
int l,c;
} Ponto;
Ponto p = {1,0};/* A posição no documento anotado. */
/* Funções para manipular ponto */
void inc(Ponto *p);
void incL(int i,Ponto *p);
void incC(int i,Ponto *p);
void incN(int il,int ic,Ponto *p);
/*
Faz análise semântica, ie compara os nomes das tags de abertura e fecho.
Cria raiz do grove.
a: grove da tag principal, ie grove com os atributos desta sem filhos nem irmãos.
b: grove do conteudo, propriamente dito do documento, ie e o futuro filho do grove a.
g: parametro de saída que aponta para a raiz do grove que representa o documento na integra.
*/
void ar1x1(Grove *a, Grove *b, char *c, Grove **g);
/*
Junta groves a e b, ie o grove b passa a ser irmão de a
*/
int ar2x1(Grove **final, Grove *a, Grove *b);
/*
Junta groves a, b e c, ie o grove c passa a ser irmão de b e b de a.
*/
int ar2x2(Grove **final, Grove *a, Grove *b,Grove *c);
/*
Junta groves a e b, ie o grove b passa a ser irmão de a
*/
int ar2x3(Grove **final, Grove *a, Grove *b);
/*
final passa a apontar para a
*/
int ar2x4(Grove **final, Grove *a);
/*
final passa a apontar para a
*/
int ar2x5(Grove **final, Grove *a);
/*
a: Grove de uma abreviatura, para o qual final vai apontar.
*/
int ar3x1(Grove **final,Grove *a);
/*
a: Grove de uma tag de abertura e fecho simultâneo, para o qual final vai apontar
*/
int ar3x2(Grove **final,Grove *a);
/*
Faz a análise semântica da frase, e coloca em final o novo grove.
a: grove de uma tag de abertura
b: grove do conteúdo da secção
c: nome da tag de fecho
*/
int ar3x3(Grove **final,Grove *a, Grove *b, char *c);
/*
Cria-se um grove com a tag & e com o conteudo da string a que contem o nome da abreviatura.
*/
int ar4x1(Grove **final,char *a);
/*
final: passa a apontar para a lista de atributos resultante de colocar b seguido de a.
*/
int ar5x1(Atrib **final, Atrib *a, Atrib *b);
/* final = NULL */
int ar5x2(Atrib **final);
/*
final passa a ser um nodo do tipo Atrib
*/
int ar6x1(Atrib **final, char *a, Valor *b);
/*
Foi detectada uma abertura
a: identificador da tag de abertura
b: Lista de atributos desta tag
final: vai ficar com um grove com tag a, com atributos b e sem filhos
*/
int ar7x1(Grove **final,char *a,Atrib *b);
/*
Foi encontrada uma tag de fecho.
a: nome da tag
final: fica com o valor de a
*/
int ar8x1(char **final,char *c );
/*
Encontrou-se uma tag de abertura e fecho simultâneo
final: grove com tag a e com lista de atributos b, sem familia.
*/
int ar9x1(Grove **final,char *a,Atrib *b);
/*
Foi reconhecido um Valor
a : apontador para o valor.
final: fica com o o tipo e com um apontador para o valor
*/
int ar10x1(Valor **final,char *a);
int ar10x2(Valor **final,void *a);
int ar10x3(Valor **final,void *a);
/*
está-se a reconhecer caracteres sem significado, emtermos de notação.
*/
int ar11x1(Grove **final,Grove *a,char c);
int ar11x2(Grove **final,char c);
A estrutura de dados Grove
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* Identificar em ESIS o inicio de uma seccao de texto.*/
#define InicioTxt '-'
/* Maximo de caracteres para um identificador*/
#define MaxCarId 100
#define MaxCarTxt 127
#define isTxt(a) (a->tag == NULL)
#define text(a) ((Txt *)(a->content))
#define content(a) ((Child *)(a->content))
#define atribs(a) ((Child *)(a->content))->atribs
#define child(a) ((Child *)(a->content))->child
/* Definição das estruturas de dados*/
typedef struct _Grove
{
char *tag;
void *content;
struct _Grove *brother;
} Grove;
typedef struct _Txt
{
char *s;
struct _Txt *next;
} Txt;
typedef struct _Valor
{
int tipo; // 0- id, 1 - num, 2 -str ...
void *valor;
} Valor;
typedef struct _Atrib
{
char *id;
Valor *content;
struct _Atrib *next;
} Atrib;
typedef struct _Child
{
Grove *child;
Atrib *atribs;
} Child;
/* Funções para tratar a estrutura de dados */
nt nodoId(const char *nome,char **id);
int nodoS(const char *nome,char **s);
int nodoGrove(char *tag,void *content, Grove **g);
int consGrove(Grove *h,Grove **g);
int appendGrove(Grove **h,Grove *t);
int nodoChild(Grove *child, Atrib *atribs, Child **c);
int nodoTxt(char *seq, Txt **texto);
int nodoValor(int tipo,void *valor,Valor **a);
int nodoAtrib(char *id,Valor *valor, Atrib **a);
int consAtrib(Atrib *h,Atrib **t);
int appendAtrib(Atrib **a,Atrib *b);
int showTxt(Txt *texto);
int showValor(Valor *v);
int showAtribs(Atrib *a);
int geraESIS(Grove *g,int nivel);
gauss@localhost src]$ cat ./textos/texto4.txt
<a u=0 >
&id;
\& < dsadsada ;sdsdsda
>
</a
>
[gauss@localhost src]$ xml < ./textos/texto4.txt >./textos/rtexto4.txt
[gauss@localhost src]$ cat ./textos/rtexto4.txt
(a u=0
-
-id -
\ \ dsadsada ;sdsdsda
>
)a[gauss@localhost src]$
[gauss@localhost src]$ cat ./textos/erroSem2.txt
<doc\>
<doc />
<a>
</a>
<b>
&sdsadasd;
<i>
ksdqjfksjklfjkdsl
</a>
</b>
</doc>
[gauss@localhost src]$ xml < ./textos/erroSem2.txt
(10,6) Erro Sem^antico "\>"
[gauss@localhost src]$
[gauss@localhost src]$ cat ./textos/erroSin5.txt
<doc>
<a>
<a/>
<doc/>
[gauss@localhost src]$ xml< ./textos/erroSin5.txt
(6,6) syntax error ""
[gauss@localhost src]$
Da elaboração deste trabalho resalta a aprendizagem de um novo método de abordagem de um problema. Que é a programação orientada às gramáticas.
Agradecemos a todos os Docentes e Colegas da disciplina de Pl1.
Bibliografia: