Kai

3月底，Brian送我了这本书。看到现在才看完。真是本好书，刚拿上手的时候非常的有相见恨晚的感觉。
所有对设计感兴趣的同学都应该读一读这本书。对我来说，是第一次有看到这么细致的讲设计时的一些小问题。比如函数的命名，变量的命名，Property Bag还是Strong Named Property，重载的使用，虚函数与回调函数的比较，以及一些常用的简单的设计模式与其他类似手段的比较等等。还有很重要的一点，我以前一直就觉得OOD其实是有点问题的，因为用起来很复杂。这本书里面就很直接的说，OOD只是适合于程序员开发而已，对于用户使用，并没有什么好处，所以凡事不必拘泥于OOD。

这本书是将.Net Framework的设计原则的，虽然我们大多数人一辈子都没有机会做一些像样的Framework，但是他的设计里面的很多考虑还是可以借鉴的。因为我们写的代码总有一部分会给别的程序员使用，要想让别的程序员不会背地里抱怨接口难用，最好在接口的易用性上多花点功夫。

今天下午才组装起来，发现，手感很奇特。不想电子琴那样软绵绵的，键按到底会有真的按到东西的感觉，如果音量开的比较小的话，听起来轻轻的按声音很小。反正我也没摸过真的钢琴，就当做手感还行吧。不过下意识的总觉得，如果用电脑键盘的x架构做钢琴键盘，手感会更容易适应。配重键盘摸起来，好像挺迟钝的，都不能很快弹起来。

嘿嘿这只手是放上去摆造型的。

Yes, I miss you, 想你在心里种出一颗大树---------------------------为什么要种大树……？
我们面对面，挂在天边---------------------------------------------------真可怜啊~
你的眼泪淹没整个宇宙，连流星都难过------------------------------比白素贞还厉害！
是你让我又再次听见自己心跳，幸福得快晕倒---------------------听见自己心跳，竟然幸福的不得了；幸福的极限原来是晕倒！

DirectX SDK里面有个Pick的程序，实现了鼠标点选3D世界三角形的功能。第一次看哪个例子，看了一个小时都没看懂他的算法。主要难点有两个，第一个是点选向量的构造，第二个是光线与三角形相交的计算。

首先，我忽略的Projection Matrix，一直都理解成和Shadow Matrix一样的东西。事实上Shadow Matrix比Projection Matrix要复杂一些，Projection Matrix是Shadow Matrix的特例。代码里面的计算过程是在纸上简化过的，直接看会有些莫名其妙。后来对照Projection Matrix的构造过程，去理解那段代码才有点明白。另外，View Matrix的第四行就是摄像机的位置。还有，World, View矩阵的第四列都是空的，所以构造的时候，不需要使用齐次向量。

第二，判断光线与三角形相交。原始方法就是解析几何的那套，先用方程计算交点，然后判断是不是在三角形里面。但是DX SDK里面的那个例子用的一个很漂亮的算法，我直接看完全看不懂。于是在网上查了一下光线与三角形相交的算法，竟然找到一篇SIGGRAPH 2005的论文，“Fast, minimum storage ray/triangle intersection”。DX SDK的Pick程序用的就是这个论文里提出的算法。果然很巧妙。

我好像记得以前看OpenGL的时候，OpenGL里面有一个叫做SelectBuffer的东西，可以用来做点选判断，占用了更多的内存，但是数学计算上，要简单很多。

前些天闲的无所事事，偶遇译言上的一个连接，于是就翻译了。
http://www.yeeyan.com/articles/view/76376/35225

原来大学编译原理学的上下文无关文法不是最适合程序语言的文法，而且Yacc也没有应用在主流编译器上。呵呵……

------------------------------------------------------------------------------------

解析表达文法
来自维基百科，自由的百科全书

解析表达文法，简称PEG，是一种解析形式的文法。这种文法用一个识别字符串的规则的集合来描述某种形式语言。解析表达文法以纯公式的形式的展现递归下降 解析器的基础语法，对这个具体的解析器可能会采用的实现方法不做任何限定。解析表达文法看起来与，正则表达式和巴科斯形式的上下文无关文法（CFG）很 像，但是表达的意思不同。

