語彙解析

語彙トークン化とは、テキストを「lexer」プログラムによって定義されたカテゴリに属する​​ (意味的または構文的に) 意味のある語彙トークンに変換することです。自然言語の場合、これらのカテゴリには名詞、動詞、形容詞、句読点などが含まれます。プログラミング言語の場合、カテゴリには識別子、演算子、グループ化記号、データ型が含まれます。語彙トークン化は、大規模言語モデル(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, ;)]

トークン名は、言語学では品詞と呼ばれるものです。

語彙トークン化とは、生のテキストを (意味的または構文的に) 意味のある語彙トークンに変換することです。この語彙トークンは、「lexer」プログラムによって定義されたカテゴリ (識別子、演算子、グループ化記号、データ型など) に属します。結果として得られたトークンは、他の形式の処理に渡されます。このプロセスは、入力の解析のサブタスクと考えることができます。

たとえば、次のテキスト文字列では、

The quick brown fox jumps over the lazy dog

文字列は、自然言語話者のように暗黙的にスペースで分割されるわけではありません。生の入力である 43 文字は、指定されたスペース区切り文字 (つまり、文字列" "または正規表現 /\s{1}/に一致する) を使用して、明示的に 9 つのトークンに分割される必要があります。

トークン クラスが複数の可能な語彙素を表す場合、多くの場合、レキサーは元の語彙素を再現するのに十分な情報を保存するため、意味解析で使用できます。パーサーは通常、この情報をレキサーから取得し、抽象構文木に格納します。これは、数字も有効な識別子になる可能性がある場合に情報の損失を避けるために必要です。

トークンは、レクサーの特定のルールに基づいて識別されます。トークンを識別するために使用される方法には、正規表現、フラグと呼ばれる特定の文字列、区切り文字と呼ばれる特定の分離文字、および辞書による明示的な定義が含まれます。句読点を含む特殊文字は、記述言語やプログラミング言語で自然に使用されているため、レクサーがトークンを識別するためによく使用されます。通常、字句解析プログラムはトークンの組み合わせに対しては何も行いません。これはパーサーに任せられたタスクです。たとえば、一般的な字句解析プログラムは括弧をトークンとして認識しますが、各「(」が「)」と一致するかどうかは確認しません。

レクサーがパーサーにトークンを供給するとき、使用される表現は通常、数値表現のリストである列挙型です。たとえば、「識別子」は 0 で、「代入演算子」は 1 で、「加算演算子」は 2 で表すことができます。

トークンは、多くの場合、正規表現によって定義されます。正規表現は、 lexなどの字句解析器ジェネレーター、または手動でコーディングされた同等の有限状態オートマトンによって解釈されます。字句解析器 (lex などのツールによって自動的に生成されるか、手動で作成される) は、文字のストリームを読み取り、ストリーム内の語彙素を識別して、トークンに分類します。これをトークン化と呼びます。字句解析器が無効なトークンを見つけると、エラーが報告されます。

トークン化の次は解析です。そこから、解釈されたデータは、一般的な使用、解釈、またはコンパイルのためにデータ構造にロードされる場合があります。

プログラミング言語の仕様には、多くの場合、語彙構文を定義する一連の規則、語彙文法が含まれます。語彙構文は通常、正規表現で構成される文法規則を持つ正規言語です。正規表現は、トークンの可能な文字シーケンス (語彙素) のセットを定義します。レキサーは文字列を認識し、見つかった文字列の種類ごとに、語彙プログラムはアクションを実行します。最も単純なアクションは、トークンを生成することです。

2 つの重要な共通語彙カテゴリは、空白とコメントです。これらも文法で定義され、レクサーによって処理されますが、破棄される可能性があり (トークンを生成しない)、重要ではないと見なされ、せいぜい 2 つのトークンを分離するだけです (if xの代わりに のようにifx)。これには 2 つの重要な例外があります。まず、インデントでブロックを区切るオフサイドルール言語では、最初の空白はブロック構造を決定するため重要であり、通常はレクサー レベルで処理されます。以下の句構造を参照してください。次に、レクサーの使用法によっては、コメントと空白を保持する必要があります。たとえば、プリティプリンタはコメントも出力する必要があり、一部のデバッグ ツールは元のソース コードを示すメッセージをプログラマに提供することがあります。1960 年代には、特にALGOLでは、空白とコメントは行再構築フェーズ (コンパイラ フロントエンドの初期フェーズ)の一部として削除されましたが、この別のフェーズは削除され、現在はレクサーによって処理されます。

