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

"M.G.J. van den Brand" <Mark.van.den.Brand@cwi.nl>
13 Oct 2002 16:03:51 -0400

          From comp.compilers

Related articles
[11 earlier articles]
Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-09-25)
Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-09-29)
Re: LR Grammars not in LALR(1) or LR(1) haberg@matematik.su.se (Hans Aberg) (2002-09-29)
Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-09-29)
Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-13)
Re: LR Grammars not in LALR(1) or LR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2002-10-13)
Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-10-13)
Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (Sönke Kannapinn) (2002-10-18)
Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-10-20)
Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-24)
Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (Sönke Kannapinn) (2002-10-25)
| List of all articles for this month |

From: "M.G.J. van den Brand" <Mark.van.den.Brand@cwi.nl>
Newsgroups: comp.compilers
Date: 13 Oct 2002 16:03:51 -0400
Organization: Centrum voor Wiskunde en Informatica (CWI)
References: 02-09-014 02-09-029 02-09-068 02-09-092 02-09-097 02-09-126 02-09-130 02-09-143 02-09-161
Keywords: parse
Posted-Date: 13 Oct 2002 16:03:51 EDT

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


Post a followup to this message

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