Shellex.info

得益与Graphviz以及Python强劲的自省能力——Abettor GG，这就是你当年乐道的‘反射’啦，Shellex搞了一个可以生成Call Graph的东东。
谢谢Python-cn的各位同学给偶这个小菜菜的帮助，顺便过了一遍《源码剖析》的第八章。

class call_tracker:
def __init__(self, cls, logfile=’track.log’):
self.stack = [('Push', 'start')]
self.call_map = {}

cls = cls if isinstance(cls, list) else [cls]

[...]

在上一篇文章里面，Shellex阐述了将正则表达式转换成NFA的通用方法，算是对以前编译原理课程的回炉重炼了一遍。
下面Shellex将重炼进行下去。对于一个NFA，如何转换成DFA呢？
根据上回说的，一个 NFA 在读入符号串之后，并不确切地知道自动机的下一个状态是什么。但可以肯定的是，下一个状态一定处于某个状态集中。不妨该状态集记做  {q1,q2,…qk}  。
而一个等价的DFA 读入同样的符号串一定处于某个确定的状态上。
这样，都是读入同样的w，  DFA  到达某一个状态，而  NFA  到达某一个状态集。由  w  的任意性，可将  NFA  的所有的状态集和  DFA  的状态一一对应起来。这种对应的前提就是能识别同样的输入串。即  L(M1)=L(M2)  。
所以可以看出，我们要做的就是将 NFA 状态集归并为 DFA 中的状态。
为了归并的成功，Shellex先介绍三种基本操作：
ε-closure(s)：从状态s出发，返回仅仅通过ε边可以到达的最大状态集合
ε-closure(T)：从状态集合T中的每一个状态出发，返回仅仅通过ε边可以到达的最大状态集合
move(T, w)：从状态集合T中的每一状态出发，返回w边指向的下一个状态的集合
接下来Shellex用一个NFA为例，分析整个过程：

可以看到，这是一个典型的NFA。状态1到状态2存在ε边，而状态3有两个b边，分别指向自己和状态4。
S1=ε-closure(1); //S1={1,2}
S1a = move(S1, ‘a’); //S1a = {3}
S1b = move(S1, ‘b’); //S1b = {}
S2 = ε-closure(S1a); //S2 = {3}
S2a = move(S2, ‘a’); //S2a={}
S2b = move(S2, ‘b’); //S2b={3, 4}
S3 = ε-closure(S2b); //S3={3, 4}
S3a = [...]

最近得做一些跟自动机有关的东东，其中一部分可以简要地看作是由一套正则文法生成状态自动机的过程。
什么是正则表达式？
首先我们看看什么是正则表达式。这个东东呢，一般用于描述一个字符串的集合——直接说就是一个正则表达式可能可以匹配一大堆字符串，而这一大堆字符串可以形成一个集合，它们的共同特征就是可以被这个正则表达式匹配。就像去死去死团，但是不同的是去死去死团的团员的共同特征是不被任何异性所匹配——但是这没关系，我们不妨取去死去死团的补集就行了。
反正正则表达是很好啦，因为你只要用一点点在脏话里，就可以骂好多好多人，比如：
Mar(y|k|cus) is son of bitch.
真是非常de省力，唯一的缺点是可能对方不知道你在说什么。
好了，从上面我们可以看出正则表达式中的两个基本结构：

连结 (Concatenation)，比如 bitch，由b, i, t, c, h连接而成
联合 (Union)，比如 y|k|cus，可以认为是y或k或者cus

下面是第三个基本结构，被称为Kleene star (或者 Kleene 闭包)的。因为这个操作是Stephen Cole Kleene发明的。啊啊，其实正则表达式这个东西就是Kleene发明的。这个同学真是非常的牛B，因为他是更加牛B的 阿隆佐 – 丘奇 ( Alonzo Church )——历史上和阿兰 – 图灵 ( Alan Turing ) 并称的人物——的学生。有多牛B呢，这个Kleene还和他的老师，还有图灵，就递归论发表了论文，奠定了可计算理论的根基。啊哈哈哈，真是牛B啊。
嗯，所谓Kleene Star的例子就是这样的。