最初の段階であるスキャナは、通常、有限状態マシン(FSM)に基づいています。スキャナには、処理するトークン内に含めることができる文字の可能なシーケンスに関する情報がエンコードされています (これらの文字シーケンスの個々のインスタンスは語彙素と呼ばれます)。たとえば、整数語彙素には、任意の数字文字のシーケンスを含めることができます。多くの場合、最初の非空白文字を使用して、後続のトークンの種類を推測し、後続の入力文字を 1 つずつ処理して、そのトークンに許容される文字セットにない文字に到達します (これは、最大マンチ ルール、または最長一致ルールと呼ばれます)。一部の言語では、語彙素作成ルールがより複雑で、以前に読み取った文字をバックトラックする必要がある場合があります。たとえば、C では、1 つの「L」文字では、「L」で始まる識別子とワイド文字列リテラルを区別するのに十分ではありません。

ただし、語彙素は、特定の種類であることがわかっている文字列 (たとえば、文字列リテラル、文字のシーケンス) にすぎません。トークンを作成するために、字句解析器には、語彙素の文字を調べて値を生成する 2 番目のステージである評価器が必要です。語彙素の型とその値の組み合わせがトークンを適切に構成するもので、パーサーに渡すことができます。括弧などの一部のトークンには実際には値がなく、そのため、これらの評価関数は何も返さない場合があります。必要なのは型だけです。同様に、評価器は語彙素を完全に抑制してパーサーから隠すことができる場合があります。これは、空白やコメントに便利です。識別子の評価器は通常単純 (識別子を文字通り表す) ですが、アンストロッピングが含まれる場合があります。整数リテラルの評価器は、文字列を渡す (評価を意味解析フェーズに延期する) か、または評価自体を実行する場合があります。評価は、異なる基数または浮動小数点数に関係する場合があります。単純な引用符付き文字列リテラルの場合、評価者は引用符のみを削除する必要がありますが、エスケープされた文字列リテラルの評価者には、エスケープ シーケンスをエスケープ解除するレクサーが組み込まれています。

例えば、コンピュータプログラムのソースコードでは、文字列

net_worth_future = (assets – liabilities);

次のような字句トークン ストリームに変換される可能性があります。空白は抑制され、特殊文字には値がありません。

識別子 net_worth_future
等しい
OPEN_PARENTHESIS
識別子資産
マイナス
識別子の責任
閉じ括弧
セミコロン

レクサーは手動で記述できます。これはトークンのリストが小さい場合に便利ですが、コンパイラ コンパイラ ツールチェーンの一部として自動化ツールによって生成されたレクサーは、潜在的なトークンの数が多い場合に便利です。これらのツールは、通常、入力ストリームで許可されるトークンを記述する正規表現を受け入れます。各正規表現は、プログラミング言語の語彙文法の生成規則に関連付けられており、正規表現に一致する語彙素を評価します。これらのツールは、コンパイルおよび実行可能なソース コードを生成したり、有限状態マシンの状態遷移表を作成したりします(これは、コンパイルおよび実行のためにテンプレート コードにプラグインされます)。

正規表現は、語彙素内の文字が従う可能性のあるパターンを簡潔に表します。たとえば、英語ベースの言語の場合、 IDENTIFIER トークンは、任意の英語のアルファベット文字またはアンダースコアに、任意の数の ASCII 英数字および/またはアンダースコアのインスタンスが続くものになります。これは、文字列 によって簡潔に表すことができます[a-zA-Z_][a-zA-Z_0-9]*。これは、「任意の文字 a ～ z、A ～ Z、または _ に、0 個以上の a ～ z、A ～ Z、_、または 0 ～ 9 が続く」ことを意味します。

正規表現とそれが生成する有限状態マシンは、「n 個の開き括弧、その後に文、その後にn 個の閉じ括弧」などの再帰パターンを処理できるほど強力ではありません。nに許容される値の有限セットが存在しない限り、カウントを保持したり、両側のnが同じであることを確認したりすることはできません。このようなパターンを完全に一般化して認識するには、完全なパーサーが必要です。パーサーは、括弧をスタックにプッシュしてから、それらをポップして、最後にスタックが空かどうかを確認できます (「Structure and Interpretation of Computer Programs 」の本の例^[3]を参照)。

