Output and TestingWhat to turn inAssorted AdviceUNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 164 P. N. HilfingerSpring 2005Project #1: Lexer and Parser for PythDue: Monday, 2 March 2005This first project calls for writing a lexical analyzer and parser for our Python dialect(Pyth) that produces abstract syntax trees (ASTs). The semantic actions o f your par serwill build up these trees, and the main program will print them in a Lisp-like format. Sothat you can see whether you’re getting things right, we will supply a sample back-endthat accepts these ASTs and prints out corresponding Python translations. The resultingprograms will not, of course, be identical to the input, but should have the same effects.Pa r t of your job is to test systematically that this is so.When the directory ~cs164/hw/proj1 becomes readable, you can copy the files wehave placed there to help with this project. We will provide here some classes for creating,reading, and printing a bstract syntax trees for the Pyth dialect. Alternatively (althoughwe certainly do not recommend this) you can throw them away and work from scratch.Your task is to fulfill a specification, not to do it in any par t icular way.The homework page will contain pointers to current descriptions of the Pyth subset youare to implement . We’ll stick to electronic form, at least for now, since the description issubject to change if we discover things that we decide are more trouble for you to implementthan they’re worth.Abstract Syntax TreesAlso look at the homework page f or links to t he AST description. For this assignment, itis only necessary for you to produce the external (printed) form of the AST. Nevertheless,we’ll provide a convenient library for building these trees internally, which you’ll probablywant to use.We have considerably simplified the description of the AST by relying on an interest-ing feature of the Python language: most operators correspond to special methods. For1Project #1 2example, the + operator corresponds to the method __add__, so tha t 3+x is equivalent to(3).__add__(x). This eliminates t he need for individual node types for all the operators;we can make almost everything a method call with the right ident ifier for the methodname.1 Output and TestingThe output of t he progra m is a textual representation o f the AST. This design is notoptimal for a real compiler, since there is considerable overhead involved in convertingback and forth between the internal tree form and text. For our purposes, however, itis useful that the output of our compiler modules has this representation- independenttextual form. It frees us from dependence on a particular implementation language, forone thing, and minimizes interactions between compiler phases (particularly useful whenwe plug our backend modules into your front ends).Naturally, t his raises the question of how you check that your compiler’s output iscorrect. It’s all very well to decide that you are going to test your results, but just whatdoes this mean? Presumably, you must start with a body of test cases: Pyth programsthat systematically exercise all constructs of the language and all parts of your compiler.You’ll need a convenient way to run all your tests (your test suite) against the latest versionof your compiler, and to mechanically check the result. One possibility is to look at theactual ASTs produced and make sure they are “rig ht,” which implies that you figure outby hand what your test cases are supposed to produce. This can be rather tedious and alsohas the problem that there may be alternative equivalent ASTs for any given program, andyour compiler is no t necessarily wrong for picking something different from your canonicalsolution.Therefore, we’re looking for a slightly different approach. We will provide a back endthat “compiles” your ASTs into standard Python, suitable for execution with a Pythoninterpreter. By making each of your test cases “self-testing”—by having them be littleprograms each of which prints something—you can compare the outputs of these programswith what they are supposed to produce.Testing is importa nt and, quite frankly, we don’t have you do enough of it. To try tochange that, 6 points of your project grade will come from the quality and completenessof yo ur test cases.2 What to turn inYou will be turning in three things:• Source files (in flex, jflex, bison, jbison, C++, or Java).Project #1 3• A testing subdirectory containing Pyth source files and corresponding files with thecorrect output.• A Makefile that provides (at least) two targets:– The default target (built with a plain gmake command) should compile yourprogram, producing an executable program called pythc (we will provide in-structions for how to accomplish this in Java , so t hat you don’t need the javacommand to run your program.– The command gmake check should run all your tests against your compiler andcheck the results.3 Assorted AdviceFirst, get started as soon as possible. Second, don’t ever waste time beating your headagainst a wall. If yo u come to an impasse, recognize it quickly and come see one of us or, ifwe are not immediately available, work on something else for a while (you can never haveenough test cases, for example). Third, keep track of your partner. If possible, scheduletime to do most of your work together. I’ve seen all too many instances of the Case of theFlaky Partner.Learn your tools. You should be doing all of your compilations using gmake. Get toknow this tool and try to understand the “makefiles” we give you. It really does makelife much easier for you. Learn to use it from within Emacs. Learn to use the gdb andgjdb debuggers (also usable from within Emacs). In most cases, if your C++ programblows up, you should be able to at least tell me where, it blew up (even if the error thatcaused it is elsewhere). I do not look kindly on those who do not at least make that effortbefore consulting me. Use CVS o r PRCS to store a history of versions of your programand to share development with your partner (we’ll have a session or two on this subject).If you are using some other IDE at home (like Eclipse), make sure you learn how to usethe analogous features in it (if it doesn’t have such features, it is not a proper IDE;
View Full Document
Unlocking...