手机站
网通分站
电信主站
密 码:
用户名:
当前位置 : 主页>程序设计>C/C++>列表

递归下降纯解释器编写的困惑

来源:互联网 作者:west263.com 时间:2008-02-23
西部数码-全国虚拟主机10强!40余项虚拟主机管理功能,全国领先!双线多线虚拟主机南北访问畅通无阻!免费赠送企业邮局,.CN域名,自助建站480元起,免费试用7天,满意再付款! P4主机租用799元/月.月付免压金!
python,lua更有javascript这些脚本语言其实是通过编译成中间码,然后再解释这个中间码来执行的,所以并不是纯解释的脚本。假如要写一个纯解释的脚本语言解释器,这种解释器的速度肯定不会很快,但是程式能够更简单一些。这对于需要小型的脚本解释器的情况比较适用,因为一个人只要几天就能够完成。比如unix的shell,windows中的cmd等。当然,对于一般的程式员来说,主要是为了嵌入自己的程式。假设我们的脚本包含变量,基本表达式,顺序,分支,循环语句,goto等。手工编写,当然是采用递归下降方法。

  变量用一个链表或数组就能够解决。解释赋值语句时,将变量存在符号表中。  

  表达式已有很成熟的解决方法,就是个算符堆栈,一个操作数堆栈,然后按算符优先级来做就能够了  

  然后我们讨论基本语句的执行  

  statements==>if_statements,for_statements,goto_statements等

  我们用c函数exec_if,exec_for,exec_goto来分别解释他们,用exec_statements()函数来递归调用前面这些函数。  

   假如是如下顺序执行的脚本,实现是比较容易的,就是顺序执行。  

  COMMAND:statements;  

  就是前面是命令后面是语句,在c语言中能够用一个switch轻松搞定。但是假如出现了分支和循环,函数的时候,情况就变得复杂了。先看循环语句,比如如下脚本  

  for i= 1 to 100 do  

  statements;  

  end  

  假设现在我们已将脚本都加载到内存中了,有一个char *指针current指向当前的脚本的位置。这个解释执行并不难。先解释for i=1 to 100 do这句,将自变量i保存到符号表中,这时候current已指向statements了。循环解释执行的c程式伪码如下:  

  char *old=current;  

  for(i=自变量开始值;i ;i<自变量目标值)  

  {  

   current =old;  

   执行 statements;(这个过程中current会变化)  

  }  

  其中自变量开始值和自变量目标值都能够解释获得,每次执行完statements后在开始循环时恢复current指针即可。 

   但是分支语句可没这么简单,比如脚本  

  if exp1 then  

   statements1;  

  elseif exp2 then  

  statements2;  

  end  

  假设exp1为真则执行statements1,exp2为真则执行statement2。那么解释执行的时候问题就来了,当exp1为真时,执行完statements1后,我们要跳过statements2到end,然后再执行,同样exp1为假,exp2为真的时候,问题也同样存在,需要跳过statements1.问题是怎么跳过?statements1,statements2均可能包含嵌套的分支或循环。在编译型的脚本中,其实不管是statements1,statements2在编译的时候都是需要编译的,在编译完这些语句后再进行代码回填。这样在执行中间码的过程中exp1,exp2执行完后,就知道跳到哪里执行了,实际上在执行中间码的时候脚本编译器已进行了一次源码的扫描了,执行的函数不关心这些。但是我们现在是纯解释执行,就是一次扫描了。除了编译成中间码这个方法外,我没有想到更优雅的办法,这个方法因为涉及到编译,不是纯解释因此排除掉。对每种语句都有一个解释执行该语句的函数,例如  

  for 语句我们用exec_for()函数来执行,if我们用exec_if来执行。一种方法是能够对应编写一个pass函数,例如pass_for(),pass_if(),这样对于statements我们只需要一个pass_statements()函数就能够了,pass_statements()递归调用pass_for,pass_if,这样就能够过滤掉无需执行的语句了。pass函数只改变current的值而并不执行被pass掉的那些语句。  

  显然pass_statemts除了不修改符号表,不做其他动作外,其他逻辑流程和exec_statements函数相同。这显然不够优雅。
  
  goto则需要先扫描行号,执行goto时跳到对应的行。  

   不知有没有更好的coding技巧,探索中。



文章整理:西部数码--专业提供域名注册虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息,谢谢!

热点关注
IDC资讯 虚拟主机 域名注册 托管租用 vps主机 智能建站
网站运营 建站经验 策划盈利 搜索优化 网站推广 免费资源
网站联盟 联盟新闻 联盟介绍 联盟点评 网赚技巧
行业资讯 业界动态 搜索引擎 网络游戏 门户动态 电子商务 广告传媒
网络编程 Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术 Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷 Internet Explorer
网页制作 FrontPages Dreamweaver Javascript css photoshop fireworks Flash
程序设计 Java技术 C/C++ VB delphi
网络知识 网络协议 网络安全 网络管理 组网方案 Cisco技术
操作系统 Win2000 WinXP Win2003 Mac OS Linux FreeBSD
返回首页 |关于我们 | 联系我们 | 付款方式 | 创业联盟 | 价格总览 | 资讯中心 | 友情链接 | 网站地图 | 招贤纳士 | RSS