Re: Parsing with infinite lookahead

hbaker@netcom.com (Henry G. Baker)
Tue, 1 Mar 1994 17:24:10 GMT

          From comp.compilers
Related articles
[2 earlier articles]
Parsing with infinite lookahead bevan@cs.man.ac.uk (Stephen J Bevan) (1994-02-24)
Re: Parsing with infinite lookahead dwohlfor@cs.uoregon.edu (1994-02-24)
Re: Parsing with infinite lookahead parrt@s1.arc.umn.edu (Terence Parr) (1994-02-25)
Re: Parsing with infinite lookahead corbett@lupa.Eng.Sun.COM (1994-02-26)
Re: Parsing with infinite lookahead nandu@cs.clemson.edu (1994-02-27)
Re: Parsing with infinite lookahead hbaker@netcom.com (1994-02-28)
Re: Parsing with infinite lookahead hbaker@netcom.com (1994-03-01)
Re: Parsing with infinite lookahead bromage@mundil.cs.mu.OZ.AU (1994-03-02)
Re: Parsing with infinite lookahead mareb@cis0.levels.unisa.edu.au (1994-03-24)
| List of all articles for this month |
Newsgroups: comp.compilers
From: hbaker@netcom.com (Henry G. Baker)
Summary: Lingol takes quadratic, not cubic, space
Keywords: parse, theory
Organization: Compilers Central
References: 94-02-174 94-02-208
Date: Tue, 1 Mar 1994 17:24:10 GMT

> For ambiguous sentences, Lingol gives you a fully factored parse tree in
> which the potentially infinite number of different parses are stored in
> cubic space.


My 'cubic space' comment was incorrect; Lingol uses space _quadratic_ in
the length of the sentence. Consider an nxn matrix where n is the length
of the sentence (# of nonterminals). You can fill in this matrix with
bitvector entries whose length is the number (N) of distinct nonterminals
in the grammar (O(1)). The set at (i,j) indicates the phrases that can be
constructed from the i-th word to the j-th word in the sentence. The
space is thus |N|xnxn or O(n^2). The non-bitvector space is proportional
to the bitvector space.


Sorry about the brain fade.


--
            Henry Baker
--

Post a followup to this message

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