Chapter 6 - Structures 6

Implement a simple version of the #define processor (i.e., no arguments) suitable for use with C programs, based on the routines of this section. You may also find getch and ungetch helpful.

Solution by Akil Adeshwar

 

 

/*
   Implement a simple version of the #define processor (i.e., no arguments)
   suitable for use with C programs, based on the routines of this section.
   You may also find getch and ungetch helpful.
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define HASHSIZE 101
#define MAXLEN 200
#define BUFSIZE 1000
#define STATE_OUT 321
#define STATE_IN_NO_NAME 322
#define STATE_IN_WITH_NAME 323

static int state = STATE_OUT; // Initial state

char buf[BUFSIZE];
int bufp = 0;

int getch(FILE *fp){
 return (bufp > 0)? buf[--bufp] : fgetc(fp);
}

void ungetch(int c){
 if(bufp >= BUFSIZE)
  printf("\nUngetch: Too many characters");
 else
  buf[bufp++] = c;
}

// Data structure to store the definitions
typedef struct list{
 struct list *next;
 char *name;
 char *defn;
}nlist;

static nlist *hashtab[HASHSIZE]; // Pointer Table

// Hash
unsigned hash(char *s){

 unsigned hashval;
 
 for(hashval=0; *s!='\0'; s++)
  hashval = *s + 31 * hashval;

 return hashval%HASHSIZE;
}

//Lookup

nlist *lookup(char *s){

 nlist *np;
 
 for(np = hashtab[hash(s)];np!=NULL;np=np->next)
  if(strcmp(np->name,s) == 0)
   return np;
 return NULL;
}

// Install

nlist *install(char *name,char *defn){

 nlist *np;
 unsigned hashval;
 hashval = hash(name);

 if((np = lookup(name))== NULL){

  np = (nlist *) malloc(sizeof(nlist));
  if((np->name=strdup(name))==NULL)
   return NULL;
  np->next = NULL;
  if(hashtab[hashval]==NULL){
   hashtab[hashval] = np;
  } else {
   np->next = hashtab[hashval];
   hashtab[hashval] = np;
  }
 }
 else
  free((void *) np->defn);

 if((np->defn = strdup(defn))==NULL)
  return NULL;
 return np;
}

// Print the Lookup Table
void print_all_def(){
 int i=0;
 for(;i<HASHSIZE;i++){
  if(hashtab[i]!=NULL){
   nlist *p = hashtab[i];
   while(p!=NULL){
    printf("LABEL: %s DEFN: %s\n",p->name,p->defn);
    p = p->next;
   }
  }
 }
}

int getword(char *word,int lim,FILE *fp){
 
 int c;
 char *w = word;

 while(isspace(c = getch(fp)));
 if(c==EOF){
  if(state == STATE_OUT)
   return -1;
  else{
   puts("Error: Incorrect definition\n");
   return -1;
  }
 }
 // Word should be identifier in STATE_IN_WITH_NAME to name the definition
 if(isalpha(c) || c=='_' || (state == STATE_OUT) || state==STATE_IN_WITH_NAME)
  *w++=c;
 if(!isalpha(c) && c!='_' && state!=STATE_OUT && state!=STATE_IN_WITH_NAME){
  *w = '\0';
  return w-word;
 }
 for(; --lim>0; w++){
  *w = getch(fp);
  if(state!=STATE_IN_WITH_NAME){
   // Name of definition must be a valid identifier
   if((!isalnum(*w) && *w!='_')){
    ungetch(*w);
    break;
   }
  }
  else
   if(isspace(*w)) // Definition can be any character
    break;
 }
 *w = '\0';
 return w-word;
}

int main(void){
 puts("\nCheck t6.txt to understand the below output:\n"); 
 char line[MAXLEN];
 FILE *fp = fopen("t6.txt","r");
 char *name,*defn,*p;
 int len;
 if(fp!=NULL){
  while((len = getword(line,MAXLEN,fp)>0)){
   switch(state){

    case STATE_OUT:
     if(strcmp(line,"#define")==0)
      state = STATE_IN_NO_NAME;
     else{
      /*
         Check if line is present in lookup table,
         if yes, substitute the definition, else print as it is.
         */
      nlist *np;
      if((np=lookup(line))==NULL)
       printf("%s ",line);
      else
       printf("%s ",np->defn);
     } 
     break;
    case STATE_IN_NO_NAME:
     // Received name for definition
     name = (char *) malloc(len);
     strcpy(name,line);
     state = STATE_IN_WITH_NAME;
     break;
    case STATE_IN_WITH_NAME:
     // Received defn for name
     defn = (char *) malloc(len);
     strcpy(defn,line);
     // Update the lookup table
     if(install(name,defn)==NULL){
      puts("Insert Error");
      return -1;
     }
     state = STATE_OUT;
     break;
   }
  }
  // Print the Lookup Table
  printf("\nLookup Table Now: \n");
  print_all_def();
  fclose(fp);
 }
 return 0;
}

 

 

