21

私は Haskell を見てきましたが、(学習課題として) Haskell にコンパイラを書きたいと思っています。なぜなら、Haskell の生得的な機能の多くは、コンパイラ (特に再帰降下コンパイラ) に簡単に適用できるからです。

私がよく理解できないのは、Haskell 流の方法で言語の文法を表現する方法です。私が最初に考えたのは、再帰的なデータ型定義を使用することでしたが、たとえば言語のキーワード (「if」) と照合するためにそれらを使用する方法がわかりません。

考えや提案は大歓迎です。

ピート

4

5 に答える 5

16

これには、再帰的なデータ型が適しています。たとえば、次の言語があるとします。

expr ::= var
      |  "true"
      |  "false"
      |  "if" expr "then" expr "else" expr
      |  "(" expr ")"

この言語での表現の例は次のようになります。

if true then x else (if false then y else true)

Haskell データ型は次のようになります。

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr

次に、パーサーは、たとえば 、 、 などに変換しxます。つまり:Var "x"trueLit True

parse "if x then false else true" 
  ==  If (Var "x") (Lit False) (Lit True)

パーサーを作成するには、ノーマンの回答に記載されている手法を使用するか、Parsecを使用するか、 Happyなどのパーサー ジェネレーターを使用して、独自のパーサーを作成できます。

于 2009-03-25T02:14:15.603 に答える
3

実際のプロジェクトを見て、彼らがどのようにそれを行っているかを確認できますか?

1 週間も経たないうちに、Language-PythonプロジェクトがHaskell-Cafe メーリングリストで発表されました。Happyパーサー ジェネレーターとAlex lexer ジェネレーターを使用して、Haskell で実装されたPythonパーサーです。

そしてもちろん、 Haskell でのPerl 6の実装であるPugsがあります(Perl 6 仕様の重要なサブセットに準拠する Perl 6 の最初の実装です)。

于 2009-03-25T14:31:39.170 に答える
0

あなたの質問のトーンからは、あなたがコンパイラーを書こうとしているのが初めてなのか、以前にコンパイラーを書いたことがあり、Haskell に固有のアドバイスを探しているのかがわかりません。あなたがすでにコンパイラの第一人者である場合、私が提供しなければならない小さなアドバイスは役に立ちません。:)

プログラミング言語の文法は一般にBNF 形式で表され、Yacc や Bison などのツールでソース コードを解析するために使用できます。これが Haskell 流の方法と見なされるかどうかはわかりませんが、私が聞いた唯一の方法です。BNF 文法から Haskell コードを生成するためのツールを掘り下げることができるでしょう。それができると主張するこのツールを見つけました。

Haskell用のコンパイラを書きたい場合 (Haskell で Haskell コンパイラを書きたい場合) に備えて、Google で簡単に検索すると、この BNF grammar for Haskellが見つかりました。 Javaが人気のようです。

最後に、コンパイラの設計に関する本を探しているなら、古典的なテキストは"The Dragon Book"です。

于 2009-03-25T01:00:05.347 に答える
0

残念ながら、 ANTLRの Haskell 文法はありませんが、上記のリンクを使用して作成できる可能性があります。ANTLR は、優れた Java ベースのパーサー ジェネレーターです。

もっとやる気が必要な場合は、Steve Yegge がコンパイラーの作成に関するすばらしいブログを書いています。面白いです。

于 2009-03-25T01:14:37.683 に答える