9

好奇心から、C++ の構文解析に関する「理論上の」結果とは何かを知りたいと思っていました。

n をプロジェクトのサイズとします (たとえば、LOC では、big-O を扱うため、あまり重要ではありません)。

  • C++ は O(n) で解析されますか? そうでない場合、複雑さは何ですか？
  • C (または Java またはその文法の意味でより単純な言語) は O(n) で解析されますか?
  • C++1x では、解析がさらに困難になる新機能が導入されますか?

参考になれば幸いです！

4

3 に答える 3

17

「解析」という用語は、質問の目的のために、さまざまな人によってさまざまな方法で解釈されていると思います。

狭義の技術的な意味では、構文解析とは単にソース コードが文法に一致していることを検証することです (または、ツリーを構築することさえあります)。

解析する特定のシンボルの意味を解決する必要があるため、(この意味で) C++ をまったく解析できないという、かなり広く普及している定理があります。その民俗定理は単に間違っています。

これは、「弱い」(LALR またはバックトラッキング再帰降下) パーサーの使用から発生します。パーサーは、テキストの局所的にあいまいな部分のいくつかの可能なサブパースの間違った選択にコミットした場合 (このSO スレッドで例について説明します）、時々その選択をすることによって完全に失敗します。このようなパーサーを使用する人がジレンマを解決する方法は、構文解析が行われるときにシンボル テーブル データを収集し、追加のチェックを構文解析プロセスにマッシュアップして、そのような選択に遭遇したときにパーサーに正しい選択を強制することです。これは、名前と型の解決が解析と大幅に絡み合うという犠牲を払って機能し、そのようなパーサーの構築を非常に困難にします。しかし、少なくとも従来の GCC では、解析に線形時間である LALR を使用していました。パーサーが行う名前/型のキャプチャを含めても、それほどコストがかかるとは思いません (解析後にやるべきことがもっとあります。彼らがすべてを行うとは思わない）。

「純粋な」 GLR 解析テクノロジを使用して行われた C++ パーサーの実装が少なくとも 2 つあります。これは、解析が局所的にあいまいである可能性があることを単に認め、コメントや大きなオーバーヘッドなしで複数の解析をキャプチャします。GLR パーサーは、局所的なあいまいさがない線形時間です。それらはあいまいな領域ではより高価ですが、実際問題として、標準 C++ プログラムのほとんどのソース テキストは「線形時間」の部分に分類されます。したがって、実効レートは線形であり、あいまいさを捉えています。実装されたパーサーは両方とも、解析後に名前と型の解決を行い、矛盾を使用して不正確なあいまいな解析を排除します。(2 つの実装は、Elsaと私たちの (SD の) C++ フロント エンドです). Elsa の現在の機能について話すことはできませんが (何年も更新されていないと思います)、私たちのものは C++11 のすべてを実行します [2015 年 1 月編集: C++14 が完全になりました: 2017 年 10 月編集: C が完全になりました++17] GCC および Microsoft バリアントを含む)。

言語が拡張的に任意の文字列のセットとして定義されているというハードなコンピューター サイエンスの定義を採用し (文法はそれを意図的にエンコードするための簡潔な方法であると想定されています)、解析を「プログラムの構文が正しいことを確認する」として扱う場合、 C++ では、テンプレートを展開して、それぞれが実際に完全に展開されることを確認します。テンプレートにはチューリング マシンが隠されているため、理論上、C++ プログラムが有効であることを確認することは不可能です (時間制限はありません)。実際のコンパイラ (標準を尊重する) は、実行するテンプレートの展開量に固定の制約を課し、実際のメモリもそうであるため、実際には C++ コンパイラは終了します。しかし、この意味でプログラムを「解析」するには、任意の時間がかかる場合があります。そして、それがほとんどの人が気にかけている答えだと思います。

実際問題として、ほとんどのテンプレートは実際には非常に単純であるため、C++ コンパイラは平均して他のコンパイラと同じくらい速く終了できると思います。チューリングマシンをテンプレートに書くほど狂った人だけが、深刻な代償を払います。(意見: 価格は実際には、コンパイラの実行コストではなく、複雑なものをテンプレートに押し込む概念的なコストです。)

于 2010-11-13T16:38:54.393 に答える
1

ほとんどの言語とは異なり、同時にセマンティック分析を実行しないと構文を分析できないため、C++ を「解析するだけ」できるかどうかを判断するのは困難です。

于 2010-11-13T11:50:28.313 に答える
1

「解析済み」の意味によって異なりますが、解析にテンプレートのインスタンス化が含まれていると想定されている場合は、一般的ではありません。

[例を読みたくない場合のショートカット - テンプレートは十分に豊富な計算モデルを提供するため、それらをインスタンス化することは、一般的に停止型の問題です]

template<int N>
struct Triangle {
    static const int value = Triangle<N-1>::value + N;
};

template<>
struct Triangle<0> {
    static const int value = 0;
};

int main() {
    return Triangle<127>::value;
}

明らかに、この場合、コンパイラは三角形の数に単純なジェネレータ関数があることを理論的に認識し、それを使用して戻り値を計算できます。しかし、それ以外の場合、インスタンス化Triangle<k>には O(k) 時間がかかりk、型の限界まで、このプログラムのサイズが急速に大きくなる可能性がありintます。

【ショートカット終了】

Triangle<127>::valueがオブジェクトなのか型なのかを知るために、実際のコンパイラはインスタンス化する必要があります (繰り返しになりますが、この場合、 はすべてのテンプレートの特殊化でオブジェクトとして定義されているTriangle<127>ため、ショートカットを取ることができますが、一般的にはそうではありません)。シンボルがオブジェクトを表すか型を表すかは、C++ の文法に関連しているため、C++ を「解析する」にはテンプレートのインスタンス化がvalue必要であると私は主張するでしょう。ただし、他の定義は異なる場合があります。

実際の実装はテンプレートのインスタンス化の深さを恣意的に制限するため、Big-O 分析は無関係になりますが、いずれにせよ実際の実装には自然なリソース制限があり、Big-O 分析も無関係にするため、私はそれを無視します...

recursive を使用すると、同様に難しいプログラムを C で作成できると思いますが#include、解析ステップの一部としてプリプロセッサを含めるつもりかどうかはわかりません。

それとは別に、C は、他の多くの言語と同様に、O (あまり多くはない) 構文解析を行うことができます。デビッドが彼の答えで言っているように、一般に厳密な O(1) 最悪のケースを制限することはできないため、O(n) は少し楽観的かもしれません。アセンブラーでさえ、ラベルのシンボルを検索する場合があります。しかし、たとえば動的言語では、実行時に行われる可能性があるため、解析のためにシンボル検索を行う必要さえありません。パーサーが行う必要があるのは、どのシンボルがキーワードであるかを確立し、何らかのブラケット マッチングを行う言語を選択する場合、Shunting Yard アルゴリズムは O(n) であるため、希望があります。

于 2010-11-13T14:21:29.077 に答える