1

ラムダ計算を処理する言語用の小さなコンパイラを作成しようとしています。これが私が見つけた言語の曖昧な定義です：

E → ^ v . E  | E E | ( E ) | v

記号^、。、（、）およびvはトークンです。^はラムダを表し、vは変数を表します。^ vEの形式の式は関数定義です。ここで、vは関数の正式なパラメーターであり、Eはその本体です。fとgがラムダ式の場合、ラムダ式fgは、引数gへの関数fの適用を表します。

関数適用が結合性のままであり、たとえばfgh =（fg）hであり、関数適用が。、たとえば（^x。^y。 xy）^ zz =（^ x。（^ y。xy））^ zz

これが私がこれまでに持っているものですが、それが正しいかどうかはわかりません：

E -> ^v.E | T
T -> vF | (E) E
F -> v | epsilon

誰か助けてもらえますか？

4

2 に答える 2

6

質問とコメントを読む間、ここで尋ねた特定の質問だけでなく、ラムダ計算の学習と実装に関するヘルプを探しているようです。もしそうなら、私は同じ道を進んでいるので、いくつかの有用な情報を共有します。

私が持っている最高の本は、可能な限り最高の本とは言えませんが、BenjaminC.PierceによるTypesandProgramming Languages（WorldCat ）です。タイトルがラムダ計算のように聞こえないことは知っていますが、λ-Calculus拡張機能を見てください。本からのラムダ計算の多くをリストする拡張記号の意味です。この本のコードはOCamlとF＃にあります。

詳細については、 CiteSeerXでラムダ計算に関する研究論文を検索してみてください。

私がこれまでに見つけた最高のλ-微積分評価器は次のとおりです。

ここに情報があるラムダ計算削減ワークベンチ。

また、 CS：StackExchangeでのプログラミングに関連するラムダ計算の質問と、 Math：StackExcahngeでの数学関連の質問に対して、はるかに優れた回答が得られることがわかりました。

ラムダ計算を実装するためのプログラミング言語については、関数型言語をまだ習得していない場合は、おそらく習得する必要があります。はい、それは別の獣ですが、山の向こう側の悟りは壮観です。私が見つけたソースコードのほとんどは、MLやOCamlなどの関数型言語を使用しており、一度習得すれば、残りは習得しやすくなります。

具体的には、型なしラムダ計算プロジェクトのソースコード、YACCのF＃バリエーションへの入力ファイルです。これは、前の質問を読んだことから、知識の世界にあるようです。サンプル入力です。

文法はREPLを実装するためのものであるため、トップレベルのthinkコマンドプロンプトで始まり、複数のコマンド（この場合はラムダ計算式）を受け入れます。この文法は多くの計算に使用されるため、前の例ではプレースホルダーである部分があります。したがって、ここでのバインディングは、プレースホルダーに近いものです。

最後に、私たちはあなたが求めている部分に到達します

注LCIDは小文字の識別子です

Term : AppTerm
     | LAMBDA LCID DOT Term 
     | LAMBDA USCORE DOT Term 

AppTerm : ATerm   
        | AppTerm ATerm

/* Atomic terms are ones that never require extra parentheses */
ATerm : LPAREN Term RPAREN 
      | LCID
于 2013-03-02T06:41:26.573 に答える
2

劣線形時間で特定の文法のあいまいさの証拠を見つけることができますが、文法があいまいでないことを証明することはNP完全問題です。その言語で可能なすべての文を生成し、それぞれに派生が1つしかないことを確認する必要があります。

于 2013-03-03T00:43:36.080 に答える