parsing (was: related projects)

[Brian T Rice]

Oops, this is one of those cases where an email sits too long in my
editing queue.

On Fri, 28 Feb 2003, Jecel Assumpcao Jr wrote:

> On Thursday 27 February 2003 17:58, Brian T Rice wrote:
> > I suppose so, but I wouldn't point out PIE and Sketchpad as the best
> > of what was lost.
>
> Having read all the available papers on these projects, I wouldn't mind
> having them exactly as they were back then. Specially Sketchpad.

Maybe you should post some reviews and links for them on the CLiki.

> > Nope, it's entirely pragmatic. Generally, the Tunesy thing we intend
> > to do requires us to deal with programs in an abstract manner,
> > allowing annotations to be built without special syntax. So expect
> > interesting things after the bootstrapped system has been built out
> > into something semi-comfortable.
>
> That will be interesting. Integrating annotations with the "main"
> program will give you many of the same problems that the Aspects people
> face. This is a place where graphics can help: a single line linking
> one point in the source to another point in a separate "file" is far
> clearer than any textual naming convention, thought in theory it would
> seem about the same.

Yes, that's exactly what we've had in mind, like the "hyperprogramming"
systems such as Napier.

> > > [quick overview of the new syntax]
> > This appears to be requiring context-free grammars.
>
> Not really - my system doesn't have a parser at all! The code editor
> tricks you into entering and manipulating syntax trees directly :-)

Okay, so you have the grammar but you don't worry about parsing. Actually,
if individual keystrokes and such dispatch to "editors" or "specialized
grammars" then it's not really a CFG, but Lisp's READ style.

The issue I see with this is that eventually you will want some
contextual-sensitivity. But this is sort of a non-issue if you still have
an access mode to whatever you want (an implicit escape).

Anyway, I'd like to see a demo of this some time. ;)

> This is my version of "as simple as possible".
>
> I am still interested in parsers for importing code from Self/Smalltalk,
> however. And for reading other kinds of files as well.

Eventually some kind of system for serializing and reconstructing objects,
yes. Parsing in the abstract sense does help with this.

> > This kind of
> > syntax generality is why I've been looking into Maude's MetaParser
> > system (see http://cliki.tunes.org/Syntax%20in%20Maude).
>
> This looks very flexible.

It is, for the most part, although I have yet to see it used to emulate
the entirety of some other language's syntax. It would have to be
sufficiently regularized, I suppose - all terms need to be separated by
spaces to be clearest, although this often isn't needed. Perhaps if
Maude's lexer were also available for modification...

> > Right now
> > I'm translating a Smalltalk parser-generator to Slate just to get LR1
> > and LALR1 handling, and it's not attractive at all, although better
> > than it was for Smalltalk.
>
> Have you seen the Mango package for Self? It translates "structured BNF"
> into a LR1, LALR1 or SLR1 grammar (you choose which) and then generates
> a Self program to parse it. Ole Agesen's test example was ANSI C and it
> was used by Mario to parse GNU Smalltalk. I have never understood why a
> parser couldn't be generated directly from the original structured BNF.

SmaCC works mostly the same way, except that it parses input text which
partially consists of regular expressions. Ultimately, though, the main
problem is that neither Smalltalk nor Self have the same kind of code
model as Slate, so I'd have to hand-roll the code-generator in either case
from scratch.

(see src/compiler/cc.slate in the Slate CVS repository for some of the
work I've been doing on this.)

I also haven't been able to find a working link for Mango in years, and I
lost the copy that I did have. If you have a link, I'd welcome it.

Parsers can't be generated from the BNF directly because the result would
be too slow for real usage.

> > But to get the MetaParser usage, you have to implement Maude's
> > semantics to some extent, so eventually the object-oriented approach
> > has to yield somehow. I suppose this is where I should tie things in
> > with Arrow, but I'm not sure.
>
> The Maude manual pages you gave a link to talk about "objects" a lot. I
> haven't looked at the rest of the language description.

It does? I notice lots of uses of "operator" and "term" but not "object".
There /is/ a way to perceive this system as objects and messages, which is
a very interesting part of the language ("mobile"/"oo" maude), but it
doesn't seem to be emphasized there.

One of the strengths of Maude's algebraic/rewrite model for parsing is
that terms and parse trees have a lot of the same computational issues.
The "geometric" properties of an operator (associativity, idempotency, and
such) are dealt with at the same level for both domains.

-- 
Brian T. Rice
LOGOS Research and Development
mailto:water@tunes.org
http://tunes.org/~water/