Prelucrarea de texte, caracter cu caracter

Sunt frecvente problemele în care trebuie prelucrat un text; adesea, prelucrarea dorită se poate face secvențial, caracter cu caracter. Chiar dacă problemele pot fi simple, discutăm cum putem concepe programele și cum putem evita erori comune.

Strategii de prelucrare

Fără pretenția de a prezenta o clasificare exhaustivă, ilustrăm trei moduri de a soluționa astfel de probleme, pornind de la două exemple: numărarea cuvintelor (despărțite prin spații albe) dintr-o linie de text, și respectiv, eliminarea comentariilor (conform sintaxei C) dintr-un text citit de la intrare.

Urmărirea structurii textului

O strategie este de a descrie structura repetitivă a textului în termenii elementelor pe care le avem de analizat, și de a concepe programul încât sa urmărească această stuctură prin fluxul său de control (decizii și cicluri).

De exemplu, pentru numărarea cuvintelor dintr-o linie, putem privi linia ca o succesiune de spatii albe, urmate de un cuvânt (o succesiune de caractere diferite de spații albe), alternanță care se repetă până la sfârșit de linie. Programul de mai jos e conceput după această idee: 

#include <ctype.h>
#include <stdio.h>

int main(void)
{
  int c, wcnt = 0;

  do {
    // elimina spatiile initiale, cel mult pana la '\n'
    while (isspace(c = getchar()) && c != '\n');
    if (c == '\n' || c == EOF) break;	// gata linia
    ++wcnt;	// incepe un nou cuvant
    // citeste caractere noi cat timp nu sunt spatii albe sau EOF 
    do ; while (!isspace(c = getchar()) && c != EOF);
    // daca am ajuns la sfarsit de linie sau EOF iesim
  } while (c != '\n' && c != EOF);
  printf("Nr. cuvinte pe linie: %d\n", wcnt);
  return 0;
}
Programul conține un ciclu exterior, pentru alternanța spații - cuvinte, și două cicluri interioare, pentru repetiția de spații, respectiv de caractere dintr-un cuvânt. Cum linia se poate termina cu spații sau cu un cuvânt, iar ciclul (scris în ordinea: spații, apoi cuvânt) testează doar terminarea după un cuvânt, condiția de terminare c == '\n' || c == EOF trebuie adăugată și între cele două fragmente de cod pentru spații și respectiv caractere din cuvânt. Primul ciclu interior funcționează corect și în cazul când linia nu începe cu spatii: în orice caz, la terminarea lui, caracterul citit e fie diferit de spațiu, fie linie nouă, fie sfârșit de fișier.