通常、語彙のトークン化は単語レベルで行われます。ただし、「単語」の意味を定義するのが難しい場合があります。多くの場合、トークナイザーは次のような単純なヒューリスティックに依存します。

• 句読点と空白は、結果のトークンのリストに含まれる場合と含まれない場合があります。
• 連続するアルファベット文字の文字列はすべて 1 つのトークンの一部であり、数字も同様です。
• トークンは、スペースや改行などの空白文字、または句読点文字によって区切られます。

単語間のスペースを使用する言語 (ラテン アルファベットを使用するほとんどの言語やほとんどのプログラミング言語など) では、このアプローチはかなり簡単です。ただし、ここでも、短縮形、ハイフンでつながれた単語、顔文字、 URIなどのより大きな構造(目的によっては単一のトークンとしてカウントされることがあります) など、多くのエッジ ケースがあります。典型的な例は「New York-based」で、これは、(おそらく) ハイフンで区切ったほうがよいにもかかわらず、単純なトークナイザーによってスペースで区切られる可能性があります。

トークン化は、古代ギリシャ語、中国語^[4]、タイ語など、単語の境界がない連続文字で書かれた言語では特に困難です。韓国語などの膠着言語もトークン化の作業を複雑にします。

より困難な問題に対処する方法には、より複雑なヒューリスティックの開発、一般的な特殊ケースのテーブルに対するクエリの実行、または後の処理ステップでコロケーションを識別する言語モデルにトークンを適合させることなどがあります。

字句解析器は、多くの場合、字句解析器ジェネレーターによって生成されます。これは、パーサージェネレーターに類似しており、このようなツールはしばしば一緒に使用されます。最も確立されているのは、 lexとyaccパーサージェネレーターの組み合わせ、またはflexなどの多くの再実装の組み合わせです (多くの場合、 GNU Bisonと組み合わせて使用​​されます)。これらのジェネレーターは、ドメイン固有言語の一種であり、字句仕様 (通常はマークアップを含む正規表現) を受け取り、字句解析器を生成します。

これらのツールを使用すると、非常に迅速に開発を進めることができます。これは、機能するレクサーを取得するため、および言語仕様が頻繁に変更される可能性があるため、開発の初期段階では非常に重要です。さらに、これらのツールは、手動でプログラムするのが難しい事前条件や事後条件などの高度な機能を提供することがよくあります。ただし、自動的に生成されたレクサーは柔軟性に欠ける場合があり、そのため手動で変更したり、レクサーをすべて手動で記述したりする必要があります。

字句解析器のパフォーマンスは懸念事項であり、最適化する価値はあります。字句解析器が非常に頻繁に実行される安定した言語 (C や HTML など) ではなおさらです。lex/flex で生成された字句解析器はかなり高速ですが、より調整されたジェネレータを使用することで 2 ～ 3 倍の改善が可能です。手書きの字句解析器が使用されることもありますが、最新の字句解析器ジェネレータは、ほとんどの手書きの字句解析器よりも高速な字句解析器を生成します。lex/flex ファミリのジェネレータは、直接コード化されたアプローチよりもはるかに効率の悪いテーブル駆動型のアプローチを使用します。[^{疑わしい–議論]後者}のアプローチでは、ジェネレータは goto 文を介して後続の状態に直接ジャンプするエンジンを生成します。re2c ^[5]などのツールは、flex が生成したエンジンよりも 2 ～ 3 倍高速なエンジンを生成できることが実証されています。^[要出典]一般に、後者のツールで生成されたエンジンよりもパフォーマンスの優れたアナライザーを手書きすることは困難です。

字句解析は主に、文字の入力ストリームをトークンに分割し、文字をいくつかの部分にグループ化して分類するだけです。ただし、字句解析は大幅に複雑になる場合があります。最も単純な方法としては、字句解析プログラムがトークンを省略したり、追加のトークンを挿入したりします。トークン、特に空白やコメントを省略するのは、コンパイラが必要としない場合によく行われます。あまり一般的ではありませんが、追加のトークンが挿入されることもあります。これは主に、パーサーを簡素化するために、トークンをステートメントにグループ化したり、ステートメントをブロックにグループ化したりするために行われます。

行継続は、改行が通常文の終結子となる言語の特徴です。ほとんどの場合、行末にバックスラッシュ（直後に改行）を置くと、行が継続され、次の行が前の行に結合されます。これは通常、字句解析器で行われます。つまり、改行がトークン化されるのではなく、バックスラッシュと改行が破棄されます。例としては、 bash、^[6]他のシェルスクリプト、Python などがあります。 ^[7]

