字句解析

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンス字句解析字句またはトークン化のシーケンスに変換する処理である文字(例えばのようにコンピュータプログラムまたはウェブページをトークン(のシーケンスに)文字列に割り当てられ、従って同定意味を持ちます)。字句解析を実行するプログラムは、レクサートークナイザー[1]、またはスキャナーと呼ばれることがありますスキャナーはレクサーの最初の段階の用語でもあります。レクサーは通常、パーサーと組み合わされ、パーサーが一緒に分析します。構文プログラミング言語Webページなど、と。

アプリケーション

レクサーは、最新の処理におけるコンパイラフロントエンドの最初のフェーズを形成します。通常、分析は1回のパスで行われます。

ALGOLなどの古い言語では、最初の段階は代わりに行の再構築でした。これは、スロープを解除し、空白とコメントを削除しました(そしてスキャナーレスのパーサーがあり、個別のレクサーはありませんでした)。これらの手順は、レクサーの一部として実行されるようになりました。

レクサーとパーサーはコンパイラーに最もよく使用されますが、プリティプリンターリンターなどの他のコンピューター言語ツールにも使用できます字句解析は2つの段階に分けることができます。スキャンは、入力文字列を語彙素呼ばれる構文単位にセグメント化し、これらをトークンクラスに分類します。語彙素を処理された値に変換する評価

レクサーは一般に非常に単純であり、複雑さのほとんどはパーサーまたはセマンティック分析フェーズに委ねられており、多くの場合、レクサージェネレーター、特にlexまたは派生物によって生成できます。ただし、レクサーには、入力を簡単にし、パーサーを単純化するための句構造処理などの複雑さが含まれる場合があり、より多くの機能をサポートするため、またはパフォーマンスのために、部分的または完全に手動で記述される場合があります。

字句解析は、テキストまたは音波が単語やその他の単位に分割される自然言語処理の重要な初期段階でもあります。これには、完全に標準化されていないさまざまな決定が必要であり、システムが生成するトークンの数は、「1/2」、「椅子」、「できない」、「および/または」、「1/1 /」などの文字列によって異なります。 2010」、「2x4」、「...」、その他多数。これは、正確なルールが一般的に定義され、知られているプログラミングや同様の言語の字句解析とは対照的です。

語彙素

語彙素はトークンのパターンと一致し、そのトークンのインスタンスとして字句解析器によって識別されたソースプログラムの文字のシーケンスです。[2]

一部の作成者は、これを「トークン」と呼び、「トークン」を交換可能に使用して、トークン化される文字列と、この文字列をトークン化プロセスにかけた結果のトークンデータ構造を表します。[3] [4]

コンピュータサイエンスの語彙素という言葉は、言語学の語彙素と異なって定義されていますコンピュータサイエンスの語彙素は、言語学の単語ほぼ対応します(コンピュータアーキテクチャの単語と混同しないでください)が、形態素に似ている場合もあります

英語のスラングでは、語彙素は痰の別名であり、痰は副鼻腔と肺の炎症の副産物です。

トークン

字句トークンまたは単にトークンがあり、文字列割り当てられ、このようにして同定意味を持ちます。これは、トークン名とオプションのトークン値で構成されるペアとして構造化されていますトークン名は語彙単位のカテゴリです。[2]一般的なトークン名は

  • 識別子:プログラマーが選択する名前。
  • キーワード:すでにプログラミング言語で使用されている名前。
  • 区切り文字(句読点とも呼ばれます):句読文字とペア区切り文字。
  • 演算子:引数を操作して結果を生成する記号。
  • リテラル:数値、論理、テキスト、参照リテラル。
  • コメント:行、ブロック(コンパイラーがコメントをトークンとして実装するかどうかはコンパイラーに依存します。そうでない場合は削除されます)。
