摘要问题描述：
在我看来，unparsing 的意思是从 AST 中创建一个标记流，当再次解析时，会产生相等的 AST。
因此，parse(unparse(AST)) = AST 成立。
这相当于找到一个有效的解析树，该解析树将产生相同的 AST。
该语言使用 context free S-attributed 语法来描述，使用 eBNF 变体。
所以，非解析器必须在遍历的节点中找到一条有效的“路径”，其中所有语法约束都成立。这基本上意味着要找到一个有效的AST节点分配给语法制作规则。这通常是一个约束满足问题（CSP），可以通过回溯在O(exp(n))中解决，就像解析一样。幸运的是，对于解析来说，可以使用GLR（或更好地限制语法）以O(n³)的速度完成。因为AST结构与语法制作规则结构非常接近，所以我真的很惊讶看到一个实现，其中运行时比解析更糟糕：XText使用ANTLR进行解析和回溯进行非解析。
问题
- 上下文无关的S-属性文法是解析器和还原器之间需要共享的全部内容，还是还有其他限制，例如解析技术/解析器实现方面的限制？
- 我觉得这个问题通常情况下不是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，那么我可以将其解析为Area -> Highway -> Car
所以（高速公路|行人）的决策取决于子树决策。当一个叶节点乍一看可能是几种类型之一，但后来必须成为特定类型才能形成有效路径时，问题会变得更加严重。
例如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时，从语法中生成的所有约束条件都对规则A和X均满足，直到遇到"C"。这意味着对于
A -> B | C
B -> "map" {MagicNumber_42}
C -> "foreach" {MagicNumber_42}
树的两个解决方案
Obj
|
MagicNumber_42
这些是有效的，且被认为具有相同的语义，例如语法糖。
更多信息: