有关于抽象语法树

我们都知道PHP脚本的执行过程，先是由Zend引擎将PHP源码编译为opcode序列，再由Zend VM去解释执行。一般编译的过程都是先进行词法分析、语法分析，然后才是编译。在经过语法分析之后，有一个抽象语法树（Abstract Syntax Tree或者缩写为AST）的概念，他算是语法分析的产出，之后的编译过程是编译器在AST基础上进行的。

PS: php脚本的执行过程: php source --> ZEND ENGINE(compile php to opcode,no AST)--->ZEND VM(for run);

一般脚本的执行过程:   詞法分析-->语法分析(AST)-->编译(在AST基础上进行编译);

但是PHP比较特殊，Zend引擎在语法分析之后直接产出了opcode，没有生成AST。这样做最大的好处是加快了编译过程，坏处则是丧失了一些自由性，难以优化以及导致编译程序逻辑复杂。具体PHP官网上有一篇wiki探讨了在PHP的编译过程中引入AST，当然实现起来难度肯定很大。

我们在平时一般不会接触到PHP的编译过程，但是AST却是个有用的东西，我们平时工作中很多工具里面都有AST，比如PHP_CodeSniffer、PHP_Depend、ZendStudio、PDT……需要对源码进行分析的场合，或多或少都需要AST的帮忙。

PHP的词法分析

说到词法分析和语法分析，必须提到的就是lex和yacc，计算机科班出身的在编译原理课上肯定都学过，不过反正我是早忘的差不多了。现在的词法分析器、语法分析器基本上都是用这两个工具生成的。

PHP的词法分析，我们可以直接借助于Zend引擎。PHP有一个tokenizer扩展，作用就是对PHP代码进行词法分析并生成词法分析后的token（单词）。词法分析只是将源代码解析生一堆token的序列，并不处理token和token之间的关系，那是语法分析的工作。

PHP的语法分析

PHP的语法分析的工具其实有很多，我列出几个：

PHP Parser（Front End）：一个商业的工具，具体如何没用过

lex-pass：Facebook开源的工具，用haskell写的，可以生成AST

pfff：也是Facebook开源的工具，用OCaml写的，功能要远远多于语法分析，还包括代码检查、代码可视化、代码重构，很好很强大

PDT：PDT里自带了生成AST的工具，应该是Java语言写的

PHP-Parser：PHP编写的Parser，除了生成抽象语法树之外几乎什么都不做，但是很好扩展。利用了tokenizer扩展来做词法分析。

PDepend：PHP编写的代码分析工具，里面带了一个Parser，可以生成AST，不过并没有独立出来。实现机制上和PHP-Parser非常类似，也用到了tokenizer扩展。

对于一个程序员来说，使用熟悉的语言做事情是最爽的，PHP-Parser是PHP语言实现，虽然运行起来会比较慢，但在上面做开发会比较容易。我调研过pfff，OCaml在执行性能上虽然可以与C相当，但是OCaml作为函数式编程语言，它的语法实在是比较难懂，如果你不介意学习一门新语言并且持续在之上投入精力，可以考虑一下pfff。

PHP-Parser

上面提到，PHP-Parser是一个PHP写的语法分析器，它的基本功能就是生成抽象语法树，除此之外附带了一些其他功能，包括：语法树的序列化/反序列化、语法树构建、代码生成，实现的都不复杂。PHP-Parser的项目主页是：https://github.com/nikic/PHP-Parser

安装：

安装的方法有很多，这里不一一赘述，具体可参考：https://github.com/nikic/PHP-Parser/blob/master/doc/1_Installation.markdown

我是使用的composer安装，只需在项目代码的composer.json中加入：

{

    "require": {

        "nikic/php-parser": "0.9.3"

    }

}

然后执行下面命令即可：

php composer.phar install

