[plt-scheme] Example of typed lexer/parser

On Tue, Mar 10, 2009 at 11:01:28AM +0000, Paulo J. Matos wrote:
> Hi all,
> 
> I am trying to type a lexer/parser I have. Are there any examples how
> there on how to do this?

I don't know if there are any systems already around in PLT Scheme to do 
this, but I suspect not.

The way it ought to be done is:

A parser tree has various constructors, such as constructors for 
subcript expressions, sums, assignments, variable declarations, 
functions, etc.

These tend to group themselves into various kinds, which have similar 
syntactic and semantic possibilities in the language, for example, 
subscripts, sums, and variables are all expressions.

You desgnate (abstract) types for kinds like "expression" and let the 
specific varieties of expressions (such as subscripted expressions, uses 
of variables, etc.) correspond to derived subtypes (in the 
object-oriented inheritance sense).

Nonterminals can be typed with the specific subtypes when the 
productions are that restricted, but usually you'll have to use the more 
generic kind.

These two levels in the inheritance hierarch seem to be enough for 
programming language syntax.  Whether the semantics has enough 
commonality to have further intermediate levels is another matter.

If you translate this to a recursive-descent parser, of course the 
nonterminal will be translated to a function that optionally 
returns a value of the appropriate type.  If subtyping is implemented 
properly for function types, this should go through without a hitch.  
Otherwise you'll be stuck using the wider kinds for all nonterminals 
instead of the more specific ones where the grammar would seem to make 
it possible.

-- hendrik