[tern] even more notes

[david nicol]

I talked with my brother the mathematician over the TG holiday and
he suggested a good use for a general purpose rewriting tool might
be translating between the various theorem-proving languages.

More thoughts:
specific kinds of tags on entities might be overkill.  If
all the language does is group things and tag them, how far can we
get?


It was suggested that I should familiarize myself with flex and bison
before I dig deeper into a stubborn hole.  Which is very true.

Reading `man flex` I find several things.  One is that flex is
sort of similar to what I have in mind for perl -MTERN except the
user code is in Perl instead of C.

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.

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

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


flex's syntax for specifying contexts in which rules are valid
is good enough to use -- it is to precede the rule definition with 
the name of the state in anglebrackets -- we extend it by allowing
one name to represent a list of names.

Flex inputs are definitions, rules, or user code.  Tern jumbles
them all together.  Where a flex definition might be

DIGIT [0-9]

a tern rule saying the same thing is

DIGIT is [0-9]

which means from that point forward, DIGIT will get replaced
with [0-9] as in

DIGITS is DIGIT+

and to tag digits larger than 10000 with a "large" tag we need
to be able to say something like

DIGITS d is d-large when d > 10000

because a tern rule doesn't just declare a pattern-match for
rewriting, it can define an entity which can be imbued with meaning
through tagging.  Although greater-than can be built using regexes:

DIGIT{5,} d is d-large

we need to select a word for the conditional operator, I don't want
to use "if" because that is likely to be a production.

Maybe the division into definitions and productions makes sense.

Definitions are applied to create the "deep structure" and then
productions are applied to convert the deep structure into the
target language.


HTML Bison documentation:
http://www.sunsite.ualberta.ca/Documentation/Gnu/bison-1.30/html_mono/bison.html



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

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?

Bison only makes one pass over its source


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.






-- 
David Nicol, independent consultant and contractor            312 587 2868
God did not create the world in seven days; he screwed around for six days
                           and then pulled an all-nighter. -- `fortune -s`