Compilers, Aho/Sethi/Ullman, Exercise 2.15

tomazos@gmail.com
5 Jun 2006 20:47:32 -0400

          From comp.compilers

Related articles
Compilers, Aho/Sethi/Ullman, Exercise 2.15 tomazos@gmail.com (2006-06-05)
Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15 pjb@informatimago.com (Pascal Bourguignon) (2006-06-07)
Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15 cdodd@acm.org (Chris Dodd) (2006-06-07)
Re: Compilers, Aho/Sethi/Ullman, Exercise 2.15 DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-06-07)
| List of all articles for this month |

From: tomazos@gmail.com
Newsgroups: comp.compilers
Date: 5 Jun 2006 20:47:32 -0400
Organization: http://groups.google.com
Keywords: books, comment

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]


Post a followup to this message

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