Compilers, Aho/Sethi/Ullman, Exercise 2.15
5 Jun 2006 20:47:32 -0400

          From comp.compilers

Related articles
Compilers, Aho/Sethi/Ullman, Exercise 2.15 (2006-06-05)
Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15 (Pascal Bourguignon) (2006-06-07)
Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15 (Chris Dodd) (2006-06-07)
Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15 (Hans-Peter Diettrich) (2006-06-07)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 5 Jun 2006 20:47:32 -0400
Keywords: books, comment
Posted-Date: 05 Jun 2006 20:47:32 EDT

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
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.

[He promises this isn't a homework assignment. -John]

Post a followup to this message

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