Lexical analyzer for a programming language

Question

I'm doing a lexical analyzer for my programming language and I don't know if I'm doing it right. Can anyone can help me with this or suggest a better way of doing it?

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

struct node
{
    char character;
        struct node *link;
}*front = NULL, *rear = NULL;

int isEmpty()
{
        if(front == NULL)
                return 1;
        else
                return 0;
}

char name[4] = "\0";

void enqueue(char character)
{
        struct node *tmp;
        tmp = (struct node *)malloc(sizeof(struct node));
        if(tmp == NULL)
                return;

        tmp -> character = character;
        tmp -> link = NULL;
        if(front == NULL)
        front = tmp;
        else
        rear -> link = tmp;
        rear = tmp;
}

char dequeue()
{
        struct node *tmp;
        char character;
        if(isEmpty())
                return NULL;

        tmp = front;
        character = tmp -> character;
        front = front -> link;
        free(tmp);
        return character;
}

char peek()
{
        if(isEmpty())
                return NULL;
        return front -> character;
}

void display()
{
        struct node *ptr;
        ptr = front;
        if(isEmpty())
                return;

        while(ptr != NULL)
        {
        printf("%c ", ptr -> character);
        ptr = ptr -> link;
        }
}

int issymbol(char c)
{
        char symbols[] = {"!@#$%^&*()_-.?<>,+=-/\\"};

        for(int b = 0; b < strlen(symbols); b++)
                if(c == symbols[b])
                        return 0;
        return 1;
}

int checkIdent(char ident)
{
        if(issymbol(ident))
                return 28;
        else
                return -2;
}

int automaton()
{
        int i = 0;
        char ident[50] = "\0";
        char ch = '\0';
        int next = 0;

        while(1)
        {
                if(peek() == 'c') {
                        ident[i++] = dequeue();
                        if(peek() == 'a') {
                                ident[i++] = dequeue();
                                if(peek() == 's') {
                                        ident[i++] = dequeue();
                                        if(peek() == 'e') {
                                                ident[i++] = dequeue();
                                                if(isalpha(peek()))
                                                        return checkIdent(ch);
                                                else if(isspace(peek()) || peek() == NULL) {
                                                        dequeue();
                                                        return 0;
                                                }
                                        } else
                                                return -1;
                                } else
                                        return -1;
                        } else
                                return -1;
                }

                else if(peek() == 'd') {
                        ident[i++] = dequeue();
                        if(peek() == 'o') {
                                ident[i++] = dequeue();
                                if(isalpha(peek())) {
                                        for(int k = 0; k < next; k++)
                                                name[k] = ident[k];
                                        ch = ident[next + 1];
                                        return checkIdent(ch);
                                }
                                if(isspace(peek()) || peek() == NULL) {
                                        dequeue();
                                        return 1;
                                }
                        } else
                                return -1;
                }

                else if(peek() == 'e') {
                        ident[i++] = dequeue();
                        ch = ident[0];
                        if(peek() == 'l') {
                                ident[i++] = dequeue();
                                if(peek() == 's') {
                                        ident[i++] = dequeue();
                                        if(peek() == 'e') {
                                                ident[i++] = dequeue();
                                                if(isspace(peek())) {
                                                        next = i;
                                                        ident[i++] = dequeue();
                                                        if(peek() == 'i') {
                                                                ident[i++] = dequeue();
                                                                if(peek() == 'f') {
                                                                        ident[i++] = dequeue();
                                                                        if(isalpha(peek())) {
                                                                                for(int k = 0; k < next; k++)
                                                                                        name[k] = ident[k];
                                                                                ch = ident[next + 1];
                                                                                return checkIdent(ch);
                                                                        }
                                                                        if(isspace(peek()) || peek() == NULL) {
                                                                                dequeue();
                                                                                return 3;
                                                                        }
                                                                }
                                                                else {
                                                                        for(int k = 0; k < next; k++)
                                                                                name[k] = ident[k];
                                                                        ch = ident[next + 1];
                                                                        return checkIdent(ch);
                                                                }
                                                        }
                                                        else if (isalpha(peek())) {
                                                                for(int k = 0; k < next; k++)
                                                                        name[k] = ident[k];
                                                                ch = ident[next];
                                                                return checkIdent(ch);
                                                        }
                                                        return 2;
                                                } else if(peek() == NULL)
                                                        return 2;
                                                else if(isalpha(peek()))
                                                        return checkIdent(ch);
                                        } else
                                                return -1;
                                } else
                                        return -1;
                        } else
                                return -1;      
                }                

                else            
                        return -1;  
        }                    
}                        

