About
RSS

Bit Focus


Python 中函数交叉引用中的问题与解决方法

    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

Permanent Link: /p/314 Load full text

Post tags:

 Compiler Construction
 Python
 C++

表达式求值之优先关系矩阵法

    YACC 或者 ANTLR 或者 PLY 之类的东西是很不错啦, 不过当面对一个类似 C(++) 这么变态的需要将语法和符号表勾搭在一起的语言形式时, 还是可以考虑一下使用 Python 纯手工打造.

    搞定表达式求值这种现代高级程序设计语言中基础部分, 用 LR(n), LALR 分析之类的当然是可行的, 假定需要支持括号和下面这些运算
算符
优先级由高到低+ - (正负号)^ (幂运算)* /+ - (加减号)
结合方式数值左边右结合左结合左结合
    先搞个产生式集合 (运算符就不搞什么转义了, | 表示或)
Expr := Term +|- Expr
     := Term
Term := Exponential *|/ Term
     := Exponential
Exponential := Factor ^ Exponential
            := Factor
Factor := +|- Factor
       := Number
       := ( Expr )
    接着还要再计算 FIRST 集啊什么的, 等到最后写成代码, 秀吉都嫁人了.

    所幸这个世界上无痛的解决方案还是挺多的, 比如为符号设定优先级, 使用优先级来指导算符是应该移进还是规约. 这个方法可称为优先关系矩阵法.
    这里仍然会用到移进 (Shift)规约 (Reduce) 这两个术语, 不过它们的意义跟 LR 分析法里面的有些不同. 在 LR 分析中, 符号指的是词法分析中得到的 Token, 而不是运算符, 也就是说数和运算符, 以及其它任何东西都放在同一个栈中; 而在运用优先关系法的表达式分析过程中, 符号栈包括两个不同的栈, 一个专门用来存运算符 (这个栈称为算子栈), 另一个存放数或者已解析的表达式 (这个栈称为表达式栈). 在这里, 移进表示将运算符压入算子栈, 或将数压入表达式栈; 而规约指的是, 根据运算符的元数, 从表达式栈中弹出指定数目的
    遇到一个数时无条件移进, 而遇到运算符则要视情况决定移进还是规约, 而所谓的情况就是算符优先级. 比如下面这个表达式
3 + 4 * 5 + 6
    首先读入 3, 移进

表达式栈
3
算子栈
(空)

    然后是 +, 算子栈栈顶为空, 没得比, 那好, 先移进

表达式栈
3
算子栈
+

    继续, 4 移进, 接着是 *, 比一下, 发现 * 优先级较栈顶的 + (加号, 不是正号) 优先级高, 那肯定得移进

表达式栈
3 4
算子栈
+ *

    接着移进 5, 再往后又是一个 + (加号), 这时栈顶的 * 优先级高于它, 所以可以开始规约流程: 从算子栈弹出 *, 它是二元的, 于是再从表达式栈弹出栈顶 (刚刚压入的 5) 和次栈顶 (4), 将这三者组成表达式 4 * 5, 再压回表达式栈 (下面以一个二叉树的形象描述)

表达式栈
3   *
   / \
  4   5
算子栈
+

    还没完呢, 现在的算子栈顶 + (加号) 与手头上拿着的 + (加号) 平级, 由于加号是左结合的, 所以应当继续规约, 得到

表达式栈
  +
 / \
3   *
   / \
  4   5
算子栈
(空)

    现在算子栈又空了, 于是 + (最后强调一次, 加号) 压栈, 最后是 6, 移进之, 结束时, 整个算符栈从头到尾规约一次, 大功告成.

    回顾一下刚才的过程, 规则是
  • 前面说过的, 数无条件入栈
  • 如果算子栈为空, 移进当前算子
  • 如果算子栈顶的优先级高于当前算子, 或者两者优先级相等, 但当前符号是左结合的, 那么进行规约, 直到不满足规约条件
  • 算子无法规约时则移进
    这一些初步地写成代码类似这样

Permanent Link: /p/250 Load full text

Post tags:

 Compiler Construction
 Python
 Tutorial

0 Page 1


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site