0

主に学習目的で、適切な再帰パーサーをハードコーディングしていますが、いくつかの問題に遭遇しました。

例として、CSS3 文法からのこの短い抜粋を使用します。

simple_selector = type_selector | universal;
type_selector = [ namespace_prefix ]? element_name;
namespace_prefix = [ IDENT | '*' ]? '|';
element_name = IDENT;
universal = [ namespace_prefix ]? '*';

まず、とnamespace_prefixの両方のオプション部分であることに気付きませんでした。これは、プロダクションに一致する入力が盲目的に考慮されていたため、入力が与えられたときに常に失敗することにつながりました。type_selectoruniversaltype_selector*|*namespace_prefix

まともな再帰は簡単ですが、プロダクションに落ち着く前に（より適切な言葉がないため）多くの探索的再帰を行う必要があるというのが私の理解です。そこで、ブール値を返すようにプロダクションのシグネチャを変更しました。このようにして、特定のプロダクションが成功したかどうかを簡単に判断できました。

リンクされたリストのデータ構造を使用して任意の先読みをサポートし、このリストを簡単にスライスして生産を試み、生産が成功しない場合は出発点に戻ることができます。ただし、プロダクションを試している間、可変状態を渡し、ドキュメント オブジェクト モデルを構築しようとしています。制作が成功するかどうかはわからないので、うまくいきません。制作がうまくいかない場合は、どうにかして行った変更を元に戻す必要があります。

私の質問はこれです。抽象構文ツリーを中間表現として使用し、そこから移動する必要がありますか? これは、この問題を回避するために一般的に行うことですか? 問題は主にドキュメント オブジェクト モデルが再帰に適したツリー データ構造ではないことにあると思われるためです。

4

1 に答える 1

1

私は CSS に詳しくありませんが、一般的には文法をリファクタリングしてあいまいさを可能な限り排除します。ここでのケースでは、type_selector とユニバーサルの両方の先頭にある namespace_prefix プロダクションを、別のオプションのプロダクションとして前に引き出すことができます。

simple_selector = [ namespace_prefix ]? (type_selector | universal);
type_selector = element_name;
namespace_prefix = [ IDENT | '*' ]? '|';
element_name = IDENT;
universal =  '*';

ただし、このような単純な先読みのためにすべての文法を単純化できるわけではありません。それらの場合は、より複雑な shift-reduce パーサーを使用するか、お勧めのようにバックトラックを使用できます。バックトラックの場合は、通常、プロダクションを解析して文法のパスを記録しようとします。入力に一致するプロダクションを取得したら、記録されたパスを使用して、そのプロダクションのセマンティック アクションを実際に実行します。

于 2011-03-29T18:48:30.283 に答える