Kleene Star，比如a*，可以接受空串和若干个a连结组成的串

当然咯，还有一些别的操作，比如我们知道的+，?，集合[]等等，但是这些操作都可以通过上面三个基本操作的组合来完成。
比如+，a+可以认为是aa*
什么是NFA？
要说NFA嘛，我得先说说DFA。所谓DFA，就是Deterministic Finite state Automata的简称。是状态机的一种。通俗的说，就是一大堆状态的集合，里面有一个初始状态和若干终止状态，每个状态可以有若干个输出边前往别的状态。但是要求每个状态的同一种输出边至多只有一个，所以自动机被称为是”Deterministic”的。
比如下面这个例子：
表述的是一个电灯de开关，这个开关每按一下就从’开’状态转换到’关’状态，或者从’关’状态转换到’开’状态。而为了从环保角度出发，在’关’状态才被认为是终止态。

上面的自动机呢，就可以描述这个灯泡的行为模式，或者说可以描述电灯的状态转换过程。输出边就是’开’或者’关’的动作，或者说这个灯泡的开关，只接受这两种动作：“Trun On”，“Trun Off”。而”Trun On”动作只会导致灯的状态变成“On”，“Trun Off”动作只会导致灯的状态变成“Off”，这是确定的，你的外婆都可以预料到的。所以说DFA是确定有限状态自动机。
现在可以说NFA了。这个NFA嘛，全称是Non-deterministic Finite state Automata。也是状态自动机的一种。确切地说，刚才的DFA是NFA的一个子集。和DFA唯一的区别就是他是”Non-deterministic”的，哈，非确定的，每个状态的同一种输出边可以不止一个。
还是用刚才的例子。现在假设我们的电灯有一种新的状态咯～：坏掉了。灯丝被过大的电流烧断了，听上去遭透了，因为一”Trun On”就得准备换灯泡了：

但是我们没法确定的知道哪一次Trun On会导致灯泡坏掉，使得灯泡进入”Down”状态的那次“开”操作看上去跟你昨天开灯的那次操作一模一样（严格的说，每一次点亮灯泡都会导致灯丝的状态发生变化，但是在此简化了）
所以从状态”Off”出来的输出边中，”Trun On”有两条，这就导致没法根据当前状态和输出边确定下一状态，这就是为什么称为非确定性有限自动机的原因。
如何转换？
刚才Shellex说了，正则表达式有三种基本结构。如果能先将这三种基本结构转换成对应的NFA，然后在用这三种基本结构去拼装成完整的NFA是不是很省力呢？
下面就是三种基本正则表达式的NFA
ab:

a*:

a|b:

里面出现了一种叫“None”的边。这个不代表这个边是字面上的“None”，而是指这个边是个空边。也就是说任何“动作”都可以从这个边进入下一个状态。它的学名叫 epsilon 边，一般表示成’ε’，Shellex这里表示成“None”了。
下面我们来考虑正则表达式到NFA转换。给出一个正则串的输入，得到一个NFA的输出。被广泛采用的是Thompson Algorithm，也就是所谓的子集算法。该算法的发明人应该就是写ed编辑器的那个Thompson大牛。该算法的实现和算术表达式的求值非常的类似，需要一个符号栈存放操作符，一个自动机栈存放生成的自动机。算法结束后，可以从自动机栈中Pop一个最终的结果。
比如对于正则表达式(a|b)*cd，求值过程如下：
PUSH a To automaton stack
PUSH [...]

