[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [tern] even more notes

From: Luke Palmer
Subject: Re: [tern] even more notes
Date: Sat, 7 Dec 2002 13:42:27 -0700 (MST)

> 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

> # 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

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. )


> 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.


Have fun researching!


reply via email to

[Prev in Thread] Current Thread [Next in Thread]