Re: [Query] Tree-based parsing?

Nick Kramer <>
4 May 1997 22:41:10 -0400

          From comp.compilers

Related articles
[Query] Tree-based parsing? (John Lilley) (1997-04-16)
Re: [Query] Tree-based parsing? (1997-04-18)
Re: [Query] Tree-based parsing? (Ray Dillinger) (1997-04-22)
Re: [Query] Tree-based parsing? (1997-05-04)
Re: [Query] Tree-based parsing? (Nick Kramer) (1997-05-04)
Re: [Query] Tree-based parsing? (Scott Stanchfield) (1997-05-08)
Re: [Query] Tree-based parsing? (Scott Stanchfield) (1997-05-08)
Re: [Query] Tree-based parsing? (1997-05-08)
| List of all articles for this month |

From: Nick Kramer <>
Newsgroups: comp.compilers
Date: 4 May 1997 22:41:10 -0400
Organization: School of Computer Science, Carnegie Mellon
References: 97-04-096 97-04-150
Keywords: parse, storage, question

Ray Dillinger <> wrote:
[discussing unusual parsing strategies]
> And there is something you can do to make it more friendly in
>terms of memory use. First, you can read the input stream parsing it
>into tokens until you get to one of your "top-level" landmarks, (from
>a leftparen to a rightparen, for example) then traverse the tokens
>you've read from the beginning of that lexical space to one of your
>second-level landmarks, (like a semicolon) then traverse the resulting
>tree to one of your third-level landmarks, etc... recursively until
>you have fully parsed the first lexical space you read; then you move
>on to the next. This way, you still get the recursively-refined block
>structure, but you get to interleave your passes, so you don't have to
>hold the early parts of the parsed tree in memory, nor the unread

I'm tempted to say that in today's world, such optimizations are
unnecessary. I've worked with two parsers that read the entire source
file into memory before they process it, and I haven't seen any
problems. After all, a 10,000 line file only takes up about 350KB on
disk, and I'd consider a file that big to be rather unwieldy for the
programmer. Granted, since you're storing multiple representations in
memory, your memory usage will be more, but still quite reasonable
(say, a few megabytes). On a 32- or 64-megabyte machine, is it really
worth doing anything else?

-Nick Kramer

Post a followup to this message

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