解开AST <O（exp（n））？

我看到它，unparsing手段来创建从AST，其解析时再次产生一个等于AST令牌流的方式。

因此parse(unparse(AST)) = AST成立。

这相当于找到一个可生成相同AST的有效分析树。

该语言使用eBNF变体由context free S-attributed语法描述。

因此，解析器必须通过所有语法约束所保存的遍历节点找到有效的“路径”。这个基本意思是找到一个有效的分配给文法生产规则的AST节点。这通常是constraint satisfaction problem (CSP)，并且可以通过O（exp（n））中的backtracking解析，如解析。

幸运的是，对于解析，这可以在O（n³）中使用GLR（或更好地限制语法）完成。因为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，我知道root可以是面积，我可以把它解析为

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"

我可以unparse到

A 
/\ 
B C

刚过，我可以解决 “C” 为C.

在遍历AST ，我可以从语法中产生的所有约束对于两个规则A和X都是满足的，直到我点击“C”。这意味着，对于

A -> B | C 
B -> "map" {MagicNumber_42} 
C -> "foreach" {MagicNumber_42}

为树

 Obj 
     | 
MagicNumber_42

这两种解决方案是有效的，因此认为它们具有相同的语义，e.g。句法糖。

更多信息：

来源

2012-08-12 Stefan K.

我想我不明白。深度优先解析树的遍历应该以原始顺序访问令牌树叶。 AST与分析树是否与这样的遍历不同？ – phs 2012-08-12 01:20:58

是的，分析树是'强类型'的，所以你基本知道哪个特定的语法规则被用来产生某个节点。使用通用AST时，这些信息会丢失，需要重新构建。因此，为了解析AST，构建一个生成此AST的有效分析树就足够了。请注意，可能有几个解析树，但这并不重要，因为任何有效的解析树都有相同的含义（语法糖）。问题不在于遍历AST，而在于使用有效的语法生成规则序列标记访问节点。 – 2012-08-12 01:26:23

将分析树转换为AST的转换是依赖于应用程序的;因为听起来这是你想要反转的步骤，所以你将不得不告诉我们关于具体应用（语言）。 – phs 2012-08-12 01:31:27

问题1：没有，语法本身可能还不够。以一个模棱两可的语法为例。如果最后给出了给定字符串的唯一最左边（最右边）派生（AST），那么您将不知何故必须知道解析器如何消除歧义。只要想想表达式'E：= E + E | E * E | ...'的天真语法字符串'a + b * c'即可。

问题3：您给出的任何语法示例都不是上下文相关的。制作的左手边是单个非终点，没有上下文。

来源

2012-09-14 16:27:46 user1666959

解开AST <O（exp（n））？

回答

相关问题