RE: Separation of Syntax and Semantics (was language design for parsing)

John said:


> [You can't separate syntax and semantics. Back when I was doing a
> logic and computability seminar in the math department in college, one
> of the things we proved was that anything you can define semantically
> you can in principle put into the syntax (perhaps with severe bloat,
> which mathematicians don't care about) and vice-versa. So here in
> computerland the question is really what's easier to understand and to
> maintain when you're drawing the line. -John]


Yes. There are various Turing powerful formalisms (and some
less-than-TP ones) that are nonetheless intractable for use as
semantic checkers on programming languages. van Wijngaarden grammars
come to mind. Greibach tried to put some restrictions on W-grammars in
an attempt to make them more approachable without losing too much
power, but that didn't seem to spawn much work (someone out there may
correct me on that).


Right now in my literature search I'm finding some interesting
extensions/alternatives to pushdown automata that were explored in the
late 60's, some for this purpose: stack automata and one-way stack
automata (Ginsburg, Greibach, et al.), nested stack automata (Aho),
and balloon automata (Hopcroft & Ullman). Although these appear not to
have made it past the early 70's, someone out there may correct me on
that.


Other approaches were also tried, in affix grammars, attribute
grammars, et cetera. It's perhaps some kind of dyslexia on my part
that I find those families too opaque for my limited mind to grok
sufficiently.


Recent work by Okhotin (various papers, and his PhD dissertation)
focuses on a grammar-only specification of a small programming
language, using Boolean grammars.


I've resorted to something akin to George Miller's "Rule of 7 +/-
2". If dealing with some semantic construction in the grammar requires
less than 7 (+/- 2) productions, I deal with it in the grammar. If
more, I allow myself to deal with it in the code. Anything more than
Miller's magic number becomes difficult to follow, even with a visual
tool.


--
Chev. Quinn Tyler Jackson
http://members.shaw.ca/qjackson/

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