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

最近打算写一些列有趣、而且有一定难度的文章。这个系列的名字就叫《疯狂极客》,这一系列的文章大多数与计算机有密切的关系。包括制作编译器、制作OS、Android控制电路板、机器人的制作(通过Android、IOS等设备控制)等等。

    源代码下载 

    在正式开始《疯狂极客》系列文章之前,先来热热身。用最短的时间设计一种简单,但好玩的编程语言CShell(不过不用担心,实现CShell解析器基本 上用不着编译原理的知识,但以后的文章就会涉及到很多编译原理的内容了)。从CShell的名称可以猜到,是一种C风格的语言,并且可以像Shell一样 解释执行(动态语言)。当然,这种语言不可能像C语言或Shell一样强大,因为C语言的编译器实现起来尽管不复杂(因为是结构化编程语言,没有类、接口 这些东西,实现起来要比Java编译器简单得多),但仍然不太可能在很短的时间内完成(一至两天)。不过本文实现的CShell尽管简单,但仍然可以实现 一些算法。CShell语言支持输出值和变量、条件语句(if),for循环,自加、自减、+、-、*、/操作,函数(支持递归)。由于CShell是动 态语言,所以不需要声明变量,不过支持全局和局部变量,当然,还支持数组(整数、字符串类型数组),所以使用CShell可以很容易实现像冒泡排序、阶乘 等算法。

      在讨论CShell的设计原理和实现过程之前,先看一些用CShell编写的程序。单从这些程序所完成的工作来看都太太太简单了,不过这回完全不同,这回 是用我们自己发明的新语言来实现这些算法,例如,递归阶乘计算、冒泡排序,是不是很酷呢!!Let’s go!

  1. //  简单的变量输出 
  2. xx45
  3. _ok = 64
  4. print (xx); 
  5. a1 = 65
  6. print (a1); 
  7. //  数组演示 
  8. $arr = [1,2,3,4,5,"aa"];  //  数值与字符串换搭的数组,$表示全局变量 
  9. print($arr);           //  输出数组的所有元素 
  10. print($arr[2]);         //  输出数组的第3个元素 
  11. //  三重for循环 
  12. $x = 0;  //  全局变量 
  13. //  i、j、z都为局部变量,for循环外不可访问 
  14. for(i=0;i<10;ii=i+1) 
  15.     for(j = 0; j <10jj=j+1) 
  16.     { 
  17.         for(z = 0; z <10zz = z + 1) 
  18.         { 
  19.             $x = $x + 1; 
  20.         }    
  21.     } 
  22. print($x);   //  输出1000 
  23. //  计算10的阶乘,涉及到函数的递归操作和if语句 
  24. def jc(n) 
  25.     if(n == 0) 
  26.     { 
  27.         return 1; 
  28.     } 
  29.     else if(n == 1) 
  30.     { 
  31.         return 1; 
  32.     } 
  33.     else 
  34.     { 
  35.         return jc(n - 1) *n; 
  36.     } 
  37. print("10!"); 
  38. print(jc(10));  //  计算10的阶乘(3628800) 
  39. //  冒泡排序(降序) 
  40. $arr = [5,3,1,7,5,4,-56,12]; 
  41. $len = length($arr); 
  42. //  双循环冒泡排序 
  43. for(i = 0; i < $len; i++) 
  44.     for(j = 0; j < $len - 1; j++) 
  45.     { 
  46.         if($arr[j] < $arr[j+1]) 
  47.         {    
  48.             x = $arr[j+1]; 
  49.             $arr[j+1] = $arr[j]; 
  50.             $arr[j] = x; 
  51.         } 
  52.     } 
  53. 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语言的代码。

  1. 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方法的代码如下:

  1. //  CShellAST表示AST节点的类型,一个普通Java类
  2. public Object exec(CShellAST ast) 
  3.     try
  4.     { 
  5.         switch (ast.getType()) 
  6.         { 
  7.             case CShellParser.BLOCK:  //  处理块操作
  8.                 block(ast); 
  9.                 break
  10.             case CShellParser.ASSIGN:  //  处理赋值操作
  11.                 assign(ast); 
  12.                 break
  13.             case CShellParser.LENGTH:   //  处理返回长度操作
  14.                 return length(ast); 
  15.             case CShellParser.ARRAY:   //  处理数组操作
  16.                 arrayStat(ast); 
  17.                 break
  18.             case CShellParser.RETURN: 
  19.                 ret(ast); 
  20.                 break
  21.             case CShellParser.PRINT: 
  22.                 print(ast); 
  23.                 break
  24.             case CShellParser.IF:      //  处理if语句
  25.                 ifstat(ast); 
  26.                 break
  27.             case CShellParser.FOR: 
  28.                 forloop(ast); 
  29.                 break
  30.             case CShellParser.CALL: 
  31.                 return call(ast); 
  32.             case CShellParser.ADD: 
  33.                 return add(ast); 
  34.             case CShellParser.PREV: 
  35.             case CShellParser.SUFFIX: 
  36.                 return incAndDec(ast); 
  37.             case CShellParser.SUB: 
  38.                 return op(ast); 
  39.             case CShellParser.MUL: 
  40.             case CShellParser.DIV: 
  41.                 return op(ast); 
  42.             case CShellParser.EQ: 
  43.                 return eq(ast); 
  44.             case CShellParser.LT: 
  45.                 return lt(ast); 
  46.             case CShellParser.GT: 
  47.                 return gt(ast); 
  48.             case CShellParser.INT: 
  49.                 return Integer.parseInt(ast.getText()); 
  50.             case CShellParser.CHAR: 
  51.                 returnnew Character(ast.getText().charAt(1)); 
  52.             case CShellParser.FLOAT: 
  53.                 return Float.parseFloat(ast.getText()); 
  54.             case CShellParser.STRING: 
  55.                 String s = ast.getText(); 
  56.                 return s.substring(1, s.length() - 1); 
  57.             case CShellParser.ID: 
  58.             case CShellParser.ARRAY_ELEMENT: 
  59.                 return load(ast); 
  60.             default// catch unhandled node types
  61.                 thrownew UnsupportedOperationException("无法处理"
  62.                         + ast.getText() + "<" + ast.getType() + ">"); 
  63.         } 
  64.     } 
  65.     catch (Exception e) 
  66.     { 
  67.         listener.error("异常原因: " + ast.toStringTree(), e); 
  68.     } 
  69.     returnnull

