Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!usc!apple!fox!portal!cup.portal.com!pgl
From: pgl@cup.portal.com (Peter G Ludemann)
Newsgroups: comp.lang.prolog
Subject: Ambiguities in WG17's syntax
Message-ID: <24702@cup.portal.com>
Date: 4 Dec 89 03:03:04 GMT
Organization: The Portal System (TM)
Lines: 60

A Prolog standard must be unambiguous in three respects:
- syntax
- semantics of the syntax
- semantics of the built-in predicates ("BIPs").

I wish to discuss some aspects of the syntax.  Unambiguous
syntax is much easier to define than unambiguous semantics, so
once that is resolved, we can move on to more difficult items.

In an earlier article, I said that I had tried to make an LR(k)
grammar for Prolog.  Richard O'Keefe said that no programming
language is LR(k).  Of course, Algol-60, C, Pascal, etc. are
not LR(k) or even context-free.  Like all computer languages,
they are context-sensitive.  But they can easily be made
context-free by adding a bit of intelligence to the lexical
analyzer.  And the same can be done for Prolog.

  [No sane person would attempt to make an LR(k) parser for
  Prolog -- the job is much better done with operator precedence
  (which are a subset of LR(k) languages).  But I don't trust
  myself to check out a grammar for ambiguity by hand -- I like
  to have an algorithm check it out.  LR(k) is the most general
  parser generator I have.  And I can easily construct a subset
  of Prolog grammar, say with precedence 1200, 1000, 700 and 500
  operators, and use that to verify the non-ambiguity.]

If I were starting a new Prolog implementation, I would very
much want a precise, formal definition of Prolog syntax.  So
far, I have not seen one -- what I have seen are all ambiguous
with some words added which still don't clear up all the
ambiguities.  [Yes, Richard, I have implemented a Prolog parser
or two -- in Prolog and in C.  It's not hard -- but it is hard
to verify exactly what grammar the parser accepts.]

In particular, the following potentially ambiguous situations
are not mentioned in N40.  Assume that `p', `l', `r' and `s'
are prefix (fy), left-to-right (yfx), right-to-left (xfy) and
suffix operators (yf), all of the same priority (less than
1000).  Here are the interesting cases, not covered by any of
the grammars which I have seen.  [I have tried these out on a
variety of Prologs and they have given differing answers,
including "syntax error" for some of them]:

p a l b      p a r b
a l b s      a r b s
p a s
a l b r c    a r b l c
a l p b      a l b s

I don't see an intuitive parse for any of these and I therefore
propose that all of them be forbidden in the Standard.  [For
example, if Edinburgh had prefix `-' and infix `-' at the same
priority, the term `- a - b' would parse in a non-obvious way,
as '-'(a-b).]


- Peter Ludemann      pgl@cup.portal.com
                      ...!sun!portal!cup!pgl

   --- my opinions are my sole responsibility, of course ---