void readSourceCode()    
{                        
        FILE *f = fopen("SAMPLE.nsf","r");
        char c;              

        while((c = getc(f)) != EOF)
                enqueue(c);      

        fclose(f);          
}                        

void main()              
{                        
        clrscr();            
        readSourceCode();              

        while(isEmpty() != 1)
        {
                int i = automaton();
                switch(i)
                {                    
                        case 0: printf("CASE\n"); break;
                        case 1: printf("DO\n"); break;
                        case 2: printf("ELSE\n"); break;
                        case 3: printf("ELSE IF\n"); break;
                        case 28: printf("IDENT\n"); break;
                        default : printf("Invalid! %d", i);
                }

                //printf("%d\n", strlen(name));

                /*if(i == 28 && name[0] != '\0')
                {
                        for(int i = 0; i < strlen(name); i++)
                                printf("%c", name[i]);
                }*/
        }
        getch();            
}

Answer 1

Things you could improve:

Compilation:

• I am led to believe that you are compiling your code as C++ code.

  tmp = (struct node *)malloc(sizeof(struct node));
  

  That line right there would be unacceptable when compiling as C code. And considering that your question originally had c++ on it, I am further convinced that you are compiling your C code as C++ code. Don't do that.

  Here is a very long list of the incompatibilities between ISO C and ISO C++. Those are the reasons you compile C code, as C code.

  If I happen to be wrong in my assumption that you are compiling C code as C++ code, you still should not be casting the results of malloc().

Variables/Initialization:

• You shouldn't use global variables.

  *front = NULL, *rear = NULL;
  

  The problem with global variables is that since every function has access to these, it becomes increasingly hard to figure out which functions actually read and write these variables.

  To understand how the application works, you pretty much have to take into account every function which modifies the global state. That can be done, but as the application grows it will get harder to the point of being virtually impossible (or at least a complete waste of time).

  If you don't rely on global variables, you can pass state around between different functions as needed. That way you stand a much better chance of understanding what each function does, as you don't need to take the global state into account.

  So instead of using global variables, initialize the variables in main(), and pass them as arguments to functions if necessary.

• You aren't initializing your arrays properly.

  char name[4] = "\0";
  

  You should be initializing all of your characters in the array at once.

  char name[4] = {0};
  

Efficiency:

• You can use the inline keyword on some of your functions. The point of making a function inline is to hint to the compiler that it is worth making some form of extra effort to call the function faster than it would otherwise - generally by substituting the code of the function into its caller. As well as eliminating the need for a call and return sequence, it might allow the compiler to perform certain optimizations between the bodies of both functions.

  inline int isEmpty(Node front)
  

Returns:

• You aren't returning a value from main().

  void main()
  

  You should always return a value from main(). This is an indication of the status of your program, and whether or not it exited successfully. This is very important information when it comes to debugging.

  int main(void)
  {
      ...
      return 0;  // standard return code for successive exit
  }
  

• NULL isn't a char, so you shouldn't treat it as one when you return it.

  char peek()
  {
   if(isEmpty())
       return NULL;
   return front -> character;
  }
  

  return the NUL-terminator character instead.

  return '\0';
  

Syntax

