Grammars and structure.

10 Jan 86 15:46:00 GMT

          From comp.compilers

Related articles
Grammars and structure. compilers@ima.UUCP (1986-01-10)
| List of all articles for this month |

From: compilers@ima.UUCP
Newsgroups: mod.compilers
Date: 10 Jan 86 15:46:00 GMT
Article-I.D.: ima.136300044
Posted: Fri Jan 10 10:46:00 1986
Date-Received: 12 Jan 86 13:52:49 GMT

[from harvard!uwvax!uwmacc!ejnorman (Eric Norman)]

In article <136300033@ima.UUCP> you (stan shebs) challenge:
> Can anyone refute my gut feeling that attribute grammars are a kludge?
> I've never found a really solid justification for their existence...
I can't refute it, but I'll say something about it. What attribute
grammars (or any other grammars) do is to impose a structure on a
bunch of characters; i.e. the bunch of characters gets organized
(structured) into expressions, terms, factors, and so forth. For
many purposes, this structure is useful. For many purposes,
communication among components of such a structure needs to take place
between "immediate neighbors", e.g. type inference. For this purpose,
attribute grammars seem to work well.

However, there are cases where the communication needs to take place
between more distant components. If you don't believe this, then
explain the motivation for the paper "Dynamically Bypassing Copy Rule
Chains in Attribute Grammars" by Roger Hoover in the upcoming POPL
conference. For such long-haul communication among components of a
structure, attribute grammars need to be hacked up in some way to get
the message through.

My main point though, is that grammars impose ONE KIND of structure
on the bunch of characters. There are other kinds of structure that
could be imposed that we sometimes care about. For instance, for
data flow analysis we care about the "who uses whom" and the "who
calls whom" structure. When we want to report the location of an
error, we care about the "line number" structure; e.g. the only
structure that we care that the program has is that it has bunches
of characters separated by newlines. To recover from malformed
begin-end pairs, we might want to pay attention to the indentation
structure. The list goes on. Which structure we impose on a program
depends on which details we care about and which details we want to
ignore. When we care about one of these other structures, and
especially when the other structure is not a homomorphism of the
structure imposed by the grammar, we have to resort to prestidigitation.
Eric Norman
UUCP: ...{allegra,ihnp4,seismo}!uwvax!uwmacc!ejnorman
Pony Express: 1210 West Dayton Street, Madison, WI 53706
Life: Detroit!Alexandria!Omaha!Indianapolis!Madison!Hyde

"Naw they ain't; I just happen to be in front."

Post a followup to this message

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