Scanning C++

One of the first jobs performed by a compiler is to read in the source code (which is really just one long string of characters) and group individual characters into tokens, the lowest level of symbol used in defining a programming language. Examples of tokens include identifiers, keywords, and the arithmetic and boolean operators. This process of breaking the source code up into tokens is called scanning. Your assignment is to build a scanner for C++.

C++ Tokens

C++ has the following classes of tokens. (See the C++ reference manual if you have any questions about the exact form of a token.)

1. Identifiers: an arbitrarily long sequence of letters, digits, or the underscore character; the first character cannot be a digit.

2. Keywords: asm, auto, break, case, char, class, const, continue, default, delete, do, double, else, if, inline, int, long, new, operator, overload, public, register, return, short, sizeof, static, struct, switch, this, typedef, union, unsigned, virtual, void, while.

3. Constants: there are four types of constants

   1. Integers: a sequence of one or more digits. An integer that begins with zero is an octal integer and may only include the digits zero thru seven. An integer that begins with zero and then an X (or x) is a hexadecimal integer and may contain digits a (or A) thru f (or F).

   2. Longs: an integer constant followed by the letter l (or L).

   3. Floats: consist of an integer part, a decimal point, a fraction part, an e (or E), and an optionally signed integer exponent. Either the integer part or the fractional part may be omitted, but not both. Either the decimal point or the e (or E) and exponent may be missing, but not both.

   4. Characters: any character enclosed in single quotes. Certain non-graphic characters may be represented by a single quote, a backslash, a character (representing one of the non-printing characters) or a sequence of up to three octal digits or an "x" and a sequence of up to 3 hexadecimal digits, and a terminating single quote.

4. Strings: a sequence of characters enclosed in double quotes. If a string contains a double quote character, it must be preceded by a backslash.

5. Operators: +,-,*,/,%,>>,<<,&,|,^,&&,||,?,:,=,+=,-=,*=,/=,%=, >>=,<<=,&=,|=,^=,~,!,++,--,->,<,>,<=,>=,==,!=,","

6. Special symbols: (, ), [, ], {, }, ;, #

7. Separators: blanks, tabs, newlines, and comments are ignored except as they serve to separate tokens. The characters /* begin a comment, which terminates with */. (These comments cannot be nested.) The characters // also start a comment, which terminates at the end of the line.

Your Assignment

Normally a scanner passes tokens as they are recognized on to other parts of the compiler. In this assignment however, we ask you to instead output the token (e.g., typedef) and class (e.g., reserved word) for each token recognized. Your scanner should ignore white space and separators, which need not appear in the output.

To build a scanner, you may either use the lex Unix utility, flex (GNU's version of lex), or build the scanner by hand. Using the utility will require you to learn to use lex or flex, to understand its input conventions and to describe all the tokens using its format for regular expressions. Building the scanner by hand will require much tedious coding. The choice is yours.

If you build the scanner by hand, you should turn in your source code listing. If you use lex or flex, turn in the input file that you gave to the utility. (You don't need to turn in a copy of the source code produced by lex or flex.)

Also, turn in a sample output based on a non-trivial C++ program. You may want to feed your own program in as input. Give a listing of the input program to your scanner, and the output produced.

Overview of lex/flex

Both lex and flex generate programs to be used in simple lexical analysis of text. Each filename (the standard input by default) contains regular expressions to search for, and actions written in C to be executed when expressions are found.

A C source program, lex.yy.c is generated. This program, when run, copies unrecognized portions of the input to the output, and executes the associated C action for each regular expression that is recognized. The actual string matched is left in yytext, an external character array.

For additional details, read the manual entry for lex or flex (i.e., "man lex" or "man flex").

Hint

If you decide to use lex, we recommend that you not attempt to recognize all the regular expressions of C++ the first time you run lex (or flex). Experiment with the utility on a small set of simple regular expressions until you are comfortable with the tool.

Due Date:

This assignment is due at the start of class on Thursday, March 4th.