parsinggrammarcontext-free-grammarsablecc

Changing associativity schema in a grammar


I'm trying to use SableCC to generate a Parser for models, which I call LAM. LAM in itself are simple, and a simple grammar (where I omit a lot of things) for these is:

L :=   0   |   (x,y)   | F(x1,...,xn)  |    L || L    |    L ; L

I wrote this grammar:

Helpers
    number   = ['0' .. '9'] ;
    letter   = ['a' .. 'z'] ;
    uletter  = ['A' .. 'Z'] ;

Tokens
    zero     = '0' ;
    comma    = ',' ;
    parallel = '||' ;
    point    = ';' ;
    lpar    = '(' ;
    rpar    = ')' ;

    identifier = letter+ number* ;
    uidentifier = uletter+ number* ;

Productions
    expr = {term} term |
           {parallel} expr parallel term |
           {point} expr point term;

    term = {parenthesis} lpar expr rpar |
           {zero} zero |
           {invk} uidentifier lpar paramlist rpar |
           {pair} lpar [left]:identifier comma [right]:identifier rpar ;

    paramlist  = {list} list | 
                 {empty} ;

    list  = {var} identifier |
            {com} identifier comma list ;

This basically works, but there is a side effect: it is left associative. For example, if I have

L = L1 || L2 ; L3 || L4

Then it is parsed like:

L = ((L1 || L2) ; L3) || L4

I want to give all precedence to the ";" operator, and so have L parsed like

L = (L1 || L2) ; (L3 || L4)

(other things, like "||", could remains left-associative)

My questions are:

  1. There are tips to do such conversions in a "automated" way?
  2. How could be a grammar with all the precedence on the ";" ?

It is accepted also "RTFM link" :-D Thank you all


Solution

  • You need to create a hierarchy of rules that matches the desired operator precedence.

    expr = {subexp} subexp |
           {parallel} subexp parallel expr ;
    
    subexp = {term} term |
             {point} term point subexp;
    

    Note that I also changed the associativity.