Introduction

1. List the set of token types to be returned by your lexical analyzer.
2. Define regular expressions for this set of token types.
3. Derive a single DFA from your regular expressions.
4. Implement the DFA in a C program. You should implement the lexical analyzer program as a implementation of the DFA where each state in your DFA is a separate function.

Specifications:

• The lexical analyzer should provide a procedure called lexan that returns the next token read from a file stream called source.
• Keyword tokens should be distinct from identifier tokens, and different identifier tokens should be distinct from one another. These distinctions are made with the help of a symbol table.
• The lexical analyzer should convert integer literals, including characters, into numeric values. For example, 'a' should be read as an integer token with value 97, the ASCII code of the character.
• The lexical analyzer should skip over comments which can be of the following forms:

  /* 
    this is a comment
    that can go for several
    lines
  */
  
  // this is a single line comment, where everything to right is ignored
  

• For now, the lexical analyzer should report any error it finds (i.e. output a meaningful error message including the source code line number in which it occurs) and quit.
• On end-of-file, the lexical analyzer should return a special DONE token.
• Design your lexer so that it can read input characters from any file (not just from stdin).

Getting Started

1. First find the tokens from the CFG specification of the language. You may either have one token for punctuation characters (like semicolon) or a single token for all punctuation characters, and then the attribute will specify which token it is. Same with operators and keywords. You should not have tokens for white-space or comments; both should be striped-out by your lexical analyzer.
2. Once you find the set of tokens for C--, create regular expressions for them, and then create a single DFA that accepts all tokens in C-- in two steps:
   1. Convert the regular expressions to a single NFA using algorithm on page 122
   2. Convert the NFA to a DFA using algorithm on page 118
   Remember that char literals that appear in the source code are represented as integer literals inside the compiler (char literals are represented as their ASCII values).

I suggest you use the simplecompiler as a starting point for your solution: ~newhall/public/cs75/simplecompiler/

This contains a Makefile and a reasonable modular design for your solution, both of which you should feel free to change. If you use this as a starting point, you will need to pretty much start over with the code in the lexer.c file, and you will need to change main to call just your lexan function and the emit function (main should not call parse). You can use the error and symbol table functions as they are implemented, or use them as a guide for implementing your own version of the symbol table. Also, you should change the emit function so that it outputs "TOKEN.attr" for every token. After your lexer returns the DONE token, your main function should printout the contents of the symbol table.

For example, if the input is:

if (x1 >= 'a') 

The output of your program should look something like:

IF
LPAREN
ID.x1
GE
NUM.97
RPAREN
DONE

SYMBOL TABLE CONTENTS: 		# if you added keywords to your symbol table, 
----------------------          # they would be printed here too
ID      x1

% ./lexan foo.c--  	# assuming lexan is the name of my LA executable

int main(int argc, char *argv[]) {

What to Hand in

For Parts 1-3

1. A list of token types from part 1
2. The regular expressions form part 2
3. A drawing of your DFA from part 3

A Note on Code Style and Grading:

1. A comment at the top of each file with a high-level overview of the code contained in that module (what is this module and what does it do?).

2. Each function should have a comment containing:
   1. a brief description of what the function does
   2. what the function's input values are
   3. What values the function return(s) (include what is returned on all error conditions as well as regular return values).

   For example, something like this is good:

   /*
    * Function: Area(float w, float h)
    * Computes the area of a rectangle given its height and width
    *
    * param w: the witdth of the rectangle in inches
    * param h: the height of the rectangle in inches
    * returns: the area of the rectangle 
    *          or -1 if the area cannot be computed due to a bad input value 
    */
   

3. The rest of the code should have a few (not overly many) comments to describe important data structures and to describe any complex sequences of code. If a function implements a complicated algorithm, it is good to enumerate the steps of the algorithm in the function's comment, and then have in-line comments of the same steps preceding the code implementing the step: this is a good way to ensure that you remember to implement all steps as you are writing code.

4. My advice is to write the comment first, then write the code. This way your comment will help guide your code writing. Also, by writing the comment at the same time as the code, your comments and code are more likely to match, and it is more efficient (you do not have to go back later and try to figure out what a function does so that you can write its comment).

In addition, you code should be easily extensible to allow for larger problem sizes. For example, if you use a fixed-sized array for the symbol table then use a constant when referring to its max size in your program (e.g. x = SYMTABSIZE; where SYMTABSIZE is defined as a constant) rather than the numeric value (x = 512;). This way, your program can be easily modified to handle a larger symbol table size by making just one change to the constant's definition.

See the links to Unix and C help at the bottom of the cs75 homepage if you need help using some unix commands or debugging your C program.

C-- Programming Language Specification