RE: parsing, was .NET Compiler for Interactive Fiction

Chris F. Clark said:


> 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


To that list I would add self-modifying automata, per Neto et al. of
the LTA team at University of Sao Paolo:


        http://www.pcs.usp.br/~lta/


I'd also add something that I've focused quite a bit on with Meta-S,
grammar profiling. I don't know if there are any other commercial
grammar systems that allow for detailed profiles of parse (for
instance, number of ticks/hit and miss, on a production level).


Of the things mentioned in your list above, Meta-S includes the
following:


      predication
      adaptation
      LL(k) where k>0


Something not on the list, but which Meta-S can also do, is stream
manipulation -- that is, feeding modified versions of the stream into
predicates -- something you and I have discussed privately.


There is also a form of inheritance, but it is used in a way that has
nothing to do with grammar re-use. It is used as a form of
predication.


Finally, there is something that is a real bear: adequate grammar
compile-time detection of errors in TP grammars. I'm still working on
decomposing $-grammars into their composite type > 1 sub-grammars, and
doing 2b+ error detection on the sub-grammars. (As per my latest
paper's later theorems.) This is a direction I hope will show some
fruit.


Then there is the biggest unsolved problem of modern grammar theory:
getting people to take the plunge into a new tool that doesn't work
like lex and yacc! ;-) Seriously, this particular problem may be
undecidable! It takes a long time to prove things formally, and then a
long time for the proofs to float about ... and parser users -- the
hardcore ones -- demand absolute proofs. A very hard sell.


--
Quinn Tyler Jackson

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