5

私は、BNF で形式化された Java の非常に小さなサブセットで特定の構造を最適化するプロジェクトに取り組んでいます。

これを Java で行う場合は、AST を構築する JTB と JavaCC を組み合わせて使用​​します。その後、訪問者はツリーを操作するために使用されます。しかし、Haskell で解析するための膨大なライブラリ (parsec、happy、alex など) を考えると、適切なライブラリを選択するのに少し混乱しています。

簡単に言えば、言語が BNF で指定されている場合、AST を構築する最も簡単な手段を提供するライブラリはどれでしょうか? そして、慣用的な Haskell でこのツリーを変更するための最良の方法は何ですか?

4

5 に答える 5

7

Haskell には、何かを解析する主な方法が 2 つあります。解析コンビネーターまたはパーサー ジェネレーターです。あなたはすでに BNF を持っているので、後者をお勧めします。

良いものはアレックスです。GHC のパーサー IIRC はこれを使って書かれているので、あなたは良い仲間になるでしょう。

次に、解析するデータ宣言の大きなクラクション スタックがあります。

data JavaClass = {
    className :: Name,
    interfaces :: [Name],
    contents :: [ClassContents],
    ...
 }
  data ClassContents = M Method
                     | F Field
                     | IC InnerClass

式など、必要なものは何でも。最後に、これらを次のようなものに結合します

data TopLevel = JC JavaClass
              | WhateverOtherForms
              | YouWillParse

TopLevelこれを取得すると、解析するクラス/ファイルの数に応じて、AST全体が1つまたはそれらのリストとして表されます。

ここから先に進むには、何をしたいかによって異なります。syb非常に簡潔なツリーのトラバーサルと変更を記述できる (ボイラープレートを破棄する)などのライブラリが多数あります。lensもオプションです。少なくともチェックアウトしData.TraversableてくださいData.Foldable。

ツリーを変更するには、次のような簡単なことを行うことができます

ignoreInnerClasses :: JavaClass -> JavaClass
ignoreInnerContents c = c{contents = filter isClass $ contents c}
 --                           ^^^ that is called a record update
    where isClass (IC _) = True
          isClass _      = False

そして、次のようなものを潜在的に使用できsybます

 everywhere (mkT ignoreInnerClass) toplevel

これはすべてをトラバースし、ignoreInnerClassallに適用されますJavaClasses。これはlens、他の多くのライブラリでも実行できますが、syb非常に読みやすいです。

于 2013-09-10T11:49:16.067 に答える
4

私は一度も使用したことがありません (@phg の提案による) が、 BNFCbnfc-metaを調べることを強くお勧めします(ハックについて: http://hackage.haskell.org/package/BNFC )。基本的なアプローチは、注釈付きの BNF スタイルで文法を記述することです。これにより、文法の AST、パーサー、およびプリティ プリンターが自動的に生成されます。

BNFC がどの程度適しているかは、文法の複雑さに依存します。コンテキスト フリーでない場合は、作業を進めるのに苦労する可能性があります (コンテキスト依存の拡張機能のハッキングにはある程度成功しましたが、そのコードは今では少し腐敗している可能性があります)。もう 1 つの欠点は、AST が文法仕様を直接反映することです。しかし、すでに BNF 仕様を持っているので、BNFC に必要な注釈を追加するのはかなり簡単なはずです。したがって、おそらくこれが、使用可能な AST を取得する最速の方法です。別のルートに進むことにした場合でも、生成されたデータ型を手書きバージョンの出発点として使用できる場合があります。

于 2013-09-10T23:27:35.393 に答える
2

また、Haskell Compiler Series もチェックしてください。alex を使用するための入門として最適で、Java のサブセットを解析できます: http://bjbell.wordpress.com/haskell-compiler-series/。

于 2013-09-11T00:39:26.697 に答える
2

文法は BNF で表現できるため、shift-reduce パーサー (LALR 文法) で効率的に解析できる文法のクラスになります。このような効率的なパーサーは、パーサー ジェネレーター yacc/bison (C、C++)、またはそれに相当する Haskell の "Happy" によって生成できます。

そのため、あなたの場合は「ハッピー」を使用します。BNF 形式の文法規則を取り、そこから直接パーサーを生成します。結果のパーサーは、文法規則によって記述された言語を受け入れ、AST (抽象構文ツリー) を生成します。Happy ユーザーガイドは非常に素晴らしく、すぐに使い始めることができます: http://www.haskell.org/happy/doc/html/

結果の AST を変換するには、ジェネリック プログラミングを使用することをお勧めします。Haskell でこれを実用的な方法でゼロから行う方法についての古典的な説明を次に示します 。

私はまさにこれを使用して小さなドメイン固有言語用のコンパイラを構築しましたが、これはシンプルで簡潔なソリューションでした。

于 2013-09-11T18:34:19.987 に答える