话说有一道汉语六级考试题：
路人甲：哇，Shellex是个帅哥ye
路人乙：您老是火星人吗？
路人乙的意思是___
A. 甲就是一个来自火星的人类
B. 问甲是否准备去火星养老
C. 甲的消息不灵通，少见多怪。
答案：C。
但是Shellex从物理学的角度提出了一种理论，论证了答案A的正确性。
我们都知道(via)，火星是太阳系的第四颗行星，轨道位于地球之外，木星之内。轨道半径在249 209 300 km和206 669 000 km之间，与地球的轨道半径的距离大约是1亿千米上下。由于火星轨道的原因，这个数字变化很大，但是不会对我们的论证造成很大影响。所以我们不妨取地球到火星的距离为1 00 000 000 km.
我们还知道(via)，电磁波的速度和传播介质相关，在真空中的速度与光速相同，大约三十万千米每秒，这个数字也不会对我们的论证造成很大影响，我们不妨设电磁波的速度是300 000 km/s
好了。现在假设地球上播放了一电视节目，表达了“Shellex很帅”这一事实。那么作为节目的载体——电磁波——需要多久才能到火星，被火星的同学的电视天线接收到，继而被火星上的同学得知呢？
有了以上的假设，我们容易得出，时间大约是 100 000 000 / 300 000 = 333.333秒
OK，现在我们知道了，火星上的同学比地球上的同学至少要慢上三百多秒才知道“Shellex很帅”这一事实。
那么现在我们回过头来看看那道汉语六级考试题，假如路人甲住在火星上，路人乙住在地球上；再假如路人甲和路人乙之间的交流是实时的——也就是不考虑他们之间的时间差；现在路人甲晚于路人乙三百多秒才知道“Shellex很帅”这一事实，难道路人乙没有理由怀疑他住在火星吗？
有了这样的讨论，大家可能也就明白了为什么有时候有些同学被称为“冥王星人”甚至“那美克星人”了吧，因为他们距离地球更远啊，看的都是地球上几小时甚至几千、几百年前的节目，得到的都是地球上几小时甚至几千、几百年前的信息，能不老土么？
这就是“火星人”的来历咯

入侵网络老师计算机获取考题以及答案的可行性分析
作者：Shellex
声明：

该文纯属YY，作者Shellex不对任何执行行为责任；
该文版权归Shellex (www.sxnsx.com) 所有，以CC协议发布

1 引文
1.1 编写目的

向各位同学阐述该方案的概要内容和附加信息。

1.2 背景

计算机网络 是一门专业性很强的课程，难度较高。主要讲授和讨论计算机网络前沿研究领域的重要协议和关键算法。主要内容有广域网技术、 ATM技术、TCP/IP、多播、宽带网络性能分析、网络安全等。
该课程授课教授为Prof. S，其人学识渊博，风趣幽默，理论与实践结合紧密，深受同学们爱戴。但是考试仍然是不可忽略的一环。
本着学以致用的原则，以及同学们期待的目光，在此，Shellex将针对入侵Prof. S 的计算机并获取考题和答案这一方案的可行性进行分析和论证。

2 可行性研究的前提
2.1 要求

安全与保密：绝密，保密期限，3年。
完成日期：2009年01月07日前

2.2 目标

成功获取本年度 计算机网络课程 的考试试题和答案

2.3 条件、假定和限制

能在考试前完成目标。
方案执行人的人身安全
方案不为第三方察觉
有足够的财力和精力支持

2.4 决定可行性的主要因素

时间因素
法律与道德因素
技术因素
心理因素

3. 对现有方案的分析
3.1 处理流程和数据流程

处理流程1：复习 → 考试
处理流程2：？ → 考试
数据流程1：书本 + 幻灯 + 牛人的大脑 → 备考人的大脑 → 备考人试卷
数据流程2：书本 + 幻灯 + 牛人的大脑 → 小抄或者其他设备 → 备考人的试卷
数据流程3：备考人试卷 → 备考人的试卷
数据流程2：备考人试卷 → 小抄或者其他设备 → 备考人的试卷

3.2 工作负荷

