Re: Tomita (GLR) Parser Devlopment Question

(We have a production GLR parser as part of our DMS Software
Reengineering Toolkit, see
http://www.semdesigns/Products/DMS/DMSToolkit.html).


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: idbaxter@semdesigns.com
Semantic Designs, Inc. web: http://www.semdesigns.com
12636 Research Blvd. C-214 voice: (512) 250-1018 x140
Austin, TX 78759-2200 fax: (512) 250-1191




"David Kaplan" <kapland@starfleet.com> 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....

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