和CFG不同的是，PEG不能有二义性；解析一个字符串的时候，这个字符串只产生一个确定的解析树。这个特性使得PEG更适合计算机语言的解析，对于自然语言就不是很合适。
内容
[隐藏]

    * 1 定义
          o 1.1 解析表达式的解释
          o 1.2 示例
    * 2 根据解析表达文法实现解析器
    * 3 优势
    * 4 劣势
    * 5 参考
    * 6 引用
    * 7 外部链接

定义

形式上，一个解析表达文法由以下部分组成:

    * 一个有限的非终结符的集合 N
    * 一个有限的终结符的集合 Σ， 和 N没有交集
    * 一个有限的解析规则的集合 P
    * 一个被称作起点表达式的解析表达式 eS

每一个解析规则以A ← e的形式出现，这里A是一个非终结符，e是一个解析表达式。解析表达式是类似正则表达式的层次表达式，由以下形式构成：

   1. 原子解析表达式由以下组成:
          * 任何的终结符，
          * 任何的非终结符，
          * 空字符串 ε.
   2. 给定已经存在的解析表达式e, e1, and e2, 一个新的解析表达式可以通过以下操作构成:
          * 序列: e1 e2
          * 有序选择: e1 / e2
          * 零个或更多: e*
          * 一个或更多: e+
          * 可选: e?
          * 肯定断言: &e
          * 否定断言: !e

CFG和PEG的关键不同是PEG的选择操作符是有序的。如果第一个可能成功了，那么第二个可能就忽略。因此PEG的有序选择是不可以互换的，这点和上下 文无关文法或者正则表达式在教科书上的定义不同。有序选择类似于某些逻辑编程语言中的soft cut操作符【译注：没有查到这个soft cut operator到底是什么，我的理解是逻辑操作符and或者or这样的，如果前面的条件匹配了，后面的条件就被跳过不判断】。

与上下文无关文法或者其他生成文法不同，在解析表达文法里面，对应某个非终结符，必须且只能有一个的解析规则。这意味着，在PEG里面，解析规则就是定义，每一个非终结符必须有且只能由一个定义。

这导致的区别就是如果一个上下文无关文法被直接转换为解析表达文法，所有的不确定性的地方都会被确定下来，方法是从所有可能的解析树中选择一个分支。通过仔细安排文法可能项的顺序，编程的人就可以自由控制那一个解析分支被选中。

 
解析表达式的解释

解析表达文法里面的每一个非终结符本质上表示递归下降解析器里面的一个解析函数，其对应的解析表达式展示了这个函数包含的代码内容。概念上，每一个解析函数接受一个输入字符串作为参数，返回以下其中一个结果:

    * 成功，函数可能向前移动或者“消耗”一个或多个输入字符串的字符
    * 失败，不消耗任何字符

一个非终结符有可能成功但是不消耗任何输入字符，这也是一种不同于失败的结果。

只由一个终结符组成的原子解析表达式：成功，如果输入字符串的第一个字符就是定义中的终结符，这种情况下消耗这个输入字符；否之失败。由空字符串组成的原 子解析表达式总是成功并且不消耗任何输入。只由一个非终结符A组成的原子解析表达式表示对非终结符A的解析函数的递归调用。

序列操作符 e1e2 首先调用 e1， 如果 e1成功， 接着对 e1消耗剩下的输入字符串调用 e2， 最后返回结果。如果 e1 或者 e2 失败，那么序列表达式 e1e2 失败。

选择操作符e1 / e2 首先调用 e1， 如果 e1成功， 立刻返回结果。否则如果 e1 失败，选择操作符回溯到输入字符串匹配 e1 的原始位置，调用 e2， 最后返回 e2 结果。

零个或多个，一个或多个，和可选操作符分别消耗零个或多个，一个或多个，或者零个或一个连续重复的子表达式e。与上下文无关文法和正则表达式不同的是，尽 管如此，在PEG里这些操作符总是执行贪婪的行为，那就是消耗尽可能多的输入，而且绝对不回溯。（正则表达式一开始执行贪婪匹配，但是如果整个正则表达式 失败后，会回退并尝试短一些的匹配。）例如，解析表达式a*总是尽可能多的消耗输入字符串中连续出现的a，解析表达式(a* a)则必然会失败因为前半部分a*绝对不会留下一丁点a给后半部分去匹配。

