Skip to content

Latest commit

 

History

History
247 lines (166 loc) · 12 KB

05.Languages.md

File metadata and controls

247 lines (166 loc) · 12 KB

第零五章 • 编程语言

什么是编程语言?

编程语言和自然语言非常相似,也有它背后固有的结构和规则来界定语句的正确性。当我们读写自然语言时,语言的规则就在无意中学会了。学习编程语言也是一样,需要长久的读写练习才能掌握。一旦掌握,我们就可以利用这些规则去理解其他人的代码,并写出自己的代码。

在 19 世纪 50 年代,语言学家 Noam Chomsky 定义了一系列关于语言的重要理论。这些理论支撑了我们今天对于语言结构的基本理解。其中重要的一条结论就是:自然语言都是建立在递归和重复的子结构之上的。

举例来说:

The cat walked on the carpet.

根据英语的规则,名词 cat 可以被两个由 and 连接的名词代替:

The cat and dog walked on the carpet.

我们可以像之前一样再次使用这个规则,将 cat 替换为两个使用 and 符号连接的新名词。我们还可以使用另外一个规则,将一个名词替换为一个形容词加一个名词,其中形容词作为对名词的修饰:

The cat and mouse and dog walked on the carpet.

The white cat and black dog walked on the carpet.

以上,我们只是简单的举两个例子。英语的语法规则远不止于此,汉语的语法规则就更复杂了,呵呵。

我们注意到,在编程语言中也有相似的规则。在 C 语言中,if 语句可以包含多条的新语句,新语句当然也可以是另一个 if语句。这些递归和重复的规则在语言的其他部分也同样是适用的。

if (x > 5) { return x; }

if (x > 5) { if (x > 10) { return x; } }

Chomsky 提出的理论是非常重要的。它意味着,虽然一门语言可以表达无限的内容,我们仍然可以使用有限的规则去解析所有用该门语言写就的东西。这些有限的规则就叫语法(grammar)。

对于语法,我们有多种表达方式。最容易想到的方式就是使用白话文。譬如,我们可以这样说:"句子必须是动词短语""动词词组可以是动词,也可以是副词加动词" 等等 ( 译注:事实上,这也是我们最初学习英语语法的主要方式 )。这种形式对于人类来说是非常容易理解的,但是对于计算机却太模糊的、难以理解的。所以在写程序时,我们需要对语法有一个更标准化的描述。

为了定义一门编程语言(例如我们将要编写的 Lisp),我们首先需要能够正确解析用户按照语法规则写就的程序。为此需要编写一个语法解析器,用来判断用户的输入是否合法,并产生解析后的内部表示。内部表示是一种计算机更容易理解的表示形式,有了它,我们后面的解析、求值等工作会变得更加的简单可行。

但是这一部分往往是枯燥繁琐的体力活,我们显然不希望在这上面浪费时间。所以我们就采用了一个叫做 mpc 的库来帮助我们完成工作。

解析器组合子

mpc 是我(原作者)编写的一个解析器组合子(Parser Combinators)库。这意味着,你可以使用这个库为任何语言编写语法解析器。编写语法解析器的方法有很多,使用解析器组合子的好处就在于,它极大地简化了原本枯燥无聊的工作,而仅仅编写高层的抽象语法规则就可以了。

编写语法规则

下面我们来编写一个柴犬语( Doge )的语法解析器以便熟悉 mpc 的用法。

先来看一下 Doge 语言的语法描述:

  • 形容词 (Adjective) 包括 wowmanysosuch 符号。
  • 名词 (Noun) 包括 lisplanguagecbookbuild 符号。
  • 短语 (Phrase) 由形容词 (Adjective) 后接名词 (Noun) 组成。
  • Doge 语言由 0 到多个 短语(Phrase) 组成。

现在我们尝试定义一下形容词和名词,为此我们创建两个解析器,类型是 mpc_parser_t*,然后将解析器存储在 AdjectiveNoun 两个变量中。mpc_or 函数产生一个解析器,它可接受的语句必须是指定语句中的一个。而 mpc_sym 将字符串转化为一个语句。