Solution by Barrett Drawdy
/*
 * K&R2 exercise 6-6.  By: Barrett Drawdy
 * "Implement a simple version of the #define processor (i.e., no arguments)
 * suitable for use with C programs, based on the routines of this section.
 * You may also find getch and ungetch helpful."
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define HASHSIZE 101
#define MAXWORD 1000

/* nlist:  From K&R2 page 144.  Points to a search text and
 * a replacement text */
struct nlist
{
 struct nlist *next;
 char *name;
 char *defn;
};

static struct nlist *hashtab[HASHSIZE];

struct nlist *lookup(char *);
struct nlist *install(char *, char *);
int process(void);
int getch(void);
void ungetch(int);
int preproc(void);
int backslash(void);
int comment(void);
int literal(void);
int readword(void);

int main(void)
{
 int c;
 const int done = 0;     /* just a dummy for the infinite loop */
 int status = 1; /* 1 at line begin, 2 for failure, 0 otherwise */
 
 while(!done) {
  while(isspace(c = getch())) {
   putchar(c);
   if(c == '\n')
    status = 1;
  }
  
  if(c == '#' && status == 1)
   status = preproc();
  
  else if(c == '\\')
   status = backslash();
  
  else if(c == '/')
   status = comment();
  
  else if(c == '\"')
   status = literal();
  
  else if(c == EOF)
   return 0;
  
  else if(!isalpha(c) && c != '_') {
   putchar(c);
   status = 0;
  }
  
  else {
   ungetch(c);
   status = readword();
  }
  
  if(status == 2)
   return 1;
 }
 return 0;
} /* end main() */

/*
 * preproc:  Called when a '#' is found at the beginning of a line.
 * If a #define statement is found, it stores add the search and replacement
 * text to the hash table.  Otherwise it just prints what it reads.
 * The line a #define statement is found on is replaced with a blank line.
 */
int preproc(void)
{
 int c;
 char name[MAXWORD+1], defn[MAXWORD+1];
 char *n, *d;
 
 /* Read what comes after the '#' */
 for(n = name; isalpha(c = getch()) && n - name < MAXWORD; ++n)
  *n = c;
 *n = '\0';
 
 /* If it's a #define... */
 if(strcmp(name, "define") == 0) {
  
  /* ignore whitespace */
  while(isspace(c)) {
   if(c == '\n') { /* a #define followed by a '\n' is discarded */
    putchar(c);
    return 1;
   }
   c = getch();
  }
  
  /* Read search text */
  for(n = name; (isalnum(c) || c == '_') && n - name < MAXWORD; ++n) {
   *n = c;
   c = getch();
  }
  *n = '\0';
  
  /* Ignore whitespace */
  while(isspace(c)) {
   if(c == '\n')
    *defn = '\0'; /* If there is no replacement text. */
   c = getch();
  }
  
  /* Read replacement text. */
  for(d = defn; (isalnum(c) || c == '_') && d - defn < MAXWORD; ++d) {
   *d = c;
   c = getch();
  }
  *d = '\0';
  
  /* Add to hash table. */
  if(install(name, defn) == NULL)
   return 2;
 }
 else {                    /* not a #define statement */
  putchar('#');
  printf("%s", name);
 }
 
 /* finish line reading/printing line */
 while(c != '\n') {
  if(c == EOF)
   return EOF;
  putchar(c);
  c = getch();
 }
 putchar(c);
 return 1;
} /* end preproc() */

