Happy Context-Dependent Operator Precedence

Question

ここでは、通常の優先順位ルールを使用するハッピーコードとコンテキスト依存優先順​​位ルールを使用するスニペットがあります（どちらもhereと記載されています）。

ノーマル：

%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でない限り、本番の最後の端末の優先順位をコピーすることによって設定されます。あるいは、別の言い方をすれば、生産のprecdenceは%prec節で設定され、最後のトークンの優先順位がデフォルトになります。いずれにしても、プロダクションの優先順位は、端末の優先順位と同じであるということでしか定義できません。これは必ずしも便利ではないので、パーサジェネレータは、文法シンボルの名前ではない任意の名前を使用するオプションを提供します。実装は、名前を端末として扱い、実際にはどの文法ルールでも使用されないという事実を無視するが、論理的にはその特定のプロダクションに割り当てられる優先レベルの名前である。

最初の例では、プロダクションのデフォルトを、各プロダクションの最後の（実際は唯一の）端末にデフォルトさせます。しかし、2番目の例では、PLUSとTIMESの2つの名前付き優先レベルを定義し、それらを使用して2つのプロダクションの優先順位を設定します。しかし、あなたは端末の優先順位を宣言しません。したがって、パーサジェネレータが、縮小される可能性があるプロダクションの相対的な優先順位と、シフト可能なターミナルとをチェックしようとすると、それらのうちの1つだけが宣言された優先順位を有することがわかる。そしてその場合、それは常にシフトします。