parsing - レクサーとパーサー

Question

レクサーとパーサーは理論的にそんなに違うのですか?

正規表現を嫌うのは流行のようです:コーディング ホラー、別のブログ投稿。

ただし、一般的な字句ベースのツールであるpygments、geshi、またはprettifyは、すべて正規表現を使用します。彼らは何でもレックスするようです...

lexing で十分な場合、EBNF が必要になるのはいつですか?

これらのレクサーによって生成されたトークンを bison または antlr パーサー ジェネレーターで使用した人はいますか?

Answer 1

パーサーとレクサーに共通するもの：

1. 彼らは入力からいくつかのアルファベットの記号を読みます。

   • ヒント：アルファベットは必ずしも文字である必要はありません。ただし、パーサー/レクサーが理解できる言語に対してアトミックな記号である必要があります。
   • レクサーの記号：ASCII文字。
   • パーサーの記号：文法の終端記号である特定のトークン。

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

   • 本当の違いは通常ここにあります。詳細については、以下を参照してください。
   • 字句解析プログラムで理解される文法：正規文法（チョムスキーのレベル3）。
   • パーサーが理解する文法：文脈自由文法（チョムスキーのレベル2）。

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

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

4. それらは、認識された要素にいくつかの追加の意味（データ）を付加することができます。

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

5. それらはすべて、認識した言語の適切な文を出力に生成します。

   • レクサーはトークンを生成します。トークンは、認識できる正規言語の文です。各トークンは内部構文（レベル2ではなくレベル3）を持つことができますが、それは出力データとそれらを読み取るものには関係ありません。
   • パーサーは構文ツリーを生成します。これは、パーサーが認識する文脈自由言語の文の表現です。通常、ドキュメント/ソースファイル全体が適切な文であるため、ドキュメント/ソースファイル全体に対して1つの大きなツリーになります。しかし、パーサーが出力に一連の構文ツリーを生成できなかった理由はありません。たとえば、プレーンテキストに貼り付けられたSGMLタグを認識するパーサーである可能性があります。したがって、SGMLドキュメントを一連のトークンにトークン化します。[TXT][TAG][TAG][TXT][TAG][TXT]...

ご覧のとおり、パーサーとトークナイザーには多くの共通点があります。1つのパーサーは、他のパーサーのトークナイザーになることができます。これは、ある言語の文が他のより高いレベルのアルファベットシンボルになるのと同じように、入力トークンを独自のアルファベットからのシンボルとして読み取ります（トークンは単にいくつかのアルファベットのシンボルです）。言語。たとえば、*と-がアルファベットの記号M（「モールス信号記号」として）である場合、これらのドットと線の文字列をモールス信号でエンコードされた文字として認識するパーサーを作成できます。「モールス信号」という言語の文は、他のパーサーのトークンである可能性があり、これらのトークンはその言語のアトミックシンボルです（例：「英語の単語」言語）。そして、これらの「英語の単語」は、「英語の文」の言語を理解するいくつかの高レベルのパーサーのトークン（アルファベットの記号）である可能性があります。そして、これらの言語はすべて、文法の複雑さだけが異なります。これ以上何もない。

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

• レベル3：正規文法

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

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

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

• レベル1：状況依存文法

• レベル0：無制限文法
  帰納的可算文法とも呼ばれます。

Answer 2

はい、それらは理論的にも実装的にも大きく異なります。

レクサーは、言語要素を構成する「単語」を認識するために使用されます。そのような単語の構造は一般に単純であるためです。正規表現は、この単純な構造の処理に非常に優れており、レクサーの実装に使用される非常に高性能な正規表現マッチング エンジンがあります。

パーサーは、言語フレーズの「構造」を認識するために使用されます。そのような構造は一般に「正規表現」が認識できるものをはるかに超えているため、そのような構造を抽出するには「コンテキスト依存」パーサーが必要です。文脈依存のパーサーを構築するのは難しいため、エンジニアリング上の妥協点は、「文脈に依存しない」文法を使用し、パーサーにハック (「シンボル テーブル」など) を追加して、文脈依存の部分を処理することです。

字句解析技術も構文解析技術もすぐになくなることはありません。

それらは、いわゆるスキャナレス GLR パーサーによって現在調査されているように、「パーシング」テクノロジを使用して「単語」を認識することを決定することによって統合される可能性があります。より一般的な機械を必要としないことが多い問題に適用しているため、これにはランタイムコストがかかり、通常はオーバーヘッドでその費用を支払います。多くの空きサイクルがある場合、そのオーバーヘッドは問題にならない場合があります。大量のテキストを処理する場合、オーバーヘッドが問題になり、従来の正規表現パーサーが引き続き使用されます。

Answer 3

lexing で十分な場合、EBNF が必要になるのはいつですか?

