Project 1, Stage 2

Since several students reported difficulties with doing Stage 1 of Project 1, this note is intended to help you through Stage 2.  I've broken down Stage 2 into two parts: the first part does not require any implementation and the second part does require the implementation.  To get the full credit for Stage 2, you must do the implementation.  However, you can get up to 70% of the credit by simply doing the first part and handing it in (NOTE: if you are doing the implementation, you do not need to hand in anything for the first part).
 

Part 1 (70 points)

1. Imagine that you wanted to implement Stage 2 by writing a preprocessor for Stage 1.   In other words, you want to write a new tool that takes a Stage 2 program (i.e., meshtml with parameters) and outputs a program that contains macros but no parameters (i.e., meshtml).  You could feed this output into your existing Stage 1 and get shtml, which is the desired output.  For example, let's suppose your input file was:

<html>
<MD!salutation!name> Dear <MU!name> </MD>
<MD!JohnN> John </MD>
<MU!salutation!JohnN>:
How are you?
</html>

You could rewrite it as:
<html>
<MD!JohnN> John </MD>
<p>
<MD!name> <MU!JohnN> </MD>
Dear <MU!name>
</p>
How are you?
</html>

Assume that your preprocessor can introduce paragraphs whenever it needs a new scope; i.e., for this assignment, adding extra paragraphs is acceptable.  Given this caveat, the above rewriting produces a program which will have the desired output when you pass it through your solution to Stage 2.  The interesting lines above are:

<p>
<MD!name> <MU!JohnN> </MD>
Dear <MU!name>
</p>

These lines are effectively a copy verbatim the body of the macro "salutation".  The key difference is the <p>...</p> which is used to start a scope and that there is a new macro definition for macro "name".  In other words, I've simply replicated the body of the macro salutation and added declarations for each parameter to the macro.  Thus, now rather than accessing parameters the macro body will access the new macros (such as "name") and thus does not need parameters.

While this rewriting works for our example, does it always work?  Give an example where the above rewriting does not work (hint: what happens when "salutation" uses macros other than its parameters in the body).

2. In the description of Project 1, I mentioned the different kinds of abstract syntax tree nodes that I use: MacroDefNode, MacroUseNode, BoldNode, PlainTextNode, ParaNode, ListItemNode, ListNode, and HtmlNode.  These nodes have the obvious meaning, for example, HtmlNode represents <html>...</html> and BoldNode represents <B>...</B>.  Draw the abstract syntax tree for the example you give in question 1 (i.e., the example for which text rewriting does not work).  For each node of the tree give the kind of node it is (e.g., ParaNode) and the attributes of the nodes (e.g., a symbol table would be associated with a ParaNode).  Give an algorithm based on your abstract syntax tree how you would transform the tree to eliminate the macro parameters and discuss why your algorithm based on the abstract syntax tree will not have the problem you found in Question 1.

Part 2 (30 points)

Implement parameter passing for macros using the ideas developed in Part 1.  Note that if you do the implementation, you do not need to submit a solution to part 1.  However, it may be a useful exercise to go through part 1 to make sure you understand the problem.