用最快的速度設計一種新的編程語言
最近打算寫一些列有趣、而且有一定難度的文章。這個系列的名字就叫《瘋狂極客》，這一系列的文章大多數與計算機有密切的關系。包括制作編譯器、制作OS、Android控制電路板、機器人的制作（通過Android、IOS等設備控制）等等。
在正式開始《瘋狂極客》系列文章之前，先來熱熱身。用最短的時間設計一種簡單，但好玩的編程語言CShell(不過不用擔心，實現CShell解析器基本上用不著編譯原理的知識，但以后的文章就會涉及到很多編譯原理的內容了)。從CShell的名稱可以猜到，是一種C風格的語言，并且可以像Shell一樣解釋執行（動態語言）。當然，這種語言不可能像C語言或Shell一樣強大，因為C語言的編譯器實現起來盡管不復雜（因為是結構化編程語言，沒有類、接口這些東西，實現起來要比Java編譯器簡單得多），但仍然不太可能在很短的時間內完成（一至兩天）。不過本文實現的CShell盡管簡單，但仍然可以實現一些算法。CShell語言支持輸出值和變量、條件語句（if），for循環，自加、自減、+、-、*、/操作，函數（支持遞歸）。由于CShell是動態語言，所以不需要聲明變量，不過支持全局和局部變量，當然，還支持數組（整數、字符串類型數組），所以使用CShell可以很容易實現像冒泡排序、階乘等算法。
在討論CShell的設計原理和實現過程之前，先看一些用CShell編寫的程序。單從這些程序所完成的工作來看都太太太簡單了，不過這回完全不同，這回是用我們自己發明的新語言來實現這些算法，例如，遞歸階乘計算、冒泡排序，是不是很酷呢！！Let’s go！
- // 簡單的變量輸出
- xx= 45;
- _ok = 64;
- print (xx);
- a1 = 65;
- print (a1);
- // 數組演示
- $arr = [1,2,3,4,5,"aa"]; // 數值與字符串換搭的數組，$表示全局變量
- print($arr); // 輸出數組的所有元素
- print($arr[2]); // 輸出數組的第3個元素
- // 三重for循環
- $x = 0; // 全局變量
- // i、j、z都為局部變量，for循環外不可訪問
- for(i=0;i<10;i=i+1)
- {
- for(j = 0; j < 10; j=j+1)
- {
- for(z = 0; z < 10; z = z + 1)
- {
- $x = $x + 1;
- }
- }
- }
- print($x); // 輸出1000
- // 計算10的階乘，涉及到函數的遞歸操作和if語句
- def jc(n)
- {
- if(n == 0)
- {
- return 1;
- }
- else if(n == 1)
- {
- return 1;
- }
- else
- {
- return jc(n - 1) *n;
- }
- }
- print("10！");
- print(jc(10)); // 計算10的階乘（3628800）
- // 冒泡排序（降序）
- $arr = [5,3,1,7,5,4,-56,12];
- $len = length($arr);
- // 雙循環冒泡排序
- for(i = 0; i < $len; i++)
- {
- for(j = 0; j < $len - 1; j++)
- {
- if($arr[j] < $arr[j+1])
- {
- x = $arr[j+1];
- $arr[j+1] = $arr[j];
- $arr[j] = x;
- }
- }
- }
- print($arr); // 輸出[12, 7, 5, 5, 4, 3, 1, -56]
如何設計和實現編程語言
設計一種編程語言的方法很多，當然，通常的做法是要學好編譯原理，然后按部就班地從詞法分析器做起，然后是詞法分析器、語義分析、中間代碼生成、中間代碼優化，目標代碼生成，如果語言需要使用runtime運行，還需要編寫可以運行目標代碼的虛擬機（解釋目標代碼的程序，例如jvm就是解析Java字節碼文件的虛擬機）。看著就有點暈。而且估計現在很多科班出身的程序員編譯原理學的一塌糊涂。就算編譯原理學的很好，光憑編譯原理的理論，如果要想編寫一個比較復雜的編譯器或解析器也是很難辦到的（尤其是加入面向對象功能）。這是因為一個復雜的編譯器有很多代碼幾乎不太可能完全通過手工編寫，例如，語法分析如果使用LL（*）分析方式，計算大量的first和follow集合就非常恐怖，就算把代碼編寫完了，如果要為語言增加或修改新的語法，修改這些代碼將又是一場惡夢。所以大多數復雜的工業級編程語言都是通過半自動化的方式完成的。
所謂半自動化，就是指不可能完全通過自動的方式生成編譯器，而只能通過自動的方式生成編譯器最核心的部分：詞法分析器和語法分析器。基本的做法是通過DSL（domain-specific language ）指定詞法和語法的結構和必要的信息，然后編譯器的編譯器（生成編譯器的程序）會根據DSL自動生成詞法和語法解析器，當然，通過DSL可以增加語義部分的代碼，這樣生成的程序就直接擁有語義解析功能了。
對于很多***的企業，如google、微軟、intel、IBM，都會有自己的CC（編譯器的編譯器），不過對于個人或小企業，完全開發一套CC難度會很大（這東西比開發一套編譯器的難度更大）。所以我們可以使用開源免費的CC。例如JavaCC、lex、yacc、antlr等。其中JavaCC只支持Java語言，lex是詞法分析器的生成器、yacc是語法分析器的生成器，這兩個支持從C語言，而antlr支持多種語言，如Java、C#、ruby、C/C++、JavaScript等等。所以本文使用Antlr來設計和實現CShell語言。
CShell語言是如何練成的
盡管CShell依靠Antlr來實現，需要自己編寫的代碼仍然非常多，因此本文只介紹核心的代碼和實現原理。更詳細的代碼請參考本文提供的源代碼。
學過編譯原理的讀者首先就會想到，設計語言首先就是進行詞法分析，然后根據詞法分析的結果進行語法分析。幸運的是，這兩樣都可以利用Antlr自動完成。
所謂詞法分析，就是將語言文本分成最小但愿的詞素（稱為Token）。例如，下面的是一段CShell語言的代碼。
- for(i = 0; i < $len; i++)
- {
- }
如果要對這段代碼進行詞法分析，就會分解成如下的一系列Token
- “for”、“(”、“i”、“=”、“0”、“;”、“i”、“<”、“$len”、“;”、“i”、“++”、“{”、“}”
當然，要想自己編程實現這個分析，就需要使用到有限自動機（DFA）進行處理，盡管程序不復雜，但還是比較麻煩的。有了Antlr，就容易得多了。通常只要定義這些Token的規則即可。有些Token是與語法規則放到一起的，有些是單獨的詞法規則。例如，上面代碼中有兩個變量（i和$len），其中i局部變量、$len為全局變量，這兩個變量都屬于標識符范疇，所以可以定義一個專門識別標識符號的詞法規則。
- ID : '$'?(LETTER|'_') (LETTER | '0'..'9')* ;
其中ID是詞法規則名稱，詞法規則名稱的***個字母必須大寫。LETTER表示26個小寫和26個大寫字母。“？”表示可以有，也可能沒有，“*”為星閉包，表示重復0次到N次。
- LETTER: ('a'..'z' | 'A'..'Z')
從ID的詞法規則可以看出，ID就是可能以“$”開頭，也可能沒有“$”。不管有沒有“$”，下一個字符必須是字母或下劃線，接下來的字母或者是字母、或者是數字的任意字符串。例如abc、_xyz123、$_23都認為是ID。Antlr會自動根據這個規則生成Java代碼。
其他的Token分析也采用類似的方法，例如，識別字符串可以使用下面的規則。
- STRING: '\"' .* '\"' ;
其中“.*”表示任意字符序列。也就是在CShell里一個字符串就是在兩個雙引號中的任意字符序列。
詞法處理完，就是相應的語法了，詞法的分析結果是Token序列，而這個序列正式語法分析的輸入。也就是說語法分析和詞法分析的方式很像，只是詞法分析的輸入是單個字符序列，輸出是Token序列。而語法分析的輸入是Token序列，輸出可能有多種，也可能沒有輸出，在分析的過程中就執行相應的動作（語義處理），也可能生成AST（抽象語法樹），然后進一步對其進行優化。本例使用的是AST方式，也就是說將CShell源代碼經過語法分析后轉換為一顆AST，目的是去掉一些雜質，例如，for循環中只有i、$len、++等標識符和運算符號是有用的，但左右括號就沒有任何用處，這些輔助符號是為了區分for語句和其他語句的。
這里只看一個稍微簡單的if語句的語法規則。
- statement : 'if' '(' expr ')' slist elseif_statement_all else_statement?
其中slist是另外一個產生式，表示if和else if之間的部分。
- slist // 原內容： ':' NL (statement)+ '.' NL
- : NL*'{' NL* (statement)* NL* '}'NL* -> ^(BLOCK statement*)
- ;
其中NL表示空行。而^(BLOCK statement*)部分表示AST，其中BLOCK為AST的根節點，從這一點可以看出，AST已經將slist中的左右大括號都過濾出去了，只剩下有實際意義的statement。
從statement和slist的定義可以看出，if語句必須以“if”開頭，Antlr會將if作為一個Token返回給語法分析器。然后緊跟著if的是左括號，接觸是表達式（expr，另外一個產生式），然后就是if語句的執行體（slist），接著就是elseif部分，剩下的部分就與if部分的定義類似了，請讀者參看源代碼中的antlr/CShell.g文件。
那么編寫完Antlr需要的DSL，接下來做什么呢？接下來就要自己來做語義部分，這部分內容非常復雜，基本的思想就是通過語法分析將變量、關鍵字（for、if等）返回，然后由語義部分決定如何做。例如，對于變量，通常做法是定義一個符號表（使用Map對象即可），變量名就是Map的key，先將該變量存儲在Map對象中。如果遇到某個變量，會首先到Map對象中查找，如果未找到，就定義該變量（將變量和變量值存入Map對象），如果找到，就直接去除變量值使用。至于for、if語句如何處理，就要利用語法分析生成的AST了。
其中Interpreter類是分析的核心類，給類有一個exec方法，需要將AST的根節點傳入該方法，也就是說執行CShell代碼的過程就是遍歷AST的過程，AST是多叉樹，遍歷需要使用廣度優先方式遍歷。exec方法的代碼如下：
- // CShellAST表示AST節點的類型，一個普通Java類
- public Object exec(CShellAST ast)
- {
- try
- {
- switch (ast.getType())
- {
- case CShellParser.BLOCK: // 處理塊操作
- block(ast);
- break;
- case CShellParser.ASSIGN: // 處理賦值操作
- assign(ast);
- break;
- case CShellParser.LENGTH: // 處理返回長度操作
- return length(ast);
- case CShellParser.ARRAY: // 處理數組操作
- arrayStat(ast);
- break;
- case CShellParser.RETURN:
- ret(ast);
- break;
- case CShellParser.PRINT:
- print(ast);
- break;
- case CShellParser.IF: // 處理if語句
- ifstat(ast);
- break;
- case CShellParser.FOR:
- forloop(ast);
- break;
- case CShellParser.CALL:
- return call(ast);
- case CShellParser.ADD:
- return add(ast);
- case CShellParser.PREV:
- case CShellParser.SUFFIX:
- return incAndDec(ast);
- case CShellParser.SUB:
- return op(ast);
- case CShellParser.MUL:
- case CShellParser.DIV:
- return op(ast);
- case CShellParser.EQ:
- return eq(ast);
- case CShellParser.LT:
- return lt(ast);
- case CShellParser.GT:
- return gt(ast);
- case CShellParser.INT:
- return Integer.parseInt(ast.getText());
- case CShellParser.CHAR:
- return new Character(ast.getText().charAt(1));
- case CShellParser.FLOAT:
- return Float.parseFloat(ast.getText());
- case CShellParser.STRING:
- String s = ast.getText();
- return s.substring(1, s.length() - 1);
- case CShellParser.ID:
- case CShellParser.ARRAY_ELEMENT:
- return load(ast);
- default: // catch unhandled node types
- throw new UnsupportedOperationException("無法處理"
- + ast.getText() + "<" + ast.getType() + ">");
- }
- }
- catch (Exception e)
- {
- listener.error("異常原因： " + ast.toStringTree(), e);
- }
- return null;
- }
下面只看一個如何處理if語句的ifstat方法的實現代碼
- private void ifstat(CShellAST ast)
- {
- // 下面的代碼需要從當前AST節點（表示if語句根節點）的子節點獲取
- // if語句的各個組成部分
- // 獲取if語句的兩個圓括號直接的表達式部分
- CShellAST expr = (CShellAST) ast.getChild(0);
- // 獲取if條件如果為true要執行的代碼塊
- CShellAST ifBlock = (CShellAST) ast.getChild(1);
- // 獲取elseif的部分（包括條件表達式和要執行的塊）
- CShellAST elseifAll = (CShellAST) ast.getChild(2);
- // 獲取else部分要執行的代碼塊
- CShellAST elseBlock = (CShellAST) ast.getChild(3);
- // 利用遞歸方式再次調用exec方法執行表達式，并返回值
- Boolean c = (Boolean) exec(expr);
- // 如果為true，執行if block
- if (c.booleanValue())
- {
- exec(ifBlock); // 遞歸執行if block
- }
- else
- {
- // 判斷有多少個elseif部分，CShell支持有無限多個else if語句
- if (elseifAll.getChildCount() > 0)
- {
- List<CShellAST> children = elseifAll.getChildren();
- // 挨個判斷else if后面的表達式是否為true
- for (CShellAST child : children)
- {
- expr = (CShellAST) child.getChild(0);
- ifBlock = (CShellAST) child.getChild(1);
- c = (Boolean) exec(expr);
- // 如果某個else if條件為true，直接執行else if后面的代碼塊，
- // ***返回，剩下的都不執行了
- if (c.booleanValue())
- {
- exec(ifBlock);
- return;
- }
- }
- }
- // ***會執行else語句（因為前面的條件都為false）
- // 判斷是否有else語句（最多只能有1個else子句）
- if (elseBlock.getChildCount() == 1)
- {
- exec((CShellAST) elseBlock.getChild(0)); // 執行else block
- }
- }
- }
CShell代碼分析器的入口類是CShell，在該類中調用了Interprefer.process方法讀者CShell語言源代碼。其中bubble.cs就是CShell語言的源代碼文件，可以換成其他的源代碼文件。調用process方法后，就會根據具體的CShell代碼執行相應的操作。例如，print(…)語句會輸出相應的字符串。
- public class CShell
- {
- public static void main(String[] args) throws Exception
- {
- InputStream input = null;
- input = new FileInputStream("source/bubble.cs");
- Interpreter interp = new Interpreter();
- interp.process(input);
- }
- }
如果讀者對Antlr還不太理解也沒關系，本文只是拋磚引玉，目的并不是講解Antlr。只是希望讀者對Antlr以及設計一種語言的過程有所了解。在后面的一系列文章中將會深度探討編譯原理以及Antlr的使用方法。通過設計自己的專有語言***的作用是可以顯著提高工作效率，例如，可以將常用的工作抽象成某些語句，到時只要一執行腳本就可完成需要數小時，甚至數天才能完成的工作。
原文鏈接：http://www.cnblogs.com/nokiaguy/archive/2013/03/12/2955128.html
