疯狂极客前传：用最快的速度设计一种新的编程语言

最近打算写一些列有趣、而且有一定难度的文章。这个系列的名字就叫《疯狂极客》，这一系列的文章大多数与计算机有密切的关系。包括制作编译器、制作OS、Android控制电路板、机器人的制作（通过Android、IOS等设备控制）等等。
    源代码下载 
    在正式开始《疯狂极客》系列文章之前，先来热热身。用最短的时间设计一种简单，但好玩的编程语言CShell(不过不用担心，实现CShell解析器基本上用不着编译原理的知识，但以后的文章就会涉及到很多编译原理的内容了)。从CShell的名称可以猜到，是一种C风格的语言，并且可以像Shell一样解释执行（动态语言）。当然，这种语言不可能像C语言或Shell一样强大，因为C语言的编译器实现起来尽管不复杂（因为是结构化编程语言，没有类、接口这些东西，实现起来要比Java编译器简单得多），但仍然不太可能在很短的时间内完成（一至两天）。不过本文实现的CShell尽管简单，但仍然可以实现一些算法。CShell语言支持输出值和变量、条件语句（if），for循环，自加、自减、+、-、*、/操作，函数（支持递归）。由于CShell是动态语言，所以不需要声明变量，不过支持全局和局部变量，当然，还支持数组（整数、字符串类型数组），所以使用CShell可以很容易实现像冒泡排序、阶乘等算法。
      在讨论CShell的设计原理和实现过程之前，先看一些用CShell编写的程序。单从这些程序所完成的工作来看都太太太简单了，不过这回完全不同，这回是用我们自己发明的新语言来实现这些算法，例如，递归阶乘计算、冒泡排序，是不是很酷呢！！Let’s go！
[html] 
//  简单的变量输出  
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语言的代码。
[html]  
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就是可能以“$”开头，也

补充：综合编程 , 其他综合 ,