Re: Why put type information into syntax?

Marat Boshernitsan <maratb@CS.Berkeley.EDU>
15 Apr 2000 10:29:16 -0400

          From comp.compilers

Related articles
[5 earlier articles]
Re: Why put type information into syntax? kst@cts.com (Keith Thompson) (2000-04-01)
Re: Why put type information into syntax? michael.prqa@indigo.ie (Michael Spencer) (2000-04-05)
Re: Why put type information into syntax? rod.bates@wichita.boeing.com (Rodney M. Bates) (2000-04-05)
Re: Why put type information into syntax? kst@cts.com (Keith Thompson) (2000-04-11)
Re: Why put type information into syntax? idbaxter@semdesigns.com (Ira D. Baxter) (2000-04-14)
Re: Why put type information into syntax? world!bobduff@uunet.uu.net (Robert A Duff) (2000-04-14)
Re: Why put type information into syntax? maratb@CS.Berkeley.EDU (Marat Boshernitsan) (2000-04-15)
Re: Why put type information into syntax? mspencer@eircom.net (Michael Spencer) (2000-04-15)
| List of all articles for this month |

From: Marat Boshernitsan <maratb@CS.Berkeley.EDU>
Newsgroups: comp.compilers
Date: 15 Apr 2000 10:29:16 -0400
Organization: University of California at Berkeley
References: 00-03-133 00-03-146 00-04-017 00-04-050 00-04-073 00-04-102
Keywords: types, parse

> > {
> > typedef int foo;
> > foo(x); /* This is a variable declaration. */
> > bar(y); /* This is a function call.
> > }
>
> Would it be possible to deal with this by having the parser build
> trees that retain the ambiguity, and then resolve it during a separate
> semantic-analysis tree walk? ...
> [Sure, that's what Earley parsers do, but the performance hit can be
> phenomenal. -John]


Actually, GLR (generalized LR) parsing due to Tomita does just that.
The performance hit is minimal: this is achieved through optimal
sharing of the parse trees and other tricks.


See "Current Parsing Techniques in Software Renovation Considered
Harmful" by Mark van den Brand et. al
http://www.tinaa.com/harmful/parsing.html


This paper offers some performance numbers and includes a host of great
references (including a reference to a comparison with Earley's
algorithms).


I have plenty of other GLR references if you are interesting in the
implementation details, but this paper offers a great overview.


Marat.


Post a followup to this message

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