トークン値の例
トークン名 トークン値のサンプル
識別子 xcolorUP
キーワード ifwhilereturn
セパレーター }(;
オペレーター +<=
リテラル true6.02e23"music"
コメント /* Retrieves user data */// must be negative

Cプログラミング言語でこの式を考えてみましょう

x = a + b * 2;

この式の字句解析により、次の一連のトークンが生成されます。

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

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

語彙文法

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

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

トークン化

トークン化は、入力文字列のセクションを区切り、場合によっては分類するプロセスです。結果のトークンは、他の形式の処理に渡されます。このプロセスは、入力解析するサブタスクと見なすことができます。

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

The quick brown fox jumps over the lazy dog

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

トークンはXML表すことができます

<文> 
  <単語> </ワード> 
  <単語>素早く</ワード> 
  <単語>ブラウン</ワード> 
  <単語></ワード> 
  <単語>ジャンプ</単語を> 
  <言葉>を超える</ワード> 
  <単語> </ワード> 
  <単語>怠惰</ワード> 
  <単語></ワード> 
</文>

またはs式として


  単語 ワード速いワードブラウンワードキツネ単語がジャンプ単語以上単語単語怠け者ワード))
   
   
   
   
   
   
   
   

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

トークンは、レクサーの特定のルールに基づいて識別されます。トークンを識別するために使用されるいくつかの方法には、正規表現フラグと呼ばれる特定の文字シーケンス、区切り文字と呼ばれる特定の区切り文字、および辞書による明示的な定義が含まれます。句読文字を含む特殊文字は、記述言語やプログラミング言語で自然に使用されるため、トークンを識別するためにレクサーによって一般的に使用されます。

トークンは、多くの場合、文字コンテンツまたはデータストリーム内のコンテキストによって分類されます。カテゴリは、レクサーのルールによって定義されます。カテゴリには、多くの場合、データストリームで使用される言語の文法要素が含まれます。プログラミング言語は、多くの場合、トークンを識別子、演算子、グループ化シンボル、またはデータ型によって分類します書記言語は通常、トークンを名詞、動詞、形容詞、または句読点として分類します。カテゴリは、パーサーまたはプログラム内の他の関数によるトークンの後処理に使用されます。

字句解析プログラムは通常、トークンの組み合わせ、つまりパーサーに残されたタスクでは何もしませんたとえば、一般的な字句解析プログラムは括弧をトークンとして認識しますが、各「(」が「)」と一致することを保証するために何もしません。

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

トークンは、多くの場合、正規表現によって定義されます。正規表現はlexなどの字句解析ジェネレーターによって理解されます。字句アナライザー(lexなどのツールによって自動的に生成されるか、手作り)は、文字のストリームを読み取り、ストリーム内の語彙素識別して、トークンに分類します。これはトークン化と呼ばれます。レクサーが無効なトークンを検出すると、エラーを報告します。

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

スキャナー

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

評価者

語彙素は、しかし、特定の種類(例えば、文字列リテラル、文字の配列)であることが知られている文字の文字列だけです。トークンを作成するために、字句アナライザーには2番目のステージであるエバリュエーターが必要です。エバリュエーターは語彙素の文字を調べてを生成します。。語彙素の型とその値の組み合わせは、パーサーに与えることができるトークンを適切に構成するものです。括弧などの一部のトークンには実際には値がないため、これらの評価関数は何も返すことができません。必要なのは型だけです。同様に、評価者が語彙素を完全に抑制してパーサーから隠すことができる場合があります。これは空白やコメントに役立ちます。識別子のエバリュエーターは通常単純です(文字通り識別子を表します)が、いくつかのunstropingが含まれる場合があります整数リテラルのエバリュエーター文字列を渡す(評価をセマンティック分析フェーズに延期する)か、評価自体を実行することができます。これは、さまざまなベースまたは浮動小数点数に関係する可能性があります。単純な引用符で囲まれた文字列リテラルの場合、エバリュエーターは引用符のみを削除する必要がありますが、エスケープされた文字列リテラルのエバリュエーターには、エスケープシーケンスをエスケープ解除するレクサーが組み込まれています。

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

net_worth_future = (assets liabilities);

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

識別子net_worth_future
EQUALS
OPEN_PARENTHESIS
IDENTIFIERアセット
マイナス
識別子の負債
CLOSE_PARENTHESIS
セミコロン

既存のパーサーのライセンス制限により、レクサーを手動で作成する必要がある場合があります。これは、トークンのリストが小さい場合に実用的ですが、一般に、レクサーは自動化されたツールによって生成されます。これらのツールは通常、入力ストリームで許可されるトークンを記述する正規表現を受け入れます。各正規表現は、正規表現に一致する語彙素を評価するプログラミング言語の字句文法の生成ルール関連付けられています。これらのツールは、コンパイルして実行できるソースコードを生成したり有限状態マシンの状態遷移表作成したりできます(コンパイルと実行のためにテンプレートコードにプラグインされます)。

