Chapter 2: A Simple Compiler


Getting Started (5 minutes)

If this is your first time running eclipse, make sure your workspace is in a place that is backed up reliably.

Studio Exercises

  1. Open, and look at the examples array. The code in main runs the parser on each element of that array.

    Run the application by right- (control-) clicking on Main in the package explorer, and then selecting Run as..Java Application.

    Tip: After running an application the first time, subsequent runs can be launched by clicking the green circle with the white triangle near the top of eclipse's window.

    The output should appear in the console window.

    In report.txt, indicate which examples passed the parse and which failed.

  2. Example 1 is from the text. Figure 2.4 shows the input and its parse tree.

    As a group, read through the program and discuss which portions of the input declare variables, assign values, and print values. Use the tree shown in Figure 2.4 as a guide.

    Answer the questions in report.txt.

  3. Some of the examples did not parse correctly, and the parser emits an error message in such cases, based on what it was expecting to see in the input.

    The parse is structured by the grammar shown in Figure 2.1. For each example that did not parse correctly, use the grammar to determine why the example is not syntactically correct, and document your findings in report.txt.

  4. The scanner is the first phase of a compiler. Open ScannerCode and compare what you see there with the pseudocode given in Figures 2.5 and 2.6.

    Answer the questions in report.txt.

  5. In German, the word for print is drucken. What changes would have to be made to the software you are given, so that the reserved keyword for printing something would change from p to d?

    Implement these changes as a group. Modify the test inputs in Main and make sure your changes work.

    How does the abstraction of the print keyword as a PRINT token in facilitate the change you just made? Document your findings in report.txt.

  6. Open and examine the structure and nature of this class. The instance variables are final and public. What does this prevent and what does this allow?
  7. What is the role of TokenStream in this project? How do its peek() and advance() methods differ from those in CharStream?
  8. The parser is the next component of a compiler. While we have not yet studied how parsers are crafted, the file contains a recursive-descent implementation of the grammar given in Figure 2.1 of the text.

    Compare the code for Stmts() in Parser with the pseudocode in Figure 2.8. Discuss and document in report.txt the similarities and differences.

  9. Look at Figure 2.1 and discuss the productions for Val. Currently, a value can be an identifier, an integer constant, or a float constant.

    Consider adding a new symbol to the language, spelled as # that represents infinity. What production should be added go Figure 2.1, so that # can serve as a value?

  10. What changes must be made to ScannerCode and Token to accommodate #?
  11. What changes are needed in Parser to accommodate #?
    Test your augmented software by running it on some examples from Main, using the # value occasionally.

  12. Consider augmenting the language with the usual operator for multiplication. Let's assume that it will be denoted as * in programs, and that it has the same operator precedence as + and -. What changes are needed for this operator?
    Try out some examples that include the * operator.

Finishing Up

Submit your work as directed by your instructor.

Copyright 2010 by Ron K. Cytron
Last modified 14:32:04 CDT 13 August 2010