Loading article…
語彙トークン化とは、テキストを「レクサー」プログラムによって定義されたカテゴリに属する（意味的または構文的に）意味のある語彙トークンに変換することです。自然言語の場合、これらのカテゴリには名詞、動詞、形容詞、句読点などが含まれます。プログラミング言語の場合、カテゴリには識別子、演算子、グループ化記号、データ型、言語キーワードなどが含まれます。語彙トークン化は、大規模言語モデル（LLM）で使用されるトークン化の種類と関連していますが、2つの違いがあります。まず、語彙トークン化は通常、語彙文法に基づいているのに対し、LLMトークナイザーは通常、確率に基づいています。次に、LLMトークナイザーは、トークンを数値に変換する2番目のステップを実行します。
字句トークン化を実行するルールベースのプログラムは、トークナイザー[ 1 ]またはスキャナと呼ばれますが、スキャナは字句解析器の最初の段階を表す用語でもあります。字句解析器は、コンパイラのフロントエンド処理の最初の段階を形成します。解析は通常、1回のパスで行われます。字句解析器と構文解析器は、コンパイラで最もよく使用されますが、プリティプリンタやリンタなどの他のコンピュータ言語ツールにも使用できます。字句解析は、入力文字列を字句と呼ばれる構文単位に分割し、これらをトークンクラスに分類するスキャン段階と、字句を処理済みの値に変換する評価段階の2つの段階に分けることができます。
字句解析器は一般的に非常に単純で、複雑な処理のほとんどは構文解析や意味解析の段階に委ねられており、多くの場合、lexやその派生版などの字句解析器生成ツールによって生成されます。しかし、字句解析器は、入力処理を容易にし、構文解析器を簡素化するための句構造処理など、ある程度の複雑さを含む場合があり、より多くの機能をサポートするため、あるいはパフォーマンス向上のために、部分的に、または完全に手作業で記述されることもあります。
ルールベースの自然言語処理における「語彙素」は、言語学における「語彙素」とは異なります。ルールベースの自然言語処理における「語彙素」は、英語のような分析言語では言語学上の同等物と一致する可能性がありますが、融合言語のような高度に総合的な言語では一致しません。ルールベースの自然言語処理における「語彙素」は、言語学における「単語」 （コンピュータアーキテクチャにおける「単語」と混同しないように）により近いものですが、場合によっては形態素により近い場合もあります。
語彙トークンは、大規模言語モデルで使用される確率トークンとは対照的に、意味が割り当てられ識別された文字列です。語彙トークンは、トークン名とオプションのトークン値で構成されます。トークン名は、ルールベースの語彙単位のカテゴリです。[ 2 ]
C言語におけるこの式を考えてみましょう。
x=a+b*2;この表現の語彙解析の結果、以下のトークン列が得られました。
[(identifier,'x'),(operator,'='),(identifier,'a'),(operator,'+'),(identifier,'b'),(operator,'*'),(literal,'2'),(separator,';')]トークン名は、言語学における品詞に相当するものと言えるでしょう。
語彙トークン化とは、生のテキストを、識別子、演算子、グループ化記号、データ型など、「レクサー」プログラムによって定義されたカテゴリに属する、意味的または構文的に意味のある語彙トークンに変換するプロセスです。生成されたトークンは、その後、別の処理に渡されます。このプロセスは、入力の構文解析のサブタスクと考えることができます。
例えば、テキスト文字列では：
The quick brown fox jumps over the lazy dog文字列は、自然言語" "話者のようにスペースで暗黙的に分割されるわけではありません。入力された43文字の生データは、指定されたスペース区切り文字（つまり、文字列または正規表現 に一致する）を使用して、9つのトークンに明示的に分割する必要があります/\s{1}/。
トークンクラスが複数の字句を表す場合、字句解析器は元の字句を再現するのに十分な情報を保存することが多く、これにより意味解析に利用できるようになります。構文解析器は通常、字句解析器からこの情報を取得し、抽象構文木に格納します。これは、数値も有効な識別子になり得る場合に情報損失を防ぐために必要です。
トークンは、字句解析器の特定の規則に基づいて識別されます。トークンを識別するために使用される方法には、正規表現、フラグと呼ばれる特定の文字シーケンス、区切り文字と呼ばれる特定の区切り文字、および辞書による明示的な定義などがあります。句読点などの特殊文字は、書き言葉やプログラミング言語で自然に使用されているため、字句解析器によってトークンを識別するためによく使用されます。字句解析器は通常、トークンの組み合わせに対して何も処理を行わず、そのタスクは構文解析器に委ねられます。たとえば、一般的な字句解析器は括弧をトークンとして認識しますが、各「(」が「)」と一致するようには何もしません。
字句解析器が構文解析器にトークンを渡す際、通常使用される表現は列挙型であり、これは数値表現のリストです。例えば、「識別子」は0、「代入演算子」は1、「加算演算子」は2などで表現できます。
トークンは、多くの場合、 lexなどの字句解析器ジェネレータによって理解される正規表現、または手書きで記述された同等の有限状態オートマトンによって定義されます。字句解析器（lexなどのツールによって自動的に生成されるか、手書きで作成される）は、文字ストリームを読み込み、ストリーム内の字句を識別し、それらをトークンに分類します。これをトークン化と呼びます。字句解析器が無効なトークンを見つけた場合、エラーを報告します。
トークン化の次は構文解析です。そこから、解釈されたデータは、汎用的な使用、解釈、またはコンパイルのためにデータ構造にロードされます。
プログラミング言語の仕様には、多くの場合、字句構文を定義する一連の規則、すなわち字句文法が含まれます。字句構文は通常、正規言語であり、文法規則は正規表現で構成されます。これらの規則は、トークンの可能な文字シーケンス（字句）の集合を定義します。字句解析器は文字列を認識し、検出された文字列の種類ごとに、字句プログラムは何らかの処理を実行します。最も単純な処理は、トークンを生成することです。
重要な共通語彙カテゴリとして、空白とコメントの2 つがあります。これらは文法で定義され、字句解析器によって処理されますが、破棄される場合もあり (トークンを生成しない)、意味のないものとして扱われ、せいぜい 2 つのトークンを区切るだけです (の代わりに)。ただし、これには 2 つの重要な例外があります。まず、ブロックをインデントで区切るオフサイドルール言語では、先頭の空白はブロック構造を決定するため重要であり、通常は字句解析器レベルで処理されます (後述の句構造を参照)。次に、字句解析器の一部の使用例では、コメントと空白を保持する必要があります。たとえば、プリティプリンタはコメントも出力する必要がありますし、一部のデバッグツールは元のソースコードを示すメッセージをプログラマに提供する場合があります。1960 年代、特にALGOLでは、空白とコメントは行再構築フェーズ (コンパイラ フロントエンドの初期フェーズ)の一部として削除されていましたが、この独立したフェーズは削除され、現在は字句解析器によって処理されています。if xifx
最初の段階であるスキャナは、通常、有限状態機械（FSM）に基づいています。スキャナには、処理するトークンに含まれる可能性のある文字シーケンスに関する情報がエンコードされています（これらの文字シーケンスの個々のインスタンスは、レクセムと呼ばれます）。たとえば、整数レクセムには、任意の数字のシーケンスが含まれる可能性があります。多くの場合、最初の空白以外の文字を使用して、後続のトークンの種類を推測でき、その後、トークンに許容される文字セットに含まれない文字に到達するまで、後続の入力文字が一度に 1 つずつ処理されます（これは、最大マッチ、または最長一致ルールと呼ばれます）。一部の言語では、レクセムの作成ルールがより複雑で、以前に読み取った文字を遡って確認する必要がある場合があります。たとえば、C 言語では、1 つの「L」文字だけでは、「L」で始まる識別子とワイド文字文字列リテラルを区別するには不十分です。
しかし、語彙素とは、特定の種類の文字であることがわかっている文字列（例えば、文字列リテラル、文字の並び）にすぎません。字句解析器の第2段階である評価器は、語彙素の文字を解析し、構文解析器にとって関連情報を含む値を生成します。
語彙素の型とその値の組み合わせが、トークンを適切に構成します。トークン内の値は、パーサーがその型のトークンを解釈するために必要と判断されるものであれば何でも構いません。評価器によって生成される典型的な値の例としては、次のようなものがあります。
評価器は、字句を完全に抑制して構文解析器から隠蔽することも可能で、これは空白文字やコメントに役立ちます。
例えば、コンピュータプログラムのソースコードでは、文字列
net_worth_future=(assets–liabilities);TYPEは、次の字句トークン ストリームに変換される可能性があります。各行は、 とそれに続くオプションの値で構成されるトークンを表します。
識別子 "net_worth_future" 等しい 括弧 識別子「アセット」 マイナス 識別子「負債」 括弧を閉じる セミコロン
字句解析器は手動で作成することもできます。トークンのリストが小さい場合は手動作成が実用的ですが、潜在的なトークンの数が多い場合は、コンパイラツールチェーンの一部として自動ツールで生成される字句解析器の方が実用的です。これらのツールは通常、入力ストリームで許可されるトークンを記述する正規表現を受け入れます。各正規表現は、プログラミング言語の字句文法における生成規則に関連付けられており、その規則が正規表現に一致する字句を評価します。これらのツールは、コンパイルおよび実行可能なソースコードを生成したり、有限状態機械の状態遷移表（コンパイルおよび実行用のテンプレートコードに組み込まれる）を構築したりすることができます。
正規表現は、字句内の文字が従う可能性のあるパターンを簡潔に表現します。たとえば、英語をベースとした言語の場合、IDENTIFIERトークンは、任意の英字またはアンダースコアに、任意の数のASCII英数字および/またはアンダースコアが続くものになります。これは、文字列 で簡潔に表現できます[a-zA-Z_][a-zA-Z_0-9]*。これは、「任意の文字az、AZ、または_に、0個以上のaz、AZ、_、または0～9が続く」という意味です。
正規表現とそれらが生成する有限状態機械は、「n 個の開き括弧、それに続く文、それに続くn 個の閉じ括弧」のような再帰的なパターンを処理するには十分な能力を持っていません。nに対して許容される値の有限セットが存在しない限り、カウントを保持したり、両側でnが同じであることを検証したりすることができません。このようなパターンをその一般性において完全に認識するには、完全なパーサーが必要です。パーサーは括弧をスタックにプッシュし、その後ポップして、最後にスタックが空かどうかを確認できます（『コンピュータプログラムの構造と解釈』の例[ 3 ]を参照）。
通常、語彙トークン化は単語レベルで行われます。しかし、「単語」の意味を定義するのは難しい場合があります。多くの場合、トークナイザーは次のような単純なヒューリスティックに依存します。
単語間にスペースを使用する言語（ラテン文字を使用するほとんどの言語や、ほとんどのプログラミング言語など）では、このアプローチは非常に簡単です。しかし、このような場合でも、短縮形、ハイフンでつながれた単語、絵文字、URIなどのより大きな構造（場合によっては単一のトークンとしてカウントされる）といった多くの例外的なケースが存在します。典型的な例は「New York-based」で、単純なトークナイザーではスペースで分割してしまう可能性がありますが、実際にはハイフンで分割するのがより適切であると考えられます。
トークン化は、古代ギリシャ語、中国語[ 4 ]、タイ語のように単語の境界がない連続文字で書かれた言語では特に困難です。韓国語のような膠着語もトークン化の作業を複雑にします。
より困難な問題に対処する方法としては、より複雑なヒューリスティックを開発したり、一般的な特殊ケースのテーブルを照会したり、トークンを言語モデルに適合させて、後の処理ステップでコロケーションを識別したりすることが挙げられる。
字句解析器は、構文解析器と同様に、字句解析器生成器によって生成されることが多く、こうしたツールはしばしばセットで使用されます。最もよく知られているのは、yacc構文解析器生成器と組み合わせたlex 、あるいはflex （ GNU Bisonと組み合わせられることが多い）など、lexの多くの再実装版です。これらの生成器はドメイン固有言語の一種であり、字句仕様（一般的には正規表現とマークアップ）を入力として受け取り、字句解析器を出力します。
これらのツールは開発速度を非常に速くします。これは、動作する字句解析器を作成するため、また言語仕様が頻繁に変更される可能性があるため、開発初期段階において非常に重要です。さらに、これらのツールは、手動でプログラミングするのが難しい事前条件や事後条件などの高度な機能を提供することがよくあります。ただし、自動生成された字句解析器は柔軟性に欠ける場合があり、そのため手動での修正が必要になるか、あるいは完全に手動で字句解析器を作成する必要があるかもしれません。
字句解析器のパフォーマンスは懸念事項であり、最適化は有益です。特に、字句解析器が頻繁に実行される安定した言語（C や HTML など）ではなおさらです。lex/flex で生成された字句解析器は十分に高速ですが、より調整されたジェネレータを使用することで 2 ～ 3 倍の改善が可能です。手書きの字句解析器が使用されることもありますが、最新の字句解析器ジェネレータは、ほとんどの手書きの字句解析器よりも高速な字句解析器を生成します。lex/flex ファミリーのジェネレータは、テーブル駆動方式を採用していますが、これは直接コーディング方式よりもはるかに効率が劣ります。後者の方式では、ジェネレータは goto 文を介して後続の状態に直接ジャンプするエンジンを生成します。re2c [ 5 ] のようなツールは、flexで生成されたエンジンよりも 2 ～ 3 倍高速なエンジンを生成することが実証されています。一般的に、これらのツールで生成されたエンジンよりも優れたパフォーマンスを発揮するアナライザーを手書きすることは困難です。
字句解析は主に、入力された文字ストリームをトークンに分割し、文字を単純にグループ化して分類します。しかし、字句解析ははるかに複雑になる場合があり、最も単純な例としては、字句解析器がトークンを省略したり、トークンを追加したりすることがあります。特に空白やコメントなどのトークンは、コンパイラにとって不要な場合に省略されることがよくあります。あまり一般的ではありませんが、トークンが追加されることもあります。これは主に、トークンを文に、または文をブロックにグループ化して、パーサーを簡素化するために行われます。
Line continuation is a feature of some languages where a newline is normally a statement terminator. Most often, ending a line with a backslash (immediately followed by a newline) results in the line being continued – the following line is joined to the prior line. This is generally done in the lexer: The backslash and newline are discarded, rather than the newline being tokenized. Examples include bash,[6] other shell scripts and Python.[7]
Many languages use the semicolon as a statement terminator. Most often this is mandatory, but in some languages the semicolon is optional in many contexts. This is mainly done at the lexer level, where the lexer outputs a semicolon into the token stream, despite one not being present in the input character stream, and is termed semicolon insertion or automatic semicolon insertion. In these cases, semicolons are part of the formal phrase grammar of the language, but may not be found in input text, as they can be inserted by the lexer. Optional semicolons or other terminators or separators are also sometimes handled at the parser level, notably in the case of trailing commas or semicolons.
Semicolon insertion is a feature of BCPL and its distant descendant Go,[8] though it is absent in B or C.[9] Semicolon insertion is present in JavaScript, though the rules are somewhat complex and much-criticized; to avoid bugs, some recommend always using semicolons, while others use initial semicolons, termed defensive semicolons, at the start of potentially ambiguous statements.
Semicolon insertion (in languages with semicolon-terminated statements) and line continuation (in languages with newline-terminated statements) can be seen as complementary: Semicolon insertion adds a token even though newlines generally do not generate tokens, while line continuation prevents a token from being generated even though newlines generally do generate tokens.
オフサイドルール（インデントによって決定されるブロック）は、 Pythonのようにレクサーで実装できます。インデントを増やすとレクサーは INDENT トークンを出力し、インデントを減らすと 1 つ以上の DEDENT トークンを出力します。[ 10 ]これらのトークンは、ブロックに中括弧を使用する言語の開き中括弧{と閉じ中括弧に対応しており}、句文法が中括弧またはインデントの使用に依存しないことを意味します。これは、レクサーが状態、つまりインデント レベルのスタックを保持し、インデントが変更されたときにその変更を検出できることを必要とし、したがって、語彙文法は文脈自由ではありません。INDENT–DEDENT は、以前のインデント レベルの文脈情報に依存します。
一般的に、語彙文法は文脈に依存しない、あるいはほぼ依存しないため、過去や未来の参照、つまりバックトラック処理が不要となり、シンプルでクリーンかつ効率的な実装が可能になります。また、これにより、字句解析器から構文解析器への一方通行の通信が可能となり、字句解析器に情報が戻ってくる必要もありません。
ただし、例外もあります。簡単な例としては、Go のセミコロン挿入があり、これは 1 つのトークンを遡って調べる必要があります。Python の連続する文字列リテラルの連結[ 7 ]では、次のトークンが別の文字列リテラルかどうかを確認するために、1 つのトークンをバッファに保持してから出力する必要があります。また、Python のオフサイド ルールでは、インデント レベルのカウント (実際には、各インデント レベルのスタック) を維持する必要があります。これらの例はすべて字句コンテキストのみを必要とし、字句解析器を多少複雑にしますが、構文解析器とその後のフェーズからは見えません。
より複雑な例として、C言語の字句解析器のハックが挙げられます。これは、型定義名と変数名が字句的には同一であるにもかかわらず、異なるトークンクラスを構成するため、意味解析フェーズになるまで文字シーケンスのトークンクラスを判定できないというものです。そのため、このハックでは、字句解析器が意味解析器（例えばシンボルテーブル）を呼び出し、シーケンスに型定義名が必要かどうかを確認します。この場合、情報は構文解析器からだけでなく、意味解析器から字句解析器へもフィードバックされる必要があり、設計が複雑になります。