解開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））？

回答

相關問題