Issues with Erlang's Yecc precedences

Question

I’m trying to write an Erlang parser with Yecc, but I’m having some troubles with the precedence of the semantic rules. In my case I defined the grammar, the terminal and non-terminal symbols, the rules and the associated code.

This is what I wrote for testing.

%Grammar non terminals
Nonterminals    product require require1 mandatory mandatory1.

%Grammar  terminals
Terminals       'tick' 'feature' '(' ')' 'req' 'mand' ';' 'nil'. 

%Initial symbol
Rootsymbol product.

%Operands priority

Left 200 require.
Left 190 require1.
Left 180 mandatory.
Left 170 mandatory1.

Left    80  'req'.
Left    60  'mand'.
Left    50  ';'.        %Secuence
Left    40  'feature'.  %Optional feature



%--------------------------------------------------
%Grammar with operational rules

%[req1 & req2]
product -> require: '$1'.
require -> feature req feature '(' feature ';' product ')' :    if
                                                                    '$1' == '$5'    -> {'$5', {'$4', '$7', '$8', {mand,1}, '$3'}};
                                                                    true            -> {'$5', {'$1', '$2', '$3', '$4', '$7', '$8'}}
                                                                end.
%[req3]
product -> require1 : '$1'.
require1 -> feature req feature '(' tick ')' : {nil,1}.



%[mand2 & mand3]
product -> mandatory : '$1'.
mandatory -> '(' feature ';' product ')' mand feature : if
                                                        '$2' == '$7'    -> {'$2', {'$4'}};
                                                        true            -> {'$2',{'$1', '$4', '$5', '$6', '$7'}}
                                                    end.


%[mand1]
product -> mandatory1: '$1'.
mandatory1 -> '(' tick ')' mand feature : {$5, {tick,1}}.


%[tick]
product -> feature ';' tick : {'$1', {nil,1}}.
product -> nil.
product -> feature ';' product : {'$1', {'$3'}}.


Erlang code.    
%To remove brackets and return only the third parameter, right now is not used.
unwrap_feature({_,_,V}) -> V.


%%How to compile and use
%Save this as stack.yrl
%Run erl and then
%yecc:yecc("stack.yrl","stack.erl"). 
%c(stack).

Now lets execute a specific term to check how rules are applied.

stack:parse([{feature,1,'A'},{'req',1},{feature,1,'C'},{'(',1},{feature,1,'A'},{';',1},{feature,1,'B'},{';',1},{feature,1,'C'},{';',1},{tick,1},{')',1}]).

The parser output is:

{ok,{{feature,1,'A'},
     {{'(',1},
      {{feature,1,'B'},{{{feature,1,'C'},{nil,1}}}},
      {')',1},
      {mand,1},
      {feature,1,'C'}}}}

But I need this. I’m writing the output as long the parser process the term (like a debug output).

Initial term.

{feature,1,'A'},{'req',1},{feature,1,'C'},{'(',1},{feature,1,'A'},{';',1},{feature,1,'B'},{';',1},{feature,1,'C'},{';',1},{tick,1},{')',1}

Rule %[req1 & req2]. (This is applied correctly – Case '$1' == '$5')

{feature,1,'A'},{{'(',1},{feature,1,'B'},{';',1},{feature,1,'C'},{';',1},{tick,1},{')',1},{mand,1},{feature,1,'C'}}

Now, I don’t know what happens, but the output should be as this.

Rule %[mand2 & mand3]. (Case true)

{feature,1,'A'},{{feature,1,'B'},{{'(',1},{feature,1,'C'},{';',1},{tick,1},{')',1},{mand,1},{feature,1,'C'}}}

Rule %[mand2 & mand3]. (Case '$2' == '$7')

{feature,1,'A'},{{feature,1,'B'},{{feature,1,'C'},{{tick,1}}}}

Rule %[tick] – And final result.

{feature,1,'A'},{{feature,1,'B'},{{feature,1,'C'},{{{tick,1},{nil,1}}}}}

I already tried this:

As is explained in Yecc manual, I was able to do this:

• Playing with the operator precedences.
• Applying precedence to rules. From the documentation (It is also possible to declare precedence for non-terminals, "one level up". This is practical when an operator is overloaded (see also example 3 below)).

But it doesn’t seem to work for me. Any help???

Thanks!

Answer 1

Just a few notes:

1. Left 200 require. Left 190 require1. Left 180 mandatory. Left 170 mandatory1. is not effective. Those are not operators as they are not present in righthand side of ->.

1. Again about require, require1, mandatory and mandatory1: those are not conflicting rules. Just write product -> feature req feature '(' feature ';' product ')': …. product -> feature req feature '(' tick ')': …. …

2. Why do you sometimes add {·,1}? That should be the lexer's job.

Answer 2

I had the same problem in a parser for Lua on which I was working. The solution I found was that you need to use the operators within the same terminal for it to work. I could break it out into one terminal which handled all the binary operators which had a precedence:

bin_op -> exp '+' exp : ... .
bin_op -> exp '-' exp : ... .
...
bin_op -> exp 'and' exp -> ... .
bin_op -> exp 'or' exp -> ... .

So if you could something like

Left    80  'req'.
Left    60  'mand'.
Left    50  ';'.        %Secuence
Left    40  'feature'.  %Optional feature

product -> feature 'req' feature : ... .
product -> feature mand feature : ... .
product -> feature ';' feature : ... .

This is not of course not always possible. If you look at the examples which use precedence in the yecc documentation they are structured like this. Also if you look at the erlang grammar you will see that it does not use precedence but does each precedence level explicitly.

In your case with only four levels it should be relatively easy.