Re: Eliminating conflicts of parenthesized subexpressions

[Hans Aberg]

Actually, I found a way to resolve the problem, using a paper I wrote
myself :-) on "constrained grammars", that admits one to prohibit a choice
of rule expansions in a CFG, and then rewrite it to a new CFG. I will
briefly describe how I did it.

The original ambiguous grammar is as below, where M = metaformula, and F =
object_formula.

-- Original grammar ---
%token m
%token f

%token or_key "or"

%token comma_key ","

%left ","
%left "or"

%%

M: m;
M: M "," M;
M: "(" M ")";
M: F;

F: f | F "or" F | "(" F ")";

%%
--------------------------

The problem is that there are two expansions
    M -> "(" M ")" -> "(" F ")"
    M ->     F     -> "(" F ")"
Here, I only want to admit the second one. I thus want to prohibit the
expansion
    M -> F
in the M argument of the rule
    M -> "(" M ")"

The rewriting algorithm then says that every nonterminal that should be
constrained should be rewritten with new symbols, one for every left hand
side it appears in. In addition, every constrained right hand argument
should be given a new name. I then get:

-- First rewritten grammar --
M: M1 | M2 | M3 | M4;

M1: m;
M2: M "," M;
M3: "(" M31 ")";
M4: F;

M31: M1 | M2 | M3;

F: f | F "or" F | "(" F ")";
------------------------------

The construction is fairly obvious: In the constrained argument M31, just
add the admissible expansions. Here I have merely taken away M31 -> F.

Then I can simplify this grammar by letting N standing for the equivalent
symbols M1, M2, M3, and M31, and replacing M4 with F.

-- Final rewritten grammar --
M: N | F;

N: m;
N: M "," M;
N: "(" N ")";

F: f | F "or" F | "(" F ")";
---------------------------------

This is in fact a grammar that passes a Bison compilation, too.

  Hans Aberg