5

私はC++ 11でシフト/リデュースパーサージェネレーターに取り組んでいますが、入力プロダクションとリダクションアクション関数のインターフェイスタイプを指定して、入力したい情報を保持する方法がわかりません。

文法を静的に指定したいのですが、C++ 型を使用します (別のビルド ツールではありません)。

各記号 (終端記号と非終端記号) に対して、ユーザーは文字列名とタイプを指定します。

次に、各プロダクションでヘッド シンボル名と 1 つ以上のボディ シンボル名を指定します。

プロダクションごとに、ヘッドの非終端型を返し、(対応するタイプの) プロダクション ボディ シンボルに対応するパラメーターを持つアクション関数がユーザー (ハード パーツ) によって提供されます。

主な問題は、これらのアクション関数のパラメーターの型と戻り値の型を対応するシンボルの型に静的にバインドすることです

たとえば、次のようになります。

非終端記号 があるとしますX。A B C

それらの名前/タイプは次のとおりです。

"X" Foo
"A" string
"B" string
"C" int

そして、文法では、生産があるかもしれません:

X -> A B C

そして、そのプロダクションのためにユーザーによって提供されるアクション関数があります:

Foo f(string A, string B, int C)

そのプロダクションが関数 f よりも削減されている場合、プロダクション ボディ パラメータを使用して呼び出す必要があります。f によって返された値は、そのシンボルが上位のリダクションで使用されたときに格納されます。

したがって、パーサー ジェネレーターに文法を指定するには、次のようなものを提供する必要があります。

（私は以下が無効であることを知っています）

struct Symbol
{
    string name;
    type T;
}

struct Production
{
    string head;
    vector<string> body;

    function<head.T(body[0].T, body[1].T, ..., body[n].T)> action;
}

struct Grammar
{
    vector<Symbol> symbols;

    vector<Production> productions;
}

そして、前の例を指定すると、次のようになります。

Grammar example =
{
    // symbols
    {
        { "X", Foo },
        { "A", string },
        { "B", string },
        { "C", int }
    },

    // productions
    {
        { 
            "X",
            { "A", "B", "C" },
            [](string A, string B, int C) { ... return Foo(...); }
        }
    }
}

もちろん、これは機能しません。型パラメーターとランタイムパラメーターをそのように混在させることはできません。

1つの解決策は、いくつかの一般的なベースを持つことです:

struct SymbolBase
{
    ...
}

template<class SymbolType>
struct SymbolDerived<SymbolType> : SymbolBase
{
    SymbolType value;
}

次に、次のタイプのすべてのアクション関数を作成します。

typedef function<SymbolBase(vector<SymbolBase>)> ActionFunction;

実行時に並べ替えます。しかし、これにより使用が難しくなり、すべてのキャストが遅くなります。コンパイル時に関数シグネチャをチェックして、メカニズムをユーザーから隠しておきたいと思います。

Symbol、Production、および Grammar の型を再構築して、法的な C++11 で伝えようとしている情報を保持するにはどうすればよいですか?

(はい、私は Boost Spirit とその友人を見てきました。これは素晴らしいフレームワークですが、再帰的降下であるため、1 回のパスで処理できる言語は LALR パーサーよりも少なく、バックトラッキングを使用するため、リダクション アクションが複数回呼び出されます。など）

4

1 に答える 1

1

私はまさにこの問題をいじっています。私が見てきた可能性は、うまくいくように見えますが、おそらくboost::variantまたはboost::anyなどのバリアントオブジェクトのスタックを使用することです。各リダクションはスタックから何が期待されているかを認識しているため、アクセスはタイプ セーフになります。残念ながら、型チェックは実行時に行われますが、非常に安価なはずです。これには、バグをキャッチするという利点があります:)。また、オブジェクトがスタックからポップされるときに、オブジェクトを正しく破棄します。

リクエストに応じて利用できるサンプル コードを PoC としてまとめました。リダクション ルールを記述するための基本的なスタイルは、次のようなものです。

parse.reduce<Expression(Expression, _, Expression)>
  ( [](Expression left, Expression right){
      return BinaryOperation(Operator::Times, left, right);
  });

これは次のルールに対応します。

expression: expression TIMES expression

ここで、BinaryOperationは AST ノード タイプであり、に変換可能でなければなりませんExpression。テンプレート引数Expression(Expression, _, Expression)は、型として表現されたプロダクションの左側と右側です。(2 番目の RHS 型は _ であるため、テンプレートはわざわざ値を削減規則に渡す必要はありません。適切なパーサー ジェネレーターを使用すると、そもそも句読点トークンをスタックにプッシュする理由さえ実際にはありません。)を使用して、タグ付き共用体Expressionとパーサー スタックのタグ付き型の両方を実装しましたboost::variant。これを試す場合は、バリアントを別のバリアントのオプション タイプの 1 つとして使用しても、実際には機能しないことを知っておく価値があります。最終的に、小さいユニオンを としてラップするのが最も簡単でしたstruct。また、再帰型に関するセクションも読む必要があります。

于 2012-12-22T07:17:01.067 に答える