多くの言語では、セミコロンを文の終端子として使用します。ほとんどの場合、これは必須ですが、一部の言語では、多くのコンテキストでセミコロンがオプションです。これは主に、入力文字ストリームにセミコロンがなくても、レクサーがトークン ストリームにセミコロンを出力する、レクサー レベルで行われます。これは、セミコロン挿入または自動セミコロン挿入と呼ばれます。これらの場合、セミコロンは言語の正式な句文法の一部ですが、レクサーによって挿入できるため、入力テキストに見つからない場合があります。オプションのセミコロンやその他の終端子や区切り文字も、末尾のカンマやセミコロンの場合に特に、パーサー レベルで処理されることがあります。

セミコロンの挿入はBCPLとその遠い子孫であるGoの機能であるが^[8]、BやCには存在しない。^{[9]セミコロンの挿入は}JavaScriptにも存在するが、ルールはやや複雑で批判も多い。バグを避けるために常にセミコロンを使うことを推奨する人もいれば、潜在的に曖昧な文の先頭に 防御セミコロンと呼ばれる先頭セミコロンを使う人もいる。

セミコロンの挿入 (セミコロンで終了する文を持つ言語) と行の継続 (改行で終了する文を持つ言語) は、相補的なものとして考えることができます。つまり、改行は通常トークンを生成しませんが、セミコロンの挿入ではトークンが追加されます。一方、改行は通常トークンを生成しますが、行の継続ではトークンが生成されないようにします。

オフサイドルール（ブロックはインデントによって決定される）は、 Pythonのように、字句解析器に実装することができ、字句解析器はインデントを増やすとINDENTトークンを出力し、インデントを減らすと1つ以上のDEDENTトークンを出力する。^[10]これらのトークンは、ブロックに中括弧を使用する言語の開き中括弧{と閉じ中括弧に対応し}、句の文法は中括弧またはインデントが使用されているかどうかに依存しないことを意味する。これには、字句解析器が状態、つまりインデントレベルのスタックを保持し、これが変化したときにインデントの変化を検出できる必要がある。そのため、字句の文法は文脈自由ではなく、INDENT–DEDENTは以前のインデントレベルの文脈情報に依存する。

一般的に、語彙文法は文脈自由、またはほぼ文脈自由であるため、前または後ろを振り返る、またはバックトラックする必要がなく、シンプルでクリーンかつ効率的な実装が可能になります。これにより、語彙解析器からパーサーへの単純な一方向通信も可能になり、語彙解析器に情報が戻る必要もありません。

ただし、例外もあります。簡単な例としては、Go でのセミコロンの挿入 (1 つのトークンをさかのぼって調べる必要がある)、Python での連続する文字列リテラルの連結^[7] (次のトークンが別の文字列リテラルかどうかを確認するため、1 つのトークンをバッファーに保持してから出力する必要がある)、Python でのオフサイド ルール (インデント レベルのカウント (実際には、各インデント レベルのスタック) を維持する必要がある) などがあります。これらの例はすべて、語彙のコンテキストのみを必要とし、レキサーを多少複雑にしますが、パーサーとそれ以降のフェーズには表示されません。

より複雑な例としては、 C の字句解析ハックがあります。字句解析ハックでは、 typedef名と変数名は字句的には同じですが、異なるトークン クラスを構成するため、文字列のトークン クラスは意味解析フェーズまで決定できません。したがって、このハックでは、字句解析ハックは意味解析ハック (たとえば、シンボル テーブル) を呼び出し、文字列に typedef 名が必要かどうかを確認します。この場合、情報はパーサーからだけでなく、意味解析ハックから字句解析ハックに返される必要があり、設計が複雑になります。

• 語彙化
• 語彙意味論
• パーサージェネレーターのリスト

• Yang , W.; Tsay, Chey-Woei; Chan, Jien-Tsai (2002). 「語彙解析における最長一致規則の適用可能性について」。コンピュータ言語、システム、構造。28 (3): 273–288。doi : 10.1016 /S0096-0551(02)00014-0。NSC 86-2213-E-009-021 および NSC 86-2213-E-009-079。
• Trim, Craig (2013 年 1 月 23 日)。「トークン化の技術」。Developer Works。IBM。2019年 5 月 30 日時点のオリジナルよりアーカイブ。
• 単語言及セグメンテーションタスクの分析