Re: Why context-free?

Hello - can I suggest that you take a look at the language machine:


      http://languagemachine.sourceforge.net


The language machine implements applies grammatical rewriting or
substitution rules to a stream of input symbols. The application of a
rule has a recognition phase and a substitution phase. The rules are
completely general - the recognition phae can produce any number of
symbols to be recognised, and the substitution phase can produce any
number of symbols to be substituted, and either can be empty. The
lm-diagram (lots of examples on the site) lets you see exactly how
this works in practice.


The effect of an analysis is described by means of variable bindings
and side effect actions which can include calls on external procedures
in the D or C languages. Translations are constructed as fragments
which are bound as variable values and which are typically not
evaluated until the end of a unit of analysis. In effect each fragment
is a closure with scope that relates to the nesting structure of
recognition phases.


I have used predecessors of this system to deal with type information
in several compilers and translators.


In my view, W-grammars are hard to understand for reasons which also
led to an unhealthy obsession with CFGs: however useful for theory, it
was unhelpful for practical purposes to think of the grammar as
generating the language.


The generative theory of grammar takes string rewriting rules as given.
But rewriting systems that allow nesting in both recognition and
substitution phases and that deal in terminal and nonterminal symbols
are themselves grammatical engines which are relatively easy to
understand, can be reasonably efficient, and can apply any kind of
grammatical rule.


I would be interested to hear what you think. If you have questions,
there is a mailing list and also a forum.


Regards
Peri Hankey


Nick Maclaren wrote:
> Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> >
> >> I have been thinking about a programming language, and have good
> >> reasons to abandon context-free grammars completely.

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