摘要问题描述：
在我看来，解解析意味着从 AST 创建令牌流，再次解析时会生成相等的 AST。
So parse(unparse(AST)) = AST成立。
这相当于找到一个有效的解析树来生成相同的 AST。
该语言由一个描述上下文无关 http://en.wikipedia.org/wiki/Context-free_grammar S属性 http://en.wikipedia.org/wiki/S-attributed_grammar语法使用eBNF http://en.wikipedia.org/wiki/EBNF变体。
因此，解解析器必须通过遍历的节点找到一条有效的“路径”，其中所有语法约束都成立。这基本上意味着找到有效的分配AST http://en.wikipedia.org/wiki/Abstract_syntax_tree语法产生规则的节点。这是一个约束满足问题（CSP） http://en.wikipedia.org/wiki/Constraint_satisfaction一般来说，可以像解析一样解决回溯 http://en.wikipedia.org/wiki/Backtracking在 O(exp(n)) 中。
幸运的是，对于解析来说，这可以在 O(n3) 内完成，使用GLR http://en.wikipedia.org/wiki/GLR_parser（或者更好地限制语法）。因为AST http://en.wikipedia.org/wiki/Abstract_syntax_tree结构与语法生成规则结构非常接近，我真的很惊讶地看到运行时比解析更糟糕的实现：XText http://www.eclipse.org/Xtext/ uses ANTLR http://www.antlr.org/用于解析和回溯以进行解析。
问题
- 解析器和解解析器需要共享的所有内容都是上下文无关的 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
因此（高速公路 | 行人）决策取决于子树决策。当叶子乍一看可能是多种类型中的一种，但后来必须是特定类型才能形成有效路径时，问题会变得更糟。
示例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
是有效的，并且被认为具有相同的语义，例如语法糖。
更多信息：
