| Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
Esta página foi extraída (com várias modificações) da seção 5 (Defining a scanner ADT) do capítulo 8 (Abstract Data Types) do livro de Eric Roberts. da seção 8.5 do livro de Eric Roberts. Veja também o capítulo 10 do The Art and Science of C de Eric Roberts.
Esta página implementa um token scanner (to scan = esquadrinhar, varrer; token = símbolo, ficha). O objetivo do scanner é extrair os tokens de uma string. Cada token é uma "unidades lógica" da string. Por exemplo, a string
| Question: what is the variable x12 used for? |
é formada pelos seguintes tokens:
| Question | : | what | is | the | variable | x12 | used | for | ? |
Nosso token scanner deverá extrair tokens de uma string da mesma forma que a função fgetc extrai caracteres de um arquivo: cada chamada fgetc(arq) extrai um novo caracter do arquivo arq.
[A propósito, veja exercício 3 do PigLatin e a tarefa 08.]
// Este programa extrai os tokens de uma string e imprime // cada token em uma nova linha (depois de transformá-lo em // uma string). Por definição, cada token é // // 1. um cadeia de caracteres alfanuméricos (isto é, // letras e dígitos) consecutivos ou // 2. uma cadeia de um só caracter que representa um // sinal de pontuação ou um separador. // //////////////////////////////////////////////////////////// //////////////////////////////////////// // Seção 1: Bibliotecas e tipos de dados //////////////////////////////////////// #include <stdlib.h> // quero usar malloc, etc. #include <stdio.h> // quero usar getc, etc. #include <string.h> // quero usar strlen, etc. #include <ctype.h> // quero usar isalnum typedef char * string; //////////////////////////////////////////////////////// // Seção 2: Scanner // Implementação de um scanner, ou seja, um mecanismo que // extrai tokens de uma string. //////////////////////////////////////////////////////// // Usaremos três variáveis globais para representar // o scanner: string str; // str é a string a ser analisada int len; // len é o comprimento da string int cp; // cp é a posição corrente dentro de str // Protótipo de função auxiliar string subString( int p1, int p2); // A função abaixo extrai o próximo token de str. // O próximo token está no início de str[cp..len-1]. // O código supõe que cp < len. string GetNextToken( void) { char ch; int start, finish; start = finish = cp; ch = str[cp]; if (isalnum( ch)) { while (cp < len && isalnum( str[cp])) cp++; finish = cp - 1; } else { cp++; } return subString( start, finish); } // Copia o vetor str[p1..p2] para um espaço alocado // por malloc. Devolve a nova string. A função supõe que // 0 <= p1 <= p2 < len. Esta função foi inspirada // em SubString da biblioteca strlib de Eric Roberts. string subString( int p1, int p2) { int n; string result; n = p2 - p1 + 1; result = malloc( n + 1); if (result == NULL) exit( EXIT_FAILURE); strncpy( result, str + p1, n); result[n] = '\0'; return result; } ///////////////////////////////////////////////////// // Seção 3: Código do programa de impressão de tokens ///////////////////////////////////////////////////// string getLine( void); int main( void) { string token; printf( "Teste de um token scanner\n"); printf( "Digite uma linha\n"); str = getLine(); len = strlen( str); cp = 0; while (cp < len) { token = GetNextToken(); printf( "%s\n", token); free( token); } free( str); return 0; } // Lê uma linha do teclado e devolve a linha na forma de // uma string. A linha deve ter no máximo 100 caracteres. // Esta função foi inspirada na GetLine da biblioteca // simpio de Eric Roberts, mas é bem mais simples que // aquela. string getLine( void) { string line; int n, ch; n = 0; line = malloc( 100+1); if (line == NULL) exit( EXIT_FAILURE); while ((ch = getc( stdin)) != '\n') { if (n >= 100) { free( line); exit( EXIT_FAILURE); } line[n++] = ch; } line[n] = '\0'; return line; }
Observe como as variáveis globais e as funções que definem o scanner foram todos reunidos em uma só seção do programa.
3.14159
tem um único token (e não três, como diria o scanner acima).
Vale a pena isolar e estudar a parte do código que lida com o scanner propriamente dito (seção 2 do código). Isso é um primeiro passo no sentido de tratar o scanner como um tipo abstrato de dados (= ADT = abstract data type).
O scanner é representado por uma struct scannerT (o "T" final só está aí para lembrar que isso é o nome de um tipo-de-dados e não o nome de uma variável). O campos str, len e cp da struct correspondem às variáveis globais que usamos acima.
// Um scanner permite extrair tokens de uma string. Cada token é // 1. um cadeia de letras e dígitos consecutivos ou // 2. uma cadeia de um só caracter que representa // um sinal de pontuação ou um separador. // Para usar esse módulo, você deve começar por criar um objeto // do tipo scannerT: // // sc = NewScanner( ); // // Todas as chamadas subseqüentes às funções do módulo usarão // essa variável como primeiro argumento. Para inicializar o // scanner de modo que ele contenha uma string str diga // // SetScannerString( sc, str); // // Para extrair os sucessivos tokens de str basta dizer // // token = GetNextToken( sc); // // Cada chamada produzirá o próximo token. Para determinar se // ainda há tokens no scanner sc, chame a função booleana // MoreTokensExist( sc). typedef char * string; /////////////////////////////////////////////////////////////////// // Implementação do scanner // ------------------------ // Um objeto do tipo scannerT é uma struct com os seguintes campos: // str : string que o scanner está processando // len : comprimento da string str // cp : posição do caracter corrente na string str // Um objeto do tipo scannerT tem a missão de manter o "estado // interno" do scanner entre chamadas sucessivas da função // GetNextToken. /////////////////////////////////////////////////////////////////// typedef struct { string str; int len; int cp; } scannerT; // Esta função devolve o próximo token do scanner sc. Se não houver // mais tokens, GetNextToken devolve uma string de comprimento 0. // O espaço ocupado pelo token devolvido é alocado por malloc, de // modo que o cliente pode usar free para liberar o espaço quando // ele não for mais necessário. A função supõe sc->str != NULL. string GetNextToken( scannerT *sc) { char ch; int start, finish; start = finish = sc->cp; if (start >= sc->len) return copyString( ""); ch = sc->str[sc->cp]; if (isalnum( ch)) { while (sc->cp < sc->len && isalnum( sc->str[sc->cp])) sc->cp++; finish = sc->cp - 1; } else { sc->cp++; } return subString( sc->str, start, finish); } // Faz uma cópia da string s. A função supõe que s != NULL. // O espaço para a cópia é alocado por malloc. Esta função // foi inspirada na CopyString da biblioteca strlib de Eric // Roberts. string copyString( string s) { string newstr; newstr = malloc( strlen( s) + 1); if (newstr == NULL) exit( EXIT_FAILURE); strcpy( newstr, s); return newstr; } // Copia a substring s[p1..p2] para um espaço alocado por // malloc. Devolve a nova string. A função supõe que // 0 <= p1 <= p2 < strlen( s). Esta função foi inspirada // em SubString da biblioteca strlib de Eric Roberts. string subString( string s, int p1, int p2) { int n; string result; n = p2 - p1 + 1; result = malloc( n + 1); if (result == NULL) exit( EXIT_FAILURE); strncpy( result, s + p1, n); result[n] = '\0'; return result; }
É conveniente que o módulo tenha algumas funções "auxiliares" além da função "principal" GetNextToken:
// Esta função cria um scanner e devolve o seu endereço. // O usuário pode criar e usar vários scanners simultaneamente. scannerT *NewScanner( void) { scannerT *sc; sc = malloc( sizeof (scannerT)); sc->str = NULL; return sc; } // Esta função libera a memória associada com um scanner sc // previamente criado por NewScanner. void FreeScanner( scannerT *sc) { if (sc->str != NULL) free( sc->str); free( sc); } // Esta função "carrega" a string str no scanner sc. void SetScannerString( scannerT *sc, string str) { if (sc->str != NULL) free( sc->str); sc->str = copyString( str); sc->len = strlen( str); sc->cp = 0; } // Esta função devolve 1 se o scanner sc ainda tem tokens e 0 // se todos os tokens já foram extraídos. int MoreTokensExist( scannerT *sc) { if (sc->str == NULL) exit( EXIT_FAILURE); return sc->cp < sc->len; }