Re: LR Grammars not in LALR(1) or LR(1)

Hans Aberg wrote:
>
> Then one would want to be able to compare those algorithms by merely
> change the parsing algorithm. And then the method of disambiguation should
> be independent of the parsing algorithm.


Yes, this would be great if this was possible. However, our group has
quite some experiences in using GLR techniques. One of the problems is
that postponing disambiguation entirely to the end of the parsing
process leads to an explosion in the parse forest. The filtering of
this forest becomes far too expensive.


In the paper
@InProceedings{KV94,
        author = "P. Klint and E. Visser",
        title = "Using filters for the disambiguation of contextfree
grammars",
        booktitle = {Proceedings of the ASMICS Workshop on Parsing Theory},
        editors = {G. Pighizzini and P. San Pietro},
        pages = {1--20},
        year = "1994",
        note = {Tech. Rep. 126-1994 Dipartimento di Scienze
dell'Informazione, Universita di Milano}
}


a technique is described to use associativity and priority information
to "filter" the parse table in order to reduce the number of parallel
branches latter on in the GLR algorithm. In this way the parse forest
is reduced and the GLR speeds up.


The filters described in


>+ http://www.cs.uu.nl/people/visser/ftp/BSVV02.pdf


are again applied as soon as possible, however we did several
experiments in which the filters were applied after the parsing and
indeed conceptually this is possible, but you do not gain with respect
to performance.


-- Mark


---------------------------------------------------------------
M.G.J. van den Brand,
Department of Software Engineering
CWI
Kruislaan 413, NL-1098 SJ AMSTERDAM, The Netherlands.


Tel___(+31) 20 5924213 WWW____http://www.cwi.nl/~markvdb/
Fax___(+31) 20 5924199 Email__Mark.van.den.Brand@cwi.nl

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