自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

用最快的速度設(shè)計(jì)一種新的編程語(yǔ)言

作者：李寧的極客世界
開(kāi)發(fā) 開(kāi)發(fā)工具 后端
在正式開(kāi)始《瘋狂極客》系列文章之前，先來(lái)熱熱身。用最短的時(shí)間設(shè)計(jì)一種簡(jiǎn)單，但好玩的編程語(yǔ)言CShell(不過(guò)不用擔(dān)心，實(shí)現(xiàn)CShell解析器基本上用不著編譯原理的知識(shí)，但以后的文章就會(huì)涉及到很多編譯原理的內(nèi)容了)。

最近打算寫(xiě)一些列有趣、而且有一定難度的文章。這個(gè)系列的名字就叫《瘋狂極客》，這一系列的文章大多數(shù)與計(jì)算機(jī)有密切的關(guān)系。包括制作編譯器、制作OS、Android控制電路板、機(jī)器人的制作（通過(guò)Android、IOS等設(shè)備控制）等等。

源代碼下載 

在正式開(kāi)始《瘋狂極客》系列文章之前，先來(lái)熱熱身。用最短的時(shí)間設(shè)計(jì)一種簡(jiǎn)單，但好玩的編程語(yǔ)言CShell(不過(guò)不用擔(dān)心，實(shí)現(xiàn)CShell解析器基本上用不著編譯原理的知識(shí)，但以后的文章就會(huì)涉及到很多編譯原理的內(nèi)容了)。從CShell的名稱可以猜到，是一種C風(fēng)格的語(yǔ)言，并且可以像Shell一樣解釋執(zhí)行（動(dòng)態(tài)語(yǔ)言）。當(dāng)然，這種語(yǔ)言不可能像C語(yǔ)言或Shell一樣強(qiáng)大，因?yàn)镃語(yǔ)言的編譯器實(shí)現(xiàn)起來(lái)盡管不復(fù)雜（因?yàn)槭墙Y(jié)構(gòu)化編程語(yǔ)言，沒(méi)有類、接口這些東西，實(shí)現(xiàn)起來(lái)要比Java編譯器簡(jiǎn)單得多），但仍然不太可能在很短的時(shí)間內(nèi)完成（一至兩天）。不過(guò)本文實(shí)現(xiàn)的CShell盡管簡(jiǎn)單，但仍然可以實(shí)現(xiàn)一些算法。CShell語(yǔ)言支持輸出值和變量、條件語(yǔ)句（if），for循環(huán)，自加、自減、+、-、*、/操作，函數(shù)（支持遞歸）。由于CShell是動(dòng)態(tài)語(yǔ)言，所以不需要聲明變量，不過(guò)支持全局和局部變量，當(dāng)然，還支持?jǐn)?shù)組（整數(shù)、字符串類型數(shù)組），所以使用CShell可以很容易實(shí)現(xiàn)像冒泡排序、階乘等算法。

