Lab 3: Tokenization and Parsing

You may work in pairs for this lab. If you choose to do so, only have one partner submit the required files electronically. Be sure to include both partners' names at the top of every submitted file.

This lab is due at the beginning of your next lab period. You should submit a folder called lab03 containing all of the following files:

Flex basics and flex/bison interactions

Flex is a tool that generates scanners. One of its main purposes is to provide yylex() functions for bison-generated parsers. Flex and bison are GNU versions of lex and yacc, which are traditional Unix development tools. They both have manuals online: flex manual, bison manual.

Download the following files into your lab03 directory:

These three files define a simple calculator program. In fact, it's the same simple program we had from Class 7. The big difference is that now, instead of writing our scanner by hand, we're using the standard tool flex to create it.

What do flex and bison do?

Look at the Makefile. We start off with the file calc.ypp that defines the grammar and action rules for our calculator. The call

bison -d calc.ypp
creates files and The first contains the C++ code for the parser (which is a function called yyparse()), the second is a header file that contains, among other things, the definitions of the token names NUM, OPA, etc., and the variable yylval that we use to pass the bison code the semantic values of tokens. The flex file calc.lpp needs those definitions so that the yylex() function it defines for bison can pass back the information it needs to pass back.

The next thing we have is the flex file calc.lpp. The call

flex -o lex.yy.cpp calc.lpp
creates the file lex.yy.cpp that contains, among other things, the definition of the yylex() function. Of course we haven't talked about flex, so this file is new. The basic idea is that you write regular expressions for the different token types, and actions for each regular expression. The flex generated scanner code tries to match characters from the current input stream to these regular expressions, and when a match is found, it executes the associtated action code. The variable yytext contains the string (in the C sense, i.e. '\0' terminated char*.) of characters that were matched. When more than one match is possible it breaks ties by going with the longest match --- i.e. it follows the "maximal munch" rule. When there are several "longest" matches, it goes with the regular expression listed first in the flex file. Of course, you should realize that flex is simply creating the same program implementing a finite automaton that we talked about in class. The difference is that we users specify tokens by regular expressions. So flex has to convert the regular expressions into finite automata for each token type, which are then combined into a single finite automaton. This is then converted, automatically, into a program.


  1. Examine these files carefully and make sure you understand what flex is doing and how flex and bison interact and communicate. Run make and confirm that the mycalc program works as intended.

Adding Features to the Calculator

For the remainder of this lab, you will add features to the simple calculator program. These features will involve significant additions to the scanner (calc.lpp), and some to the parser (calc.ypp) as well.

The features you will implement are listed as A-J below. Everyone must implement features A-E. You must also implement at least two of the features F-J.

Peer Review and features.txt

Next week, each submission will be (anonymously) reviewed by your classmates. The goal of this peer review will be to judge whether all features have been implemented correctly and completely. When developing your lab this week, think about how you would rigorously test every feature. Part of your lab grade will be based on the quality of your review.

To facilitate this review, you must list every feature that you implement in the features.txt file. An example file is here: features.txt. Since I have to process these files very quickly at the beginning of next week's lab, you must follow the following formatting rules:

