Parsing an If...End If construct

I'm attempting to create a compiler for an old flavor of BASIC called
AMOS.  The grammar of this language uses the IF...THEN...ELSE
construct but also specifies an alternative IF construct called
IF...END IF.

There are 4 forms:

IF condition statements END IF
IF condition statements ELSE statements END IF
IF condition statements ELSE IF statements ... END IF
IF condition statements ELSE IF statements ... ELSE statements END IF

So that something like could be written:

If X=10
Print "Ten"
Else If X=20
Print "Twenty"
Else If X=30
Print "Thirty"
Else
End
End If

The bison grammar I have so far is listed below.  It is has several
conflicts that I'm having trouble resolving.  Can anyone give me some
pointers on how to deconflict this grammar?

Thanks,
Mike



%token NEWLINE LABEL LINE_NUMBER COLON
%token END GOSUB GOTO PRINT RETURN
%token IF THEN ELSE

%nonassoc ELSE
%nonassoc COLON


program : lines
| /* empty */
;

lines : lines line
| line
;

line : label statements NEWLINE
;

label : LABEL
| LINE_NUMBER
| /* empty */
;

destination : LABEL
| LINE_NUMBER
;

statements : statements COLON statement
| statement
| /* empty */
;

statement : instruction
;

instruction : END
| GOSUB destination
| GOTO destination
| IF conditions THEN statements	opt_else
| IF conditions statements else_if_list opt_else END IF
| PRINT print_list
| RETURN
;

else_if_list : else_if_list else_if
| else_if
;

else_if : ELSE IF conditions statements
| /* empty */
;

opt_else : ELSE statements
| /* empty */
;

Michael wrote:
> The bison grammar I have so far is listed below.  It is has several
> conflicts that I'm having trouble resolving.  Can anyone give me some
> pointers on how to deconflict this grammar?
>[...]
> instruction : END
> 	| GOSUB destination
> 	| GOTO destination
> 	| IF conditions THEN statements	opt_else
> 	| IF conditions statements else_if_list opt_else END IF
> 	| PRINT print_list
> 	| RETURN
> 	;
>
> else_if_list : else_if_list else_if
> 	| else_if
> 	;
>
> else_if : ELSE IF conditions statements
> 	| /* empty */
> 	;
>
> opt_else : ELSE statements
> 	| /* empty */
> 	;

A few obvious problems.  The END IF and ELSE IF are ambiguous beyond 1
token of lookahead.  You can fix this by disambiguating in the
scanner, producing ELSEIF and ENDIF tokens.  Second problem is that
you are burying the optional else_if_list too deep.

Rewrite your grammar like this:

instruction: END
| GOSUB destination
| GOTO destination
| IF conditions THEN statements opt_else
| IF conditions THEN statements opt_else_if_list opt_else ENDIF
| PRINT print_list
| RETURN
;

opt_else_if_list: /* empty */ | else_if_list;

else_if_list: else_if
| else_if_list else if
;

else_if: ELSEIF conditions statement;

opt_else: /* empty */ | ELSE statements;

You will have 2 shift/reduce conflicts left:
1. the classic if/then/else conflict
2. the BASIC classic colon conflict

both of which you want to shift so it is OK if you leave them alone.

--
Scott Nicol
snicol@apk.net

mness1978@hotmail.com (Michael) schreibt:

>If X=10
>   Print "Ten"
>Else If X=20
>   Print "Twenty"
>Else If X=30
>   Print "Thirty"
>Else
>   End ' <-------- are you sure that this is acceptable???
>End If

Perhaps you misunderstood the "End" token as a statement?
At least I'd try to treat "End" as a special keyword, distinct from statemen
ts.

And I'd also try to convert "End If" into a single token, different from bot
h
"End" and "If". AFAIR typical Basic byte code uses a single token herefore,
that's only displayed with a space inside the keyword.

IMO you also should handle NEWLINE appropriately. In Basic syntax the line e
nds
almost are significant parts of the syntax, serving e.g. as statement
separators. In your grammar a NEWLINE is not allowed within "statements", so
that an "Else" would be illegal at the begin of a line. I'd define an
statement_separator as either ":", or as NEWLINE possibly followed by an lab
el.

All in all I'd implement an handcrafted lexer and parser for Basic, which
allows to handle the special conditions in a Basic syntax easier than with
general lexer/parser generators. I'd also look at the source code of an open
source Basic interpreter, in order to find out more about the Basic grammar,
lexers and parsers.

DoDi

Michael wrote:
> The bison grammar I have so far is listed below.  It is has several
> conflicts that I'm having trouble resolving.  Can anyone give me some
> pointers on how to deconflict this grammar?
>[...]
> else_if_list : else_if_list else_if
> 	| else_if
> 	;
>
> else_if : ELSE IF conditions statements
> 	| /* empty */
> 	;

I just want to amplify one of the points made by Scott Nicol as it
points out a common error many grammar writers make when writing
recursive/optional productions.  Scott wrote:

