This assignment is worth 20 points.
RULE Plus: Exp ::= Exp '+' Exp END;An object can have an arbitrary number of children. For example, here is a rule defining a concrete class whose name is uninteresting. It inherits from the abstract class Stmts, and has an arbitrary number of children. Each child must be a concrete class that inherits from Stmt, Iteration, or Block:
RULE: Stmts LISTOF Stmt | Iteration | Block END;
You have already seen how Eli can generate Java or C++ declarations for a set of tree node classes, and for an abstract visitor class, from files containing LIDO rules. You have implemented computations over trees defined in LIDO rules by writing concrete visitor classes that inherit from the generated abstract visitor class.
In order to write a concrete visitor class, you first have to decide upon the task that visitor must accomplish. Usually this means associating some interesting values with nodes, and postulating some relationship among those values. For example, if the task of the visitor is to evaluate the expression represented by a tree then each node represents a sub-expression and the value of that sub-expression could be associated with the node representing it. Clearly you can then postulate a relationship among those values in the case of the Plus node defined above: The value at the node is the sum of the values at its children.
The task of a concrete visitor is to establish the interesting values at each node, guaranteeing that the postulated relationships hold. It may also involve some side effect, such as printing out some of the interesting values. You have decided upon the task when you have decided upon the interesting values, the postulated relationships, and the side effects. Your work is finished at this point if you can capture your decisions in a LIDO file; Eli can use this information to generate the concrete visitor classes as well as the tree node classes and the abstract visitor class.
In the remainder of this section we shall present a general strategy for capturing decisions about tree computations, explain the role of entities with state independent of their position, and discuss the implicit dependence that these entities introduce.
|Each lower context of the symbol requires a different computation of the information.||Design an appropriate computation for each rule having the symbol on the left-hand side.|
|Each upper context of the symbol requires a different computation of the information.||Design an appropriate computation for each rule having the symbol on the right-hand side.|
|The information can be computed independently of the particular context, using attributes of the symbol itself or remote-access attributes.||Design an appropriate lower-context symbol computation.|
|The information can be computed almost independently of the particular context, using attributes of the symbol itself or remote-access attributes. There are a few exceptions where a lower context of the symbol requires a different computation.||Design an appropriate lower-context symbol computation and override it in the exceptional contexts.|
|The information can be computed almost independently of the particular context, using attributes of the symbol itself or remote-access attributes. There are a few exceptions where an upper context of the symbol requires a different computation.||Design an appropriate upper-context symbol computation and override it in the exceptional contexts.|
For example, the postulated relationships among the expression values in the Plus rule state that the value at the node is the sum of the values of the children. That requires a computation in the lower context of the node (i.e. the context of the node and its children). Moreover, the computation will be different for each rule (Plus, Minus, etc.) because different rules embody different operations. Thus this case fits row one's pattern, and we should design an appropriate computation for each rule having Expr on the left-hand side:
RULE Plus: Exp ::= Exp '+' Exp COMPUTE Exp.Value=ADD(Exp.Value,Exp.Value); END; RULE Minus: Exp ::= Exp '-' Exp COMPUTE Exp.Value=SUB(Exp.Value,Exp.Value); END; ...
Information can be associated with particular entities, rather than with the appearances of those entities in the tree. The variable A is an example of an entity that may appear at many points in the tree representing an expression. That variable has a state, which is its associated value. The value is associated with the variable itself, not with any specific tree context in which that variable might appear. This description is characteristic of the Flyweight design pattern, in which the information is stored in a shared object that can be used in multiple contexts simultaneously.
Eli implements the Flyweight design pattern by a definition table key, a ``handle'' that provides access to an arbitrary number of properties of arbitrary types. Thus a variable is represented by a definition table key, and the variable's value is stored as a property of that key. Every tree node representing a variable has an attribute named Key, of type DefTableKey; the Key attributes of nodes representing instances of the same variable have the same value. This definition table key can be used to access a Value property, so that it is possible to obtain the value of a variable at any node representing that variable.
Computations like the example at the end of the last sub-section represent explicit dependence because of the way they are written: Exp depends explicitly on Exp and Exp. The fact that an entity with state can be referenced at many places in the tree means that there may be implicit dependences among the computations in the tree. For example, suppose that our expressions included assignment. In that case, a variable's state (its value) would be updated by some computations and used by others. This implicit dependence determines the order in which certain computations must take place, and therefore it must somehow be made explicit.
Here is a general process for designing computations involving property values:
Step (1) might require a new declaration in a property definition language specification. Computations involving the the property value might require that additional access functions be defined. Steps (2) and (3) serve to place the property access operations in the tree, while step (4) determines what computations are needed to express the implicit dependence.
Dependence is made explicit in the case of all (2) before any (3) by using remote dependence to make an attribute of a common parent of all (2) and (3) depend on the computations that set the property's value. All computations using the property's value are then made dependent on that attribute of the common parent, again using remote dependence. The attribute of the common parent is often VOID, but this is not required.
Dependence is made explicit in the case of textual order dependence by using a chain. Again, the chain is often VOID.
Your group is developing the ``named menu'' facility. After some discussion, it becomes clear that this may be a nontrivial project. For example, consider the simple case of roasting a chicken. If the user simply selects a ``chicken'' menu item, you don't have enough information because you don't know how much the chicken weighs. Thus your solution has to be able to input arbitrary information in association with menu selection. Each menu item will have to have an associated program that prompts the user, accepts input, and calculates the time to run the oven.
Moreover, being experienced in the ways of the marketing department, you realize that it's only a small step to having the user create menus. Clearly the user isn't going to be able to write programs to implement their recipes! Why not get ahead of marketing for once, and make your job easier also? You therefore decide that you will store each recipe as a string consisting of a sequence of simple expressions. Such a representation will take less space than the program to implement the recipe, it will be easier for you to create recipes (writing expressions is easier than writing programs), and you'll be in a fine position when marketing finally thinks of user recipes.
When the user selects the name of a recipe on the touch screen, the corresponding string will be fed to a program that reads it, builds a tree, queries the user for the necessary data, and evaluates the expression sequence. The result becomes the time input of the oven. Of course you recognize immediately that this program can be generated by Eli, and therefore you don't have to actually write it!
You and your colleagues decide that the tree structure should be defined as follows:
RULE Recipe: Source LISTOF Action END; RULE Store: Action ::= Name '=' Exp END; RULE Print: Action ::= Name END; RULE Fetch: Exp ::= Name END; RULE Constant: Exp ::= Number END; RULE Plus: Exp ::= Exp '+' Exp END; RULE Minus: Exp ::= Exp '-' Exp END; RULE Negate: Exp ::= '-' Exp END; RULE Star: Exp ::= Exp '*' Exp END; RULE Slash: Exp ::= Exp '/' Exp END; RULE Variable: Name ::= Identifier END;
You also decide that the form of an integer should be that same as it is in C. That's easy to remember, and easy to specify to Eli by using a canned description.
Identifiers are more interesting. You decide that they should be able to carry units with them, so that when the user is queried for a value they will know what units are expected. Here are some examples of legal identifiers:
Since parentheses are used for the units, you decide not to use them for grouping. That means you may need temporary variables like scratch to override operator precedence. For example, suppose that you need to assign the value of (a+1)*b to result. Because parentheses can't be used for grouping, you would need to write a sequence of two actions:Weight(lb) Temperature(F) Doneness(1-3) scratch
Presumably such temporary variables don't need units.scratch = a+1 result = scratch*b
You were tasked with the specification of the basic symbol formats and the tree computation; your colleagues have specified the tree builder, the identification of variables, and the actual process of getting input from the user. Click here for the file Calci.fw, which contains all of those specifications. You should not alter file Calci.fw unless you find a bug! Instead, simply put the name Calci.fw in your specs file along with the names of your specification files. As the semester goes on, you will learn about everything in Calci.fw. You can ask Eli to format Calci.fw as a PDF file for easy reading:
-> Calci.fw :fwTex :pdf > Calci.pdf
Your tree computations should establish an integer value for every expression, according to the normal rules of integer arithmetic. Assume that every value is in bounds and that no divisor will ever be zero.
Number is the integer value represented by a Constant node.
The result of evaluating a Fetch expression must be the current value of the variable. From specifications in file Calci.fw, Eli creates a function that you can use to obtain the value. Here is its interface:
Computations generated by Eli from specifications in file Calci.fw set the attribute Name.Key to the definition table key of the variable and the attribute Name.Sym to the string table index of the variable's name. You should use those attributes as arguments to ObtainValue.int ObtainValue(DefTableKey key, int sym) /* Obtain the value of a variable, possibly by asking the user * On entry- * key=definition table key of the variable * sym=string table index of the variable name * On exit- * ObtainValue=value of the variable ***/
A Store action must set the value of the variable to the result of evaluating the expression. From specifications in file Calci.fw, Eli creates a function that you can use to set the value. Here is its interface:
void ResetValue(DefTableKey key, int val) /* Reset the current value of a variable * On entry- * key=definition table key of the variable * val=value to which the variable should be set * On exit- * The variable's current value is val ***/
A Print action outputs the value of the expression to the oven. Use printf with the format string "%d\n" to output the value of the variable at every Print node.
Your specification must guarantee that all actions are carried out in the order in which they appear in the input text. Note that this requirement results in an implicit dependence among the actions, and that dependence must be made explicit as discussed above.
After you create a file containing input text (assume that it is named input), you can test your processor in two ways:
-> Calc.specs :exe > myprog
The program will request input if it has variables whose values are unknown.% myprog input
This Eli request can be explained as follows:. +cmd=(Calc.specs :exe) (input) :run
Click here for further information about the form of an Eli request.
|Instructor||Revision 1.7 (2005/09/22 20:14:53)|