在討論CShell的設(shè)計(jì)原理和實(shí)現(xiàn)過(guò)程之前，先看一些用CShell編寫(xiě)的程序。單從這些程序所完成的工作來(lái)看都太太太簡(jiǎn)單了，不過(guò)這回完全不同，這回是用我們自己發(fā)明的新語(yǔ)言來(lái)實(shí)現(xiàn)這些算法，例如，遞歸階乘計(jì)算、冒泡排序，是不是很酷呢?。et’s go！

  1. //  簡(jiǎn)單的變量輸出   
  2. xx= 45;   
  3. _ok = 64;   
  4. print (xx);   
  5. a1 = 65;   
  6. print (a1);   
  7.     
  8. //  數(shù)組演示   
  9.     
  10. $arr = [1,2,3,4,5,"aa"];  //  數(shù)值與字符串換搭的數(shù)組，$表示全局變量   
  11. print($arr);           //  輸出數(shù)組的所有元素   
  12. print($arr[2]);         //  輸出數(shù)組的第3個(gè)元素   
  13.     
  14. //  三重for循環(huán)   
  15. $x = 0;  //  全局變量   
  16. //  i、j、z都為局部變量，for循環(huán)外不可訪問(wèn)   
  17. for(i=0;i<10;i=i+1)   
  18. {   
  19.     for(j = 0; j < 10; j=j+1)   
  20.     {   
  21.         for(z = 0; z < 10; z = z + 1)   
  22.         {   
  23.             $x = $x + 1;   
  24.         }       
  25.     }   
  26. }   
  27. print($x);   //  輸出1000   
  28.     
  29. //  計(jì)算10的階乘，涉及到函數(shù)的遞歸操作和if語(yǔ)句   
  30.     
  31. def jc(n)   
  32. {   
  33.     if(n == 0)   
  34.     {   
  35.         return 1;   
  36.     }   
  37.     else if(n == 1)   
  38.     {   
  39.         return 1;   
  40.     }   
  41.     else 
  42.     {   
  43.         return jc(n - 1) *n;   
  44.             
  45.     }   
  46.         
  47. }   
  48. print("10！");   
  49. print(jc(10));  //  計(jì)算10的階乘（3628800）   
  50.     
  51. //  冒泡排序（降序）   
  52. $arr = [5,3,1,7,5,4,-56,12];   
  53. $len = length($arr);   
  54. //  雙循環(huán)冒泡排序   
  55. for(i = 0; i < $len; i++)   
  56. {   
  57.     for(j = 0; j < $len - 1; j++)   
  58.     {   
  59.         if($arr[j] < $arr[j+1])   
  60.         {       
  61.             x = $arr[j+1];   
  62.             $arr[j+1] = $arr[j];   
  63.             $arr[j] = x;   
  64.         }   
  65.     }   
  66. }   
  67.     
  68. print($arr);  //  輸出[12, 7, 5, 5, 4, 3, 1, -56] 

如何設(shè)計(jì)和實(shí)現(xiàn)編程語(yǔ)言

設(shè)計(jì)一種編程語(yǔ)言的方法很多，當(dāng)然，通常的做法是要學(xué)好編譯原理，然后按部就班地從詞法分析器做起，然后是詞法分析器、語(yǔ)義分析、中間代碼生成、中間代碼優(yōu)化，目標(biāo)代碼生成，如果語(yǔ)言需要使用runtime運(yùn)行，還需要編寫(xiě)可以運(yùn)行目標(biāo)代碼的虛擬機(jī)（解釋目標(biāo)代碼的程序，例如jvm就是解析Java字節(jié)碼文件的虛擬機(jī)）?？粗陀悬c(diǎn)暈。而且估計(jì)現(xiàn)在很多科班出身的程序員編譯原理學(xué)的一塌糊涂。就算編譯原理學(xué)的很好，光憑編譯原理的理論，如果要想編寫(xiě)一個(gè)比較復(fù)雜的編譯器或解析器也是很難辦到的（尤其是加入面向?qū)ο蠊δ埽＿@是因?yàn)橐粋€(gè)復(fù)雜的編譯器有很多代碼幾乎不太可能完全通過(guò)手工編寫(xiě)，例如，語(yǔ)法分析如果使用LL（*）分析方式，計(jì)算大量的first和follow集合就非?？植?，就算把代碼編寫(xiě)完了，如果要為語(yǔ)言增加或修改新的語(yǔ)法，修改這些代碼將又是一場(chǎng)惡夢(mèng)。所以大多數(shù)復(fù)雜的工業(yè)級(jí)編程語(yǔ)言都是通過(guò)半自動(dòng)化的方式完成的。

所謂半自動(dòng)化，就是指不可能完全通過(guò)自動(dòng)的方式生成編譯器，而只能通過(guò)自動(dòng)的方式生成編譯器最核心的部分：詞法分析器和語(yǔ)法分析器。基本的做法是通過(guò)DSL（domain-specific language ）指定詞法和語(yǔ)法的結(jié)構(gòu)和必要的信息，然后編譯器的編譯器（生成編譯器的程序）會(huì)根據(jù)DSL自動(dòng)生成詞法和語(yǔ)法解析器，當(dāng)然，通過(guò)DSL可以增加語(yǔ)義部分的代碼，這樣生成的程序就直接擁有語(yǔ)義解析功能了。

