0

文法と添付されたアクション コードが与えられた場合、各プロダクションがどのような型になる必要があるか (そして、その結果、呼び出し側のプロダクションがそれから取得する必要がある型) を推測するための標準的な解決策はありますか?

C# の構文のようなものを使用する OO プログラムとアクション コードを考えていvarます (ただし、C# 固有のものを探しているわけではありません)。

関数のオーバーロードと再帰文法がなければ、これは非常に簡単です。

この問題は、次のような場合に発生します。

Foo ::= 
    Bar Baz { return Fig(Bar, Baz); }
    Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))
4

2 に答える 2

4

関数型言語でコードを書いている場合は簡単です。標準の Hindley-Milner 型推論はうまく機能します。 これをしないでください。Icon、c、および標準 ML をサポートする私の EBNF パーサー ジェネレーター (リリースされたことはありませんが、要求に応じてソース コードを入手できます) では、標準 ML バックエンドについて質問 されているアイデアを実際に実装しました。すべての型が推論されました。結果として生じる文法は、デバッグがほぼ不可能でした。

オーバーロードをミックスに投入すると、結果はデバッグが難しくなるだけです。（そうです！これはちょうど入っています！不可能よりも難しいです！無限よりも大きいです！就寝時間を過ぎました！）本当に自分で試してみたい場合は、私のコードにようこそ。（そうではありません。私がリリースしなかったのには理由があります。）

于 2008-12-17T05:19:47.170 に答える
1

文法アクションの戻り値は実際にはローカル変数と変わらないため、C# の型推論を使用してジョブを実行できるはずです。C# の型推論がどのように実装されているかについては、このペーパーを参照してください。

型推論を行う標準的な方法はHindley-Milner アルゴリズムですが、そのままではオーバーロードを処理できません。

型推論言語のパーサー ジェネレーターでさえ、通常は文法アクションの型を推論しないことに注意してください。たとえば、ocamlyaccには型注釈が必要です。HaskellのHappyパーサー ジェネレーターは型を推測できますが、その実践は推奨されないようです。これは、文法で型を推測することが難しいか、悪い考えであるか、またはその両方であることを示している可能性があります。

[更新] 苦い経験の恩恵を受けているノーマン・ラムジーによって非常にpwned.

于 2008-12-17T05:24:00.080 に答える