Happy context sensitive operator priority

I have two snippets of Happy code that use normal priority rules and one that uses context-sensitive priority rules (both of which are described here ).

Normal:

%left '+' %left '*' %% Exp :: { Exp } : Exp '+' Exp { Plus $1 $3 } | Exp '*' Exp { Times $1 $3 } | var { Var $1 } 

depends on the context:

 %left PLUS %left TIMES %% Exp :: { Exp } : Exp '+' Exp %prec PLUS { Plus $1 $3 } | Exp '*' Exp %prec TIMES { Times $1 $3 } | var { Var $1 } 

Given input:

 a * b + c * d 

The normal version gives:

 Plus (Times (Var "a") (Var "b")) (Times (Var "c") (Var "d")) 

whereas the context-sensitive version gives:

 Times (Var "a") (Plus (Var "b") (Times (Var "c") (Var "c"))) 

Should this data not give the same result? What am I doing wrong here, that forcing them to generate different parsing trees?

+6
source share
1 answer

"Context-sensitive Priority" is a very misleading way to describe this feature. However, the description of the priority algorithm in the previous section is much more accurate.

As they say, a comparison of priorities always occurs between production (which can be reduced) and the terminal (which can be shifted). This simple fact is often overshadowed by the decision to develop a priority declaration syntax, since priority was exclusively an attribute of the terminal.

The production priority is set by copying the priority of the last terminal in production if there is no explicit declaration with %prec . Or, to put it another way, production prevention is set with the %prec clause, by default - with the priority of the last token. In any case, you can determine the priority of production by saying that it is the same as any terminal. Since this is not always convenient, the parser generator gives you the opportunity to use an arbitrary name that is not a symbol of the grammar. The implementation is to consider the name as a terminal and ignore the fact that it is never used in any grammar rule, but logically it is the name of the priority level that should be assigned to this particular product.

In the first example, you allow products to take precedence by default up to the last (in fact, the only) terminal in each work. But in the second example, you defined two named priority levels: PLUS and TIMES, and you use them to set the priority of two productions. But you do not declare the priority of any terminal. Therefore, when the parser generator tries to check the relative priority of production, which can be reduced, and the terminal, which can be shifted, it discovers that only one of these things has declared priority. And in this case, it always moves.

+4
source

Source: https://habr.com/ru/post/1014386/


All Articles