WEB开发网
开发学院软件开发C++ 递归下降纯解释器编写的困惑 阅读

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

 2008-03-08 21:57:15 来源:WEB开发网   
核心提示:python,lua还有javascript这些脚本语言其实是通过编译成中间码,然后再解释这个中间码来执行的,递归下降纯解释器编写的困惑,所以并不是纯解释的脚本,假如要写一个纯解释的脚本语言解释器,执行goto时跳到对应的行, 不知有没有更好的coding技巧,这种解释器的速度肯定不会很快,但是程序可以更简单一些

  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技巧,探索中。

Tags:递归 下降 解释器

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接