[解決済み] レクサーとパーサーの比較

質問

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

正規表現を嫌うのが流行っているようですが。 コーディングホラー , 別のブログ記事 .

しかし、人気のあるレキシングベースのツール。 断片 , ゲシ または プレティファイ は、すべて正規表現を使用しています。 何でもかんでもレキシングしているように見えるが...。

レキシングで十分な場合と、EBNFが必要な場合とは？

これらのレキサーで生成されたトークンをbisonやantlrパーサージェネレータで使用した方はいらっしゃいますか？

解決方法は？

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

1. 読み取るのは シンボル いくつかの アルファベット を入力します。

   • ヒント：アルファベットは必ずしも文字である必要はない。しかし である記号である必要があります。 原子 言語に対して パーサ/レクサが理解できる。
   • レキサーのシンボル。ASCII文字。
   • パーサーのシンボル：文法の終端記号である特定のトークンである。

2. これらを分析するのです。 シンボル とマッチングさせようとします。 文法 を理解することができました。
   

   • 通常、本当の違いはここにあります。詳しくは以下をご覧ください。
   • レキサーが理解できる文法：正則文法（チョムスキーのレベル3）。
   • パーサーが理解する文法：文脈自由文法（チョムスキーのレベル2）。

3. を付けています。 セマンティクス (意味）を見出す。

   • レキサーは、以下のように分類して意味を付与します。 語彙 (入力されたシンボルの文字列)を特定の トークン . 例：これらの語彙をすべて * , == , <= , ^ は、C/C++ レキサによって "operator" トークンとして分類されます。
   • パーサーは、入力（文）のトークンの文字列を、特定の 非終端記号 を構築し パースツリー . 例：これらのトークン文字列をすべて [number][operator][number] , [id][operator][id] , [id][operator][number][operator][number] は、C/C++パーサーによって、非終端記号(expression")として分類されます。

4. 認識された要素に何らかの付加的な意味（データ）を付けることができるのです。

   • レキサーは、適切な数を構成する文字列を認識した場合、そのバイナリ値に変換して "number"トークンとともに格納することができます。
   • 同様に、パーサーは式を認識すると、その値を計算し、構文木の "expression"ノードに格納することができます。

5. これらはすべて、出力に適切な センテンス を認識することができます。

   • レキサーは トークン である。 センテンス の 正規言語 を認識します。各トークンは内部構文（ただし、レベル2ではなくレベル3）を持つことができますが、それは出力データとそれらを読むものにとって重要ではありません。
   • パーサーは 構文木 の表現である。 センテンス の 文脈自由言語 を認識します。通常、文書/ソースファイル全体に対して1つの大きなツリーしかありません。なぜなら、文書/ソースファイル全体は適切な 文 となります。しかし、パーサーが一連の構文木を出力できない理由は何もありません。たとえば、プレーンテキストに貼り付けられたSGMLタグを認識するパーサーもありえます。そうすると トークン化 SGML 文書を一連のトークンに変換します。 [TXT][TAG][TAG][TXT][TAG][TXT]... .

このように、パーサーとトークナイザーには多くの共通点があります。ある言語の文が他の上位言語のアルファベット シンボルであるのと同じように、トークンを独自のアルファベットのシンボルとして読み取ります（トークンは単にあるアルファベットのシンボルです）。例えば * そして - はアルファベットの記号 M (モールス符号として）、この点と線の文字列をモールス符号で符号化された文字として認識するパーサーを構築することができるのです。モールス信号という言語の文は、次のようになります。 トークン 他のパーサーでは、これらの トークン はその言語の原子記号である（例えば"英単語"言語）。そして、この "English Words" は、 "English Sentences" 言語を理解するいくつかの上位のパーサーにとってはトークン（アルファベットの記号）かもしれません。そして これらの言語の違いは、文法の複雑さだけです。 . それ以上はない。

では、このquot;チョムスキーの文法レベルとは一体何なのでしょうか？ノーム・チョムスキーは、文法をその複雑さによって4つのレベルに分類しました。

• レベル3：通常の文法

  正規表現を使うので、アルファベットの記号だけで構成することができる ( a , b )、その連結( ab , aba , bbb など)、または代替案(例えば a|b ).
  NFA (Nondeterministic Finite Automaton) や DFA (Deterministic Finite Automaton) のような有限状態オートマトン (FSA) として実装することができる．
  通常の文法では ネストされた構文 例えば、適切にネストされた/一致した括弧は (()()(()())) ネストされたHTML/BBcodeタグ、ネストされたブロックなど。それを扱うステートオートマトンは、無限に多い入れ子レベルを扱うために、無限に多い状態を持たなければならないからです。

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

  構文木に入れ子、再帰的、自己相似的な枝を持つことができ、入れ子構造をうまく扱うことができる。
  スタックを持つステートオートマトンとして実装することができる。このスタックは、構文のネストレベルを表現するために使用される。実際には、マシンの手続き呼び出しスタックを使ってネストレベルを追跡し、構文内の非終端記号ごとに再帰的に呼び出される手続き/関数を使用する、トップダウン、再帰的降下型パーサーとして実装されるのが普通である。
  しかし コンテクストセンシティブ の構文があります。例えば、次のような式がある場合 x+3 で、あるコンテキストでこの x は変数名であり、他の文脈では関数名などである可能性があります。

• レベル1：文脈を考慮した文法

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