ZADATAK 3 - LEKSI - 60 bodova TEST PODACI (skraćeni prikaz) ULAZ IZLAZ 1. a A 2. abeceda 123 +-)))) l e "ferti" m ABDDDDDDAAEA 3. "laaaaaaaaaaa(aaaaaaaaaa" bezveze_da_123a fora 2.5 je to luda no+11-'Đ'' EAACAAAADBDE 4. mala (g.5e-13 A@@C test primjeri 5-8 su preveliki za ispis OPIS ALGORITMA Zadatak je tipičan primjer leksičke analize teksta kod baratanja programskim jezicima. Simboli koje susrećemo u programu su cijeli i realni brojevi, imena, stringovi, operatori, te razdjelni znakovi u koje spadaju i komentari. To su osnovni elementi velike većine programskih jezika. Na temelju tih simbola izvodi se kasnija sintaktička te semantička analiza, nakon koje slijedi samo prevođenje, odnosno interpretiranje, u ovisnosti o implementaciji programskog jezika. Za leksičku analizu ovog primjera moguća su tri rješenja. Prvo, očigledno, rješenje bi bilo kreiranje case strukture kroz koju bi se propuštao ulazni file, znak po znak : prepoznaj (znak) slučaj 1: .... slučaj 2: .... slučaj 3: .... .... slučaj n: .... Svaki prepoznati znak, može pobliže odrediti vrstu ulaznog simbola, no u nekim slučajevima je potrebno dodatno grananje prilikom prepoznavanja cijelog simbola. Nakon prepoznatog simbola ispisuje se tip u izlazni file, a zatim se s novim ulaznim znakom kreće u analizu s vrha. Drugo i treće rješenje koristi konačni automat, tj. najčešće opće rješenje problema leksičke analize. O konačnim automatima može se saznati pobliže iz knjige "Algorithms" Roberta Sedgewicka, koja se može nabaviti preko HSIN-a. Razlika između dva rješenja jest u načinu smještanja konačnog automata. U lakšem primjeru smještamo konačni automat u memoriju kao slabo popunjenu matricu, tj. svaka vrsta znaka zauzima jedan stupac. Optimalno, treće rješenje, prije same analize generira potpunu tabelu konačnog automata, kojom se daleko brže prolazi. Naime, u svakom stupcu se tretira po jedan znak ASCII tabele, pa je nepotrebno u svakom koraku ocjenjivati vrstu znaka. Za to optimalno rješenje dan je i primjer koji generira potpunu tabelu, koja se zatim koristi u samom radu konačnog automata. GENTAB.C #include #define ERR 16 #define NAME 17 #define INT 18 #define REAL 19 #define STR 20 #define OPER 21 int tmp[16][14] = { {0, 7, 7, 8, 7, 3, 7, 1, 11, 13, 1, 1, 2, ERR}, {NAME, NAME, NAME, NAME, NAME, ERR, NAME, 1, ERR, ERR, 1, 1, 1, ERR}, {INT, INT, INT, INT, INT, 3, INT, ERR, ERR, ERR, 4, ERR, 2, ERR}, {REAL, REAL, REAL, REAL, REAL, ERR, REAL, ERR, ERR, ERR, 4, ERR, 3, ERR}, {ERR, ERR, 5, ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, 6, ERR}, {ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, ERR, 6, ERR}, {REAL, REAL, REAL, REAL, REAL, ERR, REAL, ERR, ERR, ERR, ERR, ERR, 6, ERR}, {OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, ERR}, {OPER, OPER, OPER, OPER, 9, OPER, OPER, OPER, OPER, OPER, OPER, OPER, OPER, ERR}, {9, 9, 9, 9, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9}, {9, 9, 9, 0, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9}, {11, 11, 11, 11, 11, 11, 12, 11, 15, 11, 11, 11, 11, 11}, {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11}, {13, 13, 13, 13, 13, 13, 14, 13, 13, 15, 13, 13, 13, 13}, {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13}, {STR, STR, STR, STR, STR, ERR, STR, ERR, ERR, ERR, ERR, ERR, ERR, ERR} }; int main (void) { FILE *f; int i, j; f = fopen ("tabela.c", "w"); fprintf (f, "extern int tabela[16][256] = {\n"); for (i = 0; i <16; i++) { fprintf (f, "{"); for (j = 0; j < 33; j++) fprintf (f, "%d, ", tmp[i][0]); fprintf (f, "%d, %d, ", tmp[i][1], tmp[i][8]); for (j = 35; j < 39; j++) fprintf (f, "%d, ", tmp[i][1]); fprintf (f, "%d, %d, %d, %d, %d, %d, %d, %d, %d, ", tmp[i][9], tmp[i][1], tmp[i][1], tmp[i][4], tmp[i][2], tmp[i][1], tmp[i][2], tmp[i][5], tmp[i][3]); for (j = 48; j < 58; j++) fprintf (f, "%d, ", tmp[i][12]); for (j = 58; j < 65; j++) fprintf (f, "%d, ", tmp[i][1]); for (j = 65; j < 69; j++) fprintf (f, "%d, ", tmp[i][11]); fprintf (f, "%d, ", tmp[i][10]); for (j = 70; j < 91; j++) fprintf (f, "%d, ", tmp[i][11]); fprintf (f, "%d, %d, %d, %d, %d, %d, ", tmp[i][1], tmp[i][6], tmp[i][1], tmp[i][1], tmp[i][7], tmp[i][1]); for (j = 96; j < 101; j++) fprintf (f, "%d, ", tmp[i][11]); fprintf (f, "%d, ", tmp[i][10]); for (j = 102; j < 123; j++) fprintf (f, "%d, ", tmp[i][11]); for (j = 123; j < 127; j++) fprintf (f, "%d, ", tmp[i][1]); fprintf (f, "\n"); for (j = 127; j < 255; j++) fprintf (f, "%d, ", tmp[i][13]); fprintf (f, "%d}, \n", tmp[i][13]); } fprintf (f, "};\n"); fclose (f); return 0; } LEKSI.C #include #include "leksi.h" #define ERR 16 int main (void) { int i, c; FILE *fin, *fout; fin = fopen ("leksi.in", "r"); fout = fopen ("leksi.out", "w"); c = fgetc (fin); i = 0; while (!feof (fin)) { i = tabela[i][c]; if (i < ERR) c = fgetc (fin); else { fputc (i + 48, fout); if (i == ERR) c = fgetc (fin); i = 0; } } c = ' '; i = tabela[i][c]; if (i >= ERR) fputc (i + 48, fout); else if (i > 0) fputc ('@', fout); fclose (fin); fclose (fout); return 0; } LEKSI.H #ifndef _LEKSI_H #define _LEKSI_H extern int tabela[16][256]; #endif LEKSI.PAS program Leksi_Pascal; const INPUT_F = 'LEKSI.IN'; OUTPUT_F = 'LEKSI.OUT'; _ERR = 16; _NAME = 17; _INT = 18; _REAL = 19; _STR = 20; _OPER = 21; tmp: array [0..15, 0..13] of byte = ( (0, 7, 7, 8, 7, 3, 7, 1, 11, 13, 1, 1, 2, _ERR), (_NAME, _NAME, _NAME, _NAME, _NAME, _ERR, _NAME, 1, _ERR, _ERR, 1, 1, 1, _ERR), (_INT, _INT, _INT, _INT, _INT, 3, _INT, _ERR, _ERR, _ERR, 4, _ERR, 2, _ERR), (_REAL, _REAL, _REAL, _REAL, _REAL, _ERR, _REAL, _ERR, _ERR, _ERR, 4, _ERR, 3, _ERR), (_ERR, _ERR, 5, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, 6, _ERR), (_ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, 6, _ERR), (_REAL, _REAL, _REAL, _REAL, _REAL, _ERR, _REAL, _ERR, _ERR, _ERR, _ERR, _ERR, 6, _ERR), (_OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _ERR), (_OPER, _OPER, _OPER, _OPER, 9, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _OPER, _ERR), (9, 9, 9, 9, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9), (9, 9, 9, 0, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9), (11, 11, 11, 11, 11, 11, 12, 11, 15, 11, 11, 11, 11, 11), (11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11), (13, 13, 13, 13, 13, 13, 14, 13, 13, 15, 13, 13, 13, 13), (13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13), (_STR, _STR, _STR, _STR, _STR, _ERR, _STR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR, _ERR) ); var fin, fout: text; line : string; i, j, c : integer; tabela : array [0..15, 0..255] of byte; begin for i := 0 to 15 do begin for j := 0 to 32 do tabela[i, j] := tmp[i, 0]; tabela[i, 33] := tmp[i, 1]; tabela[i, 34] := tmp[i, 8]; for j := 35 to 38 do tabela[i, j] := tmp[i, 1]; tabela[i, 39] := tmp[i, 9]; tabela[i, 40] := tmp[i, 1]; tabela[i, 41] := tmp[i, 1]; tabela[i, 42] := tmp[i, 4]; tabela[i, 43] := tmp[i, 2]; tabela[i, 44] := tmp[i, 1]; tabela[i, 45] := tmp[i, 2]; tabela[i, 46] := tmp[i, 5]; tabela[i, 47] := tmp[i, 3]; for j := 48 to 57 do tabela[i, j] := tmp[i, 12]; for j := 58 to 64 do tabela[i, j] := tmp[i, 1]; for j := 65 to 68 do tabela[i, j] := tmp[i, 11]; tabela[i, 69] := tmp[i, 10]; for j := 70 to 90 do tabela[i, j] := tmp[i, 11]; tabela[i, 91] := tmp[i, 1]; tabela[i, 92] := tmp[i, 6]; tabela[i, 93] := tmp[i, 1]; tabela[i, 94] := tmp[i, 1]; tabela[i, 95] := tmp[i, 7]; for j := 96 to 100 do tabela[i, j] := tmp[i, 11]; tabela[i, 101] := tmp[i, 10]; for j := 102 to 122 do tabela[i, j] := tmp[i, 11]; for j := 123 to 126 do tabela[i, j] := tmp[i, 1]; for j := 127 to 254 do tabela[i, j] := tmp[i, 1]; tabela[i, 255] := tmp[i, 13]; end; assign(fin, INPUT_F); assign(fout, OUTPUT_F); reset(fin); rewrite(fout); i := 0; repeat readln(fin, line); c := 1; while c <= length(line) do begin i := tabela[i, ord(line[c])]; if i < _ERR then inc(c) else begin write(fout, chr(i + 48)); i := 0; end; end; until eof(fin); i := tabela[i, ord(' ')]; if i >= _ERR then write(fout, chr(i + 48)) else if i > 0 then write(fout, '@'); close(fin); close(fout); end.