EBNF は、文法の能力を大幅に向上させるものではありません。これは、標準のチョムスキーの正規形 (CNF) 文法規則に対する便宜/ショートカット表記/ 「構文糖衣」です。たとえば、EBNF の代替案は次のとおりです。

S --> A | B

各代替プロダクションを個別にリストするだけで、CNF で達成できます。

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

EBNF のオプション要素:

S --> X?

nullableプロダクション、つまり空の文字列に置き換えることができるプロダクションを使用することで、CNF で実現できます(ここでは単なる空のプロダクションで示されます。他のものはイプシロン、ラムダ、または交差円を使用します)。

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

上記の最後のような形式のプロダクションは、B「消去」と呼ばれます。これは、他のプロダクションで意味するものをすべて消去できるためです (何か他のものではなく空の文字列を生成します)。

EBNF からの 0 回以上の繰り返し:

S --> A*

再帰的な生成、つまり、自分自身をどこかに埋め込むものを使用することで取得できます。それには 2 つの方法があります。最初の 1 つは左再帰です(トップダウン再帰降下パーサーは解析できないため、通常は避ける必要があります)。

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

空の文字列 (最終的に) が生成され、その後に 0 個以上Aの が続くことを知っていれば、同じ文字列 (ただし、同じ言語ではありません! ) をright-recursionを使用して表現できます。

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

そして、+EBNF からの 1 回以上の繰り返しに関しては、次のようになります。

S --> A+

1つを因数分解して、以前と同じようにA使用することで実行できます。*

S --> A A*

これは CNF でそのまま表現できます (ここでは右再帰を使用します。演習として、もう一方を自分で見つけてみてください)。

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

これを知っていれば、おそらく、正規表現の文法 (つまり、正規文法) を、終端記号のみから構成される単一の EBNF 生成で表現できるものとして認識することができます。より一般的には、次のような表現を見れば、通常の文法を認識することができます。

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

つまり、空の文字列、終端記号、単純な非終端記号のみを置換と状態変更に使用し、再帰を使用して繰り返しを実現します (反復、これは単なる線形再帰であり、ツリーのように分岐しないものです)。これらよりも高度なものはありません。それなら、それは通常の構文であり、そのためのレクサーだけで行くことができます。

しかし、構文で再帰を重要な方法で使用して、次のようなツリーのような自己相似のネストされた構造を生成する場合:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

そうすれば、正規表現ではこれを実行できないことが簡単にわかります。これは、1 つの EBNF プロダクションに解決できないためです。S無期限に置換することになります。これにより、常に別aの s とbs が両側に追加されます。レクサー (より具体的には、レクサーによって使用される有限状態オートマトン) は、任意の数まで数えることができません (それらは有限です、覚えていますか? a) b。このような文法は(少なくとも)文脈自由文法と呼ばれ、パーサーが必要です。

文脈自由文法は解析することがよく知られているため、プログラミング言語の構文を記述するために広く使用されています。しかし、もっとあります。より一般的な文法が必要になる場合があります。同時に、独立して数えなければならないものがもっとある場合です。たとえば、丸括弧と角括弧をインターリーブして使用できる言語を記述したいが、それらを互いに正しくペアにする必要がある場合 (中括弧と中括弧、丸と丸)。この種の文法は、文脈依存と呼ばれます。左側 (矢印の前) に複数の記号があることで認識できます。例えば：

A R B --> A S B

左側のこれらの追加記号は、ルールを適用するための「コンテキスト」と考えることができます。いくつかの事前条件、事後条件などが存在する可能性があります。たとえば、上記のルールは に置き換えRられますが、 と の間にSある場合にのみ、それらとそれ自体は変更されません。この種の構文は、本格的なチューリング マシンが必要なため、解析が非常に困難です。それはまた別の話なので、ここで終わります。ABAB

Answer 4

尋ねられたとおりに質問に答える (他の回答に表示されることを過度に繰り返さずに)

受け入れられた回答で示唆されているように、レクサーとパーサーはそれほど違いはありません。どちらも単純な言語形式に基づいています。レクサーには通常の言語が使用され、パーサーにはほとんどの場合、コンテキスト フリー (CF) 言語が使用されます。どちらも、かなり単純な計算モデル、有限状態オートマトンとプッシュダウン スタック オートマトンに関連付けられています。通常の言語は文脈自由言語の特殊なケースであるため、より複雑な CF テクノロジを使用してレクサーを作成できます。しかし、少なくとも 2 つの理由から、これは良い考えではありません。

プログラミングの基本的なポイントは、システム コンポーネントを最も適切なテクノロジで構築して、作成、理解、保守が容易になるようにすることです。必要以上に複雑でコストのかかる技術を使用したり、目的を達成するために技術的なゆがみを必要とする限界に達したりしてはなりません。

