レクサーとパーサー 質問する

パーサーとレキサーの共通点:

1. 入力からアルファベットの記号を読み取ります。

   • ヒント: アルファベットは必ずしも文字である必要はありません。ただし、パーサー/レクサーが理解できる言語にとってアトミックな記号でなければなりません。
   • 字句解析器のシンボル: ASCII 文字。
   • パーサーのシンボル: 文法の終端記号である特定のトークン。

2. 彼らはこれらの記号を分析し、理解している言語の文法と一致させようとします。
   

   • 本当の違いは通常ここにあります。詳細については以下を参照してください。
   • レクサーが理解する文法: 正規文法 (チョムスキーのレベル 3)。
   • パーサーが理解する文法: 文脈自由文法 (チョムスキーのレベル 2)。

3. 彼らは、見つけた言語断片にセマンティクス（意味）を付与します。

   • レクサーは、語彙素(入力からの記号の文字列) を特定のトークンとして分類することで意味を付与します。たとえば*、、、==など<=の語彙素はすべて、 ^C/C++ レクサーによって「演算子」トークンとして分類されます。
   • パーサーは、入力（文）からのトークンの文字列を特定の非終端記号として分類し、解析ツリーを構築することで意味を付加します。たとえば[number][operator][number]、これらのトークン文字列はすべて[id][operator][id]、[id][operator][number][operator][number]C/C++ パーサーによって「式」非終端記号として分類されます。

4. 認識された要素に追加の意味 (データ) を付加することができます。

   • レクサーは、適切な数値を構成する文字シーケンスを認識すると、それをバイナリ値に変換し、「number」トークンとともに保存できます。
   • 同様に、パーサーは式を認識すると、その値を計算し、構文ツリーの「式」ノードに保存できます。

5. 彼らは皆、認識している言語の適切な文章を出力します。

   • レクサーは、認識した通常の言語の文であるトークンを生成します。各トークンは内部構文を持つことができますが (レベル 2 ではなくレベル 3)、出力データとそれを読み取るデータにとっては関係ありません。
   • パーサーは構文木を生成します。構文木は、パーサーが認識する文脈自由言語の文の表現です。パーサーにとっては、文書/ソース ファイル全体が適切な文であるため、通常は文書/ソース ファイル全体に対して 1 つの大きな木だけになります。ただし、パーサーが出力時に一連の構文木を生成できない理由はありません。たとえば、パーサーはプレーン テキストに埋め込まれた SGML タグを認識することができます。その場合、SGML 文書は一連のトークンにトークン化されます。[TXT][TAG][TAG][TXT][TAG][TXT]...

ご覧のとおり、パーサーとトークナイザーには多くの共通点があります。あるパーサーは他のパーサーのトークナイザーになることができ、そのパーサーは入力トークンを自身のアルファベットの記号として読み取ります (トークンは単にアルファベットの記号です)。これは、ある言語の文が他の高水準言語のアルファベット記号になるのと同じです。たとえば、*とが-アルファベットの記号M(「モールス信号記号」として) である場合、これらの点と線の文字列をモールス信号でエンコードされた文字として認識するパーサーを構築できます。「モールス信号」言語の文は、他のパーサーのトークンになる可能性があり、そのパーサーにとってこれらのトークンはその言語の原子記号です (たとえば、「英語の単語」言語)。そして、これらの「英語の単語」は、「英語の文」言語を理解する高水準パーサーのトークン (アルファベットの記号) になる可能性があります。そして、これらすべての言語の違いは、文法の複雑さだけです。それ以上はありません。

では、「チョムスキーの文法レベル」とは何でしょうか? ノーム・チョムスキーは、文法をその複雑さに応じて 4 つのレベルに分類しました。

• レベル3: 通常の文法

  これらは正規表現を使用します。つまり、アルファベットの記号 ( a、b)、それらの連結 ( ab、aba、bbbなど)、または代替 (例a|b) のみで構成できます。
  これらは、NFA (非決定性有限オートマトン) やより優れた DFA (決定性有限オートマトン) などの有限状態オートマトン (FSA) として実装できます。正規文法は、ネストされた構文(適切にネスト/一致する括弧、ネストされた HTML/BBcode タグ、ネストされたブロックなど)
  を処理できません。これは、これを処理する状態オートマトンが、無限のネスト レベルを処理するために無限の数の状態を持つ必要があるためです。(()()(()()))

• レベル2: 文脈自由文法

  構文ツリーにはネストされた再帰的自己相似ブランチを持つことができるため、ネストされた構造を適切に処理できます。
  スタックを持つ状態オートマトンとして実装できます。このスタックは、構文のネスト レベルを表すために使用されます。実際には、通常、マシンのプロシージャ呼び出しスタックを使用してネスト レベルを追跡し、構文内のすべての非終端記号に対して再帰的に呼び出されるプロシージャ/関数を使用するトップダウンの再帰下降パーサーとして実装されます。ただし、コンテキスト依存の
  構文は処理できません。たとえば、式があり、あるコンテキストではこれが変数の名前である可能性があり、別のコンテキストでは関数の名前などである可能性がある場合です。x+3x

• レベル1: 文脈依存文法

• レベル 0: 無制限文法。
  再帰的に列挙可能な文法とも呼ばれます。