先読み

先読みまたはルックアヘッド（英: Lookahead）は、アルゴリズムにおいて未処理の入力の一部を先に参照し、現在の処理での判断に利用することで効率化する方法。

先読みと遅延評価

先読みは、実際に必要になるまで計算を遅延させる遅延評価という技法と対照的である。どちらの技法も時間やメモリ消費量を節約する目的で使われる。先読みは、予め判断を正しく行うことで、後で無駄なバックトラッキングが発生しないようにする。ただし、そのために先読みのオーバーヘッドが若干かかることになる。遅延評価は即座に必要とされないアルゴリズム上の計算を後回しにすることで、時間とメモリ使用量を節約しようとする。遅延評価の応用例として、オペレーティングシステムでのデマンドページングや、コンパイラでの構文解析表の遅延作成がある。

何らかの探索が必要な場合、両方の技法が使われる。アルゴリズム上次に見るべき経路がわかっている場合、遅延評価を使って探索すべき経路をキューやスタックに保持する。次に見るべき経路がわかっていない場合、新たな経路が見るべき経路かどうかを判断するために先読みを使う。

コンパイラも両方の技法を使う。構文解析表を規則から作成する場合は遅延評価が行われ、入力を構文解析する場合には先読みが行われる。

探索問題における先読み

人工知能では、先読みは組合せ最適化の重要な要素であり、問題を表すグラフをどれだけ深く探索すべきかを示すものと言える。コンピュータチェスやコンピュータ囲碁などでは問題を表すグラフの先読みを制限する必要がある。素朴な幅優先探索を行うと、最新のコンピュータでもすぐに全メモリを消費してしまう。そのために先読みに制限を加えることで、アルゴリズムにかかる時間を注意深く制御する。先読みの制限が緩められると、それに対して指数関数的に処理時間が延びる。

より洗練された探索技法としてアルファ・ベータ法などは、部分木全体を考慮から除外することができる。このような技法を使う場合、先読みは単に量的に制限されるのではなく、深さを制限したり、何らかの平均値を制限する形で制限される。

構文解析における先読み

先読みは、コンパイラでの構文解析でも重要な概念である。構文解析器が次に適用すべき生成規則を決定する際に入力トークン列を何個か先読みする。

LL法、LR法、LALR法などの構文解析では、後に括弧つきで先読みするトークン数を記することが多い（LALR(1)など）。

多くのプログラミング言語は、限定的な先読み（1個が典型的）で構文解析できるよう設計されている。というのも先読みを制限した方が構文解析器が効率化されるためである。1990年、Terence Parr は博士論文でANTLRを作成し、この傾向に重大な変化をもたらした。ANTLRは、効率的な LL(k) 構文解析器を生成するパーサジェネレータであり、k として任意の固定値が可能である。

構文解析器は、各トークンを参照したときにとりうるアクションが限られている。

• shift - トークンをスタックに積み、後で reduce する。
• reduce - スタックからトークンを取り出し、生成規則を適用して構文要素を構築する。
• end - 構文解析終了（終了トークンを受け取ったとき）
• error - 構文規則にないトークンの並びが入力された場合
• conflict - shift すべきか reduce すべきか判断できない。また、reduce で適用可能な規則が複数あって判断できない場合もある。

先読みには次の2つの利点がある。

• conflict 発生時、構文解析器が正しい判断をするのを助ける。例えば if 文 は先読みすることで then 節や else 節が完了したことが容易にわかる。
• 状態数を大幅に減らすことができる。C言語で先読みしない構文解析器は約10,000の状態があるが、先読みするとこれを約300に減らせる。

例として、"1 + 2 * 3" という式を構文解析する場合を示す。この場合の生成規則（構文規則）は次の通り。

• Rule1: E → E + E （式は式と式の加算である）
• Rule2: E → E * E （式は式と式の乗算である）
• Rule3: E → number （式は単なる数値である）
• Rule4: + は * より優先順位が低い。

APLなどの一部の例外を除いて、一般に加算よりも乗算が優先順位が高い。従って、上記の例は (1 + (2*3)) と解釈するのが正しい。上記のRule4は生成規則ではなく、意味論的規則である点に注意されたい。これを生成規則として表すことも可能である。しかし、意味論的規則が全て生成規則に変換できるわけではない。

単純な先読みのない構文解析器は次のように動作する。

1. reduce - Rule3 に基づき '1' を式 E にする。その E はスタックに置かれる。
2. shift - 入力 '+' から Rule1 が適用可能となることを予測しつつ、スタックに退避する。
3. reduce - Rule3 に基づき '2' を式 E にする。
4. reduce - スタック上の E+ と新たな入力 E に対して Rule1 を適用して E とする。
5. shift - 入力 '*' から Rule2 が適用可能となることを予測しつつ、スタックに退避する。
6. reduce - Rule3 に基づき '3' を式 E にする。
7. reduce - スタック上の E* と新たな入力 E に対して Rule2 を適用して E とする。

これによって生成される構文木とコードは、Rule4 が考慮されていないため正しくない。

先読みなしで正しく構文解析するには、次のような対処法がある。

• ユーザーが括弧付きで式を書く。これが不可能なことも多い。
• 構文解析器にバックトラック機能を追加し、規則違反が発生したときなどに再試行する。同様の手法はLL法で使われている。
• reduce 実施を遅延させるような論理を導入し、どちらの規則を先に reduce させるのが適切かを規則に照らして判断する。LR法がこのような手法を採用している。これによって正しい構文解析が可能となるが、状態数が増え、スタックも深くなる。

先読みのある構文解析器では、次のように動作する。

1. shift - 入力 '1' を Rule3 が適用されることを予想しつつスタックに退避する。即座には reduce しない。
2. reduce - '+' を先読みして、スタック上の '1' を Rule3 に基づいて E に reduce する。規則上、'+' の前には E しかないため。
3. shift - 入力 '+' を Rule1 が適用されることを予測しつつスタックに退避する。
4. shift - 入力 '2' を Rule3 が適用されることを予測しつつスタックに退避する。
5. reduce - '*' を先読みして、スタック上の '2' を Rule3 に基づいて E に reduce する。規則上、'*' の前には E しかないため。
6. ここまでで、スタック上には E + E があり、現在の入力は '*' である。従って、Rule1 を適用する reduce を行うという選択肢と、Rule2 に基づいて shift を行うという選択肢がある。Rule4 によれば '*' の方が優先順位が高いので、Rule2 を予測して '*' を shift する。
7. shift - 入力 '3' を Rule3 が適用されることを予測しつつスタックに退避する。
8. reduce - 先読みすると入力が終了しているので、スタック上の '3' を Rule3 に基づいて E に reduce する。
9. reduce - スタック上の E * E を Rule2 に基づき E に reduce
10. reduce - スタック上の E + E を Rule1 に基づき E に reduce

これによって生成される構文木は正しく、先読みしない場合よりも効率的に得られる。以上の方式はLALR法に基づいている。

ウェブ高速化ソフトにおける先読み

ウェブ閲覧高速化ソフトにおいては、見ているページ内のハイパーリンクが示す先をあらかじめ読み込んでおくこと。

一般用法における先読み

• 先を読むこと。
  • 発言を最後まで言う前に、後ろの文章を予想すること。早押しクイズで、問題文の読まれていない部分を推理する場合などにおいても使われることがある。