是否有衆所周知的算法來推導解析器規則的「返回類型」？

給定一個語法和附加的動作代碼，是否有任何標準的解決方案來推導每個生產需要產生的類型（以及因此，調用生產應該從中得到什麼類型）？是否有衆所周知的算法來推導解析器規則的「返回類型」？

我在考慮採用類似於c＃的var語法的OO程序和動作代碼（但我並不是在尋找特定於c＃的東西）。

如果不是函數重載和遞歸語法，這將非常簡單。

產生的問題是，像這樣的情況：

Foo ::= 
    Bar Baz { return Fig(Bar, Baz); } 
    Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))

來源

2008-12-17 BCS

如果你在一個函數式語言編寫代碼很容易;標準的Hindley-Milner類型推斷很有用。 不要這樣做。在我的EBNF解析器生成器（從未發佈過，但可以根據請求提供源代碼），它支持Icon，c和Standard ML，我實際上是實現了想要的標準ML後端的想法：所有類型都被推斷出來。 生成的語法幾乎不可能調試。

如果拋出超載混進去，結果只是將是難以調試。（這是正確的！這是正確的！比不可能的更難！超過無限！過去我的睡前時間！）如果你真的想自己嘗試一下，歡迎來到my code。（你不這樣做;我有一個原因，我從來沒有發佈它。）

來源

2008-12-17 05:19:47

如果我知道關於Icon的任何內容，我會查看一下。（注意：是的，我知道我是瘋了......我問這個問題，作爲一個先驅，爲此添加[更多]類型推演 - > http://www.dsource.org/projects/scrapple/browser/ trunk/dparser/tag/version_2/dparse.d） – BCS 2008-12-17 08:04:55

語法動作的返回值與本地變量確實沒什麼區別，所以你應該能夠使用C＃類型推斷來完成這項工作。請參閱this paper瞭解如何實現C＃類型推斷。

執行類型推斷的標準方式是Hindley-Milner algorithm，但這不會處理超出現成的超載。

請注意，即使類型推理語言的解析器生成器通常也不會推斷語法操作的類型。例如，ocamlyacc需要鍵入註釋。用於Haskell的解析器生成器Happy可以infer types，但似乎阻止了這種做法。這可能表明，推斷語法類型是困難的，不好的想法，或兩者兼而有之。

[更新]非常受諾曼拉姆齊的影響，他有着痛苦的經歷。

來源

2008-12-17 05:24:00

是否有衆所周知的算法來推導解析器規則的「返回類型」？

回答

相關問題