下面的代码也正如我们上面的描述一样:

/* Build a parser 'Adjective' to recognize descriptions */
mpc_parser_t* Adjective = mpc_or(4, 
  mpc_sym("wow"), mpc_sym("many"),
  mpc_sym("so"),  mpc_sym("such")
);

/* Build a parser 'Noun' to recognize things */
mpc_parser_t* Noun = mpc_or(5,
  mpc_sym("lisp"), mpc_sym("language"),
  mpc_sym("book"),mpc_sym("build"), 
  mpc_sym("c")
);

我怎样才能使用上面的这些 mpc 库提供的函数?

现在先不用担心编译和运行程序的事情,先确保理解背后的理论知识。在下一章中我们将使用使用mpc 实现一个更加接近我们的 Lisp 的语言。

接下来,我们使用已经定义好的解析器 AdjectiveNoun 来定义短语(Phrase)解析器。mpc_and 函数返回的解析器可接受的语句必须是各个语句按照顺序出现。所以我们将先前定义的 AdjectiveNoun 传递给它,表示形容词后面紧跟名词组成短语。mpcf_strfoldfree 指定了各个语句的组织及删除方式,我们可以暂时忽略它们。

mpc_parser_t* Phrase = mpc_and(2, mpcf_strfold, Adjective, Noun, free);

Doge 语言是由 0 到多个短语(Phrase) 组成的。mpc_many 函数表达的正是这种逻辑关系。同样的,我们可以暂时忽略 mpcf_strfold 参数。

mpc_parser_t* Doge = mpc_many(mpcf_strfold, Phrase);

上述语句表明 Doge 可以接受任意多条语句。这也意味着 Doge 语言是无穷的。下面列出了一些符合 Doge 语法的例子:

"wow book such language many lisp"
"so c such build such language"
"many build wow c"
""
"wow lisp wow c many language"
"so c"

我们可以继续使用 mpc 提供的其他函数,一步一步地编写能解析更加复杂的语法的解析器。相应地,随着复杂度的增加,代码的可读性也会越来越差。所以,这种写法其实并不简单。mpc 还提供了一系列的帮助函数来帮助用户更加简单地完成常见的任务,具体的文档说明可以参见项目主页。使用这些函数能够更好更快地构建复杂语言的解析器,并能够提供更加精细地控制。

更加自然的语法规则

mpc 允许我们使用一种更加自然的方式来编写语法规则。我们可以将整个语言的语法规则写在一个长字符串中,而不是使用啰嗦难懂的 C 语句。我们也不再需要关心如何 使用 mpcf_strfold 或是 free 参数组织或删除各个语句。所有的这些工作都是都是自动完成的。

下面,我们使用这个方法重新编写了上面实现过的 Doge 语言:

mpc_parser_t* Adjective = mpc_new("adjective");
mpc_parser_t* Noun      = mpc_new("noun");
mpc_parser_t* Phrase    = mpc_new("phrase");
mpc_parser_t* Doge      = mpc_new("doge");

mpca_lang(MPCA_LANG_DEFAULT,
  "                                           \
    adjective : \"wow\" | \"many\"            \
              |  \"so\" | \"such\";           \
    noun      : \"lisp\" | \"language\"       \
              | \"book\" | \"build\" | \"c\"; \
    phrase    : <adjective> <noun>;           \
    doge      : <phrase>*;                    \
  ",
  Adjective, Noun, Phrase, Doge);

/* Do some parsing here... */

mpc_cleanup(4, Adjective, Noun, Phrase, Doge);

即使你现在暂时不理解上面的长字符串的语法规则,也能明显地感觉到这个方法要比之前的清晰的多。下面就来具体的学习一下其中的某些特殊符号的意义及用法。

注意到,现在定义一个语法规则分为两个步骤:

  1. 使用 mpc_new 函数定义语法规则的名字。
  2. 使用 mpca_lang 函数具体定义这些语法规则。

