Re: [Query] Tree-based parsing?

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
--

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