Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15
- From: Pascal Bourguignon <pjb@xxxxxxxxxxxxxxxxx>
- Date: 7 Jun 2006 23:16:33 -0400
tomazos@xxxxxxxxx writes:
I'm trying to do exercise 2.15 from Compilers: Principles, Techniques
and Tools. Aho/Sethi/Ullman. (Dragon book), and am totally stuck.
Roughally re-stating the problem:
Consider the following for-statement:
for i:= 1 step 10 - j until 10 * j do j := j + 1
The limit 10 * j and increment 10 - j are to be evaluated once before
the loop. For example if j = 5 before the loop, we would run through
ten times and exit.
Construct a syntax-directed translation scheme to translate this
for-loop into the following stack-machine code.
The available stack-machine codes are as follows:
push v... push v onto the stack
rvalue l... push contents of data location l
lvalue l... push address of data location l
pop... throw away value on top of stack
:=... the r-value on top is place in the l-value below it and both are
popped
copy... push a copy of the top value on the stack
label l... target of jumps to l; no other effect
goto l... next instruction is taken from statement with label l
gofalse l... pop the top value; jump if it is zero
gotrue l... pop the top value; jump if it is nonzero
halt... stop execution
+,-,*, etc... pop the top two values, calculate result, and push onto
the stack.
The closest syntax-directed translation scheme I can see is:
stmt -> for lval := expr1 step expr2 until expr3 do stmt2
{ test := newlabel ||
out := newlabel ||
stmt.t :=
'lvalue' lval.lexeme ||
expr1.t ||
':=' ||
expr2.t ||
???? pop the top value and put it somewhere called STEP ???? ||
expr3.t ||
???? pop the top value and put it somewhere else called LIMIT ????
||
'label' test ||
rvalue lval.lexeme ||
push LIMIT ???? ||
'<' ||
'gofalse' out ||
stmt2.t ||
'lvalue' lval.lexeme ||
'rvalue' lval.lexeme ||
push STEP ???? ||
'+' ||
':=' ||
'goto' test ||
'label' out
}
The parts labeled with ???? are illegal in the stack machine-code. The
problem is that I need to store the initial evaluation of STEP and
LIMIT somewhere, and I don't see how this is possible to do using the
stack. There is also no mention of a way to create and allocate a new
variable, or anywhere else I could store them.
Well, since the stack operators defined lack rotations, you'll have
to store these values in static memory.
Instead of:
expr2.t
???? pop the top value and put it somewhere called STEP ???? ||
generate:
lvalue STEP
expr2.t
:=
Instead of:
push STEP ????
generate:
rvalue STEP
If you want to be able to run embedded loops, you'll have to allocate
several LIMIT/STEP pairs:
...
lvalue STEP+LOOP_LEVEL
expr2.t
:=
...
rvalue STEP+LOOP_LEVEL
...
(The address STEP+LOOP_LEVEL would be computer by the compiler).
Also, since there's no addressing mode defined (you cannot index the
addresses given to lvalue/rvalue with the frame pointer for example,
to allow loops in different functions, you'll have to allocate static
space for each function, and generate:
lvalue STEP+LOOP_LEVEL+FUNCTION_STORAGE
...
rvalue STEP+LOOP_LEVEL+FUNCTION_STORAGE
But this may be out of scope of this exercise...
--
__Pascal Bourguignon__ http://www.informatimago.com/
COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
protons, etc.) comprising this product are exactly the same in every
measurable respect as those used in the products of other
manufacturers, and no claim to the contrary may legitimately be
expressed or implied.
.
- References:
- Compilers, Aho/Sethi/Ullman, Exercise 2.15
- From: tomazos
- Compilers, Aho/Sethi/Ullman, Exercise 2.15
- Prev by Date: Re: Natural "for" Loop, using Plural / Singular transformations ??
- Next by Date: [ANN] paxCompiler, v1.0
- Previous by thread: Compilers, Aho/Sethi/Ullman, Exercise 2.15
- Next by thread: Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15
- Index(es):
Relevant Pages
|
|
