Home > Archive > Compilers > June 2006 > Compilers, Aho/Sethi/Ullman, Exercise 2.15
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Compilers, Aho/Sethi/Ullman, Exercise 2.15
|
|
| tomazos@gmail.com 2006-06-05, 7:11 pm |
| 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.
Any enlightenment on this topic appreciated.
Thanks,
Andrew.
[He promises this isn't a homework assignment. -John]
| |
| Pascal Bourguignon 2006-06-17, 7:05 pm |
| tomazos@gmail.com 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.
| |
| Chris Dodd 2006-06-17, 7:05 pm |
| tomazos@gmail.com wrote in news:06-06-019@comp.compilers:
> 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.
Your code looks correct and you've basically figured out the problem -- you
need a way of creating a new temporary data location to hold the STEP and
LIMIT values. So you just need to call a 'newdatalocation' function that is
exactly analogous to the 'newlabel' function you're already calling, and it
will give you a unqiue tag/address that you can use with the lvalue/rvalue
instructions.
Alternately, you could introduce new instructions to manipulate the stack,
which would have the advantage that it would be reentrant -- using a global
temp to hold the STEP and LIMIT values will fail if the loop contains a
recursive call to the function containing the loop.
Chris Dodd
cdodd@acm.org
| |
| Hans-Peter Diettrich 2006-06-17, 7:05 pm |
| tomazos@gmail.com wrote:
> 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 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.
>
> Any enlightenment on this topic appreciated.
IMO you can assume that according variables have been created,
somewhere, somehow. At least I can't imagine how else this problem could
be solved, on a single-stack machine with the limited instruction set
you mentioned. With more instructions, for stack pointer relative
operands (FORTH: DUP, SWAP, OVER...), it were possible to have the STEP
and LIMIT values on the stack.
DoDi
|
|
|
|
|