Path: utzoo!attcan!uunet!lll-winken!csd4.milw.wisc.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!ucsd!rutgers!okstate!norman
From: norman@a.cs.okstate.edu (Norman Graham)
Newsgroups: comp.lang.misc
Subject: Re: Language Design
Summary: Context-free gramars can be ambigous
Message-ID: <4511@okstate.UUCP>
Date: 22 Mar 89 07:07:53 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <8903172225.AA05088@explorer.dgp.toronto.edu>
Organization: Oklahoma State Univ., Stillwater
Lines: 54



From article <8903172225.AA05088@explorer.dgp.toronto.edu>, by flaps@dgp.toronto.edu (Alan J Rosenthal):
> 
> 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.
> 
> [Stuff deleted about ambiguous derivation sequence.]
> 
> It's ambiguous unless you use non-context-free information to tell you whether
> or not "x" was previously declared via typedef.

I have to agree with Bob on this one, but for a different reason.
The grammar in the back of K&R certainly is context-free... but it
is also ambiguous.  To paraphrase Aho & Ullman's "The Theory of 
Parsing, Translation, and Compiling, Volume I: Parsing", page 91:

    A grammar is Context-free if every production has a single
    nonterminal on the left and a sequence of 0 or more terminals
    or nonterminals on the right.

It is obvious that the grammars in both editions of K&R fit this 
description.  Thus they are context-free.

Now on to ambiguity. According to Aho & Ullman (same as above), pagee 143: 

    We say that a CFG G is ambiguous if there is at least one sentence
    w in L(G) for which there is more than one distinct derivation tree
    with frontier w.  This is equivalent to saying that G is ambiguous
    if there is a sentence w in L(G) with two or more distinct leftmost
    (or rightmost) derivations.

The classic example of ambiguity is the "dangling else" problem, as
illustrated by the grammars in both editions of K&R.

So we see that K&R's grammars are ambigous context-free grammars. That's
no big deal--the ambiguity doesn't affect the language generated by the
grammar.  The problem comes in when compilers base the semantic meaning
of a sentence on the derivation sequence the grammar uses to generate
that sentence.  For some reason :-) compiler writers like to choose
deterministically between competing derivation sequences.  Thus they
either statically choose the proper derivation sequence (eg. the "else"
always matches the last else-less "if") or they use run-time information
to help them choose the "proper" derivation sequence.

-- 
Norman Graham                            Oklahoma State University
  Internet:  norman@a.cs.okstate.edu     Computing and Information Sciences
      UUCP:  {cbosgd, ihnp4,             219 Mathematical Sciences Building
              rutgers}!okstate!norman    Stillwater, OK  74078-0599