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

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

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

废话,因为我失败了啊。

事情是这样的,我再叙述一遍。软件学院大一上的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.

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

然后我改到了两点。

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

就是这样。