You will be reviewed by your peers and by your instructor on all features that you worked on, whether successfully implemented or not. You will get the highest grade for features that you claim are successfully implemented, and which actually are. The next highest grades will be for features that are almost complete, and which you acknowledge (with $$) are not completed. Lower grades will be given to features which are found to be buggy, but which claim to be successfully implemented.


  1. Modify the scanner so that it accepts integers in either decimal or binary. Specifically, a string of only 0's and 1's that ends in the letter "b" (with no whitespace in between) should be interpreted as a binary integer. For example:

    > ./mycalc
    10 + 3;
    10b + 3;

    This should only require changing the flex scanner specification file. The cstdlib function strtol will be useful here (check it out with man strtol). To convert a binary integer stored in the C string called str, you can write strtol(str, NULL, 2).

  2. Modify the scanner and parser so that terminating a statement with ";b" instead of ";" results in the output being printed in binary. To make your life easier ...
    // print n as a signed binary number
    void printsbin(int n)
      if (n < 0) { cout << "-"; n = -n; }
      char res[33] = { '\0' };
      int i;
      for(i = 31; n != 0; --i, n /= 2)
        res[i] = (n & 1 ? '1' : '0');
      cout << (i == 31 ? "0" : res + i + 1);

    Now this is going to require modifying the bison file calc.ypp as well as the flex file. It should be a simple change if you understand the system, though: you need to define a new token (I might call it STOPB, or something like that), you need to modify your flex file to recognize the new token, and you need to create a new rule in the grammar to use the token.

    > ./mycalc

  3. Next we add comments! They're not too exciting in a simple calculator, but comments are always a good thing to have. C-sytle comments /* like this */ are not completely straightforward with flex. Why? Well, suppose you added the flex rule:
    "/*".*"*/" { }
    This doesn't work because .* doesn't capture \n's, and the whole point of C-style comments is to allow multi-line comments. So we make it like this:
    "/*"(.|\n)*"*/" { }
    This doesn't work either, and the problem is more fundamental. Remember that the rule is that the longest match possible is the one flex makes, so in
    /* start */ x = 4; /* end */
    flex thinks the whole string is a comment. In this case, we don't want maximal munch! (We have the same problem with string literals.) So we'll take the easy way out and use another common comment convention: A "#" character starts a comment and the comment extends to the next newline character. Here's an example session:
    > ./mycalc
    1+2+3+4+5+6+7+8+9+10; # sum 1..10 computed explicitly
    10*(10+1)/2; # sum 1..10 computed by Gauss's closed form
    Note that although the newline is part of the comment, the comment does separate tokens. So
    1000# beginning of one million
    000# end of one million
    is interpreted as 1000 followed by 0, which gives an error. Not a lexical error, though, rather a parse error!

Food for thought

One of the real advantages of using a tool like flex as opposed to writing your scanner by hand is that adding new tokens usually has no effect whatsoever on what you've already done. You simply add a new line to your flex file. When you do this by hand, that's not the case: a new token may change the underlying finite automaton substantially.


Our calculator is getting a bit more interesting. One thing it doesn't allow, though, is variables. So let's add variables. We'll start with just a single variable called an accumulator. Observe that there are two ingredients to supporting a variable:


  1. Add assignment and reference to a single accumulator variable to your calculator, as described above. Then we should be able to do:
    > ./mycalc
    ! 5;
    ! 3 * 2;
    @ + 4;
    You may decide to use symbols other than ! and @, but be sure to document this in your features.txt file if you do.

Named variables: Implementing a Symbol Table

Now let's allow many variables instead of just one. This will involve creating a symbol table to map variable names to values.

We won't require any declarations; having a name on the left-hand side of an assignment will be enough to create it. Syntax-wise, we have some decisions to make:

Semantically, we have a few decisions as well:

Finally, we have some technical implementation issues to worry about.


  1. Add a symbol table and variables as described above to your calculator program. Document in features.txt the assignment operator as well as the allowable variable names. If you used := for assignment, we should be able to do something like:
    > ./mycalc
    x := 7;
    y := 93;
    # Now we compute the sum x + ... + y
    y*(y + 1)/2 - (x-1)*x/2;
    # Now in binary!
    y*(y + 1)/2 - (x-1)*x/2;b

Last part: Your choice

You are required to implement at least two of the following "extra" features. Be sure to document what you do in features.txt.


  1. Allow single-line strings as comments, which should be ignored. If you use double-quotes like "a comment", then we should be able to do things like:
    > ./mycalc
    5 + 3; "A comment"
    5 + "Another comment" 3;
  2. Make variable names case-insensitive. So for example we can do
    > ./mycalc
    var := 10;
    vAR := 11;
  3. Add in support for two new math operators: exponentiation and remainder (i.e., mod). Be sure to document what the operators are called in features.txt.
  4. Allow numbers to be entered in scientific notation using the letter "e". Of course these will still be ints, so still no decimal points and the exponent can't be very big. It's up to you to specify the exact syntax, but this should not require any new grammar rules. For instance,
    > ./mycalc
  5. Any other feature that you choose. (Run it by the instructor first.)