> Second problem is that you are burying the optional else_if_list too
> deep.

The two productions I clipped from your grammar are typical of the
problem, and it is a commen grammar writing mistake.  The mistake is
making lists of "optional" things.  Your else_if non-terminal
describes something optional, which means it has an empty clause
(indicating that the item is not present).  Your else_if_list makes a
list of these things.  However, that introduces the problem.  How does
the parser know how many "empty" versions of the else_if to insert in
the list?  Theoretically, it can insert an unbounded number of them.
that makes the grammar inherently ambiguous.

The solution to this kind of problem, is to raise the "empty" up in
the rule nesting.  That is, don't make empty an alternative for
else_if, make the rules (in your case you have only 1) that use
else_if take care of its absence.

else_if : ELSE IF conditions statements; // else_if is not optional by itsel
f

else_if_list : else_if_list else_if
| /* empty */ // an else_if_list can be empty
;

Now, if this isn't sufficient to resolve the problem, try moving the
empty up yet another level.

else_if_list : else_if_list else_if
| else_if // an else_if_list is not optional by itself
;

instruction: END
| GOSUB destination
| GOTO destination
| IF conditions THEN statements opt_else
| IF conditions THEN statements else_if_list opt_else ENDIF // non-empty els
e_fi_list case
| IF conditions THEN statements opt_else ENDIF // empty else_if_list case
| PRINT print_list
| RETURN
;

This now brings us to the next point.  Two things which can go to
empty in a row may also cause conflicts.  In your grammar, you have an
option else_if_list followed by an otional opt_else.  That can be the
source of conflicts also, as sometimes the parser has a hard time
disambiuating whether one or both of the optional things are missing.
I don't think that's a problem with this grammar, but I haven't run
the grammar through a parser generator to be sure.  However, the point
is worth covering, since one resolves it with the same empty-raising
technique.

Change:

opt_else: ELSE statements
| /* empty */
;


else: ELSE statements;

instruction: END
| GOSUB destination
| GOTO destination
| IF conditions THEN statements else // else present
| IF conditions THEN statements // else missing
| IF conditions THEN statements else_if_list else ENDIF // non-empty else_fi
_list case, else present
| IF conditions THEN statements else_if_list ENDIF // non-empty else_fi_list
 case, else missing
| IF conditions THEN statements else ENDIF // empty else_if_list case, else 
present
| IF conditions THEN statements ENDIF // empty else_if_list case, else missi
ng
| PRINT print_list
| RETURN
;

However, now having expanded this grammar to this point, I see a
potential problem.  Both the else and else_if_list rules begin with
ELSE as their first token and the else_if_list rule would like to loop
(recurse) on seeing an ELSE, and that will be a shift-reduce conflict
that really indicates the need for two tokens of lookahead.  That kind
of problem requires a slightly different technique to correct.  One
needs to "fold" the trailing else clase into the else_if_list.  BTW,
to do that one must make the list right recursive rather than left,
because the special case occurs at the left end of the list and not
the right.

else_if_list : else_if else_if_list
| else_if // an else_if_list is not optional by itself
| else // an else if list an also end with an else clause
;

instruction: END
| GOSUB destination
| GOTO destination
| IF conditions THEN statements else // else present
| IF conditions THEN statements // else missing
| IF conditions THEN statements else_if_list ENDIF // non-empty else_fi_list
 case
| IF conditions THEN statements ENDIF // empty else_if_list case
| PRINT print_list
| RETURN
;

Soapbox warning: the following comments are simply my personal opinion
on the matter, and some may find them to be "marketing propaganda".

I find the use of recursion and empty productions to be totally opaque
for this prupose.  It is very hard to write grammars that use
recursion and empty productions and not to introduce conflicts.  It is
simply too easy to introduce these naive mistakes.

There is a better solution, ELR (aka regular-right-part) grammars.
These are grammars where one uses the regular expression operators
*,+,? to write optional items and lists.  If one uses these operators
in place of recurive rules with empty alternatives, then one naturally
writes grammars that have fewer conflict problems.  Here is a Yacc++
fragment for the problem rules.

instruction: END
| GOSUB destination
| GOTO destination
| IF conditions THEN statements else?
| IF conditions THEN statements else_if* else? ENDIF
| PRINT print_list
| RETURN
;

And here is what I would have naively written (simply because I
wouldn't have started with an "else" or "else_if" non-terminal until I
saw they made the semantics easier):

| IF conditions THEN statements (ELSE statements)?
| IF conditions THEN statements (ELSE IF conditions statements)*
(ELSE statements)? ENDIF

Hope this helps,
-Chris

 ****************************************
************************************
*
Chris Clark                    Internet   :  compres@world.std.com
Compiler Resources, Inc.       Web Site   :  http://world.std.com/~compres
23 Bailey Rd                   voice      :  (508) 435-5016
Berlin, MA  01503  USA         fax        :  (978) 838-0263  (24 hours)