引入Autoloader的时候，如果你的PHP是5.3以上，无需像文档中说的引入它的bootstrap.php，只要加载composer的autoloader即可。如果php版本低于5.3，还是老老实实加载他的bootstrap.php，里面定义了一个php5.3才引入的函数lcfirst()。

简单范例：

官方文档中给出的范例已经非常直观，这里也不做赘述了，除非哪天兴致来了再补充这章。

代码结构：

PHP-Parser主要包含以下几个功能块：

Lexer：

调用tokenizer的token_get_all()完成词法分析，token_get_all()返回的是token数组，Lexer将数组中的每个token映射到PHP-Parser的Node类当中。

如果你要在低版本的PHP环境中分析高版本PHP的代码，那么Lexer中有一个PHPParser_Lexer_Emulative类，用来模拟生成高版本PHP中才有的token。

Lexer包含下面两个关键函数：

public function startLexing($code) {}

public function getNextToken(&$value = null, &$startAttributes = null, &$endAttributes = null) {}

其中startLexing接受PHP代码作为参数，如果你想接收一个文件名作为参数，可以派生此类，并重写startLexing方法，以下是官方文档的一个例子：

public function startLexing($fileName) {

        if (!file_exists($fileName)) {

            throw new InvalidArgumentException(sprintf('File "%s" does not exist', $fileName));

        }

        parent::startLexing(file_get_contents($fileName));

    }

getNextToken则允许你在处理下一个token时，添加或者删除一些额外信息，例如下面这个同样是官方文档中的例子：

public function getNextToken(&$value = null, &$startAttributes = null, &$endAttributes = null) {

        $tokenId = parent::getNextToken($value, $startAttributes, $endAttributes);

        // only keep startLine attribute

        unset($startAttributes['comments']);

        unset($endAttributes['endLine']);

        $endAttributes['fileName'] = $fileName;

        return $tokenId;

    }

要注意上面代码里参数都是引用传递的。

Parser：

经过词法分析之后，就生成了一大堆的token，token经过Parser的解析，才会生成抽象语法树。PHPParser_Parser类是自动生成的，没事千万不要去改它。

PHPParser_Parser的构造函数接受一个PHPParser_Lexer类型作为参数，也就是上面的词法分析器。

Node：

经过Parser的解析，生成了抽象语法树，抽象语法树的每一个节点都是一个Node对象。PHP一共有140+种不同的Node对象，PHPParser将他们分成了3类：

PHPParser_Node_Stmt：声明，即没有返回值并且不能出现在表达式中的代码。例如函数定义、类定义以及控制语句等。

PHPParser_Node_Expr：表达式，即有返回值并且可以出现在表达式中的语句，例如单个变量、函数调用等

PHPParser_Node_Scalar：标量，例如字符串、整型、预定义常量如__FILE__等

还有一些不属于上述三种类型的，例如PHPParser_Node_Name、PHPParser_Node_Arg

所有Node的基类PHPParser_NodeAbstract实现了IteratorAggregate接口，这意味着你可以直接foreach来对其进行迭代访问其子节点。

每一个Node都实现了一些方法，以方便对其进行访问，例如PHPParser_Node_Stmt_Class也就是类定义，有以下几个方法可以使用：

public function isAbstract() {}

public function isFinal() {}

public function getMethods() {}

PHPParser_Node_Stmt_ClassMethod则有：

public function isPublic() {}

public function isProtected() {}

public function isPrivate() {}

public function isAbstract() {}

public function isFinal() {}

public function isStatic() {}

Traverser：

由Parser生成的抽象语法树，可以通过Traverser进行遍历，并在遍历过程中通过Visitor进行操作，比如下面这个官方的例子（我做了中文注释）：

$code = " 

$parser        = new PHPParser_Parser(new PHPParser_Lexer());

$traverser     = new PHPParser_NodeTraverser();      //创建一个Traverser

$prettyPrinter = new PHPParser_PrettyPrinter_Default();

//向Traverser添加Visitor，真正操作代码的是Visitor

