RE: Formal semantics of language semantics

"Quinn Tyler Jackson" <>
13 Oct 2002 15:37:09 -0400

          From comp.compilers

Related articles
Re: Formal semantics of language semantics (Nick Maclaren) (2002-09-29)
RE: Formal semantics of language semantics (Michael Andersen) (2002-09-29)
RE: Formal semantics of language semantics (Quinn Tyler Jackson) (2002-10-13)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <>
Newsgroups: comp.compilers
Date: 13 Oct 2002 15:37:09 -0400
Organization: Compilers Central
References: 02-09-159
Keywords: semantics
Posted-Date: 13 Oct 2002 15:37:09 EDT

> >Has there been much work on figuring out what the requirements for
> >such a notation? This seems like it would be a relatively
> >active area due to the current industry focus on common language
> >runtimes, but I
> >haven't found any good links in my brief google searches.
> Sigh, no :-( I asked precisely your question and spent some time
> tracking down what was available. Here is a summary of what I
> found:

A particularly good introductory book on the subject, IMO, is
Kirkerud's Programming Language Semantics, if you can manage to get
your hands on it. It comes under other titles, as well (Semantics of
Programming Languages). International Thomson ISBN: 1850322732.
Unfortunately, Kirkerud passed away, and the book seems to have gone
by the wayside.

As for well-formedness semantic specifications, the Meta-S Calculus is
turning out to hold its own in that area via predication (as already
mentioned by several others on this list) and named back referencing
via tries. I have just finished a paper on it that I'll be submitting
for peer-reviewed soon. If anyone has a hard-core interest in this
topic, I'm open to forwarding a pre-print as PDF via email upon
request, on the understanding that it doesn't make it into the wild.

Some Theoretical and Practical Results in Context-Sensitive and
Adaptive Parsing
Quinn Tyler Jackson


We introduce a fifth language accepting machine called the PDA-T,
demonstrate some of its interesting formal properties, and show its
role in the §-Calculus . Based upon this new machine and the
§-Calculus’ other properties, we demonstrate the §-Calculus’ formal
Turing Power, and then propose a formal language classification (the
§-Hierarchy), derived largely from the Chomsky Hierarchy, but with a
fifth class of language accepted by the PDA-T. We show that this
modified hierarchy yields several conceptual benefits over the
standard four machine Chomsky Hierarchy. We also provide some
practical examples of the use of §-grammars in context-sensitive and
semantic parsing. Keywords: context-sensitive parsing, adaptive
gram-mars, §-Calculus, push down automata, predicated parsing, Chomsky

Quinn Tyler Jackson

Post a followup to this message

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