Re: Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG G

Manoj Plakal <plakal@cs.wisc.edu>
10 Apr 2001 01:21:45 -0400

          From comp.compilers
Related articles
Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG miles@mail.jct.ac.il (2001-03-31)
Re: Re: Algorithm efficiently generating L(G), for a non-selfembedding miles@mail.jct.ac.il (2001-04-04)
Re: Re: Algorithm efficiently generating L(G), for a non-selfembedding plakal@cs.wisc.edu (Manoj Plakal) (2001-04-10)
| List of all articles for this month |
From: Manoj Plakal <plakal@cs.wisc.edu>
Newsgroups: comp.compilers
Date: 10 Apr 2001 01:21:45 -0400
Organization: University of Wisconsin-Madison
References: 01-03-186 01-04-008
Keywords: parse
Posted-Date: 10 Apr 2001 01:21:45 EDT

On Tuesday 03 April 2001 23:16, Gershon Miles\ wrote:
> Simply "walking the tree" will require recalculating many variables
> with the grammar.


                Well, can't you add some memoization to the tree-walk
                to avoid re-walking subtrees? And trade-off space with
                        time by varying the size of the memoization cache?


                        A related idea would be to do a bottom-up computation
                        of the tree and do something like dynamic programming
                        to avoid redundant recomputations.


                        Manoj

Post a followup to this message

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