根据乔姆斯基的形式语言理论，无论对象是计算机语言还是自然语言，其语言分析（parsing）的文法需要一个形式系统工具（formalism）表达。这个体系是层级（hierarchical乔姆斯基谱系_百度百科）的，对于语言分析的表现力因此强弱不同，所对应的算法及其自动机也因此具有不同的计算复杂度。这些都是经典到不能再经典的老生常谈了，细节可以看wiki百科或编译理论的教科书。

自然语言parsing中讨论最多的formalisms 是 FSA和CFG，传统的观点虽然足够权威，但大多不得要领。其说法是，FSA 有线性高效算法，用起来也直观（模式匹配而已），但表达力不够。乔姆斯基本人批评说它不适合做自然语言分析，因为FSA从原理上不能涵盖据说是自然语言本性的中心递归（center recursion）结构：这是个似是而非的论点，我们在乔姆斯基批判等博文（见文后《相关》链接）中已经多次论及，这里不再重复。CFG 是传统的短语结构文法派使用最多的工具，由于可以应对递归而倍受青睐，但没有线性实现的算法。白老师根据多年的观察，第一次提出，适合自然语言分析的formalism很可能是个穿越乔姆斯基层级体系内部边界（白老师形象地称作“乔家大院”）的“毛毛虫”。

这是令人耳目一新的新鲜观点，与我几十年的NLP实践体验非常吻合。我把这条我们从导师辈传承火种并坚持摸索30年的毛毛虫叫做 FSA++，因为毛毛虫的基础仍是 FSA但有很多扩展突破。其算法始终没有超出线速的要求，对应的文法也不是单层的大一统，而是很多个小文法叠加（cascade）成一个多层处理的pipeline，可以做到任意层面的分析深度。自然语言 parsing 因此而变得前所未有地灵活和深入。应对自然语言里的递归现象也因此易如反掌。

这是一个自然语言领域的极为重要的议题，可惜的是学术界的统计一面倒使得相关研究和讨论几乎绝迹。

本篇笔记就是一些零星的心得笔记，是多年实践的初步总结，记下来与白老师及同仁分享。NLP后学看不懂没关系，因为教科书和学术论文中少见这一类训练和讨论。不是你的错，and you are not alone，看个热闹或无视可矣。

有一个新发现，关于“毛毛虫”的。其实也不新，只是先前可能熟视无睹，没特别注意这个特点。

在线性模式匹配的 fsa++ 里面，多层的所谓 cascaded 的处理是必要的。因为有些匹配与另外的匹配有某种线性相交，如果同一层处理，往往不可兼得。顾了这头，顾不了那头。

到了 dag（directed acyclic graph）式依存句法树为基础的平面 fsa++，当然仍然可以或应该根据模块化原则分层处理，包括parsing的“休眠唤醒”。 但是对层次是依赖却由于模式的不同减弱了。完全可以在同一层做n个有相交的子树模式匹配。每个模式是从不同角度来的子树规则，各自对付不同的子现象。

无论线性还是平面，编码规则有个minimal nodes 的原则，即规则最小化。最小（必要）还足够（充分）才是好规则，好的语言学概括。只有规则最小化，才可以有效预防规则量的线性组合爆炸，增强parsing的鲁棒性，也增强对现象的覆盖（差全率 recall）。

最小化原则针对规则的个体，是对规则码农而言。与其相对应，规则整体（规则集，or 文法）在编译后执行（running）的时候，则是遵循最大原则，来保证规则之间的优先次序。对于线性模式，就是 longest matching principle（另一个线性原则是，left-to-right principle or right-to-left principle，算是人为规定的 config，根据每一层模块的匹配方向而定。）这些都是清楚明白的，但是到了二维世界，匹配原则就有些模糊了。

Longest principle 的对应物如果是 embedded patterns，当然就是大树吃小树，这个没有疑问，也符合逻辑。但更多的时候其实不是完全的 properly embedded，而是某种相交。这时候，如果毛毛虫的创造者硬性规定某个 quasi-longest principle 也是可以的，譬如相交的一端，比另一端多 n 个节点，超过阈值了，就算它赢。这样做似乎也可能带来一些好处，因为旗鼓相当自然可以算匹配双赢（只要结论不造成逻辑冲突），但是一头沉的情形似乎应该是东风压倒西风才合理。

但实际上，这个火候似乎不好掌握，不妨考虑放开，后果自负，由语言学家自己根据数据制导掌控，而不是从毛毛虫内部控制。当然也有其他的 priority 掌控方式可以实施，此处不细谈。

总结一下，一维毛毛虫成长为二维毛毛虫以后，规则执行层面的制约减弱了，使得规则的适用度增强了。减弱的第一条是，平面世界没有线性左右的区别，因此 left to right 的原则不再适用（入口 node 的原则还可以有很多说法或 config，此处不提）。减弱的第二条就是，longest principle 只遮盖很少的 proper 子树的情况。

这个转变带来的好处就是，结构层面的规则在最小化以后，可以全面开花地同时作用于数据结构，实施休眠唤醒，减叶加枝，parsing patching 或 IE 抽取等工作。

其副作用还有待更多的实践和总结。

【相关】

[转载]【白硕 - 穿越乔家大院寻找“毛毛虫”】

【泥沙龙笔记：NLP 专门语言是规则系统的斧头】

 乔姆斯基批判

乔姆斯基谱系_百度百科

 语言创造简史

智元：理论家的围墙和工程师的私货】 

【新智元笔记：李白对话录 - RNN 与语言学算法】

【立委科普：结构歧义的休眠唤醒演义】

【置顶：立委科学网博客NLP博文一览（定期更新版）】 

 《朝华午拾》总目录