[解決済み] レクサーとパーサーの比較
質問
レキサーとパーサーは理論的にそんなに違うのですか?
正規表現を嫌うのが流行っているようですが。 コーディングホラー , 別のブログ記事 .
しかし、人気のあるレキシングベースのツール。 断片 , ゲシ または プレティファイ は、すべて正規表現を使用しています。 何でもかんでもレキシングしているように見えるが...。
レキシングで十分な場合と、EBNFが必要な場合とは?
これらのレキサーで生成されたトークンをbisonやantlrパーサージェネレータで使用した方はいらっしゃいますか?
解決方法は?
パーサーとレキサーの共通点。
-
読み取るのは シンボル いくつかの アルファベット を入力します。
- ヒント:アルファベットは必ずしも文字である必要はない。しかし である記号である必要があります。 原子 言語に対して パーサ/レクサが理解できる。
- レキサーのシンボル。ASCII文字。
- パーサーのシンボル:文法の終端記号である特定のトークンである。
-
これらを分析するのです。 シンボル とマッチングさせようとします。 文法 を理解することができました。
- 通常、本当の違いはここにあります。詳しくは以下をご覧ください。
- レキサーが理解できる文法:正則文法(チョムスキーのレベル3)。
- パーサーが理解する文法:文脈自由文法(チョムスキーのレベル2)。
-
を付けています。 セマンティクス (意味)を見出す。
-
レキサーは、以下のように分類して意味を付与します。
語彙
(入力されたシンボルの文字列)を特定の
トークン
. 例:これらの語彙をすべて
*
,==
,<=
,^
は、C/C++ レキサによって "operator" トークンとして分類されます。 -
パーサーは、入力(文)のトークンの文字列を、特定の
非終端記号
を構築し
パースツリー
. 例:これらのトークン文字列をすべて
[number][operator][number]
,[id][operator][id]
,[id][operator][number][operator][number]
は、C/C++パーサーによって、非終端記号(expression")として分類されます。
-
レキサーは、以下のように分類して意味を付与します。
語彙
(入力されたシンボルの文字列)を特定の
トークン
. 例:これらの語彙をすべて
-
認識された要素に何らかの付加的な意味(データ)を付けることができるのです。
- レキサーは、適切な数を構成する文字列を認識した場合、そのバイナリ値に変換して "number"トークンとともに格納することができます。
- 同様に、パーサーは式を認識すると、その値を計算し、構文木の "expression"ノードに格納することができます。
-
これらはすべて、出力に適切な センテンス を認識することができます。
- レキサーは トークン である。 センテンス の 正規言語 を認識します。各トークンは内部構文(ただし、レベル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:無制限文法
再帰的に列挙可能な文法とも呼ばれる。
関連
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン