强大的语言[从上下文无关语法到上下文有关语法]

     转载于【强大的语言】www.cnblogs.com/buptzym/p/4828959.html

     我越来越感慨语言之美，语言之强大。

    中文，英文这类自然语言，也可以是C，C#,Python,Lisp这类通用语言，也可能是自己定义的领域特定语言(DSL)。更广泛的可以是音乐和DNA序列。

    语言就是字符串，一组由不同字符串组成的顺序链条。然而，大巧不工，越朴素简单的模式，其能力就越强大。

•     语言代表了知识: E=mc2
•     语言代表了美感: "人生若只如初见,何事秋风悲画扇"
•     语言代表了力量："尔曹身与名俱灭,不废江河万古流"
•     语言代表了智慧： (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else ( (fib (- n 1)) (fib (- n 2)
•     语言代表了模式： aa bb cc aaa bbb ccc…

    语言是艺术品，作为程序员，你应该像对待艺术品一样对待自己的代码，精心雕琢它的结构，优化它的性能，像一首诗一样优美，它是智慧和荣耀的象征。可惜的是，绝大多数人写的代码，连正确都谈不上，更枉提美感！
 

语言分类

    我感慨语言之美，是因为语言的表达能力无穷无尽。结合学习的大量资料和自己的理解，语言可以分成以下几个层级，每个层级都属于其下一个层级。
 

LV1：表格

    最基本的语言，显然是表格，此处亦可代表字典，键值对，列表等等。它只有并结构。一般的条件语句和决策，都可以用表格来表示。
    基本操作：并，分枝，循环
    工具：list,dict
    处理模式：循环，索引访问

    千万别小看表格的表现能力，通常的表格只是承载数据，如果能够承载动作和命令，那么它将极为强大，想想Lisp和S-表达式。
 

LV2：正则语言

    用过正则表达式的程序员都知道正则表达式的强大。但正则表达式无法实现计数和嵌套结构。
    基本操作： 表格的基本操作，序列和差集
    工具：状态机(NFA,DFA)
    处理模式：匹配，模式分析
 

LV3: 上下文无关语言

    因为状态机无法处理嵌套结构，因此引入上下文无关语言。该语言引入堆栈，用以保存信息。但通常在实现中，堆栈是隐含在递归下降过程的递归栈中，而非显式实现。
    基本操作： 正则语言的基本操作，嵌套，递归
    工具：递归下降语法分析
    处理模式：生成句法树，计算
 

LV4：上下文有关语言

    上下文无关语言的各条语句之间是独立的，没有环境和上下文。因此难以保存和传递状态。因而产生了上下文有关语言。
    基本操作：上下文语言的基本操作+引用，赋值
    工具：上下文无关语言的工具+符号表
    处理模式：实现通用语言，图灵完备
 

LV5：自然语言

    以上的那些语言，代表了严格的逻辑和条件，用确定的语义模型表达意图，没有模糊性和动态性。这样的语言是可计算的，也有明确的语义模型代表。
然而，当加入模糊之后，其动态性和功能变得强大的多。典型的就是自然语言，它没有明确的语义模型。现在尚无合适的技术，能够真正透彻的分析自然语言。

 值得注意的是，我们提到了分枝，循环，并，顺序，补，嵌套，递归，存储符号。但依旧没有提到反馈。反馈不属于静态的语言概念，而是运行时的自我调整。

 

LV6：意识和经验

    很多经验和知识，是难以用语言表达的，即使能背诵汽车驾驶指南，如果没有实际的练习，那就是不会开车。别人的经验，即使勉强用语言表达出来，不论表达的多么清晰，依然会大打折扣。可以认为，即使语言相同，而每个人的编译器（大脑）却各自不同，因而产生了完全不同的理解。

   我将意识和经验，看做是运行时的“自然语言”。

 

自然语言

   自然语言用词汇定义语素，用词组和句子表达模糊语义，用模糊的上下文语境代替确定的符号表。模糊产生了美感，能够描述故事，小说，诗歌和各类复杂文本。

 

自然语言的文法

    因为模糊，所以文法在自然语言中变得次要。符合文法的句子很好，但不符合文法的句子照样能很好的工作。文法和词汇都在语言的发展中不断进化。每天都有新的表达出现，改变才是最大的不变。一个有趣的问题是，文法也是一种语言，我们能否发现自然语言在发展过程中文法发展的规律？
 

基本操作

    由于自然语言的模糊性，概率论成了分析自然语言的利器。即便如此，我们能做的也非常有限，通过概率论结合一定的规则，可以实现分词，命名实体识别，词性预测，句法树生成，情感分析，关键词抽取，自动摘要生成… 这些技术只能称为“自然语言处理”，而无法称作“自然语言解析”。
如果语料足够全面，并且能够覆盖一个话题的全部语境，那么我相信纯粹的概率论就能获得最终的胜利。问题是语料的获取和分析非常复杂和昂贵，这可不是从网上抓下一批新闻数据就能办到的。在现阶段，我更相信经验规则和概率论结合的处理方法。
 

可计算性

    自然语言是可计算的吗？ 举个例子：
    如果今天下雨，那么就坐公交下班。 //这是一个典型的的可计算句子。
    买三斤苹果，如果有西瓜，就买三斤西瓜。 //这代表了二义性，没有上下文语境，很难确定真正的策略。
    剩女产生的原因：一是谁都看不上，二是谁都看不上。 //WTF!!
    这还是最普通的例子，诗歌和故事是可计算的吗？这样的计算，结果是什么？

    此处的可计算性和标准概念上的“计算性”可能有所不同。人能理解自然语言就是自然语言可计算的最好证明。 处理自然语言的核心，不是推导，而是联想。大脑具备了将众多概念联系起来的能力，配合推导和学习，最后付诸行动。
 

我们能做什么

    既然自然语言如此神奇，而目前又无法构造一台类似大脑的联想机器，那么如何让处理自然语言走的更远一些呢 ？编程语言在发展过程中，已经出现了非常完善的编译技术。能否将编译技术用在处理自然语言上？

    语言虽然千变万化，但它是有规律的，其语素是稳定的，比如描述“漂亮”的和数字的概念，其表达数量肯定是有限制的。一个再复杂的组合拆分到子单元时，就变得稳定了。因此我们总能通过规则，构造基本单元的表达，比如数字和时间。进而描述单元组合的方式，形成一套规则树结构。

    有些处理，更适合用概率分析，如分词，词性预测和情感分析。

    我的考虑是，通过一组DSL，利用规则和概率，在一定程度上规避自然语言的多样性和歧义性，将文本转换可计算和无歧义的语句，这个过程称为“文本规范化”，作为自然语言的编译器前端，最终送入一般意义上的编程语言编译器。 一切都是模式，子模式组合为父模式，用模式匹配，修改和组装新模式。

    目前正在做这方面的工作，已经取得了不错的进步。目前已经能够计算诸如：
二十七+15*15
十四点五的平方加上八十三除以三点五
 

语言的局限

     语言有强大之处，也有天生的局限。比语言更高层级的是意识和经验。语言本身就像代码，如果不编译执行，那就是一堆没有用的字符串。

    人类的理解问题和传递信息时，语言可能并不是最优的媒介，有时一图胜千言，多媒体的表达能力能够更好的激励联想。实践的价值可能比语言本身重要得多，但把运行时的概念（意识）和编译时的概念（语言）比较，这本来就是不公平的嘛。

   上班一年半了，别人会问我做什么工作，之前这个问题有些难以回答，事实上，我第一年主要做语音合成（TTS）的文本处理前端， 而这半年，对编译原理，文法推断和模式分类感兴趣。这个问题慢慢变得清晰起来，那就是研究“语言”。

    显然这篇文章里有不少错误，我连一本编译原理都没看完呢，欢迎吐槽。之后，我将总结一系列有关DSL的一些知识。