正規表現は、語彙素の文字が従う可能性のあるパターンをコンパクトに表します。たとえば、英語ベースの言語の場合、IDENTIFIERトークンは、英語の英数字またはアンダースコアの後に、ASCII英数字および/またはアンダースコアのインスタンスをいくつでも続けることができます。これは、文字列でコンパクトに表すことができます[a-zA-Z_][a-zA-Z_0-9]*。これは、「任意の文字az、AZ、または_の後に、0個以上のaz、AZ、_、または0-9が続く」ことを意味します。

正規表現とそれらが生成する有限状態マシンは、「n個の開き括弧、ステートメント、n個の閉じ括弧」などの再帰パターンを処理するのに十分なほど強力ではありません彼らは、カウントを保持することができない、とことを確認し、nは、許容値の有限集合のために存在している場合を除き、両側で同じであるn個そのようなパターンを完全に一般的に認識するには、完全なパーサーが必要です。パーサは(例を参照してくださいスタックに括弧をプッシュし、それらをオフにポップし、スタックが最後に空であるかどうかを確認しようとすることができる[5]コンピュータプログラムの構造と解釈ブック)。

障害物

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

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

単語間スペースを使用する言語(ラテンアルファベットを使用するほとんどの言語やほとんどのプログラミング言語など)では、このアプローチはかなり簡単です。ただし、ここでも、縮約ハイフンでつながれた単語、顔文字URIなどのより大きな構造(目的によっては単一のトークンとしてカウントされる場合があります)など、多くのエッジケースがあります。古典的な例は「ニューヨークベース」です。これは、(おそらく)ハイフンでのブレークの方が優れている場合でも、ナイーブなトークナイザーがスペースでブレークする可能性があります。

トークン化は古代ギリシャ語中国語[6]タイなど、単語の境界を示さないscriptiocontinuaで記述された言語では特に困難です韓国などの膠着語もトークン化タスクを複雑にします。

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

レクサージェネレーター

