Re: syntax extension, was Why context-free?
15 Dec 2005 17:53:19 -0500

          From comp.compilers

Related articles
[6 earlier articles]
Re: syntax extension, was Why context-free? (toby) (2005-11-04)
Re: syntax extension, was Why context-free? (2005-11-26)
Re: syntax extension, was Why context-free? (2005-11-27)
Re: syntax extension, was Why context-free? (2005-12-08)
Re: syntax extension, was Why context-free? (Robert Figura) (2005-12-15)
Re: syntax extension, was Why context-free? (2005-12-15)
Re: syntax extension, was Why context-free? (2005-12-15)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 15 Dec 2005 17:53:19 -0500
References: 05-10-05305-11-014 05-11-028 05-11-115 05-11-122 05-12-017 05-12-037
Keywords: parse, theory
Posted-Date: 15 Dec 2005 17:53:19 EST

>You cannot make an universal turing machine from a simple recursive

The lm-diagram shows that for unrestricted rules you need two nesting
systems that may and often will overlap - the notational equivalent is
a system of two interleaved bracket pairs (eg '(' ')' for start-end of
recognition phase, '[' ']' for start-end of substitution phase), as in:

                                      .------------------------. .-----.
                                      | .-----------. | | |
                                      | | | | | |
            ( ... ( ... )[ ... )[ ... ( ... ] ... ] ... )[ ... ]
            | | | | | |
            | '-----' | | |
            '-------------------' '------------------'

Here '...' represents a sequence of symbols and variable bindings that
have been matched/consumed in the course of the analysis, the brackets
are as described above, and the ascii art above and below the line
represents overlapped nestings of recognition phases (below the line)
and substitution phases (above the line) . Any symbol that is not
covered by nesting above the line comes from the external input. The
scope rules for variable reference relate to the nesting structure of
the recognition phases in which variables are bound.

My lambda experiment shows that this rule system in effect contains the
lambda calculus - and incidentally it does this without any kind of
self-modifying grammar - I have designed the rule system specifically
to permit grammatical rules to be added and deleted at run-time, but
have never yet needed to add the operations that would make this

The lambda experiment is intended as an educational and informative
exercise that would help place the language machine in relation to
theory and in relation to questions that are well understood - I don't
intend to vanish utterly into the 'Turing tarpit'.

On the question of the metalanguage notation, I have had this piece of

  > the syntax is weird at first glance but is in fact really concise
and efficient. I love it

I agree that the metalanguage is in effect the high-level assembler of
the language machine - but my experience has been that it gets the job
done, and I have put immense effort into making it concise and easy to
use. If you add structured complexity to the notation, you are setting
up yet another level of counterpoint, and as the lm-diagram shows, you
are already dealing with a kind of counterpoint at run-time (JS Bach
would have loved it).

I also agree about the disgustingness of c++ compile-time features, and
about the possible usefulness of doing a c++ implementation, analyser,
or converter - perhaps I'll just have to hold my nose and get on with

In fact Remy Moueza has already modified my d2d translator to help in
converting c++ to D, but there are details that I need to look into
before posting the results on the website. During the 1980s I used a
previous implementation of these language techniques to translate C to
a variant/derivative of Algol68. This used grammatical rules and symbol
tables to deal with type analysis, and proved capable of porting itself
and a minimal runtime library to a completely different machine where
it continued in use for some time. Certainly c++ is harder than C, but
I doubt if there is anything that the language machine cannot handle.

So here's a question: would anyone sponsor a project that will use the
language machine to produce a retargettable frontend for c++ and at
least a demonstration backend for use in analysing and converting c++?
I could do this either within the existing project at sourceforge, or
start a new project to do it.

Peri Hankey - - the language

Post a followup to this message

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