La ciclul care consumă un cuvânt (caractere cât timp nu sunt spații): while (!isspace(c = getchar()) trebuie adăugată și condiția c != EOF, deoarece valoarea EOF nefiind caracter, nu e nici caracter de tip spațiu alb, și altfel ciclul s-ar bloca prin testarea la infinit a valorii EOF dacă sfârșitul de fișier apare imediat după un cuvânt.

Pentru eliminarea comentariilor din textul sursă al unui program, situația mai interesantă apare la comentariile de tipul /* ... */. Aici, textul din interiorul comentariului poate fi văzut ca și alternanță de secvențe de caractere diferite de * cu secvențe de caractere * (cel putin unul), dar neurmate direct de / (în acest din urmă caz, comentariul se încheie). Aceasta se traduce în cod prin ciclul aflat la nivelul 2 în programul următor, care conține la rândul lui două cicluri interioare: 

#include <stdio.h>

int main(void)
{
  int c;
  while ((c = getchar()) != EOF) {
    if (c == '/') {	// poate incepe comentariu
      if ((c = getchar()) == '/') {	// incepe comentariu //
	while ((c = getchar()) != EOF)	// ignora pana la sfarsit
	  if (c == '\n') { putchar(c); break; } // de linie sau EOF
      }	else if (c == '*') {	// incepe comentariu /*
	do {	// cauta sfarsitul */ de comentariu
	  do c = getchar(); while (c != '*' && c != EOF);
	  // citeste pana la '*' sau EOF
	  while ((c = getchar()) == '*'); // cat se repeta *
	} while (c != '/' && c != EOF);	// daca n-a fost */ mai cauta
      } else {	// nu a inceput comentariu
	putchar('/');	// scrie '/' citit anterior
	if (c != EOF) putchar(c); // si caracterul curent daca nu e EOF
      }
    } else putchar(c);
  }
  return 0;
}
Și aici e important să prevedem teste de EOF ori de câte ori avem cicluri care se continuă atât timp cât nu apare un anumit caracter (/ sau *), deoarece fișierul de intrare s-ar putea termina fără să mai apară vreodată caracterul căutat.

Detectarea de tipare

O altă strategie este de a face prelucrările din text atunci când sunt detectate tipare relevante pentru soluția problemei. De exemplu, la numărarea de cuvinte, putem decide să număram un cuvânt atunci când suntem la începutul său. Vom detecta atunci în program începuturi de cuvinte, adică secvențe de două caractere consecutive din care primul este un spațiu alb, și al doilea nu (deci marchează începutul unui cuvănt). 
#include <ctype.h>
#include <stdio.h>

int main(void)
{
  int c, pc = ' ', wcnt = 0;

  // cat timp nu suntem la sfarsit de linie sau EOF
  while ((c = getchar()) != '\n' && c != EOF) {
    // daca caracterul anterior e spatiu alb si cel curent nu
    if (isspace(pc) && !isspace(c)) ++wcnt;	// incepe un nou cuvant
    pc = c;	// memoram caracterul curent pentru ciclul urmator
  }
  printf("Nr. cuvinte pe linie: %d\n", wcnt);
  return 0;
}
În acest caz, avem nevoie de două variabile caracter pentru a detecta tiparul de interes; la fiecare iterație, înainte de citirea caracterului următor, valoarea caracterului precedent e actualizată cu cea a caracterului curent. Variabila pentru caracterul precedent trebuie inițializată corespunzător pentru a detecta un eventual tipar aflat la început: în acest caz, un cuvânt aflat la început se numără, ca și cum ar fi fost precedat de un spațiu. La eliminarea comentariilor, tiparele care trebuiesc detectate sunt //, /* și */. Întrucât primele două au un caracter comun, acesta a fost "factorizat" și în programul de mai jos: 
#include <stdio.h>

int main(void)
{
  int c, pc = 0; // altceva decat /
  while ((c = getchar()) != EOF) {
    if (pc == '/')
      if (c == '/') {
	while ((c = getchar()) != EOF)	// ignora pana la sfarsit
	  if (c == '\n') { putchar(c); break; } //de linie sau EOF
      } else if (c == '*') {
	c = getchar();	// urmatorul caracter
	do {
	  pc = c;
	  if ((c = getchar()) == EOF) break;
	} while (!(pc =='*' && c == '/'));
	c = 0;	// nu lasam pc == /
      } else {	// a fost / dar nu e comentariu
	putchar('/');
	if (c != EOF) putchar(c);
      }
    else if (c != '/') putchar(c);
    pc = c;	// memoram caracterul curent pentru ciclul urmator
  }
  return 0;
}
Detectarea tiparului */ e relevantă doar când suntem într-un comentariu început cu /* și în concluzie apare doar pe acea ramură de program. Se avansează în intrare cu un caracter pentru a nu detecta prematur sfârșitul de comentariu în cazul /*/.

Simularea unui automat

O altă soluție sistematizează situațiile care pot apărea în prelucrarea textului ca niște stări ale unui automat, si definește pentru fiecare stare acțiunea și schimbarea stării, în funcție de caracterul citit. 
#include <ctype.h>
#include <stdio.h>

// #define defineste constante simbolice cu ajutorul preprocesorului C
#define IN_SPACE	0
#define IN_WORD		1

int main(void)
{
  int c, state = IN_SPACE, wcnt = 0;
  while ((c = getchar()) != '\n' && c != EOF) {
    switch (state) {
    case IN_SPACE: if (!isspace(c)) { state = IN_WORD; ++wcnt; }
      // daca nu e spatiu, schimba starea si numara cuvantul
      break;
    case IN_WORD: if (isspace(c)) state = IN_SPACE;
      // daca e spatiu schimba starea
      break;
    }
  }
  printf("Nr. cuvinte pe linie: %d\n", wcnt);
  return 0;
}
Numărarea cuvintelor e practic trivială: ne aflăm fie în interiorul unui cuvânt (după citirea primului caracter), fie în interiorul unui șir de spații, iar valoarea variabilei de stare se schimbă dacă se citește un caracter de tip diferit față de cel curent, altfel rămâne la fel. Inițial nu suntem într-un cuvânt, deci inițializăm starea cu "spațiu". Și aici numărăm un cuvânt când îi detectăm începutul. Nu am introdus o stare explicită pentru "sfârșit de text", dar acest caz e testat la fiecare ciclu când se citește un nou caracter. E mai relevant să exemplificăm acest stil de concepere a programului pentru problema eliminării comentariilor: 
#include <stdio.h>

// constante simbolice definite prin intermediul preprocesorului C
#define NO_CMT		0
#define LINE_CMT	1
#define STAR_CMT	2
#define WAIT_CMT	3
#define WAIT_END	4

int main(void)
{
  int c, state = NO_CMT;
  while ((c = getchar()) != EOF)
    switch(state) {
    case NO_CMT:	// nu e in comentariu
      if (c == '/') state = WAIT_CMT;	// asteapta ce vine dupa /
      else putchar(c);	// scrie normal caracterul
      break;
    case LINE_CMT:	// e in comentariu //
      if (c == '\n') { putchar(c); state = NO_CMT; }	// iese din comentariu
      break;
    case STAR_CMT:      // e in comentariu /* */
      if (c == '*') state = WAIT_END;	// asteapta ce vine dupa *
      break;
    case WAIT_CMT:	// vezi ce vine dupa /
      if (c == '/') state = LINE_CMT;	// incepe comentariu //
      else if (c == '*') state = STAR_CMT;  // incepe comentariu /* */
      else { putchar('/'); putchar(c); state = NO_CMT; }
      // nu a inceput comentariu, scrie / anterior si caracterul curent
      break;
    case WAIT_END:	// vezi ce vine dupa *
      if (c == '/') state = NO_CMT;	// gata comentariul
      else if (c != '*') state = STAR_CMT;	// * fara /, revine in cmt
      // * urmat de * ramane sa astepte /
    }
  // a fost / urmat de EOF, trebuie scris /
  if (state == WAIT_CMT) putchar('/');
  return 0;
}
Aici, pe lângă cele 3 stări evidente: în afara comentariului, în comentariu cu // si în comentariu cu /* ... */ apar și două stări intermediare: cea în care în text normal am citit un / și urmează să vedem dacă următorul caracter va începe un comentariu sau nu, și cazul în care, într-un comentariu început cu /* apare un *, și comentariul s-ar putea încheia dacă următorul caracter e /.

În general, pentru a scrie programele în acest stil, trebuie să identificăm corect stările în care se poate afla programul, și să specificăm complet acțiunile de efectuat în fiecare stare, pentru fiecare caracter de intrare posibil. Exemplele de mai sus sunt scrise așa încât programul rămâne în aceeași stare pentru caracterele după care nu se testează explicit.

Trebuie amintit că orice program definește implicit, prin graful de flux de control și variabilele sale, un automat cu stări și tranziții. Astfel, în prima soluție pentru problema comentariilor, e suficientă o variabilă cu caracterul curent, pentru că "starea" e implicit codificată în poziția curentă din program. De exemplu, ciclul interior 

	  do c = getchar(); while (c != '*' && c != EOF);
corespunde stării STAR_CMT, în care se așteaptă apariția unui caracter *, iar ciclul 
	  while ((c = getchar()) == '*');
corespunde stării WAIT_END în care programul rămâne cat timp se repeta *.
În varianta a doua de soluție, starea e codificată parțial în prin reținerea caracterului anterior, în plus față de cel curent.

Conceperea corectă a ciclurilor

Testarea de sfârșit de fișier

Printre cele mai frecvente erori care apar la încercarea programelor se numără ciclurile care iterează la infinit. În cazul programelor care citesc intrarea caracter cu caracter, trebuie detectat sfârșitul intrării pe toate căile posibile prin program. Ciclurile care se continuă atât timp cât avem un anumit caracter (sau un caracter dintr-o anumită mulțime): 
  while ((c = getchar()) == '*') { /* ... */ }
  while (isspace(c = getchar())) { /* ... */ }
se termină sigur într-un număr finit de iterații: fie se întâlnește un alt caracter decât cel(e) specificat(e), fie c ia valoarea EOF la sfârșit de fișier, care e diferită de orice caracter (presupunând că c a fost declarat corect, int), și deci nu face parte nici din clasele de caractere definite în ctype.h.

Pe de altă parte, cicluri de forma 

  while ((c = getchar()) != '*') { /* ... */ }
  while (!isspace(c = getchar())) { /* ... */ }
în care ciclul continuă cât timp c e diferit de o valoare sau o clasă dată de caractere se vor bloca dacă se ajunge la sfârșit de fișier în timpul prelucrării ciclurilor. Odată atins sfârșitul de fișier, orice apel la getchar() returnează tot EOF (în general: orice funcție de intrare eșuează corespunzător sfârșitului de fișier), și se iterează la infinit, EOF fiind diferit de orice (tip de) caracter căutat. În orice astfel de ciclu trebuie testat explicit de EOF, fie în condiția de ciclare, fie într-un if () cu break; în corpul ciclului.

Chiar când căutăm un tipar în care un anumit caracter ar trebui să apară, nu e corect să scriem astfel de cicluri care presupun că până la urmă găsim un anumit caracter, pentru că nu putem ști niciodată ce se introduce de la intrare, sau dacă conținutul unui fișier nu e eronat. Un program bun nu are voie să se blocheze, să se termine printr-o eroare de rulare, sau să dea un rezultat greșit dacă intrarea e greșită. El trebuie să semnaleze acest lucru (printr-un mesaj oricât de sumar) și să ia acțiunea corespunzătoare (terminarea programului, în lipsa unei alternative).

Progresul în fiecare ciclu

În plus, un program corect scris trebuie să progreseze în intrare pe orice cale printr-un ciclu, altfel se poate bloca testând încontinuu un caracter care nu se modifică. De exemplu, fragmentul de cod: 
c = getchar();
while (c != EOF) {
  /* eventual ceva prelucrare aici */
  while (c != '\n') {
    /* aici se face ceva cu c */
    c = getchar();
  }
  /* eventual ceva prelucrare aici */
}
deși aparent citește câte un caracter la fiecare iterație, nu citește nici un caracter în afara ciclului interior. La atingerea sfârșitului de linie, programul nu va mai intra în ciclul interior, și va repeta prelucrările din ciclul exterior pentru același caracter c == '\n', la infinit (cum c != EOF). Prin urmare, trebuie verificat, prin inspecția structurii ciclurilor și faptul că programul poate avansa în orice situație (aceasta e valabil și pentru alte aspecte legate de iterație: incrementarea unui contor, parcurgerea unei liste, etc.).
Marius Minea
Last modified: Sun Nov 6 18:54:08 EET 2005