Re: Do I need to invent a new type of parser?

stephen@estragon.uchicago.edu (Stephen P Spackman)
Sun, 26 Apr 1992 20:37:27 GMT

          From comp.compilers

Related articles
Do I need to invent a new type of parser? jeffk@ecst.csuchico.edu (Jeffery Alan Keasler) (1992-04-20)
Re: Do I need to invent a new type of parser? Jan.Rekers@cwi.nl (1992-04-21)
Re: Do I need to invent a new type of parser? jeffk@ecst.csuchico.edu (1992-04-22)
Re: Do I need to invent a new type of parser? stephen@estragon.uchicago.edu (1992-04-26)
Re: Do I need to invent a new type of parser? hagerman@ece.cmu.edu (1992-04-28)
Re: Do I need to invent a new type of parser? stephen@estragon.uchicago.edu (1992-04-29)
Re: Do I need to invent a new type of parser? anton@mips.complang.tuwien.ac.at (1992-05-04)
Re: Do I need to invent a new type of parser? visser@fwi.uva.nl) (1992-05-06)
Re: Do I need to invent a new type of parser? keithc@dcs.qmw.ac.uk (1992-05-08)
| List of all articles for this month |

Newsgroups: comp.compilers
From: stephen@estragon.uchicago.edu (Stephen P Spackman)
In-Reply-To: jeffk@ecst.csuchico.edu's message of 22 Apr 92 00:47:25 GMT
Keywords: parse, design
Organization: University of Chicago CILS
References: 92-04-087 92-04-098
Date: Sun, 26 Apr 1992 20:37:27 GMT

jeffk@ecst.csuchico.edu (Jeffery Alan Keasler) writes:
| My language is not static. Programmers can specify productions in
|their programs. These productions will be optimized and incorporated into
|the compiler as the compiler continues parsing the rest of the program.


|[Not to throw cold water on your plans, but 15-20 years ago there were quite
|a few languages which allowed to you define syntax on the fly. They all died.
|Makes you wonder, huh? -John]


The problem is (IMHO) that dynamic syntax makes parsing harder. One upon a
time the concern was compile time, of course, but the constraint is still
there on an arbitrarily fast machine, because the *human reader* also
needs to be able to parse the code. Languages come out the way they do in
part because of human perceptual limitations.


Contrary to popular belief, however, the choices are not limited by this
argument to Lisp (where you can define anything, so long as it's ugly) and
Pascal (where you're basically krazy-glued to a specific choice of names -
begin/end looks WEIRD in a french programme!); there is an array of
possible solutions which allow fixed syntax but with great flexibility in
notations (relying on the type system to do a little of the work, though).
Below is my latest experimental grammar - you'll notice that the only
SYNTACTICALLY reserved words are ; and . (though there are plenty of
operators that you can't redefine).


Note that over half of the productions below concern comment attatchment,
so this grammar is even simpler than it looks. It supports all of the
following notational styles:


cons (car x) (cdr y)
a := x + y; b := x - y; [a, b]
.if x > 0 .then x .else -x .


The lesson learned from Lisp, of course, is to do all the work at
abstract syntax, and to define that first translation stage upfront.
Oh, and lose the notion of "sequence": put the continuation into the
list of operands.
--
stephen p spackman Center for Information and Language Studies
stephen@estragon.uchicago.edu University of Chicago
----------------------------------------------------------------------
%{
#include "exemplar.h"


Expression parseTree = 0;
%}


%token identifier
%token operator
%token keyword
%token opener
%token closer
%token comment


%start programme


%%


programme: cternary {parseTree = $1;}


atom: identifier;


functional: atom {$$ = $1;}
| functional atom {$$ = apply($1, $2);}
| functional comment {$$ = note($1, $2);}
;


unary: functional {$$ = $1;}
| operator unary {$$ = apply($1, singleton($2));}
;


binary: unary {$$ = $1;}
| unary operator cbinary {$$ = apply($2, pair($1, $3));}
;


cbinary: binary {$$ = $1;}
| comment binary {$$ = note($2, $1);}
;


ternary: binary {$$ = $1;}
| unary operator cbinary ';' cternary
{$$ = apply($2, triple($1, $3, $5));}
;


cternary: ternary {$$ = $1;}
| comment cternary {$$ = note($2, $1);}
;


keystruct: '.' {$$ = $1;}
| keyword cternary keystruct
{$$ = apply(apply($1, $2), $3);}
;


atom: opener closer {$$ = brackets($1, $2);}
| opener cternary closer {$$ = apply(brackets($1, $3), $2);}
| opener ccoperator closer{$$ = apply(brackets($1, $3), $2);}
| opener cckeyword closer {$$ = apply(brackets($1, $3), $2);}
;


functional: keystruct {$$ = $1;}
;


coperator: operator {$$ = $1;}
| coperator comment {$$ = note($1, $2);}
;


ccoperator: coperator {$$ = $1;}
| comment ccoperator {$$ = note($2, $1);}
;


ckeyword: keyword {$$ = $1;}
| keyword comment {$$ = note($1, $2);}
;


cckeyword: ckeyword {$$ = $1;}
| comment cckeyword {$$ = note($2, $1);}
;


%%
--


Post a followup to this message

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