Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15

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.

Return to the comp.compilers page.
Search the comp.compilers archives again.