I found something strange in handling of priority groups in sdf2table. Might be an error, might be by design, I don’t know. Maybe this needs to go into some sdf bundle issue tracker but last time I searched for that I didn’t find any.

Anyway, it appears that if you have a priority group {left: X}, where X is a production, then X may not appear as right child of X. So a {left} attribute on X is redundant, if present.

However, if you have a priority group {left: X Y …}, i.e. with more than one production, then X may appear as right child of X. (Unless a {left} attribute is present of course.)

This can be reproduced using a grammar like this (Common module identical to EntityLang):

module Test-associativity

imports Common

exports

context-free start-symbols
Start

context-free syntax

Exp -> Start {cons("Exp")}

Exp "+" Exp -> Exp {cons("Plus")}
Exp "-" Exp -> Exp {cons("Minus")}
Exp "*" Exp -> Exp {cons("Times")}
Exp "/" Exp -> Exp {cons("Over")}
INT -> Exp {cons("Value")}

context-free priorities

{left: Exp "*" Exp -> Exp} >
{left: Exp "/" Exp -> Exp} >
{left: Exp "+" Exp -> Exp
       Exp "-" Exp -> Exp}

Then, parsing 1 + 1 + 1 or 1 - 1 - 1 will give an ambiguity, while parsing 1 * 1 * 1 or 1 / 1 / 1 will work fine (combinations with two different operators also work fine), demonstrating that self-associativity within a group is applied if and only if the number of members of that group equals one.

Using sdf2parenthesize it is possible to demonstrate this is probably an issue in parse table generation (sdf2table). For the above grammar it outputs these rules:

Test-associativityParenthesize :
Times(t_0, t_1) -> Times(Parenthetical(t_0), t_1)
where <(?Minus(_, )
+ ?Plus(, )
+ ?Over(, _)
+ fail)> t_0

Test-associativityParenthesize :
Times(t_0, t_1) -> Times(t_0, Parenthetical(t_1))
where <(?Minus(_, )
+ ?Plus(, )
+ ?Over(, )
+ ?Times(, _)
+ fail)> t_1

Test-associativityParenthesize :
Over(t_0, t_1) -> Over(Parenthetical(t_0), t_1)
where <(?Minus(_, )
+ ?Plus(, _)
+ fail)> t_0

Test-associativityParenthesize :
Over(t_0, t_1) -> Over(t_0, Parenthetical(t_1))
where <(?Minus(_, )
+ ?Plus(, )
+ ?Over(, _)
+ fail)> t_1

Test-associativityParenthesize :
Minus(t_0, t_1) -> Minus(t_0, Parenthetical(t_1))
where <(?Plus(_, _) + fail)> t_1

Test-associativityParenthesize :
Plus(t_0, t_1) -> Plus(t_0, Parenthetical(t_1))
where <(?Minus(_, _) + fail)> t_1

Note how Times as right child of Times and Over as right child of Over are forbidden, but Plus as right child of Plus and Minus as right child of Minus are allowed.

Submitted by Tobi Vollebregt on 20 May 2011 at 17:11