Markers in bottom-up eval of inherited attr.

"Will" <>
27 Oct 2001 18:43:03 -0400

          From comp.compilers

Related articles
Markers in bottom-up eval of inherited attr. (Will) (2001-10-27)
Re: Markers in bottom-up eval of inherited attr. (2001-11-05)
| List of all articles for this month |

From: "Will" <>
Newsgroups: comp.compilers
Date: 27 Oct 2001 18:43:03 -0400
Organization: Excite@Home - The Leader in Broadband
Keywords: parse, attribute
Posted-Date: 27 Oct 2001 18:43:02 EDT

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

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

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

Post a followup to this message

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