• typedef your structs, and declare and initialize them elsewhere.

  struct node
  {
      char character;
          struct node *link;
  }*front = NULL, *rear = NULL;
  

  The typedef means you no longer have to write struct all over the place. That not only saves some space, it also can make the code cleaner since it provides a bit more abstraction.

  typedef struct
  {
      char character;
      struct node *link;
  } Node;
  

• You can simplify your NULL checks.

   if(front == NULL)
  

  Since NULL is defined as (void *)0, we can treat is as a comparison to 0.

  if (!front)
  

• Use ternary operators when you have simple if-else statements.

   if(front == NULL)
       return 1;
   else
       return 0;
  }
  

  The ternary conditional expression is just as simple and verbose as your code, and a whole lot shorter.

  return (!front) ? 1 : 0;
  

  But since we are returning whether this function is true or not, we don't even have a need for the conditional expression at all.

  return !front;
  

• You don't accept any parameters for some of your functions, such as main(). If you do not take in any parameters, declare them as void.

  int main(void)
  

• You have a comparison between an int and a void *.

  peek() == NULL
  

  Compare to 0 instead.

  0 == peek()
  

Indentation

• You are very inconsistent with your indenting.

  if(front == NULL)
  front = tmp;
  else
  rear -> link = tmp;
  rear = tmp;
  

  This isn't very readable. For one, you don't include braces, which is a whole 'nother debate within itself, but then you don't use indentation. Please do everyone that is trying to read your code a favor, and indent your code properly.

Comments:

• Comments are very important to have in your source code. Your program has a lack of comments that explain why your code does what it does. You should add some so you other people can follow your code more easily.

• For the comments you do have...

  //printf("%d\n", strlen(name));
  
  /*if(i == 28 && name[0] != '\0')
   {
   for(int i = 0; i < strlen(name); i++)
   printf("%c", name[i]);
   }*/
  

  Remove them. Commented out code is really just useless clutter.

Answer 2

I think you're overcomplicating the problem by working a character at a time.

• Reading one character at a time using getc() is inefficient. You could fetch a bigger chunk at a time using fread().
• Wrapping each character into a linked list node is wasteful. While each character normally takes one byte when stored in a large array or a string, your linked list node is likely to take more than eight bytes. On a 32-bit system, a struct node will probably use one byte for the character itself, four bytes for a pointer, and three wasted bytes in between to allow the pointer to be aligned at an address that is a multiple of four. On a 64-bit system, it would be even worse. Also, malloc() incurs some memory overhead for its bookkeeping (so that it remembers the size of the chunk of memory that will be liberated when free() is eventually called).
• Analyzing the text one character at a time is tedious. That's some of the deepest indentation I've seen in any code. If you keep the data as a string, you could use some string handling routines from the standard C library, such as strsep().

Suggestion

I'll try to provide some guidance without giving away a complete solution to your homework.

The key insight is that it is possible to construct an automaton that works at a higher level than character-by-character.

I'll start with main().

/* Advice: The C standard says that main() must return an int, not void. */
int main(int argc, char *argv[]) {
    /* Advice: Don't hard-code input filename.  Accept a command-line parameter instead */
    if (argc < 2) {
        fprintf(stderr, "Usage: %s FILENAME\n", argv[0]);
        return 1;
    }
    const char *filename = argv[1];

    /* Advice: Avoid global variables. Return a pointer instead. */
    char *program = readSourceCode(filename);
    if (!program) {
        perror(filename);
        return 1;
    }

    const char *cursor = program;
    while (*cursor) {
        /* Advice: What does your automaton do?  Pick an informative name. */
        switch (consumeKeyword(&cursor)) {
          /* Advice: Avoid magic numbers.  #define constants or use an enum. */
          case CASE:    printf("CASE\n"); break;
          case DO:      printf("DO\n"); break;
          case ELSE:    printf("ELSE\n"); break;
          case ELSEIF:  printf("ELSE IF\n"); break;
          default:
            if (isIdentifier(&cursor)) {
                printf("IDENT\n"); break;
            } else {
                printf("Invalid! %s", cursor);
            }
            free(program);
            return 1;
        }
    }

    free(program);
    return 0;
}

