Lexer 必须死

lexer 和 parser 的划分一直是一个让我不能完全理解的事情。这一划分对于某些语言或许有其优势,但是对于很多现代编程语言早已不敷用了;所谓词法记号(lexical token) 在很多情况下已经成为了碍手碍脚的多余概念。

C++ 的“>>”就是很经典的例子,单靠 lexer 无法确定这是两个右尖括号(用于关闭指定类型参数的两个左尖括号“<”)还是一个右移操作符。这时最好的做法是让 lexer 产生两个“>”,然后让 parser 来判断。也就是说,此时词法记号的界定已经取决于 parser 的状态,lexer 已经不能独立完成词法记号的划分。更糟糕的是,词法记号已经不再包含语义信息:“>”可能表示的是大于操作符、右尖括号或者右移操作符的一部分。lexer 作用之有限让人捉急。

另一个很好的例子是字符串内插(虽然我不觉得这是个好特性)。考虑 shell 的例子:echo "hello `echo "world"`."。注意 world 左边的引号;如果缺少语法信息,lexer 会认为这个字符串在这个地方结束了。因此在此例中,如果缺少 parser,lexer 根本无法确定字符串的边界了。这颠覆了“parser 调用 lexer”这一传统体位。比颠覆体位更糟糕的是,parser 和 lexer 产生了耦合,lexer 不能独立于 parser 开发和调试,分离成两个部件的优势几乎都丧失了。

抛弃 lexer 抽象并没有任何技术上的问题,因为正则语言是上下文无关语言的子集。我之前尝试写了一个 jadePython 实现,手写 parser 没有用到 lexer,也没有遇到任何问题。

实际上,在很多字符含义对环境高度敏感的语言 (包括 jade) 中,因为不存在能适用于所有环境的词法划分法则,lexer 抽象不得不被抛弃。实际上即使在语法更规则的语言中,词法记号的内部也往往有其结构,把这个内部结构放到语法树中是很方便的。一个简单的例子就是 C 的浮点数字面量,它包含小数部分、可选的 e 或 E 加上指数部分、以及可选的类型后缀。把这些组成部分分别放进语法树可以简化之后的语义步骤。

词法记号在 parser 中一般称为终结符号 (terminal symbol),以示其不包含具有语法意义的内部结构。更高的文法单元则都称为非终结符号 (nonterminal symbol)。但是上述论证已经说明了,终结符号和非终结符号的划分是任意的,而且所谓“终结符号”也可能包含具有语法意义的内部结构。

维基百科的 scannerless parsing 列出了三个指控,即难于调试、不确定性和歧义性。后面两个我没有 get 到它的点,但是难于调试这一指控绝对是不成立的。去掉了多余的 lexer 的抽象之后代码的内部接口得到了简化,调试起来反而会更简单。

lexer 作为一个陈旧的、需要抛弃的抽象,为何一直没有消失?我能想到两个原因。其一,由于形式语言理论来自于自然语言理论,早期计算机科学家也就照搬了语言学对形态(morphology) 和语法(syntax) 的划分。其二,最早流行的 parser 生成器 yacc 就是要和 lexer 生成器 lex 配合使用的,这一结构也就被后来的 parser 生成器一路沿袭下来了。

今天睡觉睡得浑浑噩噩,想必写得内容混乱,不知所云。

Summer of Code!

向所有具有编码技能的在校学生推荐 Google Summer of Code (GSoC)。

GSoC

一句话版本:GSoC 是在家写代码挣钱的好机会,有兴趣的该抓紧时间套磁+申请了。下面是完整版。