レクサーはパーサージェネレーター類似しレクサージェネレーターによって生成されることが多く、そのようなツールはしばしば一緒になります。最も確立されているのはlexであり、yaccパーサジェネレータとペアになっていますまたは、flex(多くの場合GNU Bisonとペアになっているなどの多くの再実装の一部です。これらのジェネレーターは、ドメイン固有言語の形式であり、字句仕様(通常、マークアップを含む正規表現)を取り込んで、字句を発行します。

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

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

句構造

字句解析は、主に文字の入力ストリームをトークンにセグメント化し、文字を断片にグループ化して分類します。ただし、字句解析はかなり複雑になる場合があります。最も簡単に言えば、レクサーはトークンを省略したり、追加されたトークンを挿入したりできます。トークン、特に空白とコメントを省略することは、コンパイラーがこれらを必要としない場合に非常に一般的です。あまり一般的ではありませんが、追加されたトークンが挿入される場合があります。これは主に、パーサーを単純化するために、トークンをステートメントにグループ化するか、ステートメントをブロックにグループ化するために行われます。

行継続

行継続は、改行が通常ステートメントターミネータである一部の言語の機能です。ほとんどの場合、行をバックスラッシュで終了すると(直後に改行が続きます)、行は続行されます。次の行が前の行に結合されます。これは通常、レクサーで行われます。改行がトークン化されるのではなく、円記号と改行が破棄されます。例としては、bash[8]その他のシェルスクリプト、Pythonなどがあります。[9]

セミコロン挿入

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

セミコロン挿入の特徴であるBCPL、その遠い子孫進み[10] それはBまたはCには存在しないものの[11]セミコロン挿入中に存在するJavaScriptのルールが多少複雑で大いに批判されているものの、。バグを回避するために、常にセミコロンを使用することを推奨するものもあれば、あいまいな可能性のあるステートメントの先頭に防御セミコロンと呼ばれる最初のセミコロンを使用するものもあります

セミコロンの挿入(セミコロンで終了するステートメントのある言語)と行の継続(改行で終了するステートメントのある言語)は補完的と見なすことができます。改行は通常トークンを生成ませんが、セミコロンの挿入はトークンを追加しますが、行の継続はトークンを防ぎます改行は通常トークンを生成しますが、生成されません

オフサイドルール

オフ側のルール(インデントによって決定されるブロック)のように、字句解析で実現することができるPythonのインデントトークン発光レクサーでインデント結果を高め、DEDENTトークン発光レクサーでインデント結果を減少させます。[9]これらのトークンは、ブロックに中括弧を使用する言語の開始中括弧{と終了}中括弧に対応し、句の文法が中括弧またはインデントのどちらが使用されているかに依存しないことを意味します。これには、レクサーの保持状態、つまり現在のインデントレベルが必要であり、これが変更されたときにインデントの変更を検出できるため、字句文法は文脈自由ではありません。INDENT–DEDENTは、前のインデントレベルのコンテキスト情報に依存します。

状況依存の字句解析

一般に、語彙文法は文脈自由、またはほとんどそうであるため、過去または先を振り返ったり、後戻りしたりする必要がなく、シンプルでクリーンで効率的な実装が可能になります。これにより、情報がレクサーに逆流することなく、レクサーからパーサーへの単純な一方向通信も可能になります。

ただし、例外があります。簡単な例は次のとおりです。Goへのセミコロンの挿入。1つのトークンを振り返る必要があります。 Pythonでの連続する文字列リテラルの連結[9]。これは、トークンを発行する前に1つのトークンをバッファに保持する必要があります(次のトークンが別の文字列リテラルであるかどうかを確認するため)。 Pythonのオフサイドルール。インデントレベルのカウント(実際には、各インデントレベルのスタック)を維持する必要があります。これらの例はすべて字句コンテキストのみを必要とし、レクサーをいくらか複雑にしますが、パーサー以降のフェーズでは見えません。

より複雑な例は Cのレクサーハックです。typedef名と変数名は字句的に同一ですが、異なるトークンクラスを構成するため、文字シーケンスのトークンクラスはセマンティック分析フェーズまで決定できませんしたがって、ハックでは、レクサーはセマンティックアナライザー(シンボルテーブルなど)を呼び出し、シーケンスにtypedef名が必要かどうかを確認します。この場合、情報はパーサーからだけでなく、セマンティックアナライザーからレクサーに戻る必要があるため、設計が複雑になります。

も参照してください

参考文献

  1. ^ 「コンパイラとトークナイザーの構造」www.cs.man.ac.uk
  2. ^ a b 111ページ、「コンパイラの原則、手法、およびツール、第2版」。(WorldCat)https://stackoverflow.com/questions/14954721/what-is-the-difference-between-token-and-lexemeで引用されているように、Aho、Lam、Sethi、Ullmanによる
  3. ^ Perl5ポーター。「perlinterp:Perl5バージョン24.0のドキュメント」perldoc.perl.org –Perlプログラミング言語の公式ドキュメントperldoc.perl.org 2017年1月26日取得
  4. ^ Guy Coder(2013年2月19日)。「トークンと語彙素の違いは何ですか?」スタックオーバーフローStack ExchangeInc 2017年1月26日取得
  5. ^ 「コンピュータプログラムの構造と解釈」mitpress.mit.edu2012-10-30にオリジナルからアーカイブされまし2009年3月7日取得
  6. ^ Huang、C.、Simon、P.、Hsieh、S。、およびPrevot、L。(2007)中国語の単語セグメンテーションの再考:トークン化、文字分類、または単語区切りの識別
  7. ^ Bumbulis、P。; コーワン、DD(1993年3月〜12月)。「RE2C:より用途の広いスキャナージェネレーター」。プログラミング言語とシステムに関するACMレター2(1–4):70–84。土井10.1145 /176454.176487S2CID 14814637 
  8. ^ Bashリファレンスマニュアル 3.1.2.1エスケープ文字
  9. ^ a b c "3.6.4ドキュメント"docs.python.org
  10. ^ 効果的な囲碁、「セミコロン
  11. ^ Goのセミコロン」、golang-nuts、Rob'Commander 'Pike、2009年12月10日

ソース

  • C#およびJavaを使用したコンパイル、Pat Terry、2005、ISBN 032126360X 
  • アルゴリズム+データ構造=プログラム、Niklaus Wirth、1975、ISBN 0-13-022418-9 
  • コンパイラの構築、Niklaus Wirth、1996、ISBN 0-201-40353-6 
  • セベスタ、RW(2006)。プログラミング言語の概念(第7版)177ページ。ボストン:ピアソン/アディソン-ウェスリー。

外部リンク