Useful Links

How I will run your code

Save your program in a file called proj.rb in folders called proj1 and proj2 respectively for phases 1 and 2 of your project.

I will test your code in the same environment as the lab machines in MI 302, using the commands

  /usr/bin/ruby proj.rb

Phase 2 Assignment

For phase 2 of your project, you will write a scanner generator tool like flex, in Ruby. Then you will write a specification for this scanner generator that will create an interpreter for a simple RPN calculator language, described below. You should submit your program and the RPN calculator interpreter specification in a folder called proj2, and be sure that it runs as described.


Your program will read a scanner specification from a file called spec.txt. The format of this file is a series of blocks, separated by one or more blank lines. Each block after the first one specifies a token type and the code to execute for that kind of token.

The first block is just some Ruby code for the "initialization" that should be executed before the scanning starts. You will need to read in this code, and use the built-in function eval to evaluate it (just like Scheme!).

Each block after the first one starts with a line containing a regular expression. You may assume that this regular expression conforms to Ruby's regular expression syntax. This line specifies what this type of token looks like. The 2nd through last lines of each block are Ruby code. This code should evaluate to a procedure which will be called by your scanner. When your scanner calls the procedure specified in the block, it will pass to the procedure a single argument for the text in the input that matched the corresponding regular expression. So the passed argument is analogous to the yytext variable in flex specifications.

You will probably want to look up the documentation for lambda in Ruby. This will allow you to very easily write Ruby expressions that evaluate to procedures. For instance, the code

eval('lambda {|x| x + 5}').call(3)

produces the integer 8 in Ruby.

Your scanner should use the built-in regular expression utilities of Ruby. But be careful! You need to make sure that your program properly disambiguates token specifications as we discussed in class. In particular, you need to implement the maximum munch rule (longer matches take priority), and differentiate same-length matches by taking the first match of the longest length.

After reading in the scanner specification from spec.txt, your scanner should start scanning immediately from standard in. Every time you match a complete token, call the corresponding ruby function on the matched text string.

Besides your scanner generator in ruby.rb, you also need to provide a spec.txt specification that implements a simple Reverse Polish Notation (RPN) calculator. The basic syntax of this language is that we have some operands, which for us will just be numbers, and operators, which will be detailed below. A program for this calculator is just a series of operands and operators.

RPN calculators work by maintaining a single stack of operands. Whenever the next token is an operand, we just push it onto the stack. If the next token is an operator, we pop off some elements of the stack, apply the operator, and push the result of the operation back onto the stack. You can Google RPN to get lots more information.

As I said, the operands in our RPN language will be numbers. Your code should allow for both integers and floating-point numbers. The operators in the language will be as follows:

Of course you may also add your own operators! Remember that the code for interpreting this language has to go in the spec.txt file for your scanner generator. So when I run /usr/bin/ruby proj.rb, it should read this file and start interpreting the RPN language. Of course I will also test your scanner generator on other spec.txt specifications as well.


You are free to implement this in any way you wish. However, I recommend you proceed in the following steps.

  1. The first thing you need to think about is the storage. You need to remember the regular expressions for each token, and their order so you can properly disambiguate. You also need to remember the code block for each token, so you can eval it when the time comes. How do you want to store this information in Ruby?
  2. Don't worry about the RPN language at first. Instead, start by making a very simple spec.txt file that maybe has only one token type for digits that prints "hello world" or the like. See if you can get this working before you go for anything more complicated.
  3. Now slowly make your spec.txt file more sophisticated. Start by adding a second token type. Then make the code blocks do something with the passed-in string.
  4. Once you feel your scanner generator is working correctly, then get started on making the RPN interpreter. Remember that this should all be in the spec.txt file. Again, start simple, maybe with just the p operator. Then add more until everything is there.


After your RPN interpreter is working, I should be able to type in

5 2 + p

and your interpreter should print 7.

Here's a more complicated example:

2 3 d * d 4 + p - p

should print