$traverser->addVisitor(new MyNodeVisitor());

try {

    // 解析代码，生成抽象语法树$stmts

    $stmts = $parser->parse($code);

    // 遍历代码，这时候Traverser回到调用Visitor对语法树进行操作

    $stmts = $traverser->traverse($stmts);

    // 重新生成修改后的代码

    $code = 'prettyPrint($stmts);

    echo $code;

} catch (PHPParser_Error $e) {

    echo 'Parse Error: ', $e->getMessage();

}

class MyNodeVisitor extends PHPParser_NodeVisitorAbstract

{

    public function leaveNode(PHPParser_Node $node) {

        if ($node instanceof PHPParser_Node_Scalar_String) {

            $node->value = 'foo';

        }

    }

}

可以为Traverser添加多个Visitor，在遍历语法树的时候Traverser会依次调用每一个Visitor。

Traverser遍历语法树遵循以下步骤：

遍历开始前，依次调用每一个Visitor的beforeTraverse()方法，传入参数为当前抽象语法树

访问抽象语法树中的第一个节点，在开始递归前依次调用每一个Visitor的enterNode()方法，传入参数为当前节点。

若当前节点存在子节点，则递归依次处理其子节点，重复步骤2。

若当前节点不存在子节点，则依次调用每一个Visitor的leaveNode()方法，传入参数为当前节点。

所有的节点都遍历结束，则依次调用每一个Visitor的afterTraverse方法，传入参数为操作后的抽象语法树。

可以看出，要处理或者分析代码，主要是通过Visitor进行，Traverser只是适时的调用Visitor的指定方法而已。

Visitor：

Visitor刚才已经提到， 其抽象基类就包含以下几个方法：

public function beforeTraverse(array $nodes)    { }

    public function enterNode(PHPParser_Node $node) { }

    public function leaveNode(PHPParser_Node $node) { }

    public function afterTraverse(array $nodes)     { }

方法的作用就不重复讲了，需要注意的是这四个方法的返回值：

如果返回null或不返回，表示Node没有修改

leaveNode返回false，表示当前Node被删除

leaveNode返回array，则array中的每个Node会被Merge到当前Node的parent中的相应位置，例如array(A, B, C)中的B，在leaveNode(B)的时候返回了array(X, Y, Z)，则array(A, B, C)将会变成array(A, X, Y, Z, C)

返回新的Node，则当前Node被新的Node替换

Pretty printer：

一句话解释：将抽象语法树重新输出成格式化好的代码。上面Traverser的例子中有Pretty printer的用法。Pretty printer的功能还比较简单，目前只有Zend风格的，有需要可以自定制。

Serialize/UnSerialize：

将抽象语法树进行序列化/反序列化，序列化/反序列化的意义在于：

你可以将抽象语法树序列化后进行持久化存储，需要时读出来反序列化重新在内存中生成抽象语法树

你可以将抽象语法树转换格式，以供其他程序读取。

目前PHP-Parser实现了XML格式的序列化/反序列化，官方的这篇文档有介绍。你也可以简单的调用php的serialize和unserialize来序列化/反序列化。

Builder：

Builder的作用是创建抽象语法树，和Pretty print结合的话，可用于Code Generation。你可以根据一个抽象描述来生成PHP代码。这个功能很不错，会有很多应用场景：

根据服务接口描述生成客户端代码，类似于thrift所做的事情

根据表单描述生成校验表单数据的代码

根据模型定义生成setter和getter方法

具体如何使用，官方也有相应文档

What PHP-Parser Can’t Do?

知道PHP-Parser能做什么，我们还得知道它不能做什么。我们知道PHP是弱类型、解释型的语言，这意味着某些变量的类型，只有在运行时才能确定，例如如下代码：

function foo($objPrint) {

    $objPrint->say("Hello World");

}

生成的抽象语法树如下：

