Note: I've just migrated to a different physical server to run Spivey's Corner,
with a new architecture, a new operating system, a new version of PHP, and an updated version of MediaWiki.
Please let me know if anything needs adjustment! – Mike

How to use yacc to test for ambiguity: Difference between revisions

From Compilers
Jump to navigation Jump to search
No edit summary
No edit summary
Line 35: Line 35:


  2 IF 4 expr 8 THEN 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 IF 4 expr 8 THEN 9 inner 11 | ELSE BASIC
  2 IF 4 expr 8 THEN 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 IF 4 expr 8 THEN 9 inner 11 | ELSE BASIC
reduce
reduce                                                                     -----
                                                      12 IF 4 expr 8 THEN 9 stmt 10  | ELSE BASIC
                                                  ... 12 IF 4 expr 8 THEN 9 stmt 10  | ELSE BASIC
reduce
reduce                                                   -----------------------
                    9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
                ... 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce
reduce               ----------------------------------------
                    9 inner 11
                ... 9 inner 11
shift, shift, reduce, reduce
shift, shift, reduce, reduce
  2 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
  2 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce
reduce -----------------------------------
  2 inner 6
  2 inner 6
reduce
reduce
  2 stmt 5
  2 stmt 5
accept
accept


  2 IF 4 expr 8 THEN 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 IF 4 expr 8 THEN 9 inner 11 | ELSE BASIC
  2 IF 4 expr 8 THEN 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 IF 4 expr 8 THEN 9 inner 11 | ELSE BASIC
shift, shift, reduce, reduce
shift, shift, reduce, reduce
                                                      12 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
                                                  ... 12 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce
reduce                                                   ----------------------------------------
                                                      12 inner 6
                                                  ... 12 inner 6
reduce
reduce                                                   -----
                    9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
                ... 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce
reduce               ----------------------------------------
                    9 inner 11
                ... 9 inner 11
reduce
reduce               -----
  2 IF 4 expr 8 THEN 9 stmt 10
  2 IF 4 expr 8 THEN 9 stmt 10
reduce
reduce ------------------
  2 stmt 5
  2 stmt 5
accept
accept
<pre>
<pre>
%token BASIC EXPR IF THEN ELSE
%token BASIC EXPR IF THEN ELSE

Revision as of 07:52, 27 October 2021

[To be continued]

There is no algorithm that decides definitively whether a given context free grammar is ambiguous, but that does not prevent us from using yacc pragmatically. If we submit a grammar (unannotated with precedence declarations) to yacc, and yacc accepts it, then we know the grammar is in the class LALR(1), and all such grammars are unambiguous. If yacc says No and reports parsing conflicts, then either the grammar is ambiguous, or it is unambiguous, but "too difficult" for yacc to handle. In the latter case, we can look at yacc's diagnostic output and use it to find a situation where a conflict is encountered: that can help us to find a string that can be derived in more than one way.

Consider, for example, the following interesting grammar provided by Matteo Cati. It purports to be an unambiguous grammar for the classic Algol--60 dangling else problem.

stmt : inner
  | IF expr THEN stmt

inner : BASIC
  | IF expr THEN inner ELSE stmt

In order to submit this to yacc, we must surround it with some apparatus declaring various tokens, and supply semantic actions, all of which can be written as the trivial unit expression {()}. A complete input is shown towards the end of this note. Invoking ocamlyacc with

$ ocamlyacc -v cati.mly

produces the error message

1 shift/reduce conflict

and also (because of the -v flag) a report file cati.output that gives details of parsing automaton ocamlyacc compiled, and where it discovered the conflict. In what follows, I've used (because why wouldn't I?) the output of my own yacc variant, but the output of ocamlyacc is equivalent, even if the states are numbered differently. The whole of the report file is shown at the end of this note.

Examining the report, we see the conflict occurs in state 11:

State 11: shift/reduce conflict (shift 12, reduce 1) on ELSE

State 11
	inner --> IF expr THEN inner . ELSE stmt  (4)
	stmt --> inner .  (1)

	EOF  reduce 1
	ELSE  shift 12

If the machine reaches state 11 and the lookahead is ELSE, then the machine cannot decide between shifting the ELSE (in the hope of reducing with the production inner --> IF expr THEN inner ELSE stmt), or reducing immediately with the production stmt --> inner (presumably so that it can then reduce with stmt -> IF expr THEN stmt).


IF expr THEN IF expr THEN inner ELSE IF expr THEN inner | ELSE BASIC
2 IF 4 expr 8 THEN 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 IF 4 expr 8 THEN 9 inner 11 | ELSE BASIC
reduce                                                                      -----
                                                  ... 12 IF 4 expr 8 THEN 9 stmt 10  | ELSE BASIC
reduce                                                   -----------------------
               ... 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce               ----------------------------------------
               ... 9 inner 11
shift, shift, reduce, reduce
2 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce -----------------------------------
2 inner 6
reduce
2 stmt 5
accept
2 IF 4 expr 8 THEN 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 IF 4 expr 8 THEN 9 inner 11 | ELSE BASIC
shift, shift, reduce, reduce
                                                  ... 12 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce                                                   ----------------------------------------
                                                  ... 12 inner 6
reduce                                                   -----
               ... 9 IF 4 expr 8 THEN 9 inner 11 ELSE 12 stmt 13
reduce               ----------------------------------------
               ... 9 inner 11
reduce               -----
2 IF 4 expr 8 THEN 9 stmt 10
reduce ------------------
2 stmt 5
accept
%token BASIC EXPR IF THEN ELSE

%type<unit> stmt

%start stmt

%%

stmt : inner {()}
  | IF expr THEN stmt {()} ;

inner : BASIC {()}
  | IF expr THEN inner ELSE stmt {()} ;

expr : EXPR {()} ;