最后，肯定断言和否定断言实现了句法断言。&e 表达式调用子表达式e，如果e成功，则返回成功；否则返回失败。无论结果如何都不消耗任何字符。反之，当e失败时！e 表达式成功，e成功时！e 表达式失败， 同样无论结果如何都不消耗任何字符。因为向前判断的子表达式e 可以任意的复杂，所以断言表达式提供了强大的句法向前判断和去除二义性的能力。

 
示例

这是一个简单的解析表达文法，它识别基本的数学表达式，只使用了基本的四个运算符并且只接受正整数作为操作数.

    Value ← [0-9]+ / '(' Expr ')'
    Product ← Value (('*' / '/') Value)*
    Sum ← Product (('+' / '-') Product)*
    Expr ← Sum

在上面这个例子里面，终结符就是字符文本，用单引号括起来表示。比如'('和')'。[0-9]这个区间是10个字符的缩写，表示数字0到数字9里面的任 意一个。（这里区间的语义和正则表达式里面的一样。）非终结符就是被定义成其他表达式的符号：Value, Product, Sum, and Expr.

下面的例子去掉引用标记以便阅读。小写字母表示终结符，大写字母是非终结符。真实的PEG语法要求所有的小写字母都在引号里面。

解析表达式(a/b)* 匹配任意长度的a和b序列。解析规则 S ← a S? b 描述了｛anbn:n ≥1｝这样一个简单的上下文无关匹配语言。而下面的这个解析表达文法则可以描述经典的非上下文无关文法：

    S ← &(A !b) a+ B !(a/b/c)
    A ← a A? b
    B ← b B? c

接下来的递归规则匹配了标准C风格的if/then/else语句。因为/操作符的隐式优先级安排，可选的else语句总是会被绑定到最内层的if语句。（在上下文无关文法里，这种结构的文法会导致悬空的else语句这种二义性错误。

    S ← if C then S else S / if C then S

解析表达式 foo &(bar) 只有当 foo 后面紧跟着字符串 bar 的时候，才会匹配并消耗 foo。而解析表达式 foo !(bar) 只有当 foo 后面没有紧跟着字符串 bar 的时候，才会匹配。表达式!(a+ b) a 只有当a 不是一连串a后面连着一个b的情况下出现的时候，才能匹配一个单独的字母a。

下面的这个递归规则匹配Pascal格式的注释语法，(*和*)括号，其内部可以有嵌套的(*和*)对。注释符号放在双引号内内是为了与其他PEG操作符区分开来。

    Begin ← "(*"
    End ← "*)"
    C ← Begin N* End
    N ← C / (!Begin !End Z)
    Z ← any single character

根据解析表达文法实现解析器

所有的解析表达文法都能够被直接转化为递归下降解析器。尽管如此，因为PEG公式提供了理论上不受限制的向前检查的能力，所以最终得到的解析器还是可以避免最坏情况下指数级时间复杂度的。

