11

抽象的な問題の説明:

私の見方では、解析解除とは、AST からトークン ストリームを作成することを意味し、再度解析すると同等の AST が生成されます。

そう parse(unparse(AST)) = ASTです。

これは、同じ AST を生成する有効な解析ツリーを見つけることと同じです。

この言語は、 eBNFバリアントを使用した文脈自由な S 属性文法によって記述されます。

そのため、アンパーサーは、すべての文法制約が保持されるトラバースされたノードを通る有効な「パス」を見つける必要があります。これは基本的に、文法生成規則に対するASTノードの有効な割り当てを見つけることを意味します。これは一般に制約充足問題 (CSP)であり、O(exp(n)) でバックトラックすることにより、解析と同様に解決できます。

幸いなことに、これはGLRを使用して O(n³) で実行できます(または文法をより適切に制限します)。AST構造は文法生成規則構造に非常に近いため、ランタイムが解析よりも悪い実装を見て本当に驚きました。XTextは解析にANTLRを使用し、解析解除にバックトラッキングを使用します。

質問

  1. 文脈自由な S 属性文法は、パーサーとアンパーサーが共有する必要があるすべてのものですか、それとも、構文解析手法やパーサーの実装など、さらに制約がありますか?
  2. この問題は一般的に O(exp(n)) ではないと感じています - 天才がこれを手伝ってくれるでしょうか?
  3. これは基本的に文脈依存の文法ですか？

例1:

Area    returns AnyObject   -> Pedestrian | Highway
Highway returns AnyObject   -> "Foo" Car
Pedestrian  returns AnyObject   -> "Bar" Bike
Car     returns Vehicle     -> anyObjectInstance.name="Car"
Bike    returns Vehicle     -> anyObjectInstance.name="Bike"

したがって、ASTを含む場合

AnyObject -> AnyObject -> Vehicle [name="Car"] ルートがAreaになる可能性があることはわかっています。これを次のように解決できます

Area    -> Highway  -> Car

したがって、(Highway | Pedestrian) の決定は、サブツリーの決定に依存します。リーフが一見、いくつかのタイプの 1 つであっても、後で有効なパスを形成するために特定のタイプでなければならない場合、問題はさらに悪化します。

例 2:

したがって、型付けされていないオブジェクトを返す S 属性ルールがある場合、いくつかの属性を割り当てるだけです。

A -> B C   {Obj, Obj}
X -> Y Z   {Obj, Obj}
B -> "somekeyword"  {0}
Y -> "otherkeyword" {0}
C -> "C" {C}
Z -> "Z" {Z}

したがって、AST に

   Obj
  /  \
"0"  "C"

私はそれを分解することができます

   A
  / \
 B   C

「C」をCに解決できた直後。

AST をトラバースしている間、文法から生成できるすべての制約は、「C」を押すまで、ルール A と X の両方で満たされます。これは、

A -> B | C 
B -> "map"  {MagicNumber_42}
C -> "foreach" {MagicNumber_42}

ツリーの両方のソリューション

     Obj
      |
 MagicNumber_42

は有効であり、それらは同等のセマンティクス (例: シンタックス シュガー) を持っていると見なされます。

さらに詳しい情報：

4

1 に答える 1

1

質問 1: いいえ、文法自体が十分でない可能性があります。あいまいな文法の例を見てみましょう。特定の文字列の一意の左端 (右端) の派生 (AST) になった場合、パーサーがどのようにしてあいまいさを排除したかを知る必要があります。'E:=E+E|E*E|...' という単純な文法を持つ文字列 'a+b*c' について考えてみてください。

質問 3: あなたが与える文法例はどれも文脈依存ではありません。プロダクションの左側は単一の非終端であり、コンテキストはありません。

于 2012-09-14T16:27:46.010 に答える