抽象问题描述：
在我看来，解解析意味着从 AST 创建一个令牌流，当再次解析时会产生一个相等的 AST。
所以 parse(unparse(AST)) = AST成立。
这等于找到会产生相同 AST 的有效解析树。
因此，解解析器必须通过遍历所有语法约束的节点找到有效的“路径”。这基本上意味着找到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"
所以如果我有一个 AST 包含
AnyObject -> AnyObject -> Vehicle [name="Car"] 我知道根可以是区域，我可以解决它
Area -> Highway -> Car
所以 (Highway | Pedestrian) 决策取决于子树决策。当叶子乍一看可能是几种类型中的一种时，问题会变得更糟，但必须是特定的叶子才能在以后形成有效路径。
示例 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
是有效的，并且认为它们具有相同的语义，例如句法糖。
更多信息：