Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: Are compiler developers light-years ahead of other software development?
Date: Sat, 22 Jan 2022 09:34:58 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 107
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-01-086@comp.compilers>
References: <22-01-077@comp.compilers> <22-01-079@comp.compilers> <22-01-082@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="56364"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, theory, comment
Posted-Date: 22 Jan 2022 10:51:42 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:2854


gah4 <gah4@u.washington.edu> writes:
>On Friday, January 21, 2022 at 2:30:42 PM UTC-8, Anton Ertl wrote:
>> You need to know quite a bit about the implementation technique behind
>> it to understand what (for LR-based parser generators) a shift-reduce
>> or reduce-reduce conflict means and how to fix that problem.
>
>Interesting reason, as I know exactly how I learned about that.
>(And not from compiler class, where I might have.)
>
>In compiling a program, not actually changing it, the instructions warn
>that it will get a shift-reduce conflict warning, and to ignore it.

That means that the program's authors have (hopefully) determined that
the default resolution (shift) for the shift/reduce conflicts in that
program was what they intended.  It does not tell you that shift
resulution is the intended behaviour for all cases (otherwise there
would be no point in reporting the conflict).

>There is a whole separate thread on ambiguous languages, which is
>where these come from. In a language with an if-then-optional else
>construct, and which can be nested, there is an ambiguity in which
>if an else belongs to.  In most such languages it goes to the nearest
>(deepest nesting) if, and this is the default from the warning.

That's not the only occurence of shift/reduce conflicts, but it's a
relatively prominent one, because many compiler writers leave it to
the parser generator to resolve it.  However, when developing a
grammar, I have seen cases (even for relatively small languages) with
many conflicts (both shift/reduce and reduce/reduce).  I always change
the grammar to eliminate all the conflicts.  Often the syntax is
changed by these changes, which is outside the scope of pure compiler
writers, but inside the scope of language designers.

Concerning the Algol 60 case, the syntax is unambiguous (from
<https://www.masswerk.at/algol60/report.htm>):

|<if clause> ::= if <Boolean expression> then
|<unconditional statement> ::= <basic statement> |
|        <compound statement> | <block>
|<if statement> ::= <if clause> <unconditional statement>
|<conditional statement> ::= <if statement> |
|        <if statement> else <statement> |
|        <if clause> <for statement> |
|        <label>: <conditional statement>

Statements such as

if B1 then if B2 then S1 else S1

and even

if B1 then if B2 then S1

are syntax errors.  You cannot put an if-statement or a conditional
statement in a then-branch without wrapping it in a begin...end.

Languages like Pascal and C (and its descendants) changed this to
allow either, making the grammar ambiguous, and using prose to resolve
the ambiguity.  E.g., for Pascal:

|IfStatement = "if" BooleanExpression "then" Statement [ "else" Statement ].
|
|Note: The syntactic ambiguity arising from the construct
|
|if e1 then if e2 then sl else s2
|
|is resolved by interpreting the construct as equivalent to
|
|if e1 then begin if e2 then sl else s2 end

I consider either grammar to be flawed; Algol fixed the flaw in Algol
68, Wirth fixed it in Modula, but the C-syntax descendants have
unfortunately never fixed it.

<https://en.wikipedia.org/wiki/Dangling_else#Avoiding_the_conflict_in_LR_parsers>
describes how to express the intent in the grammar rather than in
prose, but looking at the example grammars makes it clear why compiler
writers prefer to rely on the parser-generator resolution of the
shift/reduce conflict rather than expressing the intent in the
grammar.

Yacc has precedence and associativity declarations to provide
additional information to the parser generator on how to resolve
ambiguity in the BNF (and for suppressing the warnings about conflicts
that are resolved by these declarations).  Something like this might
be a good solution for dealing with the dangling else if you cannot
avoid it by fixing the syntax.

>reduce-reduce results from an actual mistake in the language,
>and does need to be fixed.

There can be cases where the default behaviour is the intended
behaviour, too, but IIRC the default depends on the order of rules, so
could be destroyed by a seemingly innocuous change to the parser
generator input.  And there are (probably many) cases where either
reduction is intended in some cases, so the generator default is wrong
for some cases for all rule orders.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[The original sin of dangling else may have been COBOL.  A 1964 IBM
manual for 7080 COBOL says ELSE matches the closest IF. PL/I inherited
it shortly aftrwards.  -John]