Re: [Query] Tree-based parsing?

Nick Kramer <nkramer@cs.cmu.edu>
4 May 1997 22:41:10 -0400

          From comp.compilers

Related articles
[Query] Tree-based parsing? jlilley@empathy.com (John Lilley) (1997-04-16)
Re: [Query] Tree-based parsing? fjh@mundook.cs.mu.OZ.AU (1997-04-18)
Re: [Query] Tree-based parsing? bear@sonic.net (Ray Dillinger) (1997-04-22)
Re: [Query] Tree-based parsing? geert@sun3.iaf.nl (1997-05-04)
Re: [Query] Tree-based parsing? nkramer@cs.cmu.edu (Nick Kramer) (1997-05-04)
Re: [Query] Tree-based parsing? scotts@metaware.com (Scott Stanchfield) (1997-05-08)
Re: [Query] Tree-based parsing? scotts@metaware.com (Scott Stanchfield) (1997-05-08)
Re: [Query] Tree-based parsing? wilson@cs.utexas.edu (1997-05-08)
| List of all articles for this month |

From: Nick Kramer <nkramer@cs.cmu.edu>
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 <bear@sonic.net> 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
>input.


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.