未解析的AST< O(exp(n))? [英] Unparse AST < O(exp(n))?
问题描述
抽象问题描述:
我认为,未解析意味着从AST创建令牌流,再次对其进行解析产生相等的AST。
The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST.
所以 parse(unparse(AST))= AST
成立。
这等同于找到可以产生相同AST的有效分析树。
This is the equal to finding a valid parse tree which would produce the same AST.
The language is described by a context free S-attributed grammar using a eBNF variant.
因此,解析器必须通过遍历所有语法约束的节点找到有效的路径。这从根本上讲是指为语法生成规则找到有效的 AST 节点的分配。这通常是约束满足问题(CSP),可以像解析一样通过< O(exp(n))中的href = http://en.wikipedia.org/wiki/Backtracking rel = noreferrer>回溯。
So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in O(exp(n)).
幸运的是,可以使用 GLR (或更好地限制语法)。因为 AST 结构非常接近语法生成规则结构,所以看到一个实现真的让我感到惊讶运行时比解析差的地方: XText 使用 ANTLR 用于解析,而回溯则用于未解析。
Fortunately for parsing, this can be done in O(n³) using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.
问题
- 是上下文无关的S -为语法分配解析器和非解析器需要共享的所有内容,或者存在进一步的约束,例如
- 我感觉到这个问题通常不是O(exp(n))-某些天才可以帮助我吗? li>
- 这基本上是上下文相关的语法吗?
- Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
- I've got the feeling this problem isn't O(exp(n)) in general - could some genius help me with this?
- Is this basically a context-sensitive grammar?
示例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包含
So if I have an AST containing
AnyObject-> AnyObject-> Vehicle [name = Car]
,我知道根可以是Area,我可以将其解析为
AnyObject -> AnyObject -> Vehicle [name="Car"]
and I know the root can be Area, I could resolve it to
Area -> Highway -> Car
因此,(高速公路|行人)决策取决于子树决策。当叶子乍一看可能是几种类型中的一种,但后来必须是特定的叶子才能形成有效路径时,问题变得更加严重。
So the (Highway | Pedestrian) decision depends on the subtree decisions. The problem get's worse when a leaf might be, at first sight, one of several types, but has to be a specific one to form a valid path later on.
Example2:
因此,如果我有S属性规则返回无类型对象,则只需分配一些属性即可,例如
So if I have S-attribute rules returning untyped objects, just assigning some attributes, e.g.
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之后。
just after I could resolve "C" to C.
遍历AST时,我可以从语法生成的所有约束都满足A和X两个规则,直到我按下 C。这意味着对于
While traversing the AST, all constraints I can generate from the grammar are satisfied for both rules, A and X, until I hit "C". This means that for
A -> B | C
B -> "map" {MagicNumber_42}
C -> "foreach" {MagicNumber_42}
树的两种解决方案
Obj
|
MagicNumber_42
是有效的,并且认为它们具有相同的语义,例如
are valid and it is considered that they have equal semantics ,e.g. syntactic sugar.
其他信息:
推荐答案
问题1:不,语法本身可能不足够。以一个模棱两可的语法为例。如果以给定字符串的唯一最左(最右)派生词(AST)结尾,那么您将不得不以某种方式知道解析器如何消除歧义。只需考虑表达式'E:= E + E | E * E | ...'的天真语法的字符串'a + b * c'。
Question 1: no, the grammar itself may not be enough. Take the example of an ambiguous grammar. If you ended up with a unique leftmost (rightmost) derivation (the AST) for a given string, you would somehow have to know how the parser eliminated the ambiguity. Just think of the string 'a+b*c' with the naive grammar for expressions 'E:=E+E|E*E|...'.
问题3:您提供的语法示例都不是上下文相关的。产品的左侧是单个非终端,没有上下文。
Question 3: none of the grammar examples you give is context sensitive. The lefthand-side of the productions are a single non-terminal, there is no context.
这篇关于未解析的AST< O(exp(n))?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!