標籤:

任何編程語言都可以編譯為原生的機器碼嗎?

不考慮可移植性,可考慮是否可行。


可以。

樓主應該是說那種一遍的,直接丟 exe 或者 elf 的編譯而不是 JIT 吧,可以。

比如一個「解釋性的」語言中的 a+b

你就可以編譯成:

OpPlus(GetVariable(E, "a"), GetVariable(E, "b"));

或者(CEK 式)

GetVariable(E, "a", [](Object a){ return GetVariable(E, "b", [a](Object b) {
return OpPlus(a, b, K); }); });

這就是 Inline Tracing。


這個我得抖機靈一下…

給@Belleve補充一下實例:

PHP:HPHPc:HHVM之前Facebook的把PHP編譯為C++的編譯器

Python:Nuitka Home | Nuitka Home

還有各種用C--為後端的編譯器,例如https://www.haskell.org/ghc/


首先,現在很多通常認為是「非編譯」的語言都已經配備了 JIT。這些語言中可以編譯為 native code 的部分在運行的時候都有機會編譯成 native code。為什麼只能說有機會呢,因為這些語言的 runtime dynamic 太複雜,做整體的 compile-time 優化得不償失。不過這是題主說的「可行性」,所以不表。從這個角度說,所有語言都可以運行在 native code + runtime env 的方式下。和 C/Pascal 之類並沒有質的區別。

但是不同的是如果這個 runtime 太複雜,你也不好意思說自己是編譯出來的。比如說 C 的 runtime,基本就是一組庫。C++ runtime 複雜一些,但是基本也能和語法結構對應起來。但是如果有 GC 的語言呢,暴漲出來一塊 GC,你總不好意思說是編譯出來的吧。而且 GC 不是一個庫,它和語言其它部分的交互遠比庫複雜。或者帶 closure 的語言,不好說 closure 的東西都是編譯出來的。所以這個東西是灰色的。討論的時候腦子裡要有一個漸變圖。


————

這個答案亟待施工,寫時匆忙,沒有時間寫的更簡練;往下看時請無視磚頭和瓦斯。

先給一下我的大致觀點:

目標代碼里有runtime不影響是否是編譯。

JIT不算編譯,而是高級版的解釋技術。AOT才是。

————

這個問題乍一看起來有點難以招架。通用圖靈機UTM的定義保證任意UTM可以彼此模擬(執行等價的圖靈機——也就是程序——並給出相同意義的結果),但這種模擬是否我們一般意義上的編譯呢?

回顧一下編譯和解釋的根本區別,不難發現編譯型語言在編譯時執行的是從一個圖靈機(編程語言源代碼表示,指代為A)到另一個圖靈機(機器語言表示,指代為 B)的等價變換,目標是讓程序從只有人能讀寫的源代碼變換成能被CPU(也是一種UTM)直接執行的機器代碼。而純解釋型語言做的則是用一個物理CPU上執行的 UTM(這裡是解釋器)去直接解釋A[1];虛擬機型語言則進行了兩步:1,將A等價變換到C(中間代碼表示的A等價圖靈機);2,用另一個物理CPU上 執行的UTM(這裡是虛擬機)去解釋C[2]。由此([1][2])可見所有種類的解釋執行都少不了在通用型CPU上架設另一個UTM這一步;同樣所有編譯型語言都無需這個。

(題外話:之前java大興時,貌似有不少公司打過java原生CPU的主意,也就是讓CPU可以直接執行java bytecode——這種CPU上java bytecode就可以認為是原生代碼,java語言由是在該種CPU上就是編譯型語言。但顯而易見,目前大興的x86/arm CPU上java都不是——我的意思是當前實現包括hotspot/J9/dalvik都不是)

使如上判斷成立,問題就轉變為:是否任何圖靈機都能通過等價變換,使得在所有UTM上都可以直接(不經另一個特定UTM轉換)執行?

答案貌似是顯而易見的:是——因為這就是UTM的定義啊:能夠模擬其它所有圖靈機(包括UTM)的圖靈機。

(……結果推著推著推到最後發現跟我之前預料的答案完全相反啊!)

