最大限のムンク

コンピュータプログラミングとコンピュータサイエンスにおいて、「最大消費」または「最長一致」とは、何らかの構造を作成するときに、利用可能な入力を可能な限り多く消費するという原則です。

この用語の最も古い使用例は、RGG Cattellの博士論文^[1]で、コンパイラ用コードジェネレータの自動導出について述べられたものです。

例えば、多くのプログラミング言語の語彙構文では、入力ストリームから可能な限り多くの文字でトークンを構築する必要があります。これは、(1つ以上の小文字)などのよく使用される正規表現に固有の曖昧さの問題を解決するために行われます。 ^[2][a-z]+

この用語は、コンパイラの命令選択段階で「タイリング」の方法を説明するためにも使用されます。これは、中間言語でプログラムを表す構造化ツリーを線形マシン コードに変換する方法を決定するものです。サブツリー全体が 1 つのマシン命令に変換される可能性があり、問題はツリーを 1 つのマシン命令を表す重複しない「タイル」に分割する方法です。効果的な戦略は、任意の時点で可能な限り最大のサブツリーのタイルを作成することです。これは「最大マンチ」と呼ばれます。^[3]

状況によっては、「最大限に食べる」ことが望ましくない、または直感に反する結果につながることがあります。たとえば、Cx=y/*z;プログラミング言語では、 (空白のない)文はおそらく構文エラーになります。これは、文字シーケンスが (意図せず) コメントを開始し、コメントが終了していないか、または後の無関係な実際の/*コメントの終了トークンによって終了しているためです (C ではコメントはネストされません)。文で実際に意味されていたのは、 の値をポインタを逆参照して取得した値で割った結果を変数に割り当てることでした。これは有効なコードです。これは、空白を使用するか、 を使用して記述できます。 */xy zx=y/(*z);

C++の別の例では、テンプレートの特殊化の構文で「山括弧」文字<とが使用されていますが、連続する 2 つの文字は右シフト演算子として解釈されます。^[4] C++11 より前のバージョンでは、次のコードは、2 つの右山括弧トークンではなく右シフト演算子トークンが検出されるため、解析エラーが発生します。 >>>>

    std :: vector < std :: vector < int >> my_mat_11 ; //C++03 では誤りですが、C++11 では正しいです。std :: vector < std :: vector < int >> my_mat_03 ; //C++03 または C ++ 11 のいずれかで正しいです。  
       

2011 年 8 月に採用された C++11 標準では、右シフトトークンが一対の右山括弧 ( Javaの場合と同様) と同義として受け入れられるように文法が修正されました。これにより文法は複雑になりますが、最大マンチ原則を引き続き使用できます。いずれにしても、テンプレートに出現する可能性のあるシーケンスを処理するために、最大マンチ規則の例外を追加する必要がありました。その場合、シーケンスの後にまたはが続かない限り、文字はトークンの一部ではなく、独自のトークンとして解釈されます。 <:::><<:

プログラミング言語の研究者たちは、最大マンチの原則を他の語彙の曖昧さ解消戦術に置き換えたり、補足したりすることでも対応してきました。1 つのアプローチは、「フォロー制約」を利用することです。これは、最長一致を直接取得するのではなく、有効な一致の後に続くことができる文字にいくつかの制限を課します。たとえば、[a-z]+文字列の一致の後にアルファベット文字が続かないように規定すると、その正規表現で最大マンチと同じ効果が得られます。^{[5] (正規表現のコンテキストでは、最大マンチの原則は}貪欲と呼ばれ、怠惰と対比されます。) 別のアプローチは、最大マンチの原則を維持しながら、コンテキストなどの他の原則に従属させることです (たとえば、Java の右シフト トークンは、ジェネリック式のコンテキストでは一致しません。これは構文的に無効です)。^[6]

• Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2007)。コンパイラ：原則、テクニック、ツール（第2版）。ボストン：Addison- Wesley。ISBN 978-0-321-48681-3。
• Page, Daniel (2009)。「コンパイラ」。コンピュータアーキテクチャの実践入門。コンピュータサイエンスのテキスト。ロンドン: Springer。pp . 451–493。doi :10.1007 / 978-1-84882-256-6_11。ISBN 978-1-84882-255-9。
• ヴァンデンブランド、マークGJ。シェーダー、ジェローン;ヴィンジュ、ユルゲン J.ヴィッサー、イールコ (2002)。 「スキャナレス汎用 LR パーサー用の曖昧さ回避フィルター」。コンパイラの構築。コンピューターサイエンスの講義ノート。 Vol. 2304/2002。ベルリン/ハイデルベルク：シュプリンガー。 21–44ページ。土井：10.1007/3-540-45937-5_12。ISBN 978-3-540-43369-9. ISSN  0302-9743.
• Vandevoorde、Daveed (2005 年 1 月 14 日)。 「直角ブラケット」。2010 年3 月 31 日に取得。
• Van Wyk, Eric; Schwerdfeger, August (2007). 「拡張可能な言語を解析するためのコンテキスト認識スキャン」。第6 回国際ジェネレーティブプログラミングおよびコンポーネントエンジニアリング会議の議事録。ニューヨーク: ACM。pp. 63–72。doi : 10.1145 /1289971.1289983。ISBN 9781595938558. S2CID  9145863。