Re: parsing, was .NET Compiler for Interactive Fiction

John wrote:
> [Parsing has indeed been well studied. The main changes in recent
> years is that algorithms that used to be considered too slow for
> production use aren't any more. -John]


Joachim replied:
> Well, Kannapinn's recent work is still a noticeable improvement in LR
> parsing, so there *is* progress in this area. But I agree that things
> have come to a near-standstill, problems are either solved or
> known/assumed to be unsolvable. Research has moved on to other topics.


Actually, there is quite a bit of parsing work going on these days.
It just isn't as well regarded and well publicized. I think that the
common mis-conception that all the interesting problems have been
solved or are unsolvable is part of the problem. The result of this
is that most researchers are "amatuers" in one sense or another. In
some ways, that is good, because often amatuers don't know that
something can't be done and so go-off and find a novel new way of
approach that solves the problem (by side-stepping the part which
couldn't be solved).


There is a down-side to the amatuer phenomenon also. Many of the
interesting ideas get buried in a one-of-a-kind parser generator that
doesn't get maintained long enough to reach maturity.


Of course, this is partly a result of the fact that the base tools are
too easy to recreate from scratch. It's not like the world needs
another incompatible recusive descent parser generator nor another
graphical interface layered on top of yacc nor even another Tomita
engine based on LALR tables. (If you have something interesting to
add, these can all be valid starting points, but I've seen too many
me-too versions where the author doesn't even get the tool completely
working and hasn't added anything new, just simply recovered the
ground that is well worn--too much "not invented here".)


Here is my list of some of the more interesting things that I have
seen in "recent" years (in no particular order). These ideas have all
made it into at least one tool which is actively being maintained (and
most of them mhave been used in more than one tool, so you can compare
implementation choices).


                - predicated grammars
                - adaptive grammars
                - grammar inheritance
                - practical ELR parsing
                - Tomita (GLR) parsing
                - practical k-lookahead parsing--esp LL(infinity) parsing
                - state splitting LR parsing
                - tunnel automata
                - non-greedy regular expressions
                - customizable AST generation from grammars
                - the visitor pattern
                - tree walker generators
                - bottom up rewrite generators
                - non-canonical LR parsing


Some ideas that I recall looked intriguing, but that never were used
in a mature tool that I could investigate to my satisfaction. (This
list is harder to remember because if the idea looks good, but you
can't follow up on it, one doesn't know if it fulfills its promise and
soon one forgets it. These are ones I couldn't forget....)


                - N**2 space Earley parsing
                - tree adjoining grammars
                - fuzzy grammars
                - outside-in conflict resolution
                - dotted grammars
                - LR parser cores for managing editor buffer contents
                - a novel context/state approach called "register vectors"


Just my opinions,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------

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