コンパイル理論では、コンパイル・プロセスは通常、字句解析、構文解析、意味解析、最適化、コード生成の5つの主要な段階に抽象化されます。これらの5つの段階はUnixのパイプライン・モデルに似ており、前の段階の出力が次の段階の入力として使用されます。このうち、字句解析は、入力ソース・コードのテキスト・ストリームに基づいて、単語をセグメンテーションし、カテゴリを識別し、次のような字句要素のストリームを生成します：
int a = 10;
字句解析の結果、[, , , ]が得られ、その後の構文解析の段階で、これらの字句要素に従って対応する構文規則が照合されます。私がコンパイルの原理を勉強していたころの教科書では、字句解析の導入は正規表現が中心でした。例えばC言語では、変数名は「文字、数字、アンダースコアを含み、文字またはアンダースコアで始まる」という規則があり、[a-zA-Z][a-zA-Z0-9]*という正規表現で表すことができます。しかし、実際には、主流の言語であろうと、私自身が設計したDSLであろうと、字句解析のための正規表現では単純に表現できない例が多数あることがわかりました。C++98テンプレートの例を見てみましょう：
map<int, vector<int>>
上記のコードは、C++98コンパイラによって構文エラーとして報告されます。なぜなら、C++98コンパイラは">>"を2つのモード右括弧の代わりにビット単位の右シフト演算子として認識するからです。
map<int, vector<int>>
このC++テンプレートに加え、古典的なFORTRAN言語の構文規則は、私の知る限り、さらに字句の曖昧さが激しいです。
この種の問題の根源は、字句解析が単純な字句規則に基づいているため、文法的な情報をすべて持っておらず、字句のあいまいさを文法規則の高いレベルで排除しなければならないことにあると思います。そのため、私自身のDSLをいくつか設計したときに、字句解析と構文解析を単純にひとつにまとめました。これは、古典的な字句要素のレベルではなく、文字のレベルで構文を解析させることに等しく、スキャナレスパーシングと呼ばれています。TeX、Wiki、Makefile、Perl 6などがその例です。
スキャナレス構文解析のアプローチは、字句規則が曖昧さを解消できないという事実を補うものですが、同時に字句解析と構文解析の単純明快なパイプライン構造を破壊し、一般に実装と理解の複雑さを増大させます。加えて、C++のような大規模な言語では、字句解析から始めると、曖昧性に1つでも遭遇した場合にスキャナレス・パーシングに切り替えるのが億劫になります。この問題は長い間私を悩ませてきましたが、満足のいく解決策を見つけたのはつい最近のことです。">>"を例にとると、C++11ではスペースが使用できないため、C++11コンパイラはこの字句のあいまいさをどのように処理するのでしょうか？答えは、字句解析の段階では「>>」をうまく解析できないので、まったく解析せず、「>」「>」の解析だけを構文解析に任せ、字句のあいまいさのない他の単語は解析します。そして、字句のあいまいさのない残りの単語は文法パーサーに任せます。この方式を知ったとき、私は思わず「すばらしい」とため息をつきました！理論的には、字句解析は何もできませんが、すべての文字が一つずつ構文解析器に行っても問題はありません。したがって、単純に字句解析が確実な部分のみを行い、構文解析器に解決できないようにすることで、パイプラインの構造を維持するだけでなく、字句のあいまいさを解決することができます。
C++11仕様の問題の定義をもう一度見てみましょう：
|
ご覧のとおり、C++11では、字句解析器は">>"を2つの">"として直接構文解析器に渡します。lis 構文にマッチする場合、**** ">" シンボルは直接テンプレートの終端記号とみなされ、greater than や displacement シンボルではありません。この定義に基づいて例を作ってみました：
template<int N>
class Foo {
};
Foo<3>>1> foo;
この例は、">>"が置換操作として解釈されるC++98では正しくコンパイルされますが、C++11ではコンパイルされません。の終端として解釈されるためです。C++11 でコンパイルするには、括弧を明示的に追加する必要があります：
Foo<(3>>1)> foo;