The first thing to get out of the way is readSourceCode(). See if you can implement this:

/**
 * Returns the contents of the specified file as a NUL-terminated string.
 * If any error occurs (e.g. file not found, permission denied, no free memory),
 * returns NULL, and errno will tell the reason.
 */
char *readSourceCode(const char *filename) {
    /* Hints: Use stat() or fstat() to find the file size.
       Allocate that many bytes, plus 1 for the '\0'.
       Remember to fclose() when done!
     */
    …
}

The main challenge is consumeKeyword(). As you can see, main() passes a "cursor" to consumeKeyword() — it does so by reference, so that consumeKeyword() can increment main's cursor.

enum keyword {
    NOT_A_KEYWORD,
    …
};

/**
 * Skips over any whitespace characters at the cursor, then looks for any
 * recognizable keywords.  If a keyword is found, advances the cursor to
 * just beyond the end of the keyword.  If no keyword is found, returns
 * NOT_A_KEYWORD and leaves the cursor in place.
 */
enum keyword consumeKeyword(const char **cursor) {
    while (isspace(**cursor)) {
        (*cursor)++;
    }
    size_t advance;
    if ((advance = isKeyword(cursor, "case"))) {
        *cursor += advance;
        return CASE;
    } else if … {
        …
    } else {
        return NOT_A_KEYWORD;
    }
}

You should be able to fill in the rest:

/**
 * If the specified keyword is found at the specified cursor position,
 * returns the length of the keyword.  Otherwise, returns 0.
 */
size_t isKeyword(const char *const *cursor, const char *keyword) {
    /* Hint: With a for-loop, the entire function should take no more
       than four lines. */
}

Answer 3

Right now, I think your automaton has an awful lot of code to just recognize 4 key words. A typical lexer will read an entire (potential) token, then compare it to a table of key words to see if it matches any of them.

For example, let's assume a token must always consist of a letter followed by an arbitrary number of letters and/or digits. That's pretty easy to encode:

void read_ident(char *id, size_t max) { 
    unsigned pos = 0;
    if (isalpha(peek())) 
        while (isalnum(ch=getnext())&&pos < MAX)
            id[pos++] = ch;
    id[pos] = '\0';
}

Using this (or something similar) code to read some key words would end up quite a bit simpler:

static char const *table[] = {
    "case",
    "do",
    "else",
    "if"
};

#define elements(table) (sizeof(table)/sizeof(table[0]))
char buffer[256];