檢查之前的推論若干次才發現了問題:1,把「任何編程語言」代換成了「任何圖靈機」,但其實這後面存在一個自然語言里可以忽略但是形式代換時就不可忽略的的賓語:「的任何符合文法的程序」;2,上面的「模擬」到底是否「編譯」呢(這不是坑爹么!推演了半天然後一開始的問題又原樣蹦出來了啊喂!)。然後有一個關鍵字突然蹦進了我的腦海:eval。

(lisp的eval本生想必大家都熟悉了吧?不知道的可以去看看g9苣苣的 LISP的過去和現在http://blog.csdn.net/g9yuayon/article/details/565695 瞻仰一下)

從上面可以看出,eval本身是個天然的解釋器(另外就是。。。上面的模擬包括解釋執行)。說句不好聽的,誰學習動態語言時沒被「不到萬不得已千萬不要用eval」、「需要用到eval證明你的設計有問題」吼過?原因其實很簡單,用eval時基本所有高級語言都要進行跟解釋執行一樣的詞法語法解析、AST樹生成等等,極大降低了效率——雖然他們的始祖lisp里這個問題小得多,因為lisp里你本身就是在AST樹上編程。你看看可以AOT的java和C#都沒有直接的eval,facebook後來出的可編譯PHP變種hack也是直接去掉了eval支持,不是沒有原因的。

由此可見,有eval的語言就不要想一般意義上的編譯器了,因為eval內容只有運行時可知。其他語言……留待具體問題具體分析吧。


當然可以了。C++就不說了,IronPython和C#最終都是通過編譯成機器碼來運行的,所有其他語言最後都可以編譯成C++、C#和IronPython,因此所有語言最終都快可以通過編譯成機器碼來運行。


首先明確一點任何需要都需要被翻譯成機器碼才能最終執行。

目前的編程語言編譯類型大致可以分為三種:

1.源代碼-編譯器-本機代碼-運行

2.源代碼-解釋器-本機代碼-運行

3.源代碼-中間語言-虛擬機(相當於解釋器)-本機代碼-運行

可以發現最後都需要變成本機代碼才能執行。

Update:12月12日11:08

樓上的編譯型語言會誤導新手,語言是不分編譯型和解釋型的,只不過像C語言叫做編譯型語言,只不過是C語言一般(一般指約定俗成,或者大多數人覺得)是編譯成本機代碼再運行的。C語言完全可以用一個解釋器實時解釋(JIT:Just In Time)來運行。

綜上:我覺得語言沒有編譯型和解釋型之分。


話說不編譯成機器碼怎麼執行啊,cpu又不認識c語言。


只要可以執行,這是必然的,因為CPU只認機器碼,隨便你語法和形式上繞多少個彎,最後都必須還原成機器碼餵給CPU吃,可以說機器碼無原生與非原生這種說法


只要承認JIT也是編譯,就可以。

eval和GC可以做在庫里(例子:Pascal Script、Boehm GC),這並不妨礙編譯。


不一定。任何遞歸可枚舉的文法都可被圖靈機識別。但是如果定義一種語言,它的字母表或產生式規則不是有限的,那它就不能被圖靈機識別了吧。


首先,編譯和和解釋的區別,我認為編譯只是一種高級的優化技術,其利用計算機體系結構的特徵進行等價轉換,或者是利用提取不變數來達到加速的目的。所以,這兩者只是在技術上有差別,本質上沒有差別。

狹義的看:

代碼是數據,反過來數據也是可以是代碼,這取決於打開數據的程序。

一個簡單的例子就是,用文本軟體打開可執行文件,那就是數據,用命令行打開,就是程序;

廣義的看:

同樣一朵花,有人覺得美,有人覺得丑,有人覺得這隻一朵花,而有人則因此頓悟而微笑;

就像SICP上的一句話,如果說藝術解釋了我們的夢想,那麼計算機只是以程序的名義執行著它們。


可以可以。任何兩種圖靈機完備的機器都可以互相模擬(編譯成對方的「native code」)


不能這麼說 因為解釋型語言中間經過了解釋器。如果你認為這也算是生成了機器碼,那我只能說我用word敲一篇文檔也算被編譯成機器碼了,因為畢竟執行了。


推薦閱讀:

解釋性語言存在的意義?
為什麼沒有國產的C/C++的編譯器?
在獨自實現一個小型編譯器中你遇到過哪些困難?
ANTLR涉及編譯原理中的哪些部分?

TAG:編譯原理 |