ネストされたリストとのシフト/リダクション

Question

私は "Modern Compiler Implementation in ML"を使って、SMLをOCamlに変換しています。この本は、Tigerという言語を定義しています。この言語は、与えられた式のスコープ内の型、変数、関数を宣言するための構文がlet ... in ... endです。さらに、同じ種類の隣接宣言は、相互再帰を可能にするためにグループ化する必要があります。私は、シフト/紛争を減らす取得するが、立石はそれを私が好きな道を解決し、これにより

%right FUNCTION TYPE 

. 
. 
. 

decs: l = list(dec) { l } 

dec: 
    | l = nonempty_list(tydec) { A.TypeDec l } 
    | v = vardec { v } 
    | l = nonempty_list(fundec) { A.FunctionDec l } 

tydec: 
    | TYPE; name = ID; EQUAL; ty = ty { 
     A.{ 
     type_name = Symbol.symbol name; 
     type_ty = ty; 
     type_pos = Position.make $startpos $endpos 
     } 
    } 

：私はこれを表現しようとした

は以下の文法スニペットと立石です。私はnonempty_list(typec)を貪欲にして、隣接するTYPE宣言をまとめてグループ化します。すなわち、立石は、紛争を解決して、私の生成ASTのようなものになります。

(LetExp 
    (decs 
    ((TypeDec 
     (((type_name (my_type)) (type_ty (NameTy (int)))) 
     ((type_name (my_type2)) (type_ty (NameTy (string)))) 
    )))) 
    (body (SeqExp()))) 

を私は警告を取り除くしたいのですが、私は矛盾メンヒルと同じ方法を解決するために把握することはできません。私は%inline tydecを使って試してみましたが、これは警告を消してしまいますが、TYPEのシフトは私の予想どおりに適用されません。代わりに、好ましいのは、このようになりますAST得、decsにリストに与えられる：

(LetExp 
    (decs 
    ((TypeDec 
     (((type_name (my_type)) (type_ty (NameTy (int)))))) 
    (TypeDec 
     (((type_name (my_type2)) (type_ty (NameTy (string))) 
))))) 
    (body (SeqExp()))) 

を私はまた、明示的に優先度を設定しようとしましたが、立石は、それは役に立たない宣言だことを私に警告します。

私はここで何か基本的なものが欠けていると確信しています。リストのリストを生成するプロダクションを与えます。どのようにして内側のリストを貪欲にすることができますか？

Answer 1

（同じルールのプロダクションでは%precと同じように）あるルールよりも正確な優先順位を設定できないことを覚えていれば、私は間違っているかもしれませんが、それが不可能な理由を理解できます。そのような状況においても論理的な誤りがあったとします。私は説明しようとします。

decs: l = list(dec) { l } 

dec: 
    | l = TYPEDEF nonempty_list(tydec) { A.TypeDec l } 
    | ... 

と理由typedef我々ドンのこの場合：それはかなりのロジックはこのような何かを定義することです。この場合、

vardef i = 42 
     j = 24 
typedef all_new_int = int 
     all_new_bool = bool 

：

レッツは、我々はいくつかの次の構文を使用して言語を持っていると言います紛争は起こっていない。さて、そのような「区切り」なく、単に存在しない場合：

var i = 42 
    var j = 24 
    type all_new_int = int 
    type all_new_bool = bool 

なぜ、この2型宣言を再編成しようとするには？これはブロックではなく（前の例のように）、2つの別々の宣言です。ですから、ASTは言語と一貫していなければなりません。私はそれはあなたが探している答えではないのですが、知っている私が言うことをしようとしていることは、あなたがnonempty_listdecには必要がないということである：多分あなたのdecする必要はありません

decs: l = list(dec) { l } 

dec: 
    | l = tydec { [A.TypeDec l] } 
    | v = vardec { v } 
    | l = fundec { [A.FunctionDec l] } 

そして、この場合、リストを返す。はい、あなたのASTは%inline tydecと同じですが、それは言語に一貫しています。立石のドキュメントからところで

、：

あなたの場合：

+実際にはnonempty_list（実際の）

---

編集のためのシンタックスシュガーであります変更したくないシフトなしシフト/

%token <int> INT 
%token NONE 
%token EOF 

%start <int option list list> main 

%% 

main: l = op_list* EOF { l } 

op_list: 
     l = num+ { l } 
    | NONE { [None] } 

num: i = INT { Some i } 

2を減らす）で

1）/

を減らす：（何らかの理由で）あなたの構造あなたは常にあなたのルールを書き換えることができ、例えばこの2つの文法が完全に同じです私は0 NONE 1 2 NONE 3を見たときに

%token <int> INT 
%token NONE 
%token EOF 

%start <int option list list> main 

%% 

main: ll=main2 EOF { ll } 

main2: 
    { [] } 
    | n=num ll=main2 { match ll with 
         | ((Some i)::l)::ll -> ((Some i)::(Some n)::l)::ll 
         | _ -> [Some n]::ll 
        } 
    | NONE ll=main2 { [None]::ll } 

num: i=INT { Some i } 

はもう一度、ここで私は約[0; None; 1; 2; None; 3]なく[[0]; [None]; [1; 2; 3]; [None]; 3]と思いますが、第2の解決策は、[OK]を将来の使用のためのよりシンプルである場合。 %precとその会社（%left、%right、...）でこれを行うことができますが、いずれの場合でもルールを書き直す必要があります。あなたはそれを解決する必要がある紛争があるとき、魔法はありません。

6.3最終的に重大な競合はどのように解決されますか。重大な競合の解決方法は不明です。 Menhirは にocamlyaccの仕様を模倣しようとしています。つまり、 のシフト/縮小競合を解決して、 の文法的仕様の中で最も早く出現する生産のために、 reduce/reduce競合を解決します。しかし、この の仕様は、3方向の競合の場合には矛盾します。つまり、シフトアクションと複数の削減アクションを同時に伴う 競合が発生します。さらに、文法仕様が複数のモジュールに分割されている場合、テキストの優先順位は未定義の になる可能性があります。 短いですが、Menhirの哲学は重大な矛盾が許容されてはならないということです。したがって、それらがどのように解決されるか気にする必要はありません。