2013-05-07 73 views
10

可以使用現有的Marpa解析器來改進Perl 5的解析(例如,替換全部或大塊的現有Perl解釋器的解析器)?Can Marpa可以用來加速Perl解釋器的解析嗎?

我在理論層面上問,忽視實際考慮,如「如果可以,將花費10,000個工作小時」。

如果不是,阻止使用Marpa的具體問題是什麼? (再次,最好是理論的)。

Jeffrey Kegler(Marpa的作者)於2008年在PerlMonks上發佈了一篇着名的文章"Perl Cannot Be Parsed: A Formal Proof",這受到他當時在Marpa工作的影響。

+0

作爲一個告誡,我寧願 - 如果可能的話 - 超越瑣碎的答案「[沒有語法分析器可以解析Perl代碼,因爲您可以在編譯階段執行BEGIN代碼塊](http://stackoverflow.com/questions/1280594 /可-perl的待靜態解析?RQ = 1)」。例如。說明如何以及爲什麼Marpa不能像詞法分析器那樣纏繞perl的當前解析器似乎基於我的普通人的理解;或者爲什麼 - 即使它可以 - 馬爾帕會比現有的解析器差。 – DVK 2013-05-07 20:13:19

+2

我已將此問題的鏈接發送給Jeffrey Kegler的Marpa Google Groups,希望他會根據他的老式PerlMonks文章「[Perl無法解析:正式證明]」(http://www.perlmonks.org)回答問題。 /?node_id = 663393)「 – DVK 2013-05-07 20:22:23

+0

你怎麼能不告訴別人? – ikegami 2013-05-07 21:09:50

回答

9

感謝您的詢問。 perlmonks文章和我目前的解析工作解決了兩個不同的相關問題。問題1:Perl解析是否完全一般,可由圖靈機決定?問題2:作爲一個實際問題,Marpa可以解析Perl 5嗎?

您可能會比較兩個問題:「每個C程序的行爲是否可確定?」和「機器X可以運行用C編譯的程序嗎?」答案分別是「否」和「是爲了所有實際目的和X的合理選擇」。所以我的perlmonks文章(更新here)是關於Perl程序的語法是否完全一致的可判定的理論問題。請注意,在這種情況下Perl解析的可判定性與Marpa,遞歸下降,野牛等等無關 - 它是關於圖靈機的。

問題2是「Can Marpa驅動一個實用的Perl 5解析器嗎?」當前的Perl 5語法分析器是LALR,具有單獨的詞法分析器和大量的程序幫助。 Marpa比LALR更強大,允許使用單獨的詞法分析器,並且比LALR提供更多程序代碼的幫助。我在a recent blog post中解決了速度問題:「Earley解析速度夠快嗎?」我剛纔所說的是非常電報 - 但我希望它能夠概述我如何證明我對問題2的「是」的答案。

沒有深層的建築問題阻礙了Marpa驅動Perl 5解析器。在這一點上,這確實是一個舒適程度的問題。