呐，文如标题，这次要说的是一次十分失败的装逼经历，或者说，一场惨痛的人生教训。有那么严重么？至少，对于新年的第一天和第二天的我来说，是这样的。

讲道理，在我看来，其实装逼本身就可以说是失败的。真正的强者不需要装逼，他们的强势永远都是一种自然的流露。当然，在弱者，或者说特定圈子之外的人，可能也会把这样的行为当成是装逼。就像，知乎上的很多习惯和流露的价值观，对于知乎社区的活跃用户来说，是无比正常的事情。但是对于一些微博或者贴吧上的网友而言，这些思维方式和语言习惯必是装逼无疑。

那我为什么还要说自己是装逼呢？

废话，因为我失败了啊。

事情是这样的，我再叙述一遍。软件学院大一上的C期末作业要求我们写一个解释器，要解释的语言被称作Mao，包含int和double两类变量的声明、表达式求值和print变量。其实一开始接到这个项目我是很高兴的。因为比起去年的JSON Parser来说，这个项目可以扩展的地方太多了。语言确实没有办法描述我的心情。那是一个星期二，下午无课，我跑到图书馆看了一个下午的编译原理。

「我要做一门真正的编程语言。」

从那天开始，直到2015年结束，可以说，我的脑子里从来没有忘过这事，偶尔梦里也梦到过。以至于我11月去无锡给我朋友过生日的时候，在路上因为突然想通了Mao语言的上下文无关文法，而突然哈哈大笑起来。

然后就是紧锣密鼓的设计和写代码。其实我不是一个执行力很强的人，很多想法都停留在脑海里要拖延很久才会去实现。这带来了很多问题。递归下降的语法解析器我从十二月下旬才开始写，由于是第一次写，代码删删改改，自己觉得满意了，结果对了（我当时是怎么判断出结果对的呢？）就停下来了。好，停下来之后又开始写对象系统，整个活生生朝着PHP的方向做。直到2015年的最后一天，我把对象的运算做好了之后，输入1+1+1测试，然后……

是的，我就是这么后知后觉。

我写的递归下降语法分析器，在解析表达式的时候，因为要考虑优先级，所以把包含相同优先级的运算式，划到上下文无关文法中同一类的非终结符里。举个例子，就像很多编译原理教材都会讲的一样，两个表达式加减的结果叫做term，两个表达式乘除的结果叫做factor，一个term可以这样定义：

term = term op-1 factor
     | factor

op-1 = '+'
     | '-'

在理论上，这是一个十分完美的结构，从这样的语法结构构造出的表达式树，也可以按照正确的执行顺序进行计算。比方说1-1-1，先算左边的1-1得0，再做0-1，最后得结果是-1. 因此第二个减号是树根，第一个减号是左子树的树根。这是左结合性的运算符。那么对于右结合性的运算符，比如乘方符号^，或者说赋值号=，这些是先算右边的，那么我们修改一下语法即可：

assignment = identifier assign-op assignment
           | expr

power = expr exponent-op power
      | expr

assign-op = '='

exponent-op = '^'

当我们计算表达式2^3^4的时候，顺序并不是跟加减乘除一样的，而是先算右边的3^4，得81，然后整个表达式的值是2^81，结果就不说了，因为写不下。

但是这样做有一个很大的缺陷，那就是我们的LL(k)解析器无法解析左递归的情况，会陷入无限循环。什么是左递归呢？就是上文提到的描绘左结合性运算符的文法形式。一个term是一个term加或减一个factor，但是这个term到底到哪里为止呢？我们的递归下降解析器，至少是理论上，做不到的。所以从文法上，我们需要移除左递归。当然，如果解析器是从右向左读的，那么也处理不了右递归。

移除左递归的过程可以说是范式化的，引入一个新的非终结符，修改一下规则，像这样：

term = factor term-rest

term-rest = null
          | op-1 term

这个看上去也很好啊，能够解决我们的问题。然而两者合在一起，问题出现了——移除左递归之后，程序解析到的树，结合性出现了问题！而事实上，我写得更蠢：

term = factor op-1 factor
     | factor

这样的递归下降解析器根本无法解析1+1+1这样的式子！它到第二个1处就停下来了！而当我发现这个问题的时候，时间已然是2015年的最后一个晚上了。

没有办法了，第二天早上起来试图改进，发现越改问题越过。中午决定放弃，推倒表达式解析重来。其他像for、while等写好的语法也暂时搁置下来。撸了一个下午到晚上，在1月2日前完成了作业。

然而好景不长，第二天晚上当我写好文档准备交的时候，又发现bug了！我的程序不能正确处理表达式开头的负号。简单说就是，我的程序会自动“分划”输入的表达式。为了解决负号的问题，程序会判断当前表达式开头是不是有负号，如果有的话，就整个表达式取负。出发点是对的，但是后面一遇到加减或者各种叠加的括号，问题就来了，比如会把-1+2的结果当成-3.

剩下二十分钟，真没办法了，先交吧。

然后我改到了两点。

讲道理，我感觉自己真的没有资格参加答辩。

就是这样。