read_ident(buffer, sizeof(buffer));
for (i=0; i<elements(table); i++)
    if (0 == strcmp(buffer, table[i])
        return i;
// none of them matched
return 28;

Note that (at least for the moment) I've had it recognize "if", rather than "else if", as a keyword. I'd recognize else if as two key words: an else followed by an if, rather than as a single key word (that happens to include a space). That's not the only way to do things, but it's generally simpler.

For the moment, I've had it do a simple linear search through the table to find a (possible) keyword. Given the small number of key words you've given, that makes sense. If you had to deal with more key words, you might want to switch to a sorted table so you could use a binary search, or else to a hash table. If the 28 you used as a magic number elsewhere indicates you actually have 27 key words to recognize, a sorted table might improve speed a little, but a hash table is probably overkill.

That brings us to one other point: returning "magic" numbers for the key words (0, 1, 2, 3, 28). You normally want to use an enum (or series of #defines) to give logical names to these instead of using the raw numbers directly:

 enum { INVALID = -1, T_DO, T_CASE, T_IF, T_ELSE, T_ID};

Then the code that uses it can look a little more meaningful, like:

switch (token) { 
    T_DO:           printf("do\n");       break;
    T_CASE:         printf("case\n");     break;
    T_IF:           printf("if\n");       break;
    T_ELSE:         printf("else\n");     break;
    T_ID:           printf("ID\n");       break;
    T_INVALID:
    default:        printf("Invalid\n");  break;
}

Another possibility to consider (since you can make these contiguous and starting from 0) is to use them as an index into an array instead:

if (token >= 0 && token <= T_LAST)
    printf("%s\n", table[token]);

Note that for this, you can (and usually want to) re-use the same table you used to find keywords when tokenizing.

Answer 4

Approach

I would use arrays rather than an unnecessary linked list structure. In particular, have an array of the contents with an index into it (or pointer) and an array of your current token. This way you avoid the expensive overhead of allocating and deallocating all of the time, and you get cache locality. From a theoretical point of view, operating on characters is fine, but from a practical point of view, it's incredibly inefficient.

---

Rather than doing character by character scanning, I would try to use more general rules and then back track to check for correctness. For example, you can keep scanning forward as long as you have an alphabetic character. Then, you can check the token to make sure it's an acceptable token. A very crude example of this:

char* contents = ...;
char* content_ptr = ...;

char* token = ...;
char* token_ptr = token;

memset(token, 0, token_size);

while (isalpha(*content_ptr)) {
    *token++ = *content_ptr++;
}

if (is_valid_token(token)) {
    // do something with the token
} else {
    // Parse error!
}

So, if you had "while cake" your code would parse through the token "while", see that it's valid, store it somehow, and then continue on (the code to skip over non-tokens is not included in my example, but you could likely get away with just eating white space). When getting to "cake", you could go ahead and capture the entire thing, and only when you've captured the entire token see that it's a non-sense token and spit out an error. This way simplifies your processing since it allows you to think at a token level rather than an atom level.

---

Really, if you're planning on continuing this much farther, I would consider using something like lex. You can just give it a set of rules, and it will build an automaton for you. DFAs are quite cumbersome to build by hand and if you decide to change rules, they get even more difficult to work with. By working at a rule level, you get to avoid that clutter. You can even pair lex with something like bison to create a full parser rather than just a lexer.

---

Technicalities

There are a few things wrong with your code from a technical point of view. A good place to start is compiling with a modern compiler with the warnings turned on and thinking long and hard if the warnings are worth ignoring (hint: they almost never are).

A lot of things have been covered by others, so I will only post what I believe no one else has mentioned yet.

---

char peek()
{
        if(isEmpty())
                return NULL;
        return front -> character;
}

NULL is not a valid value for a char. Yes, it's technically allowed, but it's a very bad idea. NULL is a possible value for a pointer, not a character. It would be like int x = 'a';. Yes, it's technically possible, but it's nonsensical. If you want NULL-like sentinel for a character, you can use a null character (0, or '\0').

---

When possible, avoid non-standard parts of C. In particular, conio.h is going to tie you to very specific environments (in particular, Windows with either Turbo C compiler or Microsoft's Visual Studio's C compiler). clrscr is probably not worth tying yourself to windows over. In fact, I would consider this program clearing my terminal to be annoying. Let the terminal handle its own rendering.

---

What if reading the file fails? readSourceCode() gives no indication of success or failure. Also, if the fopen call fails, the read on the is likely going to cause a segfault. You need to check error conditions more carefully.

---

Globals have very, very few legitimate uses. Get out of the habit of using them as quickly as you can.

---

Anytime you hard code a string like a file name, ask yourself if it should be a parameter instead. Instead of readSourceCode having the file path hard coded, it should be parameter.

---

Actually, the filepath shouldn't be a parameter. A function should never create a resource it uses based on it's inputs. Rather than a filepath, you would want to pass readSourceCode a FILE*. That way it has one less responsibility in that it no longer has to handle opening/closing the file. It only has to handle reading it (look up single responsibility principle).