再帰的な降下対Lex /解析？

Question

私は（大まかに）再帰的降下パーサー（Scalaのパーサーコンビネータなど）がどのように動作するかを理解していると思います。入力文字列を1つのパーサーで解析し、そのパーサーが入力全体の各 "パーツ"入力文字列のフラグメントからASTを直接生成する低レベルパーサに達するまで

Lexing/Parsingの仕組みを理解していると思います。レクサーを実行して入力全体をフラットリストトークンを取得し、トークンリストを取得してASTを生成するパーサを実行します。

しかし、私は、Lex/Parse戦略がどのようにトークン化するかがトークン化されたトークンによって異なることを理解していません。私はXMLのチャンクを取る場合たとえば、：

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>" 

再帰下降パーサはこれを取ると、それを打破することが

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>" 
    -> "<tag attr='moo' omg='wtf'>" 
     -> "<tag" 
     -> "attr='moo'" 
      -> "attr" 
      -> "=" 
      -> "moo" 
     -> "omg='wtf'" 
      -> "omg" 
      -> "=" 
      -> "wtf" 
     -> ">" 
    -> "attr='moo' omg='wtf'" 
    -> "</tag>" 

と（後続の各インデントは親の文字列の分解を表し） <tag,attr="moo"などを個別に解析する小さなパーサーは、XMLタグの表現を構成し、それに属性を追加します。

ただし、シングルステップのLex/Parseはどのように機能しますか？ <tagの後と>の前の文字列は、別々の属性にトークン化する必要がありますが、>と</tag>の間の文字列は、必ずしも必要ではありません。最初の文字列がタグ本体内にあり、2番目の文字列がタグ本体の外側にあることをパーサーが伝える必要はありませんか？

編集：通常レクサーは、「モード」または入力に応じて変化する「状態」の設定を有することになる

Answer 1

それをより明確にするために例を変更しました。たとえば、<文字を見ると、モードは「タグ」モードに変わり、>が表示されるまで、レクサーは適切にトークン化されます。次に、 "内容"モードに入り、レクサーはattr='moo' omg='wtf'のすべてを単一の文字列として返します。プログラミング言語のレクサーは、例えば、文字列リテラルをこのように扱う：

string s1 = "y = x+5"; 

y = x+5は、数学的な表現として扱われず、その後、文字列に戻すことだろう。 "はレクサーモードを変更するため、文字列リテラルとして認識されます。

XMLやHTMLなどの言語の場合は、yacc、bison、ANTLRなどのパーサージェネレータのいずれかを使用するよりも、カスタムパーサーを作成する方が簡単でしょう。それらは、自動ツールに適したプログラミング言語とは異なる構造を持っています。

あなたのパーサが、それが出てきた文字列にトークンのリストを戻す必要がある場合、それはデザインに何か間違っているという兆候です。別の方法で解析する必要があります。

Answer 2

方法>と の間の文字列をする必要はありませんがレクサーは、必見の後の文字列を別の属性にトークン化さ ことを知っていますか？

これはありません。

最初の文字列が タグ本体内にあり、2番目のケースがタグ本体の外にあることをパーサーが通知する必要はありませんか？

はい。

一般に、レクサーは入力ストリームをトークンのシーケンスに変換します。トークンにはコンテキストがありません。つまり、トークンは入力ストリーム内でどこに発生しても同じ意味を持ちます。レキシング処理が完了すると、各トークンは単一の単位として扱われます。

XMLの場合、生成されたレクサーは、通常、整数、識別子、文字列リテラルなどを識別し、制御文字（ '<'や '>'など）を識別しますが、タグ全体は識別しません。オープンタグ、クローズタグ、属性、要素などを理解する作業は、適切なパーサに委ねられます。