Re: [tern] even more notes

[Luke Palmer]

> From: david nicol <address@hidden>
> Date: 07 Dec 2002 01:55:30 -0600
> 
> It was suggested that I should familiarize myself with flex and bison
> before I dig deeper into a stubborn hole.  Which is very true.

You don't know flex and bison??!  Yes, that would be a _very_ good
thing to do.  Do you have any experience with BNFs?

> Another is that grouping and tagging is what flex does; by rewriting
> the input file according to the flex instructions.  Flex can only
> go one level deep though.  Tern needs to have the capabilities of Flex
> to match a regex of chars and give it a name, but also to operate on
> these matched items, to an arbitrary depth.

Sounds like you want a grammar.

> Also, after seeing the cover of the current "Games," I think "is" might
> be a better single keyword than "means."

So you want to abolish compatibility with Perl 6?  I think "means" is
good.

> # here's the answer, Mr. Clinton:
> is means means

:)
 
> Bison is very similar to what Tern should end up being.  Except that
> we won't be limited to LARL grammars. I think.

I assume you mean LALR.  And LALR is a large subset of LR; i.e. there
are not a lot of grammars that are LR but not LALR.  Damian's
Parse::RecDescent is capable of parsing LR grammars, so long as they
don't left-recurse.  This poses no restriction on what is
representable.

If you want to go further than that (I don't see why you would), there
is only one module on CPAN that parses a superset of LR grammars.  As
a matter of fact it parses any grammar whatsoever, in all possible
ways.  And it was written by me :) :).  Parse::Earley.

It's not very fast though.  The algorithm itself is bounded in cubic
time... (quadratic if the grammar is unambiguous). Yuck.

> So:  Why don't we just use Bison?
> 
> Bison only outputs in C
> 
> there is no "Bison Lite" that makes sense as a macro language
> (alterntatively, Serious Perl Hackers are supposed to alter the yacc
> grammar and recompile instead of writing macros.  Some do. )

Parse::RecDescent

> Bison doesn't appear to have support for tagging tokens and groupings.
> You can have as many kinds of groupings as you like though, eventually
> grouping the whole input into a single grouping, so what is the win
> in having tags instead of more grouping types?

You might be talking about a context-sensitive grammar.  They're used
in natural language processing, and I don't think you'll need them.
If you make an example of a TERN/Perl source file, I could tell you if
you did.

> Bison only makes one pass over its source

What's the win in more than one pass?  Another example might be good.

> Bison does stand as the current best tool for parsing algol-like
> languages however, and if Tern is to be the whole caboodle and
> also the kit that I imagine it to be, we're going to have to address
> every point that Bison addresses.

...
Parse::RecDescent

Have fun researching!

Luke