每天复习若干小时，根据备考人的学习能力、作弊能力和精力决定

3.3 费用支出

复习资料和相关支出，根据备考人的能力和财力决定

3.4 人员

备考人一人，所处环境人数根据备考人的交际能力、作弊能力和财力决定

3.5 设备

纸笔若干

3.6 现存局限性

正常备考：成功率稳定，风险无，当前回报大，潜在回报大，支出大
作弊备考：成功率不稳定，风险大，当前回报大，潜在回报无，支出小

4 本方案技术可行性分析
4.1 对方案的简要描述

通过入侵 计算机网络 课程的授课教授 [...]

via: http://it.ju690.com/meme/70677
Shellex：该文与Shellex的观念完全相同。Shellex很有爱…
1，天赋＝下意识。
一般来讲，上天给了我们每个人一个Gift。这个Gift就是区别于别人的一个天赋。每个人都有。这个天赋会让你在某些事情上能够不用太多学习就可以下意识做出某种判断，因为这种选择是下意识的，所以更加精准，更加到位。我们看到有些在对于美能够凭直觉做出很好的判断，有些人对于逻辑能够做出很好的判断，有些人对于音乐能够有很好的感觉。我们也看到有些人通过后天的学习可以在审美、逻辑、音乐等等方面去具备某些能力，却总会有所欠缺。
Shellex：每个人都拥有天赋。比如我们中大多数人都有的一个天赋是不用数5以下的数目，比如说0～4个物体，大多数人不用数就可以判断出物体的数目。而牛B的数学家可以不用证明就可以猜想出简单的一个推理是否正确，而证明后发现确实是正确的。
2，大多数人终其一生都没找到自己的天赋究竟是什么。
为什么没有找到呢？主要的误导在于，我们区分不清，何谓热情，何谓天赋。有时候这确实很难。毕马威的全球CEO在自己小的的时候爱上了棒球这项运动，并且还在当地获得了很不错的成就，他暗下决心要在棒球方面大展拳脚，后来才发现，他甚至不能够在全州的预选赛上出线，也不如他弟弟打得更好。而在这个过程中才发现自己更加善于对于一切计划性得、精确性得事物是与生具来的感觉，最后成为了毕马威的CEO。热情可以让我们走得很远，但是要想走得足够远，仅有热情是不够的。
Shellex：热爱自己的天赋吧～
3，有些人发现了自己的天赋，但是这种天赋却由于社会分工的颗粒度问题，或者因为时代的变迁，因为被需要的程度，自己所拥有的这份天赋却没有广泛的用武之地。当然是否存在广泛的被需要的判断有时时偏颇的。
Shellex：也许你觉得你没有特长，也许你的特长是开星际飞船。
4，有些人发现了自己的天赋，又发现这个天赋其实社会很需要，不过由于发现的时间不对（很多时候并不是真正的时间不对，误判而已），已经失去了使用这个天赋所需要的某些前置环节或者Skills。
Shellex：相信自己的判断，坚定地走自己的路。
其实我想说的是：
如果一个人可以从事一份可以充分发挥自己那些“下意识”的工作，那么他就可以从中收获巨大的成就感、进而产生更大的热情去做这件事情，进而获得更大的成就。在这个过程中需要谨慎区分何为只是自己一腔热情、何为自己迫不得已、何为自己真正的天赋导致的如鱼得水。
如果你现在就有这种如鱼得水的感觉，那么恭喜你，坚定下去吧。如果你还没有找到，那么任何时候都不会太晚，当然，也别太太晚。
Shellex说：这不是新时代的纳粹优等人种论。人类参差不全的基因给了我们平等的机会，感谢自然。

这篇文章能告诉你什么？
—— 通过改变一点点浏览习惯，节约您的时间，优化您的生活；让您驾驭更优雅，活得更健康。
几个问题。

你是不是经常去反复浏览某些网站或者blog来获取信息？

