Problem Solving Lab #2
Using flex and bison

This lab is being done in order to help you learn various topics discussed in lecture. For attendance, you will all be asked to submit to try. You may work in pairs. Since this lab is for your learning and different people work at different paces, it's quite probable that you will not finish all activities in the two hours alotted for labs. You are not required to do anything you don't finish, although you may want to try some of the exercises to increase your understanding of the material.

Flex and Bison Sites and Information

It's always helpful to know where help is. The Unix man pages for flex and bison are fairly complete. With that said, you can also find information at:

dinosaur.compilertools.net
The on-line Bison manual

Part I - Flex

Here is the flex file for a very simple calculator. You can compile the file with the following commands:

% flex calc.lex; gcc -o calc lex.yy.c

You can then run the calculator with the 'calc' command and can quit out of it using ctrl-d.

Do the following:

1. Figure out what the calculator does with things not described by the regular expressions.
2. Add division and subtraction to the calculator.
3. Keep track of the number of lines that have been input. Make sure that you set the lineNumber variable in yylval.ti for each token and print out the line count when you print out variable information.
4. Extend the variables to handle longer variable names. The variables must start with an alphabetic character or '_' character and may be followed by 0 or more alphabetic/numerical/'_'/'-' characters.
5. Add floating point numbers to the input. For this exercise, a floating point number is a sequence of 0 or more digits followed by a '.' character and 0 or more digits. One side of the number must have digits. The print statement for real numbers should be: printf("FLOAT: %0.0f\n", yylval.ti.value);
6. (Extra) Add sqrt
7. (Extra) Allow floating point numbers to be of the form 1.e-3

Part II - Bison

• You should probably save a backup of your calc.lex file now (use RCS in you want). Rather than printing all the tokens in the calc.lex file out, change the file to return the tokens. As an example, printf("MULTIPLY\n"); should be changed to: return MULTIPLY;
  If you prefer, you can download the file as calc2.lex.

  You should remove all the structure information for tokenInfo and tokenInfo2 and delete the main function in calc.lex.

  Compile the bison calc.y file and all other necessary files (like calc.h) with the following command:

  % bison -v calc.y; flex calc2.lex; gcc -o calc calc.tab.c

  You will notice when you compile that the following message appears:

  calc.y contains 4 shift/reduce conflicts.

  This occurs because multiple parse trees can be generated from calc.y. Read the web page about shift/reduce conflicts for bison. If you want to see where the problems occur, you can look at the calc.output file. calc.output shows all the states for the finite state machine produced by the parser. If you would like a moment-by-moment look at what the parser is doing, then change the yydebug variable in the main method of calc.y to be 1 and recompile. Now when you run the program you will get a moment-by-moment look at what the parser is doing.

  Now do the following:

  1. Come up with an equation that fails to give the right answer with the current implementation.
  2. Fix the problem using %left (all the operators are left associative).
  3. Change the bison file to handle the changes you made to the flex calc.lex file.
  4. (Submitted) Change the grammer, so that the problem never occurs and do not use %left or %right.
  5. (Extra) You can handle errors by thinking of what kinds of errors people might make (for example, I tend to type "x=5+5" rather than "x:=5+5") and then implementing them with flex and bison. You can then call yyerror with your error message and the line number it occurred at.
  6. (Extra) Allow for equations with ()'s
  7. (Extra) Fix the line number problem when there is an error.

• Here is the flex file for a grammar that detects and returns j's and k's. You can compile the file with the following command:

  % flex f.lex

  I am interested in a language where the number of f's, j's, and k's matters. In this language, f's are always following by 1 or more j's, which are then followed by 1 or more k's. Whenever the number of f's is even and is directly followed by an even number of j's, and an even number of k's on one line, then the language will output an F, otherwise the language will output a K for that line.

  Create a grammar for this language and implement it in bison. Use this basic bison file to create your code. You may compile your code with the following command:

  % bison -d f.y; flex f.lex; gcc -o f lex.yy.c f.tab.c

  If you're having trouble with the odd and even number of letters, remember that an even number is always two or more and an odd number is an even number followed by an odd number in most cases.

Submission

Each of you should submit (from your own account) to try an empty file called: here.txt. In order to create the file, type:

% touch here.txt

You will be told the command to use for submitting the file in your lab.

Each of you should submit (from your own account) a file called reflections.txt after the lab is over. The goal of the file is for you to reflect on what you have learned in the lab, how far you got in the lab, what you had problems with, what I could do better next time, what you would have liked to do, and to give me feedback about the lab.

In addition, you are required to fix the problem with the grammar in the bison file without using the %left or %right bison directives.

In order to submit these files, type:

% try jdb-grd project22-1 reflections.txt calc.y

These files will be due this Thur. at midnight with the late deadline on Friday at midnight.