下面只看一个如何处理if语句的ifstat方法的实现代码

  1. privatevoid ifstat(CShellAST ast) 
  2.     //  下面的代码需要从当前AST节点(表示if语句根节点)的子节点获取
  3.     //  if语句的各个组成部分
  4.     //  获取if语句的两个圆括号直接的表达式部分
  5.     CShellAST expr = (CShellAST) ast.getChild(0); 
  6.     //  获取if条件如果为true要执行的代码块
  7.     CShellAST ifBlock = (CShellAST) ast.getChild(1); 
  8.     //  获取elseif的部分(包括条件表达式和要执行的块)
  9.     CShellAST elseifAll = (CShellAST) ast.getChild(2); 
  10.     //  获取else部分要执行的代码块
  11.     CShellAST elseBlock = (CShellAST) ast.getChild(3); 
  12.     //  利用递归方式再次调用exec方法执行表达式,并返回值
  13.     Boolean c = (Boolean) exec(expr); 
  14.     //  如果为true,执行if block
  15.     if (c.booleanValue()) 
  16.     { 
  17.         exec(ifBlock);  //  递归执行if block
  18.     } 
  19.     else
  20.     { 
  21.         //  判断有多少个elseif部分,CShell支持有无限多个else if语句
  22.         if (elseifAll.getChildCount() > 0
  23.         { 
  24.             List<CShellAST> children = elseifAll.getChildren(); 
  25.             //  挨个判断else if后面的表达式是否为true
  26.             for (CShellAST child : children) 
  27.             { 
  28.                 expr = (CShellAST) child.getChild(0); 
  29.                 ifBlock = (CShellAST) child.getChild(1); 
  30.                 c = (Boolean) exec(expr); 
  31.                 //  如果某个else if条件为true,直接执行else if后面的代码块,
  32.                 //  最后返回,剩下的都不执行了   
  33.                 if (c.booleanValue()) 
  34.                 { 
  35.                     exec(ifBlock); 
  36.                     return
  37.                 } 
  38.             } 
  39.         } 
  40.         //  最后会执行else语句(因为前面的条件都为false)
  41.         //  判断是否有else语句(最多只能有1个else子句)
  42.         if (elseBlock.getChildCount() == 1
  43.         { 
  44.             exec((CShellAST) elseBlock.getChild(0));  // 执行else block
  45.         } 
  46.     } 

         CShell代码分析器的入口类是CShell,在该类中调用了Interprefer.process方法读者CShell语言源代码。其中 bubble.cs就是CShell语言的源代码文件,可以换成其他的源代码文件。调用process方法后,就会根据具体的CShell代码执行相应的 操作。例如,print(…)语句会输出相应的字符串。

  1. publicclass CShell 
  2. {   
  3.     publicstaticvoid 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.     } 

        如果读者对Antlr还不太理解也没关系,本文只是抛砖引玉,目的并不是讲解Antlr。只是希望读者对Antlr以及设计一种语言的过程有所了解。在后 面的一系列文章中将会深度探讨编译原理以及Antlr的使用方法。通过设计自己的专有语言最大的作用是可以显著提高工作效率,例如,可以将常用的工作抽象 成某些语句,到时只要一执行脚本就可完成需要数小时,甚至数天才能完成的工作。

更多相关文章
  • <连线>杂志封面导语:<连线>杂志发表编辑史蒂芬·列维(Steven Levy)的文章,描述了对一些互联网名人的再次访问,同时阐述了黑客对网络发展的影响. 以下是文章全文:像比尔·盖茨一样,史蒂芬·列维(Steven Levy)报道过的很多黑客现在已经拥有了财富.声望和权力. ...
  • ◎译 名 普罗米修斯/异形前传/异形前传:普罗米修斯 ◎片 名 Prometheus  ◎年 代 2012 ◎国 家 美国/英国 ◎类 别 冒险/科幻/惊悚  ◎语 言 英语 ◎字 幕 中英双字幕 ◎IMDB评分 7.5/10 from 133,239 users ◎文件格式 BD-RMVB ◎视频 ...
  • 极客学以致用:光棍极客通过大数据搞定女朋友
    原文地址:http://www.lupaworld.com/article-235449-1.html摘要: 马上就要过年了,又要回家面对各种七大姑八大姨的催命问题,相信对于广大的宅男极客来说--"找女朋友没有?"已经被选为最不受欢迎的一句话了.其实在这个大数据时代里,我们生活在 ...
  • 极客极客爱折腾:智能路由器系统揭秘
    原文地址: http://www.lupaworld.com/article-233277-2.html摘要: 路由器也能像智能手机一样进行「刷机」,为其添加各种意想不到的功能.在智能路由器飞满天的情况下,为什么不亲自动手打造一个?在路由器上,我们称之为固件.而这种固件也可以根据你的路由器进行更换, ...
  • 智能硬件别做成人玩具,请把极客暂时遗忘
    大多数智能设备在设定初始,就朝着酷炫和有趣的方向走.这条路不能说走错了,只能说陷入了一个小圈子的范畴,即解决的只是一种极客需求.成为了玩具.文/张书乐当下是个智能硬件爆炸的时代,从最初的智能手机.智能手表,***,诸如什么手环.戒指.眼镜.跑鞋.跑步机.茶杯.拐棍乃至婴儿摇篮.似乎一夜之间,我们的生 ...
  • [手快福利]用我的链接注册极客学院,你我都能免费得30天VIP!6500+编程开发视频教程随便学,还能下载资料和源码:http://e.jikexueyuan.com/invite/index.html?ZnJvbV9jb2RlPTZVWEVHSSZ1bmFtZT1qaWtlXzcyMzMwODIm ...
  • 神幻、实验、搞笑、连环漫画:三国英雄前传
    原创漫画图书<三国英雄前传>神幻.实验.搞笑.连环漫画解密三国 解构三国作者:黄大耕<三国英雄前传>简介,黑龙江美术出版社南方电视台<今日一线>播放的三国迷的<三国英雄前传>视频: http://v.ku6.com/show/15z92EETCDupP ...
  • 极客公园未来企业活动感想
    昨天在北京798艺术区,参加了一场由极客公园主办的一场企业家的演讲,让我倍感深刻,也很受启发.以前我一般参加的技术类或者偏向于技术类的分享,但这一次分享的内容其实是站在一个创业者或者企业家的角度去分析,让我有了一个从不同角度看问题的思考.演讲的嘉宾里面,很多都是目前市场上比较火的app的ceo,有比 ...
一周排行
  • Win8.1,Win10,WindowsServer2012安装NetFramework3.5
    后期会在博客首发更新:http://dnt.dkill.net  网站部署之~Window ...
  • RHEL7.0正式版抢先体验
     插入光盘,根据提示我们选择合适的选项,我们不对光盘进行测试,直接选择第一个选项提示我们直 ...
  •        由于公司最近开发的项目是基于FileNet平台,所以就参加了FileNet的相关内容培训,前来参加培训的人虽然都来自IT行业,但是个人的开发背景不同,听课目的也不同,所以培训看似是一件很简单的事情,但是 ...
  • zabbix监控一台服务器
    zabbix 文档https://www.zabbix.com/documentation ...
  • 就是指网页里面的相对链接的前缀url,如在<head></head>部分定义了此链接为http://www.51xuediannao.com,那么下面的<a href=index.htm ...
  • 点击对象的获取$("body").click(function(e){var clicked = $(e.target);clicked.css("border"," ...
  • 主机: CentOS release 6.4 (Final) 目的:从/home分区分出100G来创建新分区/vm 参考: http://ryanclouser.com/?p=66 http://falstaff.a ...
  • Android底层开发需要的工具:1.JDK6JDk下载地址:http://www.oracle.com/technetwork/java/javase/downloads/index.html(推荐下载jdk6版t ...
  • 1.通过SSDT创建数据源 2.通过SSDT创建数据源视图 1.通过SSDT创建数据集 cube .创建方式:自下往上 自上往下 基于空多维数据集 .多维数据集包含一个或多个度量值组,其数据 源自 关系数 ...
  • PLSQL在64位系统连接不上32位的服务器
    1 主要是因为PLSQL只能接纳32位的客户端 2 下载oracle32位客户端 http ...