Author: Dekai Wu
Date: Due 2012.11.27 at 23:00 by CASS
Download: http://www.cs.ust.hk/~dekai/3031/assignments/a6.tar.gz
Assignment page: http://www.cs.ust.hk/~dekai/3031/assignments/a6/html/
Course page: http://www.cs.ust.hk/~dekai/3031/
In this sixth piece of your programming project, you are assigned to maintain and extend the micro-Scheme interpreter you've built in Assignments 1, 2, 3, 4, and 5, specifically to replace the parser you were previously given with your own bison-based implementation.
This means your job is to write new bison-based functionality to replace all the parsing code in the file parse.cpp. We are giving you a new version of parse.cpp which simply calls the yyparse() function that you should automatically generate by using bison.
To maintain encapsulation consistent with your previous implementations, you will still keep the same interface files cons.hpp and eval.hpp.
For portability reasons, you have decided not to use the GNU extensions in flex and bison that allow them to generate C++ code. By sticking to the standard mode of generating C, your implementation can be compiled by any Unix or Posix standard version of lex and yacc.
Therefore, for this exercise we are providing for you an additional C (as opposed to C++) wrapper for the cons.hpp interface. The files c_cons.h and c_cons.cpp will allow you to call the functions in the cons.hpp interface from the C code that lex and yacc generate. The difference is just that the C version of the interface must use void* instead of Cell*, and cannot use const to maintain const correctness.
We are also providing you skeleton parser.y and scanner.lex files that you will extend before using bison and flex to process. Note that neither parser.y nor scanner.lex contain any main() function. Instead, we will still use the original main.cpp from Assignment 4, which calls the parse() function in parse.cpp, which in turn calls the bison-generated yyparse() function.
Using the skeleton parser.y and scanner.lex files as a starting point, you will extend them by adding enough rules (consisting of CFG productions or regular expressions plus their associated C actions) to handle s-expressions. For each top-level s-expression in the input sequence of expressions, a cons data structure should be built containing the expression tree (just like in earlier assignments). You should set up the parsing actions correctly so that the cons structures are passed to eval() to evaluate, and print the value returned.
Remember not to modify the main.cpp or parse.hpp files from Assignment 4, or the new parse.cpp we are giving you!
Here is a hint: a correct solution to this assignment is really short. You just need to figure out how to change your thinking to fit the yacc/bison and lex/flex approach. If you find yourself implementing long things, you're probably on the wrong track.
At this point you should have used a yacc/lex approach to implement your own parser, resulting in exactly the same functionality as at the end of Assignment 4. To remind you, here's one of the example sessions from the Assignment 3 specification:
% main
> (define a 3)
()
> a
3
> (define asquared (* a a))
()
> asquared
9
> (define b 4.0)
()
> b
4.0
> (define csquared (+ asquared (* b b)))
()
> csquared
25.0
> (+ csquared 1)
26.0
> csquared
25.0
> (define foo (quote hello))
()
> foo
hello
> bar
ERROR: attempt to reference an undefined symbol "bar"
> (define baz hello)
ERROR: attempt to reference an undefined symbol "hello"
>
Remember to review the examples in Assignments 1, 2, 3, 4, and 5 and make sure everything still works.
Try this if you are bored or aiming for an A+ :-)
You can take advantage of how easy it is to define other grammars using yacc/bison, by defining a new syntax for the interpreter to support:
For example, the same session above using this alternate syntax looks like this:
% main
> define a = 3;
()
> a;
3
> define asquared = a * a;
()
> asquared;
9
> define b = 4.0;
()
> b;
4.0
> define csquared = asquared + (b * b);
()
> csquared;
25.0
> csquared + 1;
26.0
> csquared;
25.0
> define foo = quote(hello);
()
> foo;
hello
> bar;
ERROR: attempt to reference an undefined symbol "bar"
> define baz = hello;
ERROR: attempt to reference an undefined symbol "hello"
>
Important: in the final tarball that you submit, you should make sure the infix versions of your parser and scanner are named parser_infix.y and scanner_infix.lex. The files parser.y and scanner.lex must be the prefix versions from Step 1!
Definitely don't try this unless you have everything else in this assignment perfectly done!
You must follow the design approach outlined in this document. Do not just implement the required functionality using a different design.
Remember we are still focusing on proper use of encapsulation. So you still should not edit the files c_cons.h, c_cons.cpp, cons.hpp, or eval.hpp. Again, the programming assignments are mini-exercises in how multiple programmers are supposed to interact and communicate in the real world; these files are owned and maintained by the other author(s).
Depending on your approach, you may or may not need to change the Makefile. Whether you changed it or not, always make sure you include whatever Makefile is needed to build your program, when you submit assignment. Otherwise, the graders cannot build your program.
You must write the final version of the program on your own. Sophisticated plagiarism detection systems are in operation, and they are pretty good at catching copying! If you worked in study groups, you must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Re-read the policy on the course home page, and note the University's tougher policy this year regarding cheating.
Your programming style (how clearly and how well you speak C++, yacc/bison, and lex/flex) is what will be graded. Correct functioning of your program is necessary but not sufficient!
1.5.8