だからこそ「正規表現を嫌うのが流行り」なのです。それらは多くのことを行うことができますが、それを達成するために非常に読みにくいコーディングが必要になる場合があり、実装におけるさまざまな拡張や制限により、理論的な単純さがいくらか損なわれるという事実は言うまでもありません。通常、レクサーはそれを行わず、トークンを解析するための単純で効率的で適切なテクノロジです。可能ではありますが、トークンに CF パーサーを使用するのはやり過ぎです。

レクサーに CF 形式を使用しないもう 1 つの理由は、CF の機能をフルに使用したくなる可能性があることです。しかし、それはプログラムの読み取りに関する構造的な問題を引き起こす可能性があります。

基本的に、意味を抽出するプログラムテキストの構造の大部分はツリー構造です。構文規則から構文解析文（プログラム）がどのように生成されるかを表現します。セマンティクスは、構文規則を構成して構文木を構築する方法から、合成技法 (数学指向の準同型) によって導出されます。したがって、ツリー構造は不可欠です。トークンが通常の集合ベースのレクサーで識別されるという事実は、状況を変えません。なぜなら、通常の CF で合成された CF は依然として CF を与えるからです (文字のストリームをトークンのストリームに変換する通常の変換器について非常に大まかに話しています)。

ただし、CF で構成された CF (CF トランスデューサーを介して ... 数学で申し訳ありません) は、必ずしも CF を与えるとは限らず、物事をより一般的にする可能性がありますが、実際には扱いにくくなります。そのため、CF は使用できますが、レクサーに適したツールではありません。

通常の言語と CF の主な違いの 1 つは、通常の言語 (およびトランスデューサー) は、さまざまな方法でほとんどすべての形式主義と非常によく構成されているのに対し、CF 言語 (およびトランスデューサー) はそれ自体ではなく (いくつかの例外を除いて) 構成されていないことです。

(通常の変換器には、いくつかの構文エラー処理手法の形式化など、他の用途がある場合があることに注意してください。)

BNF は、CF 文法を表現するための特定の構文にすぎません。

EBNF は BNF のシンタックス シュガーであり、通常の表記法の機能を使用して BNF 文法のより簡潔なバージョンを提供します。これは常に同等の純粋な BNF に変換できます。

ただし、通常の表記法は、字句要素の構造に対応する構文のこれらの部分を強調するためにのみ EBNF で使用されることが多く、字句解析器で認識される必要がありますが、残りはむしろストレート BNF で表示されます。しかし、それは絶対的なルールではありません。

要約すると、トークンのより単純な構造は、通常の言語のより単純な技術でよりよく分析されますが、言語の (プログラム構文の) ツリー指向構造は、CF 文法でより適切に処理されます。

AHR's answerも参照することをお勧めします。

しかし、これには疑問が残ります。なぜ木なのか?

ツリーは構文を指定するための優れた基礎です。

• それらはテキストに単純な構造を与えます

• 上記のように、数学的によく理解された技術 (準同型による構成性) を使用して、その構造に基づいてセマンティクスをテキストに関連付けるのに非常に便利です。これは、数学的形式のセマンティクスを定義するための基本的な代数ツールです。

したがって、抽象構文木 (AST) の成功が示すように、これは優れた中間表現です。多くの専門家 (LL や LR など) によって使用される解析テクノロジは CF 文法のサブセットにのみ適用されるため、AST はしばしば解析ツリーとは異なることに注意してください。これは、任意の CF 文法を受け入れる、より一般的な解析テクノロジ (動的プログラミングに基づく) で回避できます。

プログラミング言語が CF ではなくコンテキスト センシティブ (CS) であるという事実に関する声明は恣意的で議論の余地があります。

問題は、構文とセマンティクスの分離が恣意的であることです。宣言または型一致のチェックは、構文の一部またはセマンティクスの一部と見なされる場合があります。同じことが、自然言語における性別と数の一致にも当てはまります。しかし、複数形の一致が単語の実際の意味的意味に依存する自然言語があり、構文にうまく適合しません。

表示セマンティクスにおけるプログラミング言語の定義の多くは、セマンティクスに宣言と型チェックを配置します。そのため、 Ira Baxterが行ったように、CF パーサーがハッキングされて構文が必要とするコンテキスト依存性を取得していると述べることは、せいぜい恣意的な状況の見方です。一部のコンパイラではハックとして構成されている場合がありますが、そうである必要はありません。

また、CSパーサー（ここでの他の回答で使用されている意味で）は構築が難しく、効率が悪いというだけではありません。それらはまた、必要とされるかもしれない文脈依存性を明確に表現するには不十分です。また、プログラムのセマンティクスを導出する、つまりコンパイルされたコードを生成するのに便利な構文構造 (解析ツリーなど) を自然に生成するわけではありません。