Re: Why context-free?
9 Oct 2005 20:46:46 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: Why context-free? (2005-10-07)
Re: Why context-free? (Russ Cox) (2005-10-07)
Re: Why context-free? (Robert A Duff) (2005-10-07)
Re: Why context-free? (2005-10-08)
Re: Why context-free? (2005-10-08)
Re: Why context-free? (glen herrmannsfeldt) (2005-10-09)
Re: Why context-free? (2005-10-09)
Re: Why context-free? (2005-10-09)
Re: Why context-free? (Robert Figura) (2005-10-10)
Re: Why context-free? (Ivan Boldyrev) (2005-10-10)
Re: Why context-free? (Tony Finch) (2005-10-13)
Re: Why context-free? (2005-10-13)
Re: Why context-free? (Chris F Clark) (2005-10-13)
[18 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 9 Oct 2005 20:46:46 -0400
References: 05-10-05305-10-061 05-10-062
Keywords: parse, tools
Posted-Date: 09 Oct 2005 20:46:46 EDT

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

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.

Peri Hankey

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

Post a followup to this message

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