1

では、Java コンパイラのようなものを作成する演習を行います。あまり詳しくは触れません。基本的に、閉じ括弧を識別できる正規表現を使用できるかどうかを知りたいです。たとえば、これは合法的な入力になります

void foo(){
   asd
}

そして、これはありません

void foo(){
   asd
   if (){
      asd
   }

ご覧のとおり、2 つのオープナー ({) に対して 1 つのクローザー (}) しかないため、無効な入力になります。正規表現を使用して、出現回数が一致することを識別する方法はありますか?

4

4 に答える 4

5

正しいかっこを正規表現でチェックすることはできません。これは、開いているかっこの数などを追跡する必要があるためですが、正規表現ではそれができません。

特にコンパイラを構築したい場合は、形式言語理論に慣れることをお勧めします。たとえば、このウィキペディアの記事では、形式言語理論のコンテキストでの正規表現に関する洞察が得られます: http://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory

于 2013-05-26T16:14:38.013 に答える
1

最も単純な（単純化された？）答え：

文法を解析する場合、通常、何らかの種類のスタックを (直接的または間接的に) 維持します。開き括弧ごとに、要素をスタックにプッシュします。閉じ括弧が表示されると、スタックを調べて最後の開き括弧と一致するかどうかがわかります。

また、括弧を開く方法はたくさんあることに注意してください。「{」はその 1 つにすぎません。 したがって、スタックは、開いた括弧の数だけでなく、特定の解析状態で有効な閉じ括弧のタイプも示します。

于 2013-05-26T16:19:09.847 に答える
1

標準正規表現は正規言語の文法のみを表現できます。正規言語は、決定論的有限オートマトンによって受け入れられる言語のクラスとまったく同じです。DFA には有限数の状態しかありませんが、括弧は無期限にネストできます。ネストのレベルが無限になる可能性のある言語は正規言語ではなく、正規表現だけでは解析できません。

ほとんどの言語の正規表現ライブラリは「ただの」標準正規表現ではなく、一部の非正規言語を解析できますが、通常、そのためには非常に複雑な表現が必要です。

一般に、ブラケット言語の適切なネストを確認するには、文脈自由文法(CFG) パーサーが必要です。CFG は正規表現より厳密に強力です (つまり、文法が RE で表現できる場合、それは CFG で表現できますが、その逆は必ずしも真ではありません)。

于 2013-05-26T16:36:46.630 に答える
0

C を使用している場合、適切なツールはトークン用の Flex と文法用の Bison です。

JFlex と Cup。Java で実行する場合は、プログラム構造を改善するために Visitor paddern も使用します。

于 2013-05-26T16:20:51.697 に答える