對(duì)于很多***的企業(yè)，如google、微軟、intel、IBM，都會(huì)有自己的CC（編譯器的編譯器），不過(guò)對(duì)于個(gè)人或小企業(yè)，完全開(kāi)發(fā)一套CC難度會(huì)很大（這東西比開(kāi)發(fā)一套編譯器的難度更大）。所以我們可以使用開(kāi)源免費(fèi)的CC。例如JavaCC、lex、yacc、antlr等。其中JavaCC只支持Java語(yǔ)言，lex是詞法分析器的生成器、yacc是語(yǔ)法分析器的生成器，這兩個(gè)支持從C語(yǔ)言，而antlr支持多種語(yǔ)言，如Java、C#、ruby、C/C++、JavaScript等等。所以本文使用Antlr來(lái)設(shè)計(jì)和實(shí)現(xiàn)CShell語(yǔ)言。

CShell語(yǔ)言是如何練成的

盡管CShell依靠Antlr來(lái)實(shí)現(xiàn)，需要自己編寫(xiě)的代碼仍然非常多，因此本文只介紹核心的代碼和實(shí)現(xiàn)原理。更詳細(xì)的代碼請(qǐng)參考本文提供的源代碼。

學(xué)過(guò)編譯原理的讀者首先就會(huì)想到，設(shè)計(jì)語(yǔ)言首先就是進(jìn)行詞法分析，然后根據(jù)詞法分析的結(jié)果進(jìn)行語(yǔ)法分析。幸運(yùn)的是，這兩樣都可以利用Antlr自動(dòng)完成。

所謂詞法分析，就是將語(yǔ)言文本分成最小但愿的詞素（稱為Token）。例如，下面的是一段CShell語(yǔ)言的代碼。

  1. for(i = 0; i < $len; i++)   
  2. {   
  3. } 

