Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.compilers > #2767

Re: Why are ambiguous grammars usually a bad idea? Why are languages usually defined and implemented with ambiguous grammars?

Show all headers | View raw

Roger L Costello <costello@mitre.org> writes:
>Question: Beyond the fact that bison doesn't like them, why are ambiguous
>grammars usually bad?

An ambiguous grammar means that the same input can be parsed in at
least two different ways.  In many cases the two different ways have
different meanings.

The classical example is the dangling else.  In EBNF:

S -> if E then S [ else S ]

if you see

if E then if E then S else S

which if does the else belong to?  The two parses usually have very
different meanings.

>My answer: Ambiguous grammars make it hard for users of the grammar to write
>correct instances of the grammar. Stated another way, ambiguous grammars make
>it easy to introduce errors into instances of the grammar.

Sounds wrong to me.  The if-Statement above is a correct Pascal
statement (apart from the unexpanded Es and Ss) and not erroneous (and
likewise for other languages with similar syntaxes, e.g., Algol 60 and C).

Of course, one way to deal with ambiguities would be to make the input
a syntax error, but that's usually not done (and I know of no parser
generator that supports this approach).

>Question: Opine about why languages are usually defined and implemented with
>ambiguous grammars.
>
>My answer: Writing a grammar that completely avoids ambiguities might result
>in a grammar that is nightmarishly complex. It is easier/better to create a
>simple grammar and then add rules/descriptions which explain and resolve the
>ambiguities.

Writing the grammar above in an unambiguous way to match up the else
with the closest unresolved if is more complex, but not nightmarishly
complex.  But the better solution was used in Modula-2: require an
ending for if:

S -> if E then S [ else S ] end

[Modula-2 also uses a Statement-Sequence instead of a Statement in the
then-branch and else-branch, avoiding the need for begin...end.]

This grammar is unambiguous and the programmer can write either of

if E then if E then S     else S end end
if E then if E then S end else S     end

depending on what is intended.

Hmm, makes me wonder where that style comes from; Lisp has had a
closed COND from the beginning (i.e., 1960), Forth also had a closed
IF from early on (i.e., early 1970s), but I guess neither of those
inspired Wirth when he did Modula-2.  Dijkstra's guarded command
language (which closed the if with fi) was published in 1975, and
maybe that was the inspiration, but OTOH, the Modula-2 if syntax was
already present in Modula, developed 1975, report in March 1976
<https://www.research-collection.ethz.ch/handle/20.500.11850/68669>.
Wirth writes in his HOPL-III paper:

|In planning Modula-2, I saw it as a new version of Pascal, updated to
|the requirements of the time, and I seized the opportunity to correct
|various mistakes in Pascal’s design, such as, for example, the
|syntactic anomaly of the dangling “else”

but he does not give any background on where the new syntax is coming
from.

I recommend to my students to get rid of conflicts, because the
default resolution of the conflict by Bison may be other than what is
required.  But I also design the language they have to implement such
that not having conflicts is not too hard; e.g., I give them
Modula-2-like rather than Algol-like syntax to implement.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[Algol68 had if ... then ... else .. fi in 1968. -John]

Back to comp.compilers | Previous | Next | Find similar

Thread

Re: Why are ambiguous grammars usually a bad idea? Why are languages usually defined and implemented with ambiguous grammars? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2021-12-27 09:49 +0000

csiph-web