mpca_lang 函数的第一个参数是操作标记,在这里我们使用默认选项。第二个参数是 C 语言的一个长字符串。这个字符串中定义了具体的语法。它包含一系列的递归规则。每个规则分为两部分,用冒号 : 隔开,冒号左边是规则的名字,右边是规则的定义,使用 ; 表示规则结束。

定义语法规则的一些特殊符号的作用如下:

语法表示 作用
"ab" 要求字符串 ab
'a' 要求字符 a
'a' 'b' 要求先有一个字符 a,后面紧跟一个字符 b
'a'|'b' 要求有字符 a 或字符 b
'a'* 要求有 0 个或多个字符 a
'a'+ 要求有 1 个或多个字符 a
<abba> 要求满足名为 abba 定义的语法规则

似曾相识的感觉?

上面的一些语法规则有没有似曾相识的感觉?你没有猜错,mpca_lang 函数就是用 mpc_manympc_andmpc_or 这些函数来实现的,干净利落,不拖泥带水。

根据表中给出的规则尝试着理解一下上面的代码,看看是不是等价于之前我们前面用代码定义过的语法解析器?

在后面的章节中,我们会使用这个方法来定义我们的语法规则。刚开始可能并不是那么容易理解,但随着时间的推移,我们练习的越来越多,你也将会更加熟悉,并将知道如何创建和编辑自己的语法规则。

本章更加注重的是理论知识,所以在做彩蛋部分时,不要太在意正确性,思考实现的方式才是最重要的。

彩蛋

  • 为 Doge 语言的形容词和名词添加更多的字符串。
  • 为什么在定义语法规则的字符串中," 前面要加 \ 符号?
  • 为什么在定义语法规则的字符串中的每行的结尾要加 \ 符号?
  • 描述诸如 0.0152.221 这种小数的语法规则。
  • 描述诸如https://github.com/ksco 这种 URL 的语法规则。
  • 尝试描述一些简单英语句子的语法规则,例如:the cat sat on the mat
  • 使用更加正式的语言来描述前面三个问题。如 |*+ 等符号语言。
  • 如果你熟悉 JSON,请尝试描述一下它的语法。

参考

{% collapse title="doge_code.c" %}

#include "mpc.h"

int main(int argc, char** argv) {

  /* Build a parser 'Adjective' to recognize descriptions */
  mpc_parser_t* Adjective = mpc_or(4, 
    mpc_sym("wow"), mpc_sym("many"),
    mpc_sym("so"),  mpc_sym("such")
  );

  /* Build a parser 'Noun' to recognize things */
  mpc_parser_t* Noun = mpc_or(5,
    mpc_sym("lisp"), mpc_sym("language"),
    mpc_sym("book"), mpc_sym("build"), 
    mpc_sym("c")
  );
  
  mpc_parser_t* Phrase = mpc_and(2, mpcf_strfold, 
    Adjective, Noun, free);
  
  mpc_parser_t* Doge = mpc_many(mpcf_strfold, Phrase);

  /* Do some parsing here... */
  
  mpc_delete(Doge);
  
  return 0;
  
}

{% endcollapse %}

{% collapse title="doge_grammar.c" %}

#include "mpc.h"

int main(int argc, char** argv) {

  mpc_parser_t* Adjective = mpc_new("adjective");
  mpc_parser_t* Noun      = mpc_new("noun");
  mpc_parser_t* Phrase    = mpc_new("phrase");
  mpc_parser_t* Doge      = mpc_new("doge");

  mpca_lang(MPCA_LANG_DEFAULT,
    "                                           \
      adjective : \"wow\" | \"many\"            \
                |  \"so\" | \"such\";           \
      noun      : \"lisp\" | \"language\"       \
                | \"book\" | \"build\" | \"c\"; \
      phrase    : <adjective> <noun>;           \
      doge      : <phrase>*;                    \
    ",
    Adjective, Noun, Phrase, Doge);

  /* Do some parsing here... */

  mpc_cleanup(4, Adjective, Noun, Phrase, Doge);
  
  return 0;
  
}

{% endcollapse %}