0

学校のプロジェクトでは、簡略化された「偽の」プログラミング言語を含むテキスト/ソース ファイルを解析してASTを構築する必要があります。私は を調べましたがboost::spirit、これはグループ プロジェクトであり、追加のライブラリを学習することに消極的であるように思われるため、講師/TA は C++ で簡単なライブラリを作成することを推奨しました。その道を行こうと思いました。そこにいくつかの例や開始方法に関するアイデアはありますか? 私はいくつかの試みをしていますが、まだ実際には成功していません...

行ごとの解析

  • 一連の正規表現 (プロシージャ/関数宣言用に 1 つ)、代入用に 1 つ、while 用に 1 つなどを使用して各行をテストします。
    • ただし、1 行に複数のステートメントがないことを前提とする必要があります。a=b;x=1;
  • コンテナステートメント、手順、whiles などに到達したら、indent. したがって、ネストされたすべてのステートメントはこの下に置かれます
  • 到達し}たら、インデントを減らします

より良いアイデアや提案はありますか？解析する必要があるサンプルコード (ここでは非常に単純化されています ...)

procedure Hello {
    a = 1;
    while a {
        b = a + 1 + z; 
    }
}

別のアイデアは、ファイル全体を文字列に読み取り、トップダウンに移動することでした。すべてのプロシージャに一致し、すべてをキャプチャしてから{ ... }、一致するステートメント (で終わる;) または containerを開始しwhile { ... }ます。これは PEG の動作に似ていますか? ただし、ファイル全体を読み取る必要があります

4

2 に答える 2

1

マルチパスは物事をより簡単にします。最初のパスで、「=」、「abababa」、引用符で区切られた文字列、または空白のブロックなどのトークンに分割します。破壊的ではありません (元のデータを保持します) が、物事を単純なチャンクに分解し、トークンが何であるかを説明する小さな構造体または列挙型 (つまり、空白、文字列リテラル、識別子型のものなど) を持っている可能性があります。 .

したがって、サンプル コードは次のようになります。 ) 操作(;) 空白(\n\t) など

これらのトークンには、行番号と行のオフセットも格納することができます (これは、後でエラー メッセージを生成するのに役立ちます)。

簡単なテストは、これを元のテキストに戻すことです。もう 1 つの簡単なテストは、html などできれいに印刷されたバージョンをダンプすることです (ここでは、空白をピンクの背景、ライト ブルーの識別子、ライト グリーンの操作、ライト オレンジの数字) に色付けし、トークナイザーが作成されているかどうかを確認します。検出。

さて、あなたの言語は空白を区別しないかもしれません。その場合は、空白を破棄してください。//(コメントがいつ終了するかを知るために改行が必要なため、C++ はそうではありません)

(注: プロの言語パーサーは、より高速であるため、可能な限りワンパスに近くなります。しかし、あなたは学生であり、目標はそれを機能させることです。)

これで、そのようなトークンのストリームができました。この時点で、たくさんのアプローチがあります。いくつかの深刻な解析チョップを引き出して、それらを解析する CFG を構築できます。(CFGって知ってる? LR(1)? LL(1)?)

より簡単な方法は、もう少しアドホックに行うことです。operator({) を探し、カウントアップおよびカウントダウンして一致する operator(}) を見つけます。名前 (次のトークン) とブロック ({) を期待する言語キーワード (手続きなど) を探します。本当に単純な言語のアドホック パーサーはうまく機能する場合があります。

パーサーが非常に単純なPDAで構成されている、とてつもなく単純な言語に対して、私はまさにこれを行いました。それはあなたのために働くかもしれません。またはそうではないかもしれません。

于 2012-10-29T02:21:38.467 に答える
1

あなたがPEGについて言及したので、私は私のオープンソースプロジェクトを投入したいと思います: https://github.com/leblancmeneses/NPEG/tree/master/Languages/npeg_c++

C++ バージョンをエクスポートできるビジュアル ツールは次のとおりです。

ルール文法のドキュメント: http://www.robusthaven.com/blog/parsing-expression-grammar/npeg-dsl-documentation

私が自分の言語を書いていたら、System.Linq.Expressions にある端末/非端末を見て、文法規則の素晴らしい出発点になると思います。

http://msdn.microsoft.com/en-us/library/system.linq.expressions.aspx

System.Linq.Expressions.Expression
System.Linq.Expressions.BinaryExpression
System.Linq.Expressions.BlockExpression
System.Linq.Expressions.ConditionalExpression
System.Linq.Expressions.ConstantExpression
System.Linq.Expressions.DebugInfoExpression
System.Linq.Expressions.DefaultExpression
System.Linq.Expressions.DynamicExpression
System.Linq.Expressions.GotoExpression
System.Linq.Expressions.IndexExpression
System.Linq.Expressions.InvocationExpression
System.Linq.Expressions.LabelExpression
System.Linq.Expressions.LambdaExpression
System.Linq.Expressions.ListInitExpression
System.Linq.Expressions.LoopExpression
System.Linq.Expressions.MemberExpression
System.Linq.Expressions.MemberInitExpression
System.Linq.Expressions.MethodCallExpression
System.Linq.Expressions.NewArrayExpression
System.Linq.Expressions.NewExpression
System.Linq.Expressions.ParameterExpression
System.Linq.Expressions.RuntimeVariablesExpression
System.Linq.Expressions.SwitchExpression
System.Linq.Expressions.TryExpression
System.Linq.Expressions.TypeBinaryExpression
System.Linq.Expressions.UnaryExpression
于 2012-10-29T18:34:51.413 に答える