Problemas com as precedências Yecc de Erlang

Question

Estou tentando escrever um analisador Erlang com Yecc, mas estou tendo alguns problemas com a precedência das regras semânticas.No meu caso defini a gramática, os símbolos terminais e não terminais, as regras e o código associado.

Isto é o que escrevi para teste.

%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).

Agora vamos executar um termo específico para verificar como as regras são aplicadas.

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}]).

A saída do analisador é:

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

Mas eu preciso disso.Estou escrevendo a saída desde que o analisador processe o termo (como uma saída de depuração).

Termo inicial.

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

Regra %[req1 e req2].(Isto é aplicado corretamente – Caso '$1' == '$5')

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

Agora, não sei o que acontece, mas a saída deveria ser assim.

Regra %[mand2 & mand3].(Caso verdadeiro)

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

Regra %[mand2 & mand3].(Caso '$2' == '$7')

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

Regra %[tick] – E resultado final.

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

Eu já tentei isso:

Como é explicado no manual do Yecc, consegui fazer isso:

• Brincando com as precedências dos operadores.
• Aplicando precedência às regras.A partir da documentação (também é possível declarar precedência para não-terminais, "um nível de nível".Isso é prático quando um operador está sobrecarregado (consulte também o Exemplo 3 abaixo)).

Mas não parece funcionar para mim.Qualquer ajuda???

Obrigado!

Answer 1

Apenas algumas notas:

1. Left 200 require. Left 190 require1. Left 180 mandatory. Left 170 mandatory1. não é eficaz.Esses não são operadores porque não estão presentes no lado direito do ->.

1. Novamente sobre require, require1, mandatory e mandatory1:essas não são regras conflitantes.Apenas escreva product -> feature req feature '(' feature ';' product ')': …. product -> feature req feature '(' tick ')': …. …

2. Por que você às vezes adiciona {·,1}?Esse deveria ser o trabalho do lexer.

Answer 2

Tive o mesmo problema em um analisador de Lua no qual estava trabalhando.A solução que encontrei foi que você precisa usar os operadores dentro do mesmo terminal para que funcione.Eu poderia dividi-lo em um terminal que lidasse com todos os operadores binários que tinham precedência:

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

Então, se você pudesse algo como

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 : ... .

É claro que isso nem sempre é possível.Se você observar os exemplos que usam precedência na documentação do yecc, eles serão estruturados assim.Além disso, se você observar a gramática erlang, verá que ela não usa precedência, mas faz cada nível de precedência explicitamente.

No seu caso, com apenas quatro níveis, deve ser relativamente fácil.