Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-winken!claris!hearn
From: hearn@claris.com (Bob Hearn)
Newsgroups: comp.lang.misc
Subject: Re: Language Design
Message-ID: <9122@claris.com>
Date: 21 Mar 89 00:51:46 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <9091@claris.com> <8903172225.AA05088@explorer.dgp.toronto.edu>
Reply-To: hearn@claris.com (Bob Hearn)
Organization: Claris Corporation, Mountain View CA
Lines: 53

In article <8903172225.AA05088@explorer.dgp.toronto.edu> flaps@dgp.toronto.edu (Alan J Rosenthal) writes:
>
>In article <9091@claris.com> hearn@claris.com (Bob Hearn) writes:
>>Well, the *grammar* defining C programs is certainly context-free!  Just
>>look in the back of K&R.
>
>I'm looking in the back of K&R (first edition), and if I'm not mistaken I'm
>seeing context-sensitive stuff in the grammar.
>
>Suppose you're looking at a compound-statement and you've just seen the `{'
>opening it.  Now suppose the next three tokens are `extern', "x", and `;'.
>This is produced by a declaration-list, expanding to declaration, which expands
>to decl-specifiers init-declarator-list[opt] ;.  `extern' is an sc-specifier,
>and decl-specifiers -> sc-specifier decl_specifiers[opt].  Now is "x" a
>declarator (init-declarator-list -> init-declarator -> declarator ->
>identifier) or a typedef-name (decl-specifiers -> type-specifier ->
>typedef-name -> identifier)?
>
>It's ambiguous unless you use non-context-free information to tell you whether
>or not "x" was previously declared via typedef.
>
>ajr
>

Enough of this bullshit!  How many times do I have to say it???  The grammar
in K&R is context-free.  Do you know what a context-free grammar *is*?  You're
confusing the *class* of the grammar (ever heard of the Chomsky hierarchy?)
with what categories of parsers will work on it.  You're also confusing
*syntactic correctness* with *semantic correctness*.  This is a little more
acceptable, since, as I was saying, most compilers do to make parsing
easier.

Most C compilers use LALR(1) parsers (stands for "look-ahead left to right,
order 1), which are a subcategory of shift-reduce parsers.  The 1 means they
can look at the next 1 token on the input stream when deciding whether to
shift or reduce.  And you are quite correct in saying that, in this case,
that one token is not enough; you *do* need symbol table information.  But
(1) No one says all context-free grammars have to be LALR(1) parsable
without context information, (2) no one says that the grammar in the back of
K&R is necessarily the one that's used in practice (grammars are often
tweaked (without modifying the language generated!) no make them easier to
parse), and (3) just because your compiler gives you a syntax error when
you do something like that, that doesn't necessarily mean your program
is syntactically incorrect.  It just means that treating that kind of
semantic error as a syntax error makes the language easier to parse.

Now, before anyone else wants to tell me that K&R's grammar for C is not
context-free, will you *please* go and look up the definition of context-free
grammar???  Hint: anything that can be expressed in BNF is context-free!!

Bob Hearn
hearn@claris.com