字句解析 (じくかいせき、) とは、広義の構文解析の前半の処理で、自然言語の文やプログラミング言語のソースコードなどのベタな文字列を解析して、後半の狭義の構文解析で最小単位（終端記号）となっている「トークン」の並びを得る手続きである。字句解析を行うプログラムは字句解析器である。自然言語の字句解析については形態素解析を参照。まずトークンの必要性について説明する。たとえばソースコード中の「codice_1」という記述において「let」というキーワードや「100」という数字列は、それでひとつの意味を持つカタマリであり、それ以上細かく意味を持たない。このようなカタマリのことを「トークン」という。また codice_2 と codice_3 の間にある空白など一般に空白類は、意味があるとしても、それがないと繋がってしまう場合に切り離す以上の意味は普通は無く、構文規則には通常そういったものは含めない。他にも、「codice_4」といったようなコメントや「codice_5」のような文字列リテラルなどのようなものも、入力を最初に処理する段階でひとかたまりとしてしまったほうが扱いやすい。コメントの場合はそのまま捨ててしまうこともある。また「100」に、数値として整数の100という値を、この段階で与えてしまったほうがやはり扱いやすい。ただし、Parsing Expression Grammar（PEG）のように、字句の規則も構文規則と一緒に扱ってしまうことも多い手法もあり、「字句解析」と(狭義の)「構文解析」という分担は絶対のものでもない。また実際のC言語の処理系では、言語処理系本体の前にプリプロセッサによってもトークンとしての扱いがある（プリプロセッサトークン）。C言語での文 "sum=3+2;" を考えてみよう。これは、次の表のようにトークン化される。構文解析と同様、字句解析にも字句解析器の生成系がある。古くから広く使われているツールに lex がある。lex では、各種のトークンの字句規則を正規表現で記述する。入力がどの規則にもマッチしないようであればエラーとする。字句解析の次には構文解析が行われ、その後は言語処理系本体の処理となる。例えば、"46 - number_of(cows); " という計算式を表すテキストを考えてみよう。このテキストは "46"、"-"、"number_of"、"("、"cows"、")"、";" のように分解される。字句解析器は "46" を「数値」トークン、"-" を「文字」トークン、"number_of" を独立したトークンとする。C言語のような言語では、";" も特別な意味を持つ（言語によっては、単なるセパレータとして空白と同様の捨ててしまってもよいものとして扱えるかもしれないが、C言語の場合には構造体の宣言の直後に、返却値の型を省略した関数定義がある場合、前者の最後の ";" が無いと、その構造体を返却値の型とする関数を定義していることになってしまう、といった場合がある、ということ）。トークンはトークンとして認識されるだけの段階では妥当性は必ずしも考慮されない。例えば、上記の例で "cows" や "number_of" は（おそらく）その言語にとっては意味がないが、トークンとしては問題ない（たとえば数値の値が、その言語で扱えるいかなる型がサポートする範囲よりも大きい、など、エラーにすることもある）。一般に、文字列をなめるような処理をするものをスキャナという。字句解析の場合、文字列から、1個のトークンになるような部分文字列を切り出す部分をスキャナとして分けて考える場合がある。スキャナはある種の有限状態機械にモデル化できる。その有限状態機械は、それが処理する任意のトークンに含まれる文字の考えられる並びに関するルールを元に生成される。ここでいうルールとは例えば、「整数」トークンは任意個の数字の並びである、といったようなものである。プログラミング言語では、一般に、空白でない先頭の文字の種類によって、そこから始まるトークンの種類が類推できるよう設計され、その後の文字の並びはそのトークンとして受理できない文字が出てくるまでひとまとめとして処理される（最長一致の規則）。言語によっては、規則がもっと複雑で、複数個の文字について戻るようなバックトラッキングが必要になることもある。狭義の正規表現（詳細に言うと、いわゆる非欲張り(non-greedy)量指定子が無い正規表現）による表現が面倒な字句規則の代表例に、C言語の「codice_6」のようなコメントがある。ルールを直感的に言明すると「コメントには任意の文字が使えるが、"*/" という並びが現れたらそこで終わる」というものであるが、これを何も考えずにそのまま正規表現にしてしまうと、正規表現の * が最長一致（欲張り(greedy)な量指定子）であるために、「ソースコード中に現れる最初のコメントの開始から、ソースコード中に現れる最後のコメントの終了」にマッチしてしまう。正規表現に非欲張り量指定子か先読みがあればこれに対し正しい規則を書くのは簡単だが、無い場合は不可能ではないものの、その規則は読みやすいものではない。コメントの例の場合は、手書きの解析器であればそこだけアドホックにちょっと先読みすれば簡単に済むが、こういったパターンが意外とあることも、手書きが選ばれる理由のひとつである。また、JavaのGenericsやC++のテンプレートなどの字句解析で「codice_7」という並びが現れうることも、悩ましい点のひとつである（C++でテンプレートが実装された初期の頃は、コードを書く側が空白を入れて分割しなければならないとしていた）。本格的な処理系では往々にして、こういった場合への対処のために後段からの情報を必要とし、実装がややこしいものになりやすい。トークン化は、スキャナによって得られた部分文字列に、トークンの種別の情報を付け（この部分の仕事は、実際のところスキャナによって適合するルールが選ばれた時点でほとんど済んでいる）、その種類によっては、たとえば整数ならその整数値といったような意味値（semantic value）を与える処理である。部分文字列の列からトークンを構築するには、字句解析器には第二段階の評価器が必要であり、評価器は文字列に対して「値」を付与する。文字列と型を結びつけたものが適切にトークンを表し、構文解析器に入力できるものとなる。括弧などの一部のトークンは「値」を持たないので、評価器（関数）はそれらについては何も返さない。整数、識別子、文字列などを扱う評価器は非常に複雑になる。空白やコメントなどはそのまま捨ててしまうこともある。最終的に、#トークンの節に挙げた表のような形の情報を持った、トークン列が得られる。字句解析は、一度に一文字ずつ読み込むならワンパスで実行できる。ワンパスの字句解析器は lex のような古くからあるツールで生成可能である。lex 系の生成器は表駆動型の手法を採用しており、直接的な手法よりも効率は劣る。re2c や queχ といったツールは flex よりも2倍から3倍高速な字句解析器を生成するとされている（article about re2c）。これらのツールよりも高性能な字句解析器を人間が一から書くのは非常に難しい。言語の開発途中段階などでは、仕様が頻繁に変わるため、スキャナ生成器などの単純なツールの方が有用な場合もある。正規表現として語彙構成要素を表現する能力により、字句解析器の記述が容易になる。一部のツールは、人間が書くのが難しい事前条件や事後条件を記述できる。このような場合、字句解析器生成器によって開発時間が大幅に節約できる。

出典:wikipedia