抽象問題の説明：私はそれを見るAST <O（exp（n））を解析しない？
方法、解析された場合には再度同じASTを生成するAST、からトークンストリームを作成する手段をunparsing。
従ってparse(unparse(AST)) = ASTが成立する。
これは、同じASTを生成する有効な構文解析ツリーを見つけることと同じです。
S-attributed文法では、eBNFバリアントを使用して言語を記述しています。
したがって、アンパーザは、すべての文法制約が保持されている通過ノードを通る有効な「パス」を見つけなければなりません。これは、基本的には、文法生成ルールに対してノードASTの有効な割り当てを見つけることを意味します。これは一般的にconstraint satisfaction problem (CSP)であり、O（exp（n））内のbacktrackingによって解析することができます。
幸運なことに、これはGLR（またはそれ以上の文法を制限する）を使用してO（n3）で行うことができます。 ASTの構造は文法生成規則の構造に非常に近いので、私は実行時間が解析よりも悪い実装を見て本当に驚いていました。XTextは構文解析と逆解析のためにANTLRを使用しています。
質問
- 例えば文脈自由S-属性文法のすべてのパーサーと、さらに制約を共有したり、あるためにunparser必要であり、構文解析技術/パーサー実装について
- 私はこの問題が一般的にO（exp（n））ではないという気持ちを持っています。
- これは基本的に文脈依存文法ですか？
例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"
私は
AnyObject -> AnyObject -> Vehicle [name="Car"]を含むASTを持っていると私は根がエリアとすることができる知っていれば、私はそれを解決することができ
Area -> Highway -> Car
したがって、（ハイウェイ/歩行者）の決定は、サブツリーの決定に依存します。一見、葉がいくつかのタイプのうちの1つであるかもしれないが、後で有効な経路を形成するために特定のものでなければならないとき、問題は悪化する。
例2：
だから、僕は、例えば、いくつかの属性を割り当て、型指定されていないオブジェクトを返すS-属性のルールを持っている場合ASTをトラバースしながら、私はC.
に "C" を解決することができた直後に
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
にそれをunparseすることができます私が文法から生成できるすべての制約は、AとXの両方のルールで "C"に達するまで満たされます。これは、ツリー
Obj
|
MagicNumber_42
のための両方のソリューション
A -> B | C
B -> "map" {MagicNumber_42}
C -> "foreach" {MagicNumber_42}
のために有効であり、彼らは例えば、同じ意味を持っていると考えられていることを意味しています。構文的な砂糖。
詳細情報：
私は分かりません。解析木の深さ優先のトラバーサルは、元の順序でトークンリーフを参照する必要があります。このような探索を行うには、ASTと構文解析ツリーが大きく異なるのですか？ – phs
はい、構文解析ツリーは「強い型付けされている」ので、特定の文法規則が特定のノードを生成するために使用されたことを基本的に知っています。一般的なASTでは、この情報は失われ、再構築する必要があります。したがって、ASTの解析を解除するには、このASTを生成する有効な解析ツリーを作成すれば十分です。いくつかの解析木があるかもしれないが、有効なものは同じ意味（構文的な砂糖）を持つため、これは問題ではないことに注意してください。この問題は、ASTをトラバースすることではなく、訪問されたノードに文法生成ルールの有効なシーケンスをタグ付けすることにある。 –
構文解析ツリーをASTに変換する変換はアプリケーションに依存します。これは逆にしたいステップなので、特定のアプリケーション（言語）について教えてください。 – phs