2

私は現在、交差を行う方法を知っていることを除いて、2つの通常の言語の交差をテストするに似た問題を解決しようとしていますが、追加の要件があります。

私が使用する交差ロジックは、NFA を DFA に変換するための Dragon Book のアルゴリズムですが、同時に 2 つの NFA で実行されます。すべての DFA は NFA であるため (ただし、非決定性はほとんどありません)、必要に応じてこれを繰り返して交差を増やすことができます。

私の問題は、正規表現の 1 つに、新しい正規表現の一部としてさらに使用できるグループがあることです。具体的には：

bin/x86/a.out: obj/x86/.*\.o

obj/{[a-zA-Z0-9]+}/{.*}.o: src/\2.c

最初の行の最後に、x86 ターゲットのすべてのオブジェクトに一致する正規表現があります。2 行目には、ビルド行の可能性を指定する正規表現があります。これは、最初のグループを固定の "x86" に一致させ、2 番目のグループをその後に任意の文字列に一致させる必要があります。この例では、最初の一致はまだ使用されていませんが、取得できるはずです。マッチングが確実に終了するようにする (そして再帰ルールを許可する) ために、最初の正規表現から取得した情報を 2 番目の正規表現のマッチングに使用したいと考えています。ルールは、1 行目から 2 番目の正規表現を取得し、2 行目から最初の正規表現を取得して、2 つの交差 (交差の結果の DFA) が受け入れ状態であるかどうかを判断することによって選択されます。そうであれば、両方が解析できる文があり、したがってグループが取ることができるいくつかの値があります。

一般に、最初の正規表現から情報を抽出して、2 番目の正規表現のグループと照合することは可能ですか?

一般的でない場合、どのような種類の制限を追加する必要がありますか?

4

2 に答える 2

0

Makefilesが正規表現をサポートしていないのに、なぜあなたの例はMakefileルールのように見えるのですか？

それが私が作ろうとしているものだからです（しゃれは意図されていません）。

どの正規表現ライブラリを使用していますか？

まだありません。この質問の出力に基づいて、自分で書くことを検討しています。これが不可能な場合は、これをサポートする既存のものを使用する場合があります。これが理論的に可能であれば、私はこれを正確に実行するために独自に開発し、意図したとおりにアプリケーションを作成します。

式の交差の別の方法である先読み式をサポートするものもあります

交差点の背後にある考え方は、一般的で、複数の変化する左側の部分を含むことができるルールを定義することです（通常のメイクファイルでは％を使用しますが、複数のバリエーションポイントがある場合は、ある種の再帰的なメイクを行う必要はありません） -プラットフォーム、ビルドタイプ、ファイル名など）。グループの2番目の正規表現を考慮に入れることができない場合、再帰は各ステップ/レベル間で変更がないため、そのようなルールを再帰的に使用することはできません。それは一般性を低下させますが、それでも許容できます。それでも、（つまり、一般的に実行できるか）に対する答えを知ることは興味深い質問であり、正規表現ライブラリの要件を決定することになります。

（Cookieを紛失し、アカウントがマージされるのを待っているため、元の作成者として投稿されていません）。

于 2010-05-28T14:24:20.600 に答える
0

バックティックは言語を非正規化すると信じているので、有限オートモートンに変換することはできません。

于 2010-05-28T12:03:12.457 に答える