1

C がアセンブリに変換され、次にアセンブリがマシン コードに変換されることを学びました。また、ポインタやループなどの基本的な C 構造を 32 ビット MIPS アセンブリに変換する方法も学びました。しかし、たとえばCの正規表現をアセンブリに変換する方法を学びませんでした。レシピはありますか?

4

3 に答える 3

5

Cは正規表現をサポートしていません。組み立てもしません。パターンマッチング用のアルゴリズムコードを作成する必要があります。その後、アセンブリ/マシンコードにまだ含まれていない場合は、変換/コンパイルします。魔法はありません。

于 2012-09-13T01:17:53.120 に答える
4

正規表現をアセンブリ言語に翻訳することは、数十年前に時代遅れになっているようです。代わりに、最近では、通常、決定性有限オートマトン(DFA)にコンパイルされ、多くの場合、非決定性有限オートマトン(NFA)として中間ステップが使用されます。これらの用語に慣れていない場合は、以下を参照してください。

正規表現に対応するNFAは、非常に簡単に作成できます。正規表現の各ポイントを状態と見なし、その状態から次の状態への遷移として、一致して正規表現の次のポイントに移動できる文字のセットを考慮してください。

PCREを含む他の一般的な正規表現エンジンは正規表現をまったくコンパイルしませんが、バックトラッキングマッチャーを使用します。これは書き込みが簡単ですが、メモリ使用量が病理学的に悪いです(実際の関数として実装すると、多くの再帰呼び出しフレームがスタックオーバーフローにつながります)呼び出し)および病理学的に悪いbig-Oパフォーマンス(指数関数的な時間になる可能性があります)。

于 2012-09-13T01:18:37.083 に答える
3

一般に、正規表現の実装方法によって異なります。たとえば、次のことができます。

  • PCREやPOSIX正規表現などを使用します。この場合、そのAPIへの関数呼び出しは、アーキテクチャ/ ABIに固有の呼び出し規約を使用して適切な呼び出しを行うことにより、マシン(アセンブリ)コードに単純に変換されます。
  • のようなツールを使用しますflex。この場合、ツールは、通常はテーブルとステートマシンの形式で、大量のCコードを生成し、このコードはコンパイラーを使用して変換されます。

ある種のアドホック正規表現解析スキームを実装する場合、それは単にコンパイラーがコード用に生成するものになります。

于 2012-09-13T01:19:19.843 に答える