遞歸下降純解釋器編寫的困惑

2019-11-17 05:16:45

字體：大中小

來源：轉載

供稿：網友

　　python,lua還有javascript這些腳本語言其實是通過編譯成中間碼，然后再解釋這個中間碼來執行的，所以并不是純解釋的腳本。假如要寫一個純解釋的腳本語言解釋器，這種解釋器的速度肯定不會很快，但是程序可以更簡單一些。這對于需要小型的腳本解釋器的情況比較適用，因為一個人只要幾天就可以完成。比如unix的shell,windows中的cmd等。當然，對于一般的程序員來說，主要是為了嵌入自己的程序。假設我們的腳本包含變量，基本表達式，順序，分支，循環語句，goto等。手工編寫，當然是采用遞歸下降方法。

　　變量用一個鏈表或數組就可以解決。解釋賦值語句時，將變量存在符號表中。　　

　　表達式已經有很成熟的解決方法，就是一個算符堆棧，一個操作數堆棧，然后按算符優先級來做就可以了　　

　　然后我們討論基本語句的執行　　

　　statements==>if_statements,for_statements,goto_statements等

　　我們用c函數exec_if,exec_for,exec_goto來分別解釋它們，用exec_statements()函數來遞歸調用前面這些函數。　　

　　假如是如下順序執行的腳本，實現是比較輕易的，就是順序執行。　　

　　COMMAND：statements;　　

　　就是前面是命令后面是語句，在c語言中可以用一個switch輕松搞定。但是假如出現了分支與循環，函數的時候，情況就變得復雜了。先看循環語句，比如如下腳本　　

　　for i= 1 to 100 do　　

　　statements;　　

　　end　　

　　假設現在我們已經將腳本都加載到內存中了，有一個char *指針current指向當前的腳本的位置。這個解釋執行并不難。先解釋for i=1 to 100 do這句，將自變量i保存到符號表中,這時候current已經指向statements了。循環解釋執行的c程序偽碼如下：　　

　　char *old=current;　　

　　for(i=自變量開始值;i++;i<自變量目標值)　　

　　{　　

　　 current =old;　　

　　執行 statements;(這個過程中current會變化)　　

　　}　　

　　其中自變量開始值和自變量目標值都可以解釋獲得，每次執行完statements后在開始循環時恢復current指針即可。　

　　但是分支語句可沒這么簡單，比如腳本　　

　　if eXP1 then　　

　　 statements1;　　

　　elseif exp2 then　　

　　statements2;　　

　　end　　

　　假設exp1為真則執行statements1,exp2為真則執行statement2。那么解釋執行的時候問題就來了，當exp1為真時，執行完statements1后，我們要跳過statements2到end,然后再執行，同樣exp1為假，exp2為真的時候，問題也同樣存在，需要跳過statements1.問題是怎么跳過？statements1，statements2均可能包含嵌套的分支或循環。在編譯型的腳本中，其實不管是statements1,statements2在編譯的時候都是需要編譯的，在編譯完這些語句后再進行代碼回填。這樣在執行中間碼的過程中exp1,exp2執行完后，就知道跳到哪里執行了，實際上在執行中間碼的時候腳本編譯器已經進行了一次源碼的掃描了，執行的函數不關心這些。但是我們現在是純解釋執行，就是一次掃描了。除了編譯成中間碼這個方法外，我沒有想到更優雅的辦法，這個方法因為涉及到編譯，不是純解釋因此排除掉。對每種語句都有一個解釋執行該語句的函數，例如　　

　　for 語句我們用exec_for()函數來執行，if我們用exec_if來執行。一種方法是可以對應編寫一個pass函數，例如pass_for(),pass_if(),這樣對于statements我們只需要一個pass_statements()函數就可以了，pass_statements()遞歸調用pass_for,pass_if，這樣就可以過濾掉不需要執行的語句了。pass函數只改變current的值而并不執行被pass掉的那些語句。　　

　　顯然pass_statemts除了不修改符號表，不做其它動作外，其它邏輯流程與exec_statements函數相同。這顯然不夠優雅。
　　
　　goto則需要先掃描行號，執行goto時跳到對應的行。　　

　　不知有沒有更好的coding技巧，探索中。

上一篇：用GDI+實現半透明漸變的特效窗口

下一篇：一個c++寫的發牌程序