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