Python (下面的讨论都是基于 2.7 版本的) 中, 先定义的函数可以调用后定义的函数, 比如下面这段代码

def first():
    return second()

def second():
    return 0

x = first()


    不过, 这种调用是有局限性的, 稍作修改为下面这个样子

def first():
    return second()

x = first()

def second():
    return 0


就会产生符号错误, 解释器给出的信息是符号 second 不存在.

    Python 作为一门解释型语言, 出现这样的事情很有可能是这样的原因, 假设现在正在交互模式下执行, 那么输入

def first():
    return second()

x = first()


到此为止, second 这个符号确实还没有被定义, 故产生错误. 但是如果上述代码内容是写在文件里的, 那么 Python 完全可以扫描整个文件以获得充分的上下文信息, 并正确地检测出 second 函数定义, 只是 Python 没有这么做.

    熟悉 C++ 的同学这时候肯定跳出来了, 因为在 C++ 类空间中, 这种引用是合法的, 如

struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return 0;
    }

    int x;
};


不过, C++ 这种事情其实极其危险的, 比如下面这一段代码

struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return x;
    }

    int x;
};


这实际上使用了还处于量子态的 x 来初始化它自身, 虽然这样的代码只有手贱的程序员在极其罕见的情况下才会写出这样的代码 (比如我在写这篇博客的时候), 但是本着编译器的职责, 完全应该想方设法让这种情况编不过去.

    好了, 还是先回到 Python 上来, Python 不允许这样的代码编译过去, 是因为这个原因么? 假设有下面的程序成功被解释执行

def first():
    return second()

x = first()

def second():
    return x


那么 Python 岂不是崩坏了? (Python 的整数可都是引用哦, 这不只是整数初始化的问题, 是引用野指针的大坑啊!)
    不过这种情况在 Python 中倒是一定不会发生的, 当解释器执行到那句 return x 的时候, 会窘然发现找不到 x, 因为这时 x = first() 这一句正在执行右半边, 而 x 本身到此还没有被加进符号表呢.

    Python 没这么干的本质原因听起来很挫, 其实只是因为 Python 解释器在构造语法树时认为函数定义是一种指令. 翻开 Python 源代码中, Python/ceval.c 文件里面, 找到著名的 PyEval_EvalFrameEx 函数, 在如黄河泛滥一发而不可收拾的 switch-case 中有这么不起眼的一个 case MAKE_FUNCTION, 这个 case 中就是函数定义的流程. 实际上就是说, 别看函数定义那么大个架子, 说到底也只是一个指令.
    仔细想象, 这多多少少这是有点不对的, 函数定义在正统的编译原理中是属于符号表操作, 不产生实际的运行效果, 不过 Python 既然是个交互式脚本语言, 这么掰也就由着它吧.

    那么对于非交互式的语言, 假如能够一开始就读入整个源文件, 要解决这个问题, 可以考虑在构建语法树之后将函数定义单独提取出来, 在编译 (或解释) 其它真正的指令之前将所有函数声明 (不包括定义) 加入符号表. 直到函数被调用时, 再编译函数的定义 (即编译函数体).
    这个算法的关键是, 在上下文无关文法 (CFG) 将语法树转换到语义模块, 直到解析函数引用之前. 这时首先产生函数对象, 函数对象里面有两个对象, 其中一个可以认为是直接从上游模块 (也就是从 CFG 模块) 拿过来的语法树, 同时, 将这个函数的签名加入符号表中; 另外一个对象暂时为空 (或者某种用作标记的值), 它在函数体被编译后表示编译后的语法树.
    对所有函数这么做一次之后 (注, 这时对语法树的编译还没有开始, 仅仅只是将所有函数加入符号表而已), 再开始编译语句. 当一个语句中包含有一个函数调用时, 则根据调用的函数签名找到这个函数对象, 刚才说了, 函数对象中表示编译后语法树的那个对象还是一个空对象, 那么现在先把它弄成一棵空的语法树 (而不是空对象, 或者某种标记值, 这一点很重要, 稍候会说到), 然后对函数体中的语句顺序编译, 将编译的结果放入这个语法树中. 如果一个函数对象中, 这个子对象已经编译过, 那么对这个函数的调用就可以直接返回这个对象引用.
    如果函数中含有递归, 那么这时函数体中对函数本身的调用显然不应当引起函数的重复编译, 否则编译器本身会递归下去挂掉, 所以在函数体编译刚刚开始时需要立即先弄出一个空语法树. 而这时实际上应当返回函数体正在编译的这个半成品语法树对象的引用. 不用担心这时函数调用节点会遭遇什么不幸的数据不完整性, 想象一下 C 语言体系中的链接过程, 函数调用只需要引用一个入口 (entry point) 就行了.
    以上面的代码为例子, 假设大脑里面有个编译器在读这段程序

def first():
    return second()

x = first()

def second():
    return 0


    由于可以直接搞到整个代码, 能区分出所有的函数定义, 所以这段代码在编译器眼里实际上是这个样子

def first():
    return second()

def second():
    return 0

x = first()


    将 first 和 second 先放入符号表. 现在开始编译仅有的一个语句

x = first()


    先是 first() 这一部分, 函数调用. 查表得 first, 还没编译过, 那就先编译 first 的函数体吧

return second()


    同理, 开始编译 second, 编译完成后这一句也差不多结束了, 生成一个 return 语句节点到 first 函数这时还空着的函数体语法树中, 大功告成, 返回到最外层, 继续赋值语句编译. 在一通查符号表和注册 x 之后, 这一句也差不多结束了. 编译就完成了.