array(1) {

  [0]=>

  object(PHPParser_Node_Stmt_Function)#17 (2) {

    ["subNodes":protected]=>

    array(4) {

      ["byRef"]=>

      bool(false)

      ["params"]=>

      array(1) {

        [0]=>

        object(PHPParser_Node_Param)#12 (2) {

          ["subNodes":protected]=>

          array(4) {

            ["name"]=>

            string(8) "objPrint"

            ["default"]=>

            NULL

            ["type"]=>

            NULL

            ["byRef"]=>

            bool(false)

          }

          ["attributes":protected]=>

          array(2) {

            ["startLine"]=>

            int(2)

            ["endLine"]=>

            int(2)

          }

        }

      }

      ["stmts"]=>

      array(1) {

        [0]=>

        object(PHPParser_Node_Expr_MethodCall)#16 (2) {

          ["subNodes":protected]=>

          array(3) {

            ["var"]=>

            object(PHPParser_Node_Expr_Variable)#13 (2) {

              ["subNodes":protected]=>

              array(1) {

                ["name"]=>

                string(8) "objPrint"

              }

              ["attributes":protected]=>

              array(2) {

                ["startLine"]=>

                int(3)

                ["endLine"]=>

                int(3)

              }

            }

            ["name"]=>

            string(3) "say"

            ["args"]=>

            array(1) {

              [0]=>

              object(PHPParser_Node_Arg)#15 (2) {

                ["subNodes":protected]=>

                array(2) {

                  ["value"]=>

                  object(PHPParser_Node_Scalar_String)#14 (2) {

                    ["subNodes":protected]=>

                    array(1) {

                      ["value"]=>

                      string(11) "Hello World"

                    }

                    ["attributes":protected]=>

                    array(2) {

                      ["startLine"]=>

                      int(3)

                      ["endLine"]=>

                      int(3)

                    }

                  }

                  ["byRef"]=>

                  bool(false)

                }

                ["attributes":protected]=>

                array(2) {

                  ["startLine"]=>

                  int(3)

                  ["endLine"]=>

                  int(3)

                }

              }

            }

          }

          ["attributes":protected]=>

          array(2) {

            ["startLine"]=>

            int(3)

            ["endLine"]=>

            int(3)

          }

        }

      }

      ["name"]=>

      string(3) "foo"

    }

    ["attributes":protected]=>

    array(2) {

      ["startLine"]=>

      int(2)

      ["endLine"]=>

      int(4)

    }

  }

}

可以看出在PHPParser_Node_Expr_MethodCall当中，objPrint的类型是PHPParser_Node_Expr_Variable，并且没有任何关于变量的类型信息，因为这里并不知道objPrint的类型，只知道它是一个变量。

如果我们把代码改为下面这个形式：

function foo(Print_Type $objPrint) {

    $objPrint->say("Hello World");

}

也就是在代码中加入Type Hint，那么我们可以通过Visitor在进入MethodCall这个Node时获取到参数的类型，并记录到当前Method的变量类型映射表中，在调用$objPrint的时候，就可以分析出objPrint对应的类型了。

不过，还有另外一种形式的问题，例如下面这个代码：

function foo($name){

    $classname = 'Class_'.$name;

    $obj = new $classname();

    $obj->foo();

}

这种情况就比较悲催了，得知道$name的值才能知道$obj的类型，而$name的值只有运行时才会知道，目前我也没有想到有什么好的解决办法。

总结：

以上是调研PHP代码工具过程中，对于PHP-Parser的一些记录。通过PHP-Parser，我们可以构建自己的代码工具。初步的一个想法是先利用PHP-Parser和SQLite对PHP代码进行解析和创建索引。之后可以通过SQL来对抽象代码树进行修改，最终再生成PHP代码，实现对代码进行重构的目的。这种实现的好处是SQL大家都比较熟悉，相对比较灵活。

PS:php-parser的作用:生成AST然后可以重新生成PHP代码,来实现重构的目的.看来是要配合其他工具来使用.