Re: "dangling else" in SDF

[Paul.Klint@cwi.nl (Paul Klint)]

Manuel Vilares writes:

=>We work with CENTAUR version 1.1 and we have tried to implement the
=>"dangling else" using your formalism SDF version 1.9. In particular we
=>have described a small language "If" as follows:
=>
=>------------------------------------
=>
=>module If
=> 
=>sorts ID STAT
=> 
=>lexical syntax
=> 
=>[a-z]+                     -> ID
=>[ \n]                      -> LAYOUT
=> 
=>context-free syntax
=> 
=>if ID then STAT            -> STAT
=>if ID then STAT else STAT  -> STAT
=>stat                       -> STAT
=>
=>------------------------------------
=>
=>which presents an evident shift-reduce conflict, but when we try to
=>analyze the following input 
=>
=>------------------------------------
=>
=>if a then if b then if c then stat else stat else stat
=>
=>------------------------------------
=>
=>there is not such a conflict ?????????. In relation to this, we have
=>two questions:
=>
=>    1. What is the reason, if you use an LR(0) automaton ?
=>    2. How can I do to implement the "dangling else" ?

Question 1: Why is no shift-reduce conflict reported?
=====================================================

The technology used in the SDF implementation is based on Generalized
LR parsing: the parse tables are build in a standard fashion *but*
these tables may contain shift/reduce or reduce/reduce conflicts.
Instead of eliminating these in some ad hoc way (as, for instance,
yacc does) we keep the conflict in the table and create at parse-time
*two* parsers each pursuing one of the alternatives. A clever
implementation takes care of merging parsers again as soon as possible
and of maximal sharing of parse trees.

By doing so we are able to parse arbitrary context-free languages like
languages requiring arbitrarily large look ahead or ambiguous
languages like the one in your example.

For further details of the techniques used I refer you to:

	J. Heering, P. Klint, J. Rekers
	Incremental Generation of Parsers
	IEEE Transaction on Software Engineering,
	16(12):1344-1351, 1990.

or to
	J. Rekers,
	Parser generation for interactive environments,
	Dissertation, Programming Research Group,
	University of Amsterdam, 1992.

Question 2: How can I do to implement the "dangling else" ?
===========================================================

I assume that you have the ASF+SDF Meta-environment running
(see the User's manual for details)

Create a new module If by first pressing the "add" button of
the top level window of the ASF+SDF Meta-environment and then type
in the following text in the top pane (= SDF part) of module If:

exports
  sorts ID STAT

  lexical syntax

  [a-z]+                     -> ID
  [ \n]                      -> LAYOUT

  context-free syntax

  if ID then STAT            -> STAT
  if ID then STAT else STAT  -> STAT
  stat                       -> STAT

(Note that there is no "module If" at the beginning and that the
keyword "exports" starts the definition.)

Clearly, this grammar is ambiguous and typing in the sentence:

	if a then if b then if c then stat else stat else stat
                  |         |            |         |         |
                  |         ----------1-------------         |
                  |                                |         |
                  --------------------2----------------------

Gives rise to two dialogues with the Disambiguator: one for each
of the possible ambiguities labelled 1 and 2 above.

In order to disambiguate this grammar you should add a priority
declaration that favors either the if-then or the if-then-else
rule. For instance, adding:

  priorities	
    if ID then STAT -> STAT < if ID then STAT else STAT -> STAT

defines if-then-else as rule with the highest priority which should
appear as low as possible in the tree (compare the arithmetic
operators + and * where * has higher priority than +). This gives the
standard interpretation of this grammar where the else is associated
with the innermost unclosed if:

	if a then if b then if c then stat else stat else stat
                            ------------------------
                  --------------------------------------------
        ------------------------------------------------------

The other possible priority declaration

  priorities	
    if ID then STAT -> STAT < if ID then STAT else STAT -> STAT

yields

	if a then if b then if c then stat else stat else stat
                            --------------
                  ----------------------------------
        ------------------------------------------------------


I hope this answers your questions!

Paul Klint