如果要對(duì)這段代碼進(jìn)行詞法分析，就會(huì)分解成如下的一系列Token

  1. “for”、“(”、“i”、“=”、“0”、“;”、“i”、“<”、“$len”、“;”、“i”、“++”、“{”、“}” 

當(dāng)然，要想自己編程實(shí)現(xiàn)這個(gè)分析，就需要使用到有限自動(dòng)機(jī)（DFA）進(jìn)行處理，盡管程序不復(fù)雜，但還是比較麻煩的。有了Antlr，就容易得多了。通常只要定義這些Token的規(guī)則即可。有些Token是與語(yǔ)法規(guī)則放到一起的，有些是單獨(dú)的詞法規(guī)則。例如，上面代碼中有兩個(gè)變量（i和$len），其中i局部變量、$len為全局變量，這兩個(gè)變量都屬于標(biāo)識(shí)符范疇，所以可以定義一個(gè)專門識(shí)別標(biāo)識(shí)符號(hào)的詞法規(guī)則。

  1. ID  :   '$'?(LETTER|'_') (LETTER | '0'..'9')*  ; 

其中ID是詞法規(guī)則名稱，詞法規(guī)則名稱的***個(gè)字母必須大寫(xiě)。LETTER表示26個(gè)小寫(xiě)和26個(gè)大寫(xiě)字母。“？”表示可以有，也可能沒(méi)有，“*”為星閉包，表示重復(fù)0次到N次。

  1. LETTER:   ('a'..'z' | 'A'..'Z') 

從ID的詞法規(guī)則可以看出，ID就是可能以“$”開(kāi)頭，也可能沒(méi)有“$”。不管有沒(méi)有“$”，下一個(gè)字符必須是字母或下劃線，接下來(lái)的字母或者是字母、或者是數(shù)字的任意字符串。例如abc、_xyz123、$_23都認(rèn)為是ID。Antlr會(huì)自動(dòng)根據(jù)這個(gè)規(guī)則生成Java代碼。

其他的Token分析也采用類似的方法，例如，識(shí)別字符串可以使用下面的規(guī)則。

  1. STRING:  '\"' .* '\"' ; 

其中“.*”表示任意字符序列。也就是在CShell里一個(gè)字符串就是在兩個(gè)雙引號(hào)中的任意字符序列。

詞法處理完，就是相應(yīng)的語(yǔ)法了，詞法的分析結(jié)果是Token序列，而這個(gè)序列正式語(yǔ)法分析的輸入。也就是說(shuō)語(yǔ)法分析和詞法分析的方式很像，只是詞法分析的輸入是單個(gè)字符序列，輸出是Token序列。而語(yǔ)法分析的輸入是Token序列，輸出可能有多種，也可能沒(méi)有輸出，在分析的過(guò)程中就執(zhí)行相應(yīng)的動(dòng)作（語(yǔ)義處理），也可能生成AST（抽象語(yǔ)法樹(shù)），然后進(jìn)一步對(duì)其進(jìn)行優(yōu)化。本例使用的是AST方式，也就是說(shuō)將CShell源代碼經(jīng)過(guò)語(yǔ)法分析后轉(zhuǎn)換為一顆AST，目的是去掉一些雜質(zhì)，例如，for循環(huán)中只有i、$len、++等標(biāo)識(shí)符和運(yùn)算符號(hào)是有用的，但左右括號(hào)就沒(méi)有任何用處，這些輔助符號(hào)是為了區(qū)分for語(yǔ)句和其他語(yǔ)句的。

這里只看一個(gè)稍微簡(jiǎn)單的if語(yǔ)句的語(yǔ)法規(guī)則。

  1. statement :      'if' '(' expr ')' slist elseif_statement_all  else_statement? 

其中slist是另外一個(gè)產(chǎn)生式，表示if和else if之間的部分。

  1. slist   // 原內(nèi)容： ':' NL (statement)+ '.' NL  
  2.  
  3.         :         NL*'{' NL* (statement)* NL* '}'NL*     -> ^(BLOCK statement*)  
  4.  
  5.         ; 

其中NL表示空行。而^(BLOCK statement*)部分表示AST，其中BLOCK為AST的根節(jié)點(diǎn)，從這一點(diǎn)可以看出，AST已經(jīng)將slist中的左右大括號(hào)都過(guò)濾出去了，只剩下有實(shí)際意義的statement。

從statement和slist的定義可以看出，if語(yǔ)句必須以“if”開(kāi)頭，Antlr會(huì)將if作為一個(gè)Token返回給語(yǔ)法分析器。然后緊跟著if的是左括號(hào)，接觸是表達(dá)式（expr，另外一個(gè)產(chǎn)生式），然后就是if語(yǔ)句的執(zhí)行體（slist），接著就是elseif部分，剩下的部分就與if部分的定義類似了，請(qǐng)讀者參看源代碼中的antlr/CShell.g文件。

那么編寫(xiě)完Antlr需要的DSL，接下來(lái)做什么呢？接下來(lái)就要自己來(lái)做語(yǔ)義部分，這部分內(nèi)容非常復(fù)雜，基本的思想就是通過(guò)語(yǔ)法分析將變量、關(guān)鍵字（for、if等）返回，然后由語(yǔ)義部分決定如何做。例如，對(duì)于變量，通常做法是定義一個(gè)符號(hào)表（使用Map對(duì)象即可），變量名就是Map的key，先將該變量存儲(chǔ)在Map對(duì)象中。如果遇到某個(gè)變量，會(huì)首先到Map對(duì)象中查找，如果未找到，就定義該變量（將變量和變量值存入Map對(duì)象），如果找到，就直接去除變量值使用。至于for、if語(yǔ)句如何處理，就要利用語(yǔ)法分析生成的AST了。

其中Interpreter類是分析的核心類，給類有一個(gè)exec方法，需要將AST的根節(jié)點(diǎn)傳入該方法，也就是說(shuō)執(zhí)行CShell代碼的過(guò)程就是遍歷AST的過(guò)程，AST是多叉樹(shù)，遍歷需要使用廣度優(yōu)先方式遍歷。exec方法的代碼如下：

  1. //  CShellAST表示AST節(jié)點(diǎn)的類型，一個(gè)普通Java類   
  2.     
  3. public Object exec(CShellAST ast)   
  4. {   
  5.     try 
  6.     {   
  7.         switch (ast.getType())   
  8.         {   
  9.             case CShellParser.BLOCK:  //  處理塊操作   
  10.                 block(ast);   
  11.                 break;   
  12.             case CShellParser.ASSIGN:  //  處理賦值操作   
  13.                 assign(ast);   
  14.                 break;   
  15.             case CShellParser.LENGTH:   //  處理返回長(zhǎng)度操作   
  16.                 return length(ast);   
  17.             case CShellParser.ARRAY:   //  處理數(shù)組操作   
  18.                 arrayStat(ast);   
  19.                 break;   
  20.             case CShellParser.RETURN:   
  21.                 ret(ast);   
  22.                 break;   
  23.             case CShellParser.PRINT:   
  24.                 print(ast);   
  25.                 break;   
  26.             case CShellParser.IF:      //  處理if語(yǔ)句   
  27.                 ifstat(ast);   
  28.                 break;   
  29.             case CShellParser.FOR:   
  30.                 forloop(ast);   
  31.                 break;   
  32.             case CShellParser.CALL:   
  33.                 return call(ast);   
  34.             case CShellParser.ADD:   
  35.                 return add(ast);   
  36.             case CShellParser.PREV:   
  37.             case CShellParser.SUFFIX:   
  38.                 return incAndDec(ast);   
  39.             case CShellParser.SUB:   
  40.                 return op(ast);   
  41.             case CShellParser.MUL:   
  42.             case CShellParser.DIV:   
  43.                 return op(ast);   
  44.             case CShellParser.EQ:   
  45.                 return eq(ast);   
  46.             case CShellParser.LT:   
  47.                 return lt(ast);   
  48.             case CShellParser.GT:   
  49.                 return gt(ast);   
  50.             case CShellParser.INT:   
  51.                 return Integer.parseInt(ast.getText());   
  52.             case CShellParser.CHAR:   
  53.                 return new Character(ast.getText().charAt(1));   
  54.             case CShellParser.FLOAT:   
  55.                 return Float.parseFloat(ast.getText());   
  56.             case CShellParser.STRING:   
  57.                 String s = ast.getText();   
  58.                 return s.substring(1, s.length() - 1);   
  59.             case CShellParser.ID:   
  60.             case CShellParser.ARRAY_ELEMENT:   
  61.                 return load(ast);   
  62.             default: // catch unhandled node types   
  63.                 throw new UnsupportedOperationException("無(wú)法處理" 
  64.                         + ast.getText() + "<" + ast.getType() + ">");   
  65.         }   
  66.     }   
  67.     catch (Exception e)   
  68.     {   
  69.         listener.error("異常原因： " + ast.toStringTree(), e);   
  70.     }   
  71.     return null;   
  72. } 

下面只看一個(gè)如何處理if語(yǔ)句的ifstat方法的實(shí)現(xiàn)代碼

  1. private void ifstat(CShellAST ast)   
  2. {   
  3.     //  下面的代碼需要從當(dāng)前AST節(jié)點(diǎn)（表示if語(yǔ)句根節(jié)點(diǎn)）的子節(jié)點(diǎn)獲取   
  4.     //  if語(yǔ)句的各個(gè)組成部分   
  5.     
  6.     //  獲取if語(yǔ)句的兩個(gè)圓括號(hào)直接的表達(dá)式部分   
  7.     CShellAST expr = (CShellAST) ast.getChild(0);   
  8.     //  獲取if條件如果為true要執(zhí)行的代碼塊   
  9.     CShellAST ifBlock = (CShellAST) ast.getChild(1);   
  10.     //  獲取elseif的部分（包括條件表達(dá)式和要執(zhí)行的塊）   
  11.     CShellAST elseifAll = (CShellAST) ast.getChild(2);   
  12.     //  獲取else部分要執(zhí)行的代碼塊   
  13.     CShellAST elseBlock = (CShellAST) ast.getChild(3);   
  14.     //  利用遞歸方式再次調(diào)用exec方法執(zhí)行表達(dá)式，并返回值   
  15.     Boolean c = (Boolean) exec(expr);   
  16.     //  如果為true，執(zhí)行if block   
  17.     if (c.booleanValue())   
  18.     {   
  19.         exec(ifBlock);  //  遞歸執(zhí)行if block   
  20.     }   
  21.     else 
  22.     {   
  23.         //  判斷有多少個(gè)elseif部分，CShell支持有無(wú)限多個(gè)else if語(yǔ)句   
  24.         if (elseifAll.getChildCount() > 0)   
  25.         {   
  26.             List<CShellAST> children = elseifAll.getChildren();   
  27.             //  挨個(gè)判斷else if后面的表達(dá)式是否為true   
  28.             for (CShellAST child : children)   
  29.             {   
  30.                 expr = (CShellAST) child.getChild(0);   
  31.                 ifBlock = (CShellAST) child.getChild(1);   
  32.                 c = (Boolean) exec(expr);   
  33.                 //  如果某個(gè)else if條件為true，直接執(zhí)行else if后面的代碼塊，   
  34.                 //  ***返回，剩下的都不執(zhí)行了       
  35.                 if (c.booleanValue())   
  36.                 {   
  37.                     exec(ifBlock);   
  38.                     return;   
  39.                 }   
  40.             }   
  41.         }   
  42.         //  ***會(huì)執(zhí)行else語(yǔ)句（因?yàn)榍懊娴臈l件都為false）   
  43.     
  44.         //  判斷是否有else語(yǔ)句（最多只能有1個(gè)else子句）   
  45.         if (elseBlock.getChildCount() == 1)   
  46.         {   
  47.             exec((CShellAST) elseBlock.getChild(0));  // 執(zhí)行else block   
  48.         }   
  49.     }   
  50. } 

CShell代碼分析器的入口類是CShell，在該類中調(diào)用了Interprefer.process方法讀者CShell語(yǔ)言源代碼。其中bubble.cs就是CShell語(yǔ)言的源代碼文件，可以換成其他的源代碼文件。調(diào)用process方法后，就會(huì)根據(jù)具體的CShell代碼執(zhí)行相應(yīng)的操作。例如，print(…)語(yǔ)句會(huì)輸出相應(yīng)的字符串。

  1. public class CShell   
  2. {      
  3.     public static void main(String[] args) throws Exception   
  4.     {   
  5.         InputStream input = null;   
  6.         input = new FileInputStream("source/bubble.cs");   
  7.         Interpreter interp = new Interpreter();   
  8.         interp.process(input);   
  9.     }   
  10. } 

如果讀者對(duì)Antlr還不太理解也沒(méi)關(guān)系，本文只是拋磚引玉，目的并不是講解Antlr。只是希望讀者對(duì)Antlr以及設(shè)計(jì)一種語(yǔ)言的過(guò)程有所了解。在后面的一系列文章中將會(huì)深度探討編譯原理以及Antlr的使用方法。通過(guò)設(shè)計(jì)自己的專有語(yǔ)言***的作用是可以顯著提高工作效率，例如，可以將常用的工作抽象成某些語(yǔ)句，到時(shí)只要一執(zhí)行腳本就可完成需要數(shù)小時(shí)，甚至數(shù)天才能完成的工作。

 

原文鏈接：http://www.cnblogs.com/nokiaguy/archive/2013/03/12/2955128.html

責(zé)任編輯：張偉 來(lái)源： 博客園
Java編程
相關(guān)推薦

2010-01-25 15:09:17

C++語(yǔ)言

2011-07-21 14:17:15

Ceylon

2023-07-18 18:10:04

2023-12-04 08:21:18

虛擬線程Tomcat

2012-11-01 13:41:25

編程語(yǔ)言BasicPerl

2020-07-10 10:48:51

編程語(yǔ)言JavaPython

2012-03-14 11:46:30

ibmdw

2012-03-19 10:45:44

ibmdw

2010-01-21 16:24:02

C++語(yǔ)言

2018-12-14 14:30:12

安全檢測(cè)布式系測(cè)試

2018-03-12 13:32:02

編程語(yǔ)言程序員語(yǔ)言

2010-11-04 10:55:24

編程語(yǔ)言

2017-07-05 14:09:04

系統(tǒng)設(shè)計(jì)與架構(gòu)java云計(jì)算

2018-08-21 13:50:05

編程語(yǔ)言JavaPython

2021-01-28 23:40:58

編程語(yǔ)言PythonPerl

2021-04-05 14:44:20

JavaScript循環(huán)代碼

2015-08-03 09:36:01

賽迪翻譯

2015-08-31 09:27:21

語(yǔ)言界面UI

2021-01-29 12:28:13

編程語(yǔ)言開(kāi)發(fā)代碼

2019-07-19 15:21:00

SQL編程語(yǔ)言NOSQL
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)