Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Kaz Kylheku <480-992-1380@kylheku.com>
Newsgroups: comp.compilers
Subject: Re: Why are ambiguous grammars usually a bad idea? Why are languages usually defined and implemented with ambiguous grammars?
Date: Thu, 30 Dec 2021 20:08:26 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 52
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <21-12-029@comp.compilers>
References: <21-12-003@comp.compilers> <21-12-017@comp.compilers> <21-12-020@comp.compilers> <21-12-025@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="78214"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, design
Posted-Date: 30 Dec 2021 15:37:26 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:2780

On 2021-12-30, Kaz Kylheku <480-992-1380@kylheku.com> wrote:
John> On the other hand, that C example isn't ambiguous, it's deliberately
John> indeterminate.

The C example isn't ambiguous in its parse, but the semantics is
ambiguous. Expressions can be evaluated in multiple orders in C,
and if we follow different orders for that expression, we get different
results (in such a way that it's deemed undefined).

Here is something merely unspecified:

  a() + b() + c()

Suppose a prints "a" to stdout, b prints "b" and c prints "c":

  int a() { putchar('a'); return 0; }

The behavior is not undefined, but unspecified: we don't know
which of six permutations is printed, but we know it's one of them:
abc, acb, bac, bca, cab, cba.

That's a kind of ambiguity in the language (syntax + semantics).

We know that the parse is

  (a() + b()) + c()

But the meaning requires that a, b and c are executed in order
to produce the operands to the + operator, the order in which
those calls take place is not specified.

That's a clear ambiguity.

Just like if I say "pick up the dry cleaning and fill up the gas
tank", there is no grammar ambiguity; yet we don't know whether
the sequencing is required, or whether the gas tank can be
filled first. The request describes multiple possible scenarios,
including going to gas station that does dry-cleaning, and
picking up while an attendant fills the tank.

> indeterminate.  Early Fortran allowed the compiler to compile any
> mathematically equivalent, not just numerically equivalent, version
> of an expression so A*B+A*C could turn into A*(B+C) which was great
> for optimizing, not so much for predictable results. -John]

Why wait for early Fortran to arrive? If you write in C, you can
use gcc -ffast-math (an umbrella option for turning on a whole lot
of stuff, among it -fassociative-math and -freciprocal-math).

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal