UNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionProf. R. FatemanFall, 2005CS 164 Programming Assignment 2: Lexical Analysis for MiniJavaDue: Thurs, Sept 22, 2005, 11:59PMYour second programming assignment is to familiarize yourself with the MiniJava languagesyntax and semantics, and to write the lexical analyzer component of a MiniJava system.This is intended to be another easy assignment. Try not to make it harder than it reallyis: work with your partner, start immediately, and read the programs we give you. Especiallyif you can’t understand that material, ask for help. In asking for help on a new program, firsttry to clarify to yourself what you want it to do and then how it goes wrong.Read the software/tests/ files that end in .java to see some examples of MiniJava pro-grams.It should be possible to run any MiniJava program in Java, so there should be no questionof its appropriate behavior. Note. The MiniJava spec says /* */ can be nested. In Java thisis not true. Offhand we don’t see other problems.1. The intention of this first exercise is to help you become comfortable with MiniJava,since you will eventually implement it! Write a program to take an array and to print itscontents in ascending order. Run it and show that it works as expected. We recommenda simple sorting algorithm. (Hint: There are simpler and faster sorts than “bubble sort”.If you haven’t heard this before: The only advantage of bubble sort is a cute name. Youshould know of at least 2 better O(n2) algorithms.) Do not use any language facility outsideMiniJava.2. For this part you will write, with our help, a lexical analyzer. You can see how yourlexical analyzer should work by running ours. To run lex on a file, you can execute theprogram fs for “file scanner”. The program fs repeatedly reads tokens from the named file.fs takes an optional second argument as to what to do with the tokens. One possibility is toprint the tokens as they are recognized. Another is to push them on a list and return the list(reversed) as the tokenized input. To run the lexical analyzer on a string, use the programfstring. You may need to type (in-package :mj), or for short at the top level of lisp, :pac:mj for access to these programs internal to the package in which we put the internals to1CS 164 Programming Assignment 2: Lexical Analysis for MiniJava 2mjrun. The definitions of these programs are also given in shortlex.cl, which provides askeleton for your program.To write your program, first look at the listing of source/shortlex.cl and notice thepieces of code with comments marked with *** EXERCISE ***. These represent tasks foryou to complete, with the requirement that you should mimic the behavior of our program.Fill them in, and run the whole version on test cases to make sure your program works thesame as ours or better. As turns out to be usual in CS164, the tricky programming parts aregenerally those written to make sure the program does something reasonable on erroneousinput. Any differences between your program output and ours should be explained. Youshould certainly run on testlex.txt in the software/tests directory, but you must devisesome of your own tests as well, as noted in that file.There are several debugging strategies you can pursue, including running pieces of our pre-written code interspersed with your own. In this case you will have to run within (in-package:mj) and to make emacs happy, you must change the comment on the top line of shortlexwhere it says cl-user to mj and uncomment the second line in your file so that it is set inthe :mj package. You can selectively trace programs that you’ve written or that are writtenin the compiled file. For example, you can trace our collect-number. You can then readin your definition and see if it operates the same. (Yes, the lisp defun program is smartenough to notice if something being redefined has been traced and will re-trace a re-definitionautomatically. And yes, you can trace compiled functions indistinguishably from interpretedfunctions, and yes, you can re-load files or individual functions into the same lisp.)You may draw some inspiration from the “literature”, in particular pitmantoken.cl,which we expect to mention in class – but cite it please, if you do so. Two parts of theexercise are optional:1. MiniJava does not have floating-point numbers as one of its primitive data types. Thisomission relieves the implementation of the need to consider many issues (conversions,type-checking, input and output, additional arithmetic operations, etc.). But realisti-cally, most language processors permit floating-point numbers. At least for the lexicalprocessing, we are going to allow floats. Write a version of collect-number to replacecollect-integer and put it into your lex system so that you can handle floating pointnumbers as in Java as well as integers. It is actually easy to write this program; gettingit exactly right is not so easy. Some of the more tricky parts disappear when you areusing Lisp for the implementation, since Lisp allows you to compute with integers ofany length as part of the path to an accurate floating-point representation.2. MiniJava does not have strings as one of its primitive data types. Add the type “string”and allow a string literal to be a sequence of characters enclosed in double-quotes "likethis". If you need to have a double-quote inside a string, write it as \". Do you likethis convention? If not, suggest and implement another one. There are some otherstrange cases: What if you want to have a newline inside a string, but don’t care totake that space in the program text? Or the reverse: you want a very long string butwant to “break” it into sections and continue on the next line. How would you
View Full Document
Unlocking...