1. ホーム
  2. parsing

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

2022-03-17 14:41:03

質問

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

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

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

レキシングで十分な場合と、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:無制限文法
    再帰的に列挙可能な文法とも呼ばれる。