Re: Algol 60 Syntax

Dan Sutton wrote:
> <snip>
> Yes, I know. My problem is not so much matching syntax, but, as you
> say, semantics. The goal, therefore, is to develop a functional
> semantics representation notation (which may then be incorporated as
> this interim representation) - a sort of BNF for semantics, as it
> were: as you point out, this has so far proven to be impossible...


This has not proved impossible, there are in fact several formal
notations for describing semantics, i.e., action semantics, two level
grammars, Z, and VDM. In addition, the intermediate representations
used by most compiler collections are, in essence, less formal
notations describing semantics that are usually specialized to
languages with similar semantics, i.e., gcc's intermediate
representation is a reasonable language for describing imperative
languages with argument passing mechanisms that map to either call by
value or accesss via a pointer. However, because semantics is more
complicated than syntax semantic notations are not as widely used or
known as BNF and are more difficult to learn. Further translation in
them tends to be one way, you can use the semantic description to
translate from a high level language to a low level language, but not
to another high level language (unless that high level language has a
low level subset, i.e., C)


> <snip>
>
> I get a bit farther each time, though - I still think it's possible:
> after all, if one can describe to a person how to do it such that it
> makes sense and they can continue to do it for code they've never
> seen, then it must be possible to describe it to a machine, since
> there are definitely rules involved.


In principle yes, however the resulting translation of one language
into another language might result in a Turing machine model.


Examples:
A near direct transliteration of C into Fortran would neglect
that many C expressions are allowed to have side effects that are not
allowed to exist in valid Fortran code. As a result, unless the
absence of those side effects can be verified by means other than the
formal language definition, a legal translation of C code to Fortran
code makes all such side effects obvious in terms of the Fortran
language. There are two obvious ways of doing this, translate all C
functions to Fortran subroutines and insert reads and writes to an
external file for most pointer accesses, i.e., literally implement a
Turing machine, or do the equivalent of recursively inlining all C
code into the final Fortran main.


File access. In C all files are essentially flat streams of
bytes, while Fortran files are structured (record based). It is
relatively straightforward to encode Fortran's file structure into a
stream. The translation of the C stream of bytes into a simple regular
structure that is consistent both with Fortran's semantics and with
untranslated C code is fraught with problems.


Dynamic allocation: Several languages have definitions such
that all memory useage can be straightforwardly statically allocated,
i.e., older Fortrans (Cobol?) and Occam. Translation of language with
dynamic memory access into those languages at the very least requires
imposing a set limit on recursion depth and implementing your own
machine for the dynamic variables within the resulting program. I.e.,
statically allocate a large array of integers to serve as pointers
into other statically allocated arrays.


Complicating this is that by nature people tend to avoid complex code,
but they cannot avoid it entirely in code dealing with large complex
problems. As a result an imperfect strightforward translation will
almost always work on small test cases, but fail on larger codes where
the coding relies on the detailed semantics of the language, and,
sometimes, on the details of a given implementation of the semantics.


> <snip>

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