上 sxnsx.com 和 Shellex 扯淡。
上论坛找无聊的水贴。
上 verycd.com 找最新的大片。

你是不是总是会在这个过程上花费大量的时间？

每天流连忘返花个几个小时
然后懊恼不已

最重要的是你还不知道RSS订阅！

什么是RSS？
Shellex不想使用任何学术性语言。
RSS订阅，既然被称为一种订阅，那么就可以报刊的订阅来类比：
Shellex同学是一个好孩子。在订阅报纸之前，他每天都会去图书馆翻阅当天的新闻：什么 艳照门 啦，什么 张筱雨 啦，什么 Kappa女 啦 点点点 。关心时事本来是一件很好的，但是去图书馆总是会遇到很多熟人，这样不免寒暄几句，要是遇上漂亮的MM，还会耽搁阅读和学习的进度，实在是不好。而且每天都去图书馆实在是很累，因为Shellex同学超懒的。
现在有了订阅服务，每天Shellex同学都会收到邮局的投递员送上门的报纸。而且这些报纸都是Shellex感兴趣的。没有了干扰，免去了跑腿，Shellex同学高效地阅读了新闻，也没耽搁时间。生命立刻变得美好起来。
Rss就是类似的这样一种服务，而且这个订阅服务还是 免费 的！您还在犹豫什么呢？马上拿起电话订购吧！不 对，是打开网站订阅吧！
而你需要做的，只是去RSS邮局（见下文）——google reader / 抓虾 / 鲜果 这样的地方注册一个帐户，然后根据提示添加Rss地址就可以。
如果订阅Rss？
如果你在你的浏览器地址栏(比如 Firefox )，或者 网页的任何一个地方，发现有这样一个图标：
那就说明这个网站支持 RSS 订阅。现在你只需要点击这个图标，那么得到的地址就可以加入到阅读器中去。
当然，有的Rss图标的样式可能不太一样，比如本文右边有一个这样图标 ，点它打开一个新页面后，上面还会有引导你通过阅读器订阅的按钮，总共只需要点两下就好，都不需要手工添加地址咯～
Rss有什么优点？

加载速度快（减少等待！）
内容简洁，网站上的广告等都不会有（没有干扰！）
不受功夫网的影响，能够通过RSS订阅继续阅读最新文章（非常和谐！）
及时更新，若源站有发表新文章，马上就可以阅读到（最新资讯！）
全部信息都能在RSS阅读器内全读完，不再需要一个一个地逛博客了（节约时间！节约鼠标！）

Shellex推荐的Rss“邮局”：

Google Reader
抓虾阅读器
鲜果阅读器
网易有道阅读器

最后，Shellex推荐大家订阅我的博客，订阅地址：http://feed.feedsky.com/Shellex
直接点右边的订阅按钮也是可以的。

如何判定一个数能否被3整除? 比如6。
如果你有Python，可以在交互式解释器里面输入：
import re
print re.match(“1((10*1)|(01*0))*10*$”, “110″)!=None
或者直接在你的浏览器地址栏或者Firebug终端输入：
javascript:document.write(/^1((10*1)|(01*0))*10*$/.test(“110″)); document.close();
其中那个”110″部分为任何正整数的二进制形式。
如果返回/打印出 True，则说明被测试数能被3整除；如果结果是False则是无法被3整除。
看上去很神奇，其实道理很简单。首先我们知道，对于任何一个二进制数总是可以表示为如下形式：
Ac
其中A表示前N个字符，c表示最后一个字符。比如对于12的二进制表示”1100″，A指代的是”110″，c指定”0″
我们知道，2进制中，末尾添0直观地表示原数的两倍，那么末尾添1就是原数的两倍再加一。
基于这个事实，要使得Ac被3整除即 Ac mod 3 == 0，则
存在这么一个函数
f(A, c) =
当c为0时：(A×2) mod 3 = ((A mod 3) × 2) mod 3
当c为1时：(A×2+1) mod 3 = ((A mod 3) × 2 + 1) mod 3
只需要函数f(A, c) == 0就可以了。但是这得求A mod 3，只需要向前递归，把A分解成A’和a’，然后求f(A’, a’)就可以了。现在我们把函数f作为状态转换函数，f的值作为状态，待判断二进制串作为接受串，当然了，终止态必须在0，就有如下自动机：

