摘要问题描述:
在我看来,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
这些是有效的,且被认为具有相同的语义,例如语法糖。
更多信息: