· 9 years ago · Nov 20, 2016, 07:42 PM
1/*****************************************************************************
2File Name: stable.c
3Compiler: gcc
4Author: Gabriel Bourget
5Course: CST8152 - Compilers
6Assignment: A3 - Symbol Table
7Date: September [INSERT DATE HERE WHEN SUBMITTING], 2016
8Professor: Svillen Ranev
9Purpose: Creates a symbol table that keeps track of VIDs and their attributes.
10Function List: st_create(), st_install(), st_lookup(), st_update_value()
11st_update_type(), st_get_type(), st_destroy(), st_print(), st_setsize(),
12st_incoffset(), st_store(), st_sort()
13*****************************************************************************/
14
15#include "stable.h"
16
17/* Global variables */
18extern STD sym_table;
19
20#define DEBUG
21#undef DEBUG
22
23/********************************st_create()**************************************
24Purpose: Creates a new (and empty) symbol table.
25Author: Gabriel Bourget
26History/Version: v1.0
27Called Functions: malloc(), b_create()
28Parameters: -> st_size (Number of STVR elements to put in symbol table)
29 type: int
30Return Value: STD, representing created symbol table descriptor
31Algorithm: -> Declares a local STD.
32 -> Allocates dynamic memory for an array of STVR of size st_size.
33 -> Initialize the plsBD pointer to a new buffer structure.
34 -> If creation of STD is successful, set its size to st_size.
35 -> Return STD structure that was created.
36*********************************************************************************/
37STD st_create(int st_size) {
38
39 /* Allocate local symbol table */
40 STD sym_table;
41
42 #ifdef DEBUG
43 printf("In st_create\n");
44 #endif
45
46 /* Allocate an array of STVR */
47 if ((sym_table.pstvr = (STVR*)malloc(sizeof(STVR)*st_size)) == NULL) {
48 return sym_table; /* DEV NOTE: WHAT TO RETURN HERE IF THERE IS AN ERROR? */
49 }
50
51 /* Create buffer descriptor for lexeme storage */
52 if ((sym_table.plsBD = b_create(500,15,'f')) == NULL) { /* DEV NOTE: NOT SURE WHAT CREATION PARAMETERS ARE FOR THIS BUFFER STRUCTURE */
53 return sym_table; /* DEV NOTE: WHAT TO RETURN HERE IF THERE IS AN ERROR? */
54 } /* at least 500 chars of initial capacity, USE CONSTANTS NOT NUMBERS */
55
56 /* Buffer creation successful, set st_size and initialize st_offset*/
57 sym_table.st_size = st_size;
58 sym_table.st_offset = 0;
59
60 #ifdef DEBUG
61 printf("Symbol table successfully created.\n");
62 printf("Symbol table size: %d\n",sym_table.st_size);
63 #endif
64
65 return sym_table;
66}
67
68/***********************************st_install()*****************************************
69Purpose: Creates a new (and empty) symbol table.
70Author: Gabriel Bourget
71History/Version: v1.0
72Called Functions: --- FILL THIS IN ---
73Parameters: -> sym_table (symbol table descriptor)
74 type: STD
75 -> lexeme (lexeme to be installed in symbol table)
76 type: char*
77 -> line (line number of first occurence)
78 type: int
79Return Value: int, representing offset location of lexeme, or -1 if table is full
80Algorithm: -> Call the st_lookup() function to search for the lexeme (var name) in
81 the symbol table.
82 -> If the lexeme is not found, install the new one at the current st_offset.
83 -> Set plex and o_line to their corresponding values and that status field to
84 its default value.
85 -> Set the data type indicator to a value corresponding to variable type
86 represented by the formal parameter 'type'.
87 -> The value for the type parameter:
88 -> I for integer.
89 -> F for floating point literal.
90 -> S for string.
91 -> If the variable is of type 'string', set the update flag to 1.
92 -> Set the 'i_value' to 0 for integer/floating point literals, and to -1 for
93 strings.
94 -> Increment st_offset of global sym_table by one.
95 -> If the input lexeme is found, return the offset to its current STVR.
96 -> If the symbol table is full, return -1.
97 -> Return the current st_offset of the entry.
98******************************************************************************************/
99int st_install(STD sym_table, char* lexeme, char type, int line) {
100
101 int lookupIndex = 0; /* Used to look up if lexeme is already stored */
102 int i = 0; /* Iterator */
103 int newOffset = sym_table.st_offset; /* Addition offset */
104 int wordPos; /* Used for setting plex pointer */
105
106 #ifdef DEBUG
107 printf("In st_install\n");
108 printf("Incoming lexeme is %s.\n",lexeme);
109 #endif
110
111 /* Guard against deallocated symbol table and full table */
112 if (sym_table.pstvr == NULL
113 || (sym_table.st_offset > sym_table.st_size)) return R_FAIL1;
114
115 lookupIndex = st_lookup(sym_table,lexeme); /* Offset returned when seeing if lexeme already in database */
116
117 /* See if lexeme is already stored in STVR array */
118 if (lookupIndex != R_FAIL1) return lookupIndex; /* Return index of matched STVR */
119
120 /* Add lexeme into lexeme buffer */
121 for (i=0;i<strlen(lexeme);i++) {
122 b_addc(sym_table.plsBD,lexeme[i]);
123 }
124 b_addc(sym_table.plsBD,'\0'); /* Make it a c-type string */
125
126 wordPos = b_size(sym_table.plsBD) - strlen(lexeme) -1;
127 sym_table.pstvr[newOffset].plex = &b_cbhead(sym_table.plsBD)[wordPos];
128
129 #ifdef DEBUG
130 printf("sym_table.pstvr[%d].plex == %s\n",newOffset,sym_table.pstvr[newOffset].plex);
131 #endif
132
133 sym_table.pstvr[newOffset].o_line = line; /* Set line number */
134 sym_table.pstvr[newOffset].status_field |= SET_DEFAULT; /* Set status_field to default values */
135
136 if (type == 'F') {
137 /* Update type indicator to float */
138 sym_table.pstvr[newOffset].status_field |= SET0201_01;
139 /* Set i_value */
140 sym_table.pstvr[newOffset].i_value.fpl_val = 0;
141 }
142 if (type == 'I') {
143 /* Update type indicator to int */
144 sym_table.pstvr[newOffset].status_field |= SET0201_10;
145 /* Set i_value */
146 sym_table.pstvr[newOffset].status_field = 0;
147 }
148 if (type == 'S') {
149 /* Update type indicator to string */
150 sym_table.pstvr[newOffset].status_field |= SET0201_11;
151 /* Set i_value */
152 sym_table.pstvr[newOffset].i_value.str_offset = -1;
153 /* Set update flag so string can't be updated to different type */
154 sym_table.pstvr[newOffset].status_field |= SET_LSB;
155 }
156
157 st_incoffset();
158 return sym_table.st_offset; /* THIS IS A FLAW: sym_table should be passed in by reference */
159}
160
161/********************************st_lookup()**************************************
162Purpose: Searches for a lexeme (variable name) in the symbol table.
163Author: Gabriel Bourget
164History/Version: v1.0
165Called Functions: strcmp()
166Parameters: -> sym_table (symbol table descriptor)
167 type: STD
168 -> lexeme (lexeme to be installed in symbol table)
169 type: char*
170Return Value: int, representing table position of lexeme
171Algorithm: -> Start search backwards, beginning from last entry in the STVR array.
172 -> If the lexeme is found, return the offset of its location from the
173 beginning of the array.
174 -> If not, return -1.
175*********************************************************************************/
176int st_lookup(STD sym_table, char *lexeme) {
177
178 int i = 0; /* Iterator variable */
179
180 #ifdef DEBUG
181 printf("In st_lookup\n");
182 #endif
183
184 /* Guard against deallocated or empty symbol table */
185 if (sym_table.pstvr == NULL || sym_table.st_offset == 0) return R_FAIL1;
186
187 #ifdef DEBUG
188 printf("Before backwards search\n");
189 #endif
190
191 /* Start from end of array, return location if match found */
192 for (i = (sym_table.st_offset-1);i>0;i--) {
193 if (strcmp(sym_table.pstvr[i].plex,lexeme) == 0) return i;
194 }
195
196 /* No match found */
197 return R_FAIL1;
198}
199
200/********************************st_update_type()**************************************
201Purpose: Updates the data type indicator of the variable record indicated by vid_offset.
202Author: Gabriel Bourget
203History/Version: v1.0
204Called Functions: ---
205Parameters: -> sym_table (symbol table descriptor)
206 type: STD
207 -> vid_offset (position in symbol table to access)
208 type: int
209 -> v_type (variable type to modify to)
210 type: char
211Return Value: int, representing success or failure of update
212Algorithm: -> Check update flag of variable record's status field.
213 -> If it is equal to 1, the type has been updated already, return -1.
214 -> If not, update the data type indicator of the status field.
215 -> Set the update flag.
216 -> Return vid_offset.
217***************************************************************************************/
218int st_update_type(STD sym_table, int vid_offset, char v_type) {
219
220 #ifdef DEBUG
221 printf("In st_update_type\n");
222 #endif
223
224 /* Guard against deallocated symbol table */
225 /* Also, handle case where VID is of type String */
226 if (sym_table.pstvr == NULL || v_type == 'S') return R_FAIL1;
227
228 /* Check if update flag is set */
229 if ((sym_table.pstvr[vid_offset].status_field & CHK_LSB) == 0) {
230 if (v_type == 'F') {
231 /* If type is already string, can't update it */
232 if ((sym_table.pstvr[vid_offset].status_field & CHK_STRING) == 0x0006) return R_FAIL1;
233 /* Update type indicator to float */
234 sym_table.pstvr[vid_offset].status_field |= SET0201_01;
235 }
236 if (v_type == 'I') {
237 /* If type is already string, can't update it */
238 if ((sym_table.pstvr[vid_offset].status_field & CHK_STRING) == 0x0006) return R_FAIL1;
239 /* Update type indicator to int */
240 sym_table.pstvr[vid_offset].status_field |= SET0201_10;
241 }
242 /* Set update flag */
243 sym_table.pstvr[vid_offset].status_field |= SET_LSB;
244 }
245 return R_FAIL1;
246}
247
248/********************************st_update_value()**************************************
249Purpose: Update the i_value of the variable record indicated by vid_offset.
250Author: Gabriel Bourget
251History/Version: v1.0
252Called Functions: ---
253Parameters: -> sym_table (symbol table descriptor)
254 type: STD
255 -> vid_offset (position in symbol table to access)
256 type: int
257 -> i_value (value to change record to)
258 type: InitialValue
259Return Value: int, representing success or failure of update
260Algorithm: -> Check update flag of variable record's status field.
261 -> If it is equal to 1, the type has been updated already, return -1.
262 -> If not, update the data type indicator of the status field.
263 -> Set the update flag.
264 -> Return vid_offset.
265************************************************************************************************/
266int st_update_value(STD sym_table, int vid_offset, InitialValue i_value) {
267
268 #ifdef DEBUG
269 printf("In st_update_value\n");
270 #endif
271
272 /* Guard against deallocated symbol table */
273 /* Also check to see if the status field's update flag is set */
274 if (sym_table.pstvr == NULL
275 || ((sym_table.pstvr[vid_offset].status_field & CHK_LSB) == 1)) return R_FAIL1;
276
277 sym_table.pstvr[vid_offset].i_value = i_value; /* DEV NOT: SKEPTICAL THAT THAT'S ALL THERE IS TO IT */
278 sym_table.pstvr[vid_offset].status_field |= SET_LSB;
279 return vid_offset;
280}
281
282/********************************st_get_type()**************************************
283Purpose: Returns the type of the variable record indicated by vid_offset.
284Author: Gabriel Bourget
285History/Version: v1.0
286Called Functions: --- FILL THIS IN ---
287Parameters: -> sym_table (symbol table descriptor)
288 type: STD
289 -> vid_offset (position in symbol table to access)
290 type: int
291Return Value: char, representing variable record type
292Algorithm: -> Return F for floating point, I for integer type, S for string type.
293 -> Upon failure, return -1.
294***************************************************************************************/
295char st_get_type(STD sym_table, int vid_offset) {
296
297 #ifdef DEBUG
298 printf("In st_get_type\n");
299 #endif
300
301 /* Guard against deallocated symbol table */
302 if (sym_table.pstvr == NULL) return R_FAIL1; /* DEV NOTE: DOES THIS GET CAST AS A CHAR? */
303
304 if ((sym_table.pstvr[vid_offset].status_field & CHK_INT) == 0x0002) return 'F';
305
306 if ((sym_table.pstvr[vid_offset].status_field & CHK_FLOAT) == 0x0004) return 'I';
307
308 if ((sym_table.pstvr[vid_offset].status_field & CHK_STRING) == 0x0006) return 'S';
309
310 return R_FAIL1;
311}
312
313/********************************st_destroy()**************************************
314Purpose: Frees dynamic memory areas associated with the symbol table.
315Author: Gabriel Bourget
316History/Version: v1.0
317Called Functions: free()
318Parameters: -> sym_table (symbol table descriptor)
319 type: STD
320Return Value: ---
321Algorithm: -> Free dynamic memory associated with the symbol table.
322 -> Set st_size of STD to 0.
323***************************************************************************************/
324void st_destroy(STD sym_table) {
325
326 #ifdef DEBUG
327 printf("In st_destroy\n");
328 #endif
329
330 /* Guard against deallocated symbol table */
331 if (sym_table.pstvr == NULL) return;
332
333 b_free(sym_table.plsBD);
334 free(sym_table.pstvr); /* Release memory holding entire VSTR array */
335 st_setsize();
336}
337
338/********************************st_print()**************************************
339Purpose: Prints the contents of the symbol table.
340Author: Gabriel Bourget
341History/Version: v1.0
342Called Functions: fprintf()
343Parameters: -> sym_table (symbol table descriptor)
344 type: STD
345Return Value: int, number of entries or failure indicator
346Algorithm: -> Print the contents of the symbol table to the standard output.
347 -> Return the number of entries or return -1 upon failure.
348***************************************************************************************/
349int st_print(STD sym_table) {
350
351 int i = 0; /* Loop iterator */
352
353 #ifdef DEBUG
354 printf("In st_print\n");
355 #endif
356
357 /* Guard against deallocated symbol table */
358 if (sym_table.pstvr == NULL) return -1;
359
360 fprintf(stdout,"--- Symbol Table --- \n");
361 fprintf(stdout,"Line Number | Variable Identifier\n");
362 for (i=0;i<sym_table.st_size;i++) {
363 fprintf(stdout,"\t%d\t\t%s\n",sym_table.pstvr[i].o_line,sym_table.pstvr[i].plex);
364 }
365
366 return sym_table.st_size;
367}
368
369/***********************************st_setsize()***************************************
370Purpose: Internal function that sets st_size to 0.
371Author: Gabriel Bourget
372History/Version: v1.0
373Called Functions: --- FILL IN LATER ---
374Parameters: ---
375Return Value: ---
376Algorithm: -> Set symbol table's st_size to 0.
377***************************************************************************************/
378static void st_setsize() {sym_table.st_size = 0;}
379
380/*********************************st_incoffset()***************************************
381Purpose: Internal function that increments st_offset by 1.
382Author: Gabriel Bourget
383History/Version: v1.0
384Called Functions: --- FILL IN LATER ---
385Parameters: ---
386Return Value: ---
387Algorithm: -> Increment symbol table's st_offset by 1.
388***************************************************************************************/
389static void st_incoffset() {++sym_table.st_offset;}
390
391/************************************st_store()*****************************************
392Purpose: Stores the symbol table into a text file named $stable.ste.
393Author: Gabriel Bourget
394History/Version: v1.0
395Called Functions: --- FILL IN LATER ---
396Parameters: -> sym_table (symbol table descriptor)
397 type: STD
398Return Value: int, number of records stored or failure indicator
399Algorithm: -> Open a file in the current directory, overwriting if it already exists.
400 -> Print out the symbol table size.
401 -> For each record in the symbol table database...
402 -> Print the status field in hex format.
403 -> Print the length of the lexeme.
404 -> Print the lexeme itself.
405 -> Print the line number it first appeared on.
406 -> Print its initial value.
407 -> Increment the number of records stored.
408 -> Close the file.
409 -> Print out "Symbol table stored."
410 -> Return the number of entries or return -1 upon failure.
411***************************************************************************************/
412int st_store(STD sym_table) {
413
414 int i = 0; /* Iterator variable */
415 FILE *oFile; /* File pointer to text file being written */
416 char varType = '\0'; /* Records variable type for each record */
417 int numRecordsStored = 0; /* Keeps track of the number of records stored */
418
419 #ifdef DEBUG
420 printf("In st_store\n");
421 #endif
422
423 if (sym_table.pstvr == NULL) return R_FAIL1;
424
425 if ((oFile = fopen("$stable.ste","w")) == NULL) return R_FAIL1;
426
427 fprintf(oFile,"%d",sym_table.st_size);
428
429 for (i=0;i<sym_table.st_size;i++) {
430 fprintf(oFile,"%4X ",sym_table.pstvr[i].status_field); /* Status field */
431 fprintf(oFile,"%lu ",strlen(sym_table.pstvr[i].plex)); /* Length of lexeme */
432 fprintf(oFile,"%s ",sym_table.pstvr[i].plex); /* Lexeme */
433 fprintf(oFile,"%d ",sym_table.pstvr[i].o_line); /* Line number */
434
435 /* Initial value */
436 varType = st_get_type(sym_table,i);
437 if (varType == 'F') fprintf(oFile,"%f\n",sym_table.pstvr[i].i_value.fpl_val);
438 if (varType == 'I') fprintf(oFile,"%d\n",sym_table.pstvr[i].i_value.int_val);
439 if (varType == 'S') fprintf(oFile,"%d\n",sym_table.pstvr[i].i_value.str_offset);
440
441 ++numRecordsStored; /* Increment number of records stored */
442 }
443
444 fclose(oFile); /* Close file stream */
445 fprintf(stdout,"Symbol table stored.\n");
446 return numRecordsStored;
447}
448
449/********************************st_asc_comparator()**************************************
450Purpose: Comparator function for the VIDs stored in the symbol table database. Passed to
451 qsort() function eventually for use in sorting entries in an ascending fashion.
452Author: Gabriel Bourget
453History/Version: v1.0
454Called Functions: strcmp()
455Parameters: -> a (pointer to element a)
456 type: const void*
457 -> b (pointer to element b)
458 type: const void*
459Return Value: int, comparison result
460Algorithm: -> Conduct lexicographic comparison of two strings.
461******************************************************************************************/
462static int st_asc_comparator(const void *a, const void *b) {
463 return (strcmp((char*)a,(char*)b));
464}
465
466/********************************st_desc_comparator()**************************************
467Purpose: Comparator function for the VIDs stored in the symbol table database. Passed to
468 qsort() function eventually for use in sorting entries in an descending fashion.
469Author: Gabriel Bourget
470History/Version: v1.0
471Called Functions: strcmp()
472Parameters: -> a (pointer to element a)
473 type: const void*
474 -> b (pointer to element b)
475 type: const void*
476Return Value: int, comparison result
477Algorithm: -> Conduct lexicographic comparison of two strings.
478*******************************************************************************************/
479static int st_desc_comparator(const void *a, const void *b) {
480 return (strcmp((char*)b,(char*)a));
481}
482
483/************************************st_sort()*****************************************
484Purpose: Sorts the contents of the STVR array.
485Author: Gabriel Bourget
486History/Version: v1.0
487Called Functions: -- FILL IN LATER ---
488Parameters: -> sym_table (symbol table descriptor)
489 type: STD
490 -> s_order (sorting order, ascending or descending)
491 type: char
492Return Value: int, sort status
493Algorithm: -> Call qsort function with context of order being asked for.
494***************************************************************************************/
495int st_sort(STD sym_table, char s_order) {
496
497 #ifdef DEBUG
498 printf("In st_sort\n");
499 #endif
500
501 /* Guard against deallocated symbol table */
502 if (sym_table.pstvr == NULL) return R_FAIL1;
503
504 if (s_order == 'A') {
505 /* Sort elements in symbol table ascendingly by lexeme name */
506 qsort((sym_table.pstvr)->plex,sym_table.st_size,sizeof(char),st_asc_comparator);
507 return 1;
508 }
509
510 if (s_order == 'D') {
511 /* Sort elements in symbol table descendingly by lexeme name */
512 qsort((sym_table.pstvr)->plex,sym_table.st_size,sizeof(char),st_desc_comparator);
513 return 1;
514 }
515
516 return R_FAIL1;
517}