/ GENTLE PRIMER
/ Optimal Rule Selection
A Stack Computer
Our target computer is a stack computer with the following instructions
(the instructions are given as predicates, that, when invoked,
emit the instruction):
'action' PLUS 'action' MINUS 'action' PUSH(Variable) 'action' POP(Variable)The instructions modify the stack of the computer. If the stack has the form
If K is the value of a variable V, then PUSH(V) puts K onto the stack.
If K is the value on top of the stack, then POP(V) removes it from the stack and stores it in V.
Let us write predicates Encode and StackCode that emit instructions for statements and expressions.
If we have to generate code for assign(V, X), we have to emit code for the expression X that computes its value on top of the stack. Then, we can use the POP instruction to store it in V.
'rule' Encode(assign(V,X)): StackCode(X) POP(V)The predicate StackCode processes the alternatives for Expr:
'rule' StackCode(plus(X,Y)): StackCode(X) StackCode(Y) PLUS 'rule' StackCode(minus(X,Y)): StackCode(X) StackCode(Y) MINUS 'rule' StackCode(var(V)): PUSH(V)For the Statement
assign("Res", plus("A", minus("B", "C")))the generated code is
PUSH A PUSH B PUSH C MINUS PLUS POP Reswhich, when executed, results in the following stack configurations