通过保存增量解析步骤的结果和确保每一个解析函数在同一个输入位置只被调用一次，就可以把任意解析表达文法转化成一个Packrat Parser(译注：如果这里译作收集鼠解析器，似乎太可爱了点，就用英文吧），可以实现线性的时间复杂度解析，其代价是足够大量的空间占用。

一个Packrat Parser是一种结构上类似于递归下降解析器的语法解析器，区别是在解析过程中，它会记下所有互相递归调用的函数的中间结果。因为保存了这些信息，一个 Packrat Parser就拥有了以线性时间复杂度解析多数上下文无关文法和所有解析表达文法的能力（包括某些表示的不是上下文无关文法语言的文法）。

从解析表达文法建立LL Parser和LR Parser也是可行的，但是在这两种情况下，不受限制的向前检查的能力就不能用了。

 

优势

因为PEG更加严格更加强大，PEG可以成为很好的正则表达式的替代品。例如，一个正则表达式本身是无法匹配嵌套的括号对，因为正则表达式不是递归的，但是PEG却能做到这点。

所有的PEG都能通过使用Parkrat Parser达到线性时间解析，如同上文所述。

CFG表达的解析器，比如LR解析器，需要首先进行一个单独的断词步骤。这个步骤根据空白的位置或者发音等等因素把输入分成词。分词是必要的，因为这类解 析器使用向前检查来判断上下文无关文法是否匹配要求。PEG不需要单独的断词步骤，断词的规则和其他文法规则可以用同样的方式写在一起。

许多CFG固有的存在二义性，即使它们原本要描述的东西并不具有二义性。C, C++, Java里面著名的悬空else问题就是一个例子。这个问题通常都是应用文法之外的一个规则解决。而在PEG里面，因为使用了优先权，所以根本不存在这种问题。

劣势

PEG是新事物，还没有被广泛的应用。相比之下，正则表达式和CFG已经产生了数十年了，用来解析的代码也已经优化的很好，并且很多开发者都熟悉怎么使用他们。

PEG不能表达左递归的解析规则。例如，上面的数学运算文法，通过引入更多的规则，来使得乘法和加法的优先级能够在一行里面表达出来这可是非常的有诱惑力的， 结果可能得到下面的文法：

    Value ← [0-9.]+ / '(' Expr ')'
    Product ← Expr (('*' / '/') Expr)*
    Sum ← Expr (('+' / '-') Expr)*
    Expr ← Product / Sum / Value

这个文法的问题就是，为了匹配Expr， 你需要首先判断是否某处匹配Product， 而为了匹配Product， 你又必须判断是不是此处匹配Expr。而这种逻辑是不可能做到的。

尽管如此，我们总是可以通过重写左递归规则把左递归消除掉。例如，一个左递归可能无限的重复一个规则，就像在CFG里面的：

    string-of-a ← string-of-a 'a' | 'a'

在PEG里面，可以用加号操作符重写为：

    string-of-a ← 'a'+

PEG还涉及到Packrat Parsing， 一种通过占用更多的存储空间来消除不必要解析步骤的方法。Packrat Parsing需要的存储空间与总的输入文件的大小成正比，而不是LR解析器的与解析树的深度成正比。如果稍作修改，传统的Packrat Parser也可以支持左递归。

参考

    * 形式文法
    * 正则表达式
    * 自顶向下解析语言
    * 解析器生成器的比较

Kenny, Tommy and I， 三人参与完成的最终品。
在EA完成的唯一一个项目，就是这个玩具。

想起一句话，人类可以探测火星表面，但是却无法探测自己的内心。

似乎最容易接受的情况是没有改变，最难接受的是预料之外的改变。当计划没有变化快的时候，最明智的选择大概首先是减小无法预计带来的损失吧。

本来在开始工作的前两年也没打算做什么事情，就是参与一个项目的开发而已，仅仅是参与，具体做什么也没有想过，做editor还是改bug我都不介意的。但是随着接触的越多，欲望也就越大。要不是EA人少，估计很难有机会自己去设计一个系统，然后亲手实现的。尝试过做大一点的东西后，就有点上瘾。可是现在几乎不论去那个公司，如果不像EA这么人少的话，以我的经验和年龄，估计是拿不到一个大的模块做。从这个角度来说，项目被裁与我个人的利益关系影响很大。所以如果能找到一个人手紧缺的项目进去，似乎还能沾点便宜。

如果没办法做一个MMO的模块，那么小一点的一个休闲游戏的模块也可以考虑。如果可以做到一个console的模块，也很好。另外我还得看看时机，找个机会做图形，最终我还是要回到图形上。

在析构一个链表的时候while循环里忘记++it，导致同一个地方析构2次，服务器crash。

这个本来是很低级很简单很愚蠢的错误，可是我却想当然的认为是什么地方复制了对象，所以会有两次析构。在没有看出错地方的代码的情况下就去想办法解决问题，于是首先想到了用智能指针，然后哗哗哗用半天更新了eastl库，用shared_ptr替换原来的raw指针。下午坐着想又觉得有点奇怪，觉得智能指针只是保证了浅拷贝没有问题，可以如果程序真的需要的是一个深拷贝，那该怎么办呢，于是又花了半天思考怎么做深拷贝，还借鉴了java的clone函数，打算做个能多态的拷贝的东西。后来想想还是觉得有点奇怪，总觉得不应该有拷贝发生。于是把所有相关的类的拷贝构造函数和复制操作符函数都声明一下，但是未定义，期待编译器给我一个连接错误，结果G++说一切正常。崩溃中决定打印日志到文件，这样我能知道到底是不是被同一个地址被析构两次产生的。昨天到公司看了下，果然服务器崩了，果然是析构两次。再次检查有没有相关的类没有声明拷贝构造。今天到公司看来查，看到了具体的析构函数和循环中释放的地址，发现是在循环里有个地址析构了两次。这是第一个想法是一个节点的孩子链表里面有自己（这样想其实是非常愚蠢和不现实的），于是想在循环析构之前全部输出一下孩子的地址和数量。这个时候新写的循环代码和原来的析构代码比较了一下，发现原来的代码里面迭代子it没有++。这下我真的崩溃了。

以此为记，我也会犯很愚蠢很单纯的代码错误的。以后发现错误时，首先要从简单的地方考虑。很多事情没有我想的那么复杂。

左图是瑞典DICE工作室的新游戏Mirror's Edge的女主角，右图是不爽的日本玩家自己PS的理想东方女性形象。这里可以看到东西方审美的差别。

原帖：一个女性角色引发的东西方文化差异讨论

最节省时间的方法——学习

November 8th, 2008 | by 李笑来 |

可以想象并且可以充分理解的是：无论经过怎样的改良，所有的教育体制无一例外都无法做到完美。更进一步令人毫不惊讶的是——它们而实际上通常非常失败，古今中外皆如是。教育体制最为失败的地方在于它对“学习”这个词的“妖魔化作用”——很多人接受所谓“教育”，在学校里读了许多年书的最终结果竟然是“发誓再也不学习了”。过去我总认为拒绝学习的实际上并不多。阴差阳错，我竟然最终以老师为职业，而这许多年的教学经验告诉我，太多太多的学生在不经意之间早已下定决心只要有一天离开学校就“坚决再也不受那罪了！”——他们最终也确实是这么做的，事实上，他们可能很早就开始拒绝学习了，只不过没有那么“嚣张地”表现出来而已。

为了让学生明白学习的意义，我总是尝试着用“进化”去比喻“成长”，用“适应”比喻“学习”。我想，如果我运气好的话，在这些年中总是有机会成功地转化了一些人的态度，使他们明白可以通过“学习”不断进化，当很多人实际上不过是猴子的时候，他们早已经通过学习进化为真正的人甚至尼采所说的“超人”（overman）了。

学习的目的本来就不是为了“考试”——只不过基于种种原因，连所谓的主流教育都变成了“应试教育”而已。如果说，车是人类腿脚的延伸——使人们走得更远，望远镜是人类眼睛的眼神——使人们看得更远，计算机是人脑的延伸——使人们算得更快……那么学习就是人类所有能力的延伸——可以使人们拥有更多的能力，并且往往仅需要时间与精力。事实上，学习本身不仅是一种能力，而且对人类来说更是一种天生的能力。很多人拒绝学习，本质上来看，就是在拒绝做人——因为几乎只有人类才有能力有机会“终生学习”。

我见过很多“拒绝学习”的人。我曾经尝试很多次去劝我的一个朋友花20分钟学习一下批处理命令，未果——他拒绝的理由是，现在谁还用dos啊？早就是windows时代了！我尝试过很多次同样未果：劝我的另外一个朋友花10分钟学习一下Google上的通配符的使用——她说，不用那东西也一样找到自己想要的了啊！我曾经替他们着急过，可是后来发现这是个“死结”。为什么呢？1. 因为他们拒绝学习他们就不可能有机会知道学习之后的收获；2.进而由于他们并不知道学习之后的收获是什么，于是当然不知道那收获有多好多大；3. 既然他们对学习的好处无从了解，于是就没有学习的动力……

进取之路上的人往往更可能觉得吃力而并非轻松，为什么呢？因为在那条路上“一山更比一山高”，“山外有山，天外有天”。在平庸之路上的人往往更可能并非自卑而是洋洋自得，为什么呢？因为他们总是会遇到比自己更差的人。

如果你曾经有过最终习得某种技能的经验，就知道在习得的那一瞬间，整个世界都会为之而变。或者换一个说法，因为你有能力做更多的事情了，你就不再存在于原本的世界里；因为你所习得的技能，你已经拥有另一个完全不同的世界。比如，你最终可以熟练使用一门外语，你原本生存的世界就多了一扇门，跨过那个门槛就是另外一个世界——这种情况下，再用另外一个说法就是，你比另外一些只能讲母语的人多拥有一个世界。我痴迷于学习，正是基于这样的体会。每次我掌握了一门新的技能（是否足够精通，或者是否比别人强实际上根本不重要）我就感觉我自己重生一次——如此看来，其实人一生原本可以有很多辈子的，只不过是大多数人放弃了而已。很多年前当我学会了BASIC编程语言，我并不知道它这一生都会给我带来无穷的好处，甚至不知道自己已经脱胎换骨；当我学会了当众演讲，世界就变了，就算是脱胎换骨了；当我真正学会了如何教书，我才发现我已经身处另外一个世界，我早已重生无数回……

事实上，有些人可能比其他人更有机会体会这种“一生中的许多辈子”的“诡异”体验。比如说，演员。那些最终演了几十年的演员，往往是因为他们的演技过人（所以才没有被淘汰掉）；而他们过人的演技更多来自于勤奋而非天赋——在每一出戏中他们都会用尽一切方法去了解他们所饰演的角色。罗伯特迪尼罗为了演好一名拳击手（《愤怒的公牛》），几个月内增重60磅而后几个月内又减重60磅；梅尔吉普森为了拍好《勇敢的心》，曾经花费几年时间去钻图书馆做他的功课；艾迪哈里斯为了演好贝多芬（《复制贝多芬》）花了好几年时间打磨自己的琴艺并揣摩贝多芬的心迹；刘德华为了演好《阿虎》不知道挨了多少打才不用演就能流露出虎落平阳的神态……看看这些演员二十年前的照片就会发现，他们最明显的变化其实并不是年龄，而是眼神——深邃得很。我的理解是，他们演一出戏就等于重活一辈子，而他们早已经活过不知道多少辈子，他们的眼神不深邃才怪，那眼神想要没有穿透力实在是太难……

学会起码一种技能很重要，无论它多简单，多没什么大不了，学会它总是可以让习得者了解到习得之后与之前的大不同。一旦拥有了一个起点，学习欲望就好像是发了芽的种子，无论多大的石头都压不住它——它会越来越茁壮，越来越坚强。其实，那些拒绝学习或者一不小心受了影响而已经把“学习”两个字妖魔化了的人真的非常可怜，他们每天都在挣扎着想要“管理时间”，“节约时间”，“提高效率”，却不知道他们因为当初不肯花费十几二十几分钟而其后一生少做了很多事情，错过了了很多机会，并且，一生只有一辈子却都没有过好……

-----------------------------------------------------------------------------------

今天在云风的blog看到这个帖子，觉得很不错，分享到这里。

学习不一定是需要长时间的积累，短到20分钟，半天，或者几个星期，就可以慢慢的改变人的能力范围。

去年我曾经花一个晚上背双拼韵母表，现在汉字输入的准确度与速度比使用智能拼音，模糊拼音的要提高40%左右。更为重要的，由于击键次数变少，对我个人而言打字会轻松一些。

毕业前花了3个星期学习perl，对正则表达式的使用有一些积累。现在常常在visual studio或者emeditor做一些正则表达式查找替换的简单文本操作，非常的方便。

昨天花一个小时简略的看了一下xlsx的格式，晚上我用python写了一个程序，把从去年二月份以来我一直在excel2007里面记录的每日支出情况处理到文本文件中，用csv格式保存，这样可以导入到数据库中，以便我进一步的数据分析。

由于工作需要，学习了一些linux的操作，现在我已经不像以前那么排斥linux了，而且由于我的硬盘空间越来越紧迫，我已经在考虑要不要改用linux系统，这样可以省出不少空间放电影。我突然想到linux的使用率不高有一个因素是很多人不愿意花上几天去学习linux的操作。