Markers in bottom-up eval of inherited attr.

I have two related questions about markers:


Question 1:
------------


Markers are described in section 5.6 of the new dragon book. Upon
reading example 5.18 on page 311, it seems like markers are useless.


Given the production and semantic rules:


S -> aAC C.i := A.s
S -> bABC C.i := A.s
C -> c C.s := g(C.i)


The use of the marker is because upon reduction C -> c, it is not
known whether C.i is in val[top-1] or in val[top-2] since there may
exist B between A and C or not. So the job of the marker is to make
the location of C.i consistent.


After marker insertion, we have


S -> aAC C.i := A.s
S -> bABMC M.i := A.s ; C.i := M.s
C -> c C.s := g(C.i)
M -> epsilon M.s := M.i


Forgive me, but in the second production, we have M.i := A.s ... well
isn't this the same problem we had before? I mean you still have to
search the stack for A.s! In the original we had


C.i := A.s


now we have


M.i := A.s


What's the big deal about inserting a marker when it still has to do
the same original task? Can't we just search the state stack for the
desired state and then extract the corresponding value in the first
place? (Because in the end that's what M.i := A.s has to do anyway.)
UNLESS we hard-code M.i to val[top-2].


Question 2:
-----------


After example 5.18, new dragon says "Marker terminals can also be used
to simulate semantic rules that are not copy rules.", and this is
given:


Before:
S -> aAC C.i := f(A.s)


After:
S -> aANC N.i := A.s; C.i := N.s
N -> epsilon N.s := f(N.i)


where N is the marker this time. Again I fail to see the usefulness
(and again this is due to the new dragon not evening mentioning WHY
there's a problem with the 'Before' scenario). Why can't we evaluate
f(A.s) directly in the 'Before' scenario? We know A.s will be
val[top-1], so just before you reduce, just compute f(val[top-1]).






Thank you in advance for your responses

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