/*
 * backslash:  Makes sure that if a /, *, or " is preceded by a \ it is
 * just printed, not used in a comment or string literal.
 */
int backslash(void)
{
 int c, slash = 1;
 putchar('\\');
 while((c = getch()) == '\\') {
  slash = !slash;
  putchar(c);
 }
 
 if(slash)
  putchar(c);
 else
  ungetch(c);
 
 return 0;
} /* end backslash() */

/*
 * comment:  Prints comments without changes.
 */
int comment(void)
{
 int c;
 int after_star = 0;
 
 putchar('/');
 
 if((c = getch()) == '*') {   /* comment begin */
  putchar(c);
  c = getch();
  
  while(c != EOF) {
   if(c == '\\') {
    backslash();
    after_star = 0;
   }
   else if(c == '*') {
    after_star = 1;
    putchar(c);
   }
   else if(c == '/' && after_star) {
    putchar(c);
    return 0;
   }
   else {
    after_star = 0;
    putchar(c);
   }
   c = getch();
  }
  
  if(c == EOF)
   return EOF;
  
  putchar(c);
  return 0;
 }
 else {
  ungetch(c);
  return 0;
 }
} /* end comment() */

/*
 * literal:  Prints string literals without changes.
 */
int literal(void)
{
 int c;
 putchar('\"');
 c = getch();
 
 while(c != '\"' && c != EOF) {
  if(c == '\\')
   backslash();
  else
   putchar(c);
  c = getch();
 }
 
 if(c == EOF)
  return EOF;
 
 putchar(c);
 return 0;
} /* end literal() */

/*
 * readwood:  Reads an identifier and looks for it in the hash table.  If
 * it's found, it's replaced with the replacement text.  Otherwise, it is
 * printed as is.
 */
int readword(void)
{
 int c;
 char word[MAXWORD];
 char *w;
 struct nlist *node;
 
 c = getch();
 for(w = word; (isalnum(c) || c == '_') && c != EOF; ++w) {
  *w = c;
  c = getch();
 }
 *w = '\0';
 node = lookup(word);
 if(node == NULL)
  printf("%s", word);
 else
  printf("%s", node->defn);
 
 if(c == EOF)
  return EOF;
 
 ungetch(c);
 return 0;
} /* end readword() */

/***************************************************************************
 *                              From K&R2                                  *
 ***************************************************************************/

unsigned hash(char *);
char *strdup(char *);

/* lookup: From K&R2 page 145. Look for s in hashtab. */
struct nlist *lookup(char *s)
{
 struct nlist *np;
 for(np = hashtab[hash(s)]; np != NULL; np = np->next)
  if(strcmp(s, np->name) == 0)
   return np;
 return NULL;
}

/* install: From K&R2 page 145. Put (name, defn) in hashtab. */
struct nlist *install(char *name, char *defn)
{
 struct nlist *np;
 unsigned hashval;
 
 if((np = lookup(name)) == NULL) {
  np = (struct nlist *) malloc(sizeof(*np));
  if(np == NULL || (np->name = strdup(name)) == NULL)
   return NULL;
  hashval = hash(name);
  np->next = hashtab[hashval];
  hashtab[hashval] = np;
 }
 else
  free((void *) np->defn);
 if((np->defn = strdup(defn)) == NULL)
  return NULL;
 return np;
}

/* hash: From K&R2 page 144.  Form hash value for string s. */
unsigned hash(char *s)
{
 unsigned hashval;
 for(hashval = 0; *s != '\0'; ++s)
  hashval = *s + 31 * hashval;
 return hashval % HASHSIZE;
}

/* strdup: From K&R2 page 143. Makes a duplicate of s. */
char *strdup(char *s)
{
 char *p;
 p = (char *) malloc(strlen(s) + 1);
 if(p != NULL)
  strcpy(p, s);
 return p;
}

#define BUFSIZE 100

char buf[BUFSIZE];  /* buffer for ungetch() */
int bufp = 0;       /* next free position in buf */

int getch(void) { /* get a (possibly pushed back) character */
 return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) {  /* push character back on input */
 if(bufp >= BUFSIZE)
  printf("ungetch: too many characters\n");
 else
  buf[bufp++] = c;
 return;
}