Unparse AST <O(exp(n))？

Question

摘要问题描述:

我看到它的方式,unparsing意味着从AST创建一个令牌流,当再次解析时产生一个相等的AST.

所以 parse(unparse(AST)) = AST持有.

这等于找到一个有效的解析树,它将生成相同的AST.

该语言由使用eBNF变体的无上下文 S属性语法描述.

因此,解析者必须通过所有语法约束所包含的遍历节点找到有效的"路径".这基本上意味着找到AST节点到语法生成规则的有效分配.这通常是一个约束满足问题(CSP),可以通过回溯 O(exp(n))来解决,如解析.

幸运的是,对于解析,这可以使用GLR(或更好地限制语法)在O(n³)中完成.因为AST结构非常接近语法生成规则结构,所以我真的很惊讶看到运行时比解析更糟糕的实现:XText使用ANTLR进行解析和回溯以进行解析.

问题

1. 是一个上下文无关的S属性语法解析器和解析器需要共享的所有东西,还是有进一步的约束,例如解析技术/解析器实现？
2. 我觉得这个问题一般不是O(exp(n)) - 有些天才可以帮助我吗？
3. 这基本上是一个上下文敏感的语法吗？

例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"] 我知道root可以是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

是有效的,并认为它们具有相同的语义,例如语法糖.

更多的信息:

• 在XText中解析

• 解析的语法约束,请参阅序列化程序:具体语法验证

Answer 1

问题1：不，语法本身可能还不够。举一个二义性语法的例子。如果您最终得到给定字符串的唯一最左（最右）推导（AST），您将不得不知道解析器如何消除歧义。想象一下字符串“a+b*c”和表达式“E:=E+E|E*E|...”的朴素语法。

问题3：你给出的语法例子都不是上下文相关的。产生式的左侧是单个非终结符，没有上下文。