Приоритет операционного режима, связанный с контекстом

Question

У меня есть два фрагмента кода Happy, здесь, где используются правила обычного приоритета, и один, который использует контекстно-зависимые правила приоритета (оба из которых описаны here).

Normal:

%left '+' 
%left '*' 
%% 

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

Контекст-зависимый:

%left PLUS 
%left TIMES 
%% 

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

Учитывая вход:

a * b + c * d 

Обычная версия дает:

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

в то время как контекстно-зависимой версии дает:

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

не должны они оба дают тот же результат? Что я делаю неправильно здесь, что заставляет их генерировать разные деревья разбора?

Answer 1

«Контекстно-зависимый приоритет» - очень вводящий в заблуждение способ описания этой функции. Однако описание алгоритма приоритета в предыдущем разделе в значительной степени точнее.

Как говорится, сравнение старшинства всегда между производством (которая может быть уменьшена) и терминалом (который может быть сдвинут). Этот простой факт часто омрачается решением о разработке синтаксиса объявления приоритета, поскольку приоритет был исключительно атрибутом терминала.

Приоритет производства задается путем копирования приоритета последнего терминала в производстве, если нет явного объявления с %prec. Или, говоря иначе, превенция производства задается с условием %prec, по умолчанию - с приоритетом последнего токена. В любом случае, вы можете определить приоритет производства, сказав, что он такой же, как у какого-либо терминала. Так как это не всегда удобно, генератор парсера дает вам возможность использовать произвольное имя, которое не является символом грамматики. Реализация заключается в том, чтобы рассматривать это имя как терминал и игнорировать тот факт, что он никогда не используется в любом правиле грамматики, но логически это имя уровня приоритета, который должен быть присвоен этому конкретному производству.

В первом примере вы позволяете продуктам по умолчанию использовать их приоритет до последнего (фактически, единственного) терминала в каждом произведении. Но во втором примере вы определили два именованных уровня приоритета: PLUS и TIMES, и вы используете их для установки приоритета двух производств. Но вы не объявляете приоритет любого терминала. Поэтому, когда генератор синтаксического анализатора пытается проверить относительный приоритет производства, который может быть уменьшен, и терминал, который можно сдвинуть, он обнаруживает, что только одна из этих вещей имеет объявленный приоритет. И в этом случае он всегда сдвигается.