Re: Tomita (GLR) Parser Devlopment Question

"Ira D. Baxter" <>
19 Dec 2000 17:00:33 -0500

          From comp.compilers

Related articles
Tomita (GLR) Parser Devlopment Question (2000-12-18)
Re: Tomita (GLR) Parser Devlopment Question (Ira D. Baxter) (2000-12-19)
| List of all articles for this month |

From: "Ira D. Baxter" <>
Newsgroups: comp.compilers
Date: 19 Dec 2000 17:00:33 -0500
Organization: Posted via Supernews,
References: 00-12-061
Keywords: parse
Posted-Date: 19 Dec 2000 17:00:33 EST

(We have a production GLR parser as part of our DMS Software
Reengineering Toolkit, see

You have to traverse backwards to enumerate all the possible
reductions. It is true that most of the time, there is only *one*
possible reduction, and so this seems like unnecessary overhead.
Trouble is, you're never quite sure when it is unnecessary :-}

You could mark all stack nodes (which of course includes the stack
top) with a boolean indicating that only all children have only one
alternative, and avoid enumerating any more than the first one.
Frankly, keeping track of that boolean is about as expensive as
testing whether a child has multiple alternatives, so this doesn't
seem worth the effort.

You could also replicate the GLR code, and have the "main" code take
care of the special case, and the duplicate specialized to handle
shifts having only single alternatives below them. This looks a like
a maintenance nightmare to me.

We've thought about these and a number of other ideas, but not very
hard. Frankly, optimizing the reduction path doesn't buy a lot of
performance gain. Our parser spends more time allocating nodes and
fooling with characters while lexing. This just doesn't seem like its
worth the effort.

Ira D. Baxter, Ph.D.,CTO email:
Semantic Designs, Inc. web:
12636 Research Blvd. C-214 voice: (512) 250-1018 x140
Austin, TX 78759-2200 fax: (512) 250-1191

"David Kaplan" <> wrote in message
> I have gotten pretty Far in developing my GLR parser System. I Just
> Have one question relating to optimizing. Right Now, When I Reduce, I
> have to traverse backwards along the parse-tree vertices to get to the
> next state to "goto" from. Is There A Standard Way Of doing this
> That'S Faster....

Post a followup to this message

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