GSoC 是 Google 赞助学生开发开源软件的活动。对学生来说,活动流程是这样的:

  1. GSoC 网站上挑选开源组织,并决定你想做的项目。

    入选今年 GSoC 的组织已经公布了。它们涉及计算机学术和产业的方方面面:操作系统、程序语言、科学计算、网络技术、web、机器学习等领域都有组织入选。值得注意的是,有的组织如 Python Software Foundation 是所谓的 umbrella organization,下面包含了多个相关的子组织。

    每个组织都有一个 ideas page,列出了他们觉得适合 GSoC 的项目。开发环境和技术十分多样,从硬件驱动到 web、从设计向到编码向,不一而足。另外,不必局限于 ideas page,自己提出项目也是完全可以的。

  2. 在 GSoC 网站上提交项目提案 (project proposal)。

    你的提案将由你申请的组织(而不是 Google) 审查和批准。既然是提案,就有可能被拒绝。如果在看到你的提案之前他们对你有所了解,申请的成功率会大大提高。因此强烈建议在提交提案之前“套磁”。项目的 ideas page 上一半会列出潜在的项目导师 (mentor),他们就是你的套磁对象。

    对于设计向的项目,可以和 mentor 讨论、做文档。对于编码向的项目,应该先熟悉相关代码,修一些简单的 bug 或做一些简单的改进,然后提交给 mentor。很多项目是兼有设计和编码的,那么两方面的准备都应该做。“套磁”既可以让你提前感受一下这个项目的内容和难度,也可以让 mentor 体会到你的诚意并了解你现有的水平。各个组织的讨论平台和提交代码的流程各不相同,具体操作方式需要你自己去对应组织的官方网站上了解。

    不用担心自己水平不够而不敢“套磁”。一方面,技术水平的确最重要,但开源组织也十分看重开发者的热情和沟通能力。另一方面,如果确实水平太差,那就算申请通过了,期中考察还是会被刷下去,导致费了时间精力拿不到多少钱,可能还不如就不做 ╮( ̄▽ ̄")╭

    可以申请多个项目,不过最后只会通过一个。做个不负责任的猜想:如果多个组织都中意你,应该会问你想做那一个。

  3. 提案申请通过后,做三个月的开发。

    一般来说都是在家工作,定期参加线上会议或提交报告即可。不过每个开源组织的工作流程会有所不同,具体方式还是得自己去了解。

  4. 获得一笔报酬(今年是 5500 美刀)。报酬支付是穿插在开发过程中的:

    1. 开发过程开始后 Google 会给你 500 美刀。

    2. 开发过程进行到一半时会进行一次期中考察,通过之后 Google 会给你 2250 美刀。

    3. 开发过程完成后会再进行一次期末考察,通过(“毕业”)之后 Google 会给你剩下的 2750 美刀。

    期中考察和期末考察都是开源组织的人进行的,Google 只负责给钱。我做 GSoC 2012 和 2013 的时候,支付方式是邮寄信用卡,不过据说现在也可以直接转账了。具体请以官网为准并在申请过程中留意。

今年的学生申请截止日期是 3 月 27 日。如果你有兴趣的话,现在可以开始调研入选组织并尝试“套磁”了。最后,一切信息还请以官方网站为准,很多细节问题在 FAQ 里有详细解答。

我和 GSoC

我参加了 GSoC 2012 并成功毕业,项目是用 wiki 引擎 MoinMoin 实现 issue tracker。通过那次机会认识了当时在北京实习的 Qian Hong 同学。Qian Hong 当年做的是 Wine 下的项目,后来成了 Wine 在中国大陆的一个全职开发者。

GSoC 2013 我也参加了,项目是完善我的 GSoC 2012 项目。可惜因为那段时间整个人状态很糟糕而且有实习工作,在期中检查时被刷了下去。不过还是得到了 500 美刀,我后来用这笔钱在 Steam 上买了好多游戏。2014 年则是想要专心做毕设,没有申请。

今年因为学业压力不大,准备再来申请一次 GSoC。报酬加上我的奖学金可以 cover 掉硕士第二年的生活费,也算是(再次)实现经济独立了。本来的计划是申请 Mozilla 下的项目,但连续好几年入选的 Mozilla 今年居然没有入选(Linux Foundation 也是类似的情况)。Google 或许是想要关爱一下更不为人知的开源组织,而牺牲了这些相对不怎么缺钱缺人缺爱的组织。

不过在重新调研之后,我又找到了两个中意的项目,现在已经开始着手“套磁”了。至于是哪两个项目我就暂且保密了,免得你们跟我抢……

SOCIS

另外,我从 Hacker News 这一则关于 GSoC 的讨论中得知,欧洲空间局从 2011 年开始也效仿 Google 组织 Summer of Code,其名为 Summer of Code in Space (SOCIS),赞助和空间科学有关的开源组织。他们对“和空间科学有关”的理解似乎比较宽泛:例如通用科学计算软件 Octave 就入选了去年的 SOCIS。报酬是 4000 欧元,比 GSoC 稍低但也算丰厚了。

今年 SOCIS 的时间滞后 GSoC 不少;例如学生申请截止日期是 4 月 30 日,那时 GSoC 的学生申请结果已经出来了。如果我 GSoC 申请悲剧了的话,就再申请一发 SOCIS。

TU/e 计算机系研究组一览

DISCLAIMER 本文扯淡为主,各种片面,如果读者对 TU/e 计算机系研究确实感兴趣,还请结合官方网站和其他来源以做出自己的判断。

前两天要申请硕士生 honors program,于是结合学校网站上的信息和之前上过的各个组的课程,考察了一下我系的各个研究组。

注一:honors program 是我系硕士生参与科研的一个名目,内容是在系内选两个研究组,每个研究组做半年的项目。本来我是错过了申请 deadline 了的,但是负责协调 honors program 的教授特意发邮件问我为什么没申要不要补申,感激涕零之余就补一发申请了……

注二:“计算机系”的说法其实不严谨的,因为在 TU/e 数学(Wiskunde)和计算机(Informatica)是一个系(W&I)。

考察结果如下:

我申请了形式系统组和算法组(虽然完全不知道要去做什么项目)。安全组黑 Java 和 XML 的醉人氛围我很欣赏,但是对他们的研究完全没有概念,而且有点担心智商是否够用 Orz。

最后吐槽一下自己,老这么先入为主挑肥拣瘦的,不是做科研应该有的态度。果然还是适合硕士毕业找个给法国银行维护 COBOL 代码的工作(少年别自暴自弃啊喂……

Wheelock's Latin Capvt V 笔记

总结

本章主要介绍未完成时和未来时两种时态和 -er 形容词。

未完成体的三种时态、第一第二变位法的未完成体主动语态变位

拉丁语的现在时、未完成时和未来时三种时态合称为未完成体(imperfective aspect),三者都依照现在时词根变位。现在时直接接续人称词尾,未完成时和未来时则先添加时态标志 -bā- 和 -bi- 再添加人称词尾。第一人称单数未完成时和未来时词尾分别为 -bam 和 -bō (< biō*),第三人称复数未来时词尾是 -bunt (< bint*)。

仍然以 laudō/laudāre (第一变位法) 和 moneō/monēre (第二变位法) 为例。未完成时:

未来时:

-er 形容词

有一部分第一/二变格法的形容词的阳性形式(第二变格法)是以 -er 结尾的。这其中一部分在变为另外两种形式时 -er 会变成 -r。例子和反例(列出顺序为阳性/阴性/中性):

词汇

习题解

Exercitātionēs

  1. Officium līberōs virōs semper vocābat. Eng. Duty always called free men.

  2. Habēbimusne multōs virōs et fēminās magnōrum animōrum? Eng. Will we have many men and women with great courage?

  3. Perīcula bellī nōn sunt parva, sed patria tua tē vocābit et agricolae aiuvābunt. Eng: The dangers of the war is not rare, but your country will call you and the farmers will help.

  4. Propter culpās malōrum patria nostra nōn valēbit. Eng: Because of the fault of the bad people our country will not be strong.

  5. Mora animōs nostrōs superābat et remedium nōn habēbāmus. Eng: Procrastination defeated our courage and we had no remedy.

  6. Multī in agrīs heri manēbant et Rōmānōs iuvābant. Eng: Many stayed in the fields yesterday and helped the Romans.

  7. Paucī virī dē cūrā animī cōgitābant. Eng: Few men were thinking about the care for the soul.

  8. Propter īram in culpā estis et crās peonās dabitis. Eng: Because of your anger now you are to blame and you will pay your penalty tomorrow.

  9. Vērum ōtium nōn habēs, vir stulte! Eng: You don't have true peace, stupid man!

  10. Nihil est sine culpā; sumus bonī, sī paucās habēmus. Eng: Nothing is without fault; we are good if we have few.

  11. Poēta amīcae multās rosās, dōna pulchra et bāsia dabat. Eng: The poet gives his girlfriend many roses, lovely gifts and kisses.

  12. Will war and destruction always remain in our land? Lat: Remanēbuntne bellum et exitium semper in patriā nostrā?

  13. Does money satisfy the greedy man? Lat: Satiatne pecūnia virum avarum?

  14. Therefore, you (sg.) will save the reputation of our foolish boys. Lat: Fāmam igitur puerōrum stultōrum nostrōrum servābis.

    // 这句话存疑。不确定 igitur 应置于 fāmam 后(第一个词后)还是 nostrōrum 后(第一个短语后)。

  15. Money and glory were conquering the soul of a good man. Lat: Pecūnia et glōria animum virī bonī superābant.

Sententia Antiquae

  1. Invidiam populī Rōmānī crās nōn sustinēbis. Eng: You will not keep your dislike of Roman people tomorrow.

  2. Perīculumne igitur heri remanēbat? Eng: Does danger remained yesterday then?

  3. Angustus animus pecūniam amat. Eng: Narrow souls love money.

  4. Superā animōs et īram tuam. Eng: Go beyond your pride and ire.

  5. Culpa est mea, Ō amīcī. Eng: Fault is mine, O my friends.

  6. Dā veniam fīliō et fīliābus nostrīs. Eng: Do our son and daughters a favor.

  7. Propter adulēscentiam, fīliī meī, mala vītae nōn vidēbātis. Eng: Because of your young age, my sons, you have not seen bad things of life.

  8. Amābōt tē, cūrā fīliam meam. Eng: Please take care of my daughter.

  9. Vīta hūmāna est supplicium. Eng: Human life is a punishment.

  10. Satisne sānus es? Eng: Are you healthy enough?

  11. Sī quandō satis pecūniae habēbō, tum mē cōnsiliō et philosophiae dabō. Eng: If I ever have enough money, then I will devote myself to wisdom and philosophy.

  12. Semper glōria et fāma tua manēbunt. Eng: Your glory and fame shall remain forever.

  13. Vir bonus et perītus aspera verba poētārum culpābit. Eng: A good and skillful man will blame the harsh words of the poets.

His Only Guest Was a Real Boar!

Nōn cēnat sine aprō noster, Tite, Caeciliānus: bellum convīvam Caeciliānus habet!

Eng: Titus, our Caecilianus does not dine without a boar: Caecilianus has a good guest!

Thermopylae: A Soldier's Humor

“Exercitus noster est magnus,” Persicus inquit, “et propter numerum sagittārum nostrārum caelum nōn vidēbitis!” Tum Lacedaemonius respondet: “In umbrā, igitur, pugnābimus!” Et Leōnidās, rēx Lacedaemoniōrum, exclāmat: “Pugnāte cum animīs, Lacedaemoniī; hodiē apud īnferōs fortasse cēnābimus!”

Eng: “Our army is great,” a Persian says, “and because of the number of our arrows you will not see the sky!” Then a Spartan responds: “Then we shall fight in shadow!” And Leonidas, King of the Spartans, exclaims, “Fight with courage, Spartans; today we will perhaps dine among the dead!”

Wheelock's Latin Capvt IV 笔记

总结

这一章介绍第二变格法中性名词和系动词 sum 的现在时变位、形容词的一些语法现象和无变格名词。

第二变格法中性名词几乎全是 -um 名词,其变格词尾除单复数的主格、宾格和呼格之外,和第二变格法阳性名词等同:

dōnum: dōnum / dōnī / dōnō / dōnum / donō

dōna: dōna / dōnōrum / dōnīs / dōna / donīs

系动词 sum/esse 的现在时变位:

sum/esse: sum / es / est / sumus / estis / sunt

可以比较现代法语系动词 être 的现在时变位:suis / es / est / sommes / êtes / sont。

拉丁语中不光定语形容词,表语形容词也要与主语一致(再次类比法语)。另外,形容词可以名词化。

中性名词 nihil 是无变格名词。无变格名词只能用于单数主格和单数宾格。

习题解

Exercitātiōnēs

  1. Ōtium est bonum, sed ōtium multōrum est parvum. Eng: Leisure is good, but most people enjoy little lesiure.

  2. Bella sunt mala et multa perīcula habent. Eng: Wars are bad and have many dangers.

  3. Officium nautam dē ōtiō hodiē vocat. Eng: Duty now calls the sailor away from leisure.

  4. Paucī virī multās fōrmās perīculī in pecūniā vident - nōn dēbēmus esse avārī! Eng: Few people see the many forms of danger in wealth - we shouldn't be greedy!

  5. Sī multam pecūniam habētis, saepe nōn estis sine cūrīs. Eng: If you have much wealth, you are often not without worries.

  6. Puellae magistram dē cōnsiliō malō sine morā moment. Eng: The girls warns the teacher about the bad plan without delay.

  7. Ō magne poēta, sumus vērī amīcī; mē iuvā, amābō tē! Eng: O great poet, we are true friends; help me, please!

  8. Fēmina et agrōs et portam agricolae videt. Eng: The woman sees the fields and the gate of the farmer.

  9. You (sg.) are in great danger. Lat: In perīculō magnō es.

  10. My son's opinions are often foolish. Lat: Sententiae filiī meī saepe stultae sunt.

  11. The daughters and sons of great men and women are not always great. Lat: Filiae et filiī virōrum magnōrum et feminārum magnārum nōn semper magnī sunt.

  12. Without wisdom the sailors' good fortune is nothing and they are paying the penalty. Lat: Sine sapientiā fortuna bona nautārum nihil est et poēnas dant.

Sententiae Antīqvae

  1. Fortūna caeca est. Eng: Fortune is blind.

  2. Sī perīcula sunt vēra, īnfortūnātus es. Eng: If the danger is real, you are unfortunate.

  3. Salvē, Ō amīce; vir bonus es. Eng: Greetings, my friend; you are a good man.

  4. Nōn bella est fāma fīliī tuī. Eng: The fame of your son is not good.

  5. Errāre est hūmānum. Eng: To err is human.

  6. Nihil est omnīnō beātum. Eng: Nothing is totally fortunate.

  7. Remedium īrae est mora. Eng: The remedy of anger is delay.

  8. Bonus Daphnis, amīcus meus, ōtium et vītam agricolae amat. Eng: Good Daphnis, a frind of mine, loves the leisure and life of the farmer.

  9. Magistrī parvīs puerīs crūstulta et dōna saepe dant. Eng: The teachers often give some boys cookies and gifts.

  10. Amīcam meam magis quam oculōs meōs amō. Eng: I love my girlfriend more than my eyes.

  11. Salvē, mea bella puella - dā mihi multa bāsia, amābō tē! Eng: Farewell, my good girl - give me many kisses, please!

  12. Īnfīnītus est numerus stultōrum. Eng: Infinite is the number of stupid men.

  13. Officium mē vocat. Eng: Duty calls me.

  14. Malī sunt in nostrō numerō et dē exitiō bonōrum virōrum cōgitant. Bonōs adiuvāte; cōnservāte patriam et populum Rōmānum. Eng: There are bad ones among us and they are planning the destruction of the good. Help the good ones; save the land and people of Rome.

The Rarity of Friendship

Paucī virī vērōs amīcōs habent, et paucī sunt dignī. Amīcitia vēra est praeclāra, et omnia praeclāre sunt rāra. Multī virī stultī dē pecūniā sempter cōgitant, paucī dē amīcīs; sed errant: possumus valēre sine multā pecūniā, sed sine amīcitiā nōn valēmus et vīva est nihil.

Eng: Few people have true friends, and few deserve them. True friendship is remarkable, and anything remarkable is rare. Many stupid people always think of wealth, few of friendship; but they are wrong: we can stay strong without much wealth, but without friendship we cannot stay strong and life is nothing.

拾遗

  1. 虽然看上去是阳性名词,virus中性名词。另外,作为一个质料名词,virus 是没有复数的。

  2. 系动词是所有印欧语的一个共同特性