这样不难得出对应的，判定能否被3整除的正则表达式(^1((10*1)|(01*0))*10*$)
想了解更多正则表达式的在算术上的乐趣，不妨阅读Matrix67同学的文章：http://www.matrix67.com/blog/archives/475
以及http://blog.stevenlevithan.com/archives/algebra-with-regexes

写下这个题目的时候哈，shellex又一次，情不自禁地，为我们汉语的博大精深而热泪盈眶。多么美妙的翻译啊，大脑操，要是鹰语就不行咯，彻底沦于庸俗：brainfuck。当然了，还有一些女士叫法，比如brainf**k（请看我的文章分类），b*fuck，brainf*ck等等。但是不管你怎么叫它，它都是brainfuck，是为了fuck你的brain而生的。
这个语言绝对是世界上最淫荡的语言之一了。虽然Shellex很早就知道它的淫荡，但是直到今天才介绍给大家，还望见谅咯。
好吧，这么说有点无聊，但是它不是为了fuck你的brain而生的。按照作者的说法，他想写一个最小的图灵完备的计算机语言，那么如果稍微接触一下brainfuck你会发现他也许真的达到目标了。因为brainfuck程序就是像一个图灵机那样运作。
语言说明：
Brainfuck 程序中有一个隐含的指针, 被称为 “the pointer”, 它能在一个长度为30 000字节的数组上来回移动。这个数组总是被初始化为0，而指针则总是被初始化指向数组的头部。
Brainfuck 语言很简单，只有8个指令，都用一个字符来表示

< 指针左移.
> 指针右移.
+ 指针自增.
- 指针自减.
. 输出当前指针指向的字节.
, 接受一个输入并储存在当前当前字节.
[ 如果当前指针不为0，则运行直到遇到]
] 如果当前指针不为0，跳回到匹配的 [

Shellex的brainfuck解释器的实现中，还私自添加了一个扩展指令：

$ 在内存监视器打印程序内存情况.

当然了，Brainfuck的语义可以简洁地用C语言的形式来表达（假设p是一个char *类型的变量）

> becomes ++p;
< becomes --p;
+ becomes ++*p;
- becomes [...]

由于我是从hardy升级上来的，所以我遇到的问题全新安装的要多一些。所以我在这里写下一些之后陆续遇到的问题。
上篇：升级到Ubuntu 8.10，是有史以来问题最多的一次
4. 无法自动挂载移动设备
插入USB设备没有反应。我还以为是内核的问题呢，然后看看lsusb，成功识别；再看看/dev/sd*，成功识别。手工挂载当然可以了，但是gnome volume manager死到哪里去了？好吧，我看看….虽然依赖还在，但是貌似被gnome-mount这个包代替了。去新立得重新安装这两个包就行了。
apt://gnome-mount
apt://gnome-volume-manager
5. Flash，以及某些游戏乱码。
这个和hardy的解决方案一样。自己去google搜索: Ubuntu Flash乱码
嗯。目前就发现这么些。由于我是Intel集成显卡，所以很多在显示驱动方面可能出现的问题在我的机器上都不会出现的。所以也许您升级会遇到更多的困难。
但是我仍然建议大家升级，每6个月重装一次没什么意思，当然了，如果用的是gentoo之类发行版的同学永远不会有发行版升级的烦恼（取而代之的是别的麻烦）。
总的来说，克服了这些困难，8.10始终比8.04强。gnome套件的增强是我最感兴趣的。而Compiz的重构，使我的GUI响应也有提升（感官感觉）。还是不错的。