1.3 我们的第一个语言 - hi
我们已经介绍了编译的基本概念，还实现了 Source 类。接下来我们将逐步实现自己的第一个编程语言。按照之前介绍的编译器结构，似乎我们应该开始介绍词法解析了，但是词法解析是需要根据语言的语法来进行的，所以还是让我们先了解一下，如何来对编程语言进行描述。
扩展巴科斯范式「EBNF, Extended Backus–Naur Form」
我们通过语法「Grammar」来定义我们的编程语言。语法的是由一组规则「Production Rules」组成的，通过这些规则来构成语法。
这些规则由两部分所构成：1). 规则名称 2). 规则内容。比如我们将要实现的语言「称之为 hi」：
如果上面的描述看不懂的话，我们来看一下使用我们的 hi 语言书写的程序：
看到了吧，我们的 hi 语言就只有一种类型的语句，通过它你可以 「say hi to everyone」。
在上面的语法中，我们定义了两个规则，分别是「字符串」和「say_hi」。
对于规则「字符串」而言，它的规则内容为，以「"」开头，接收任意除了「"」的任意字符，直到接收到「"」后结束该规则，在该规则内接收的字符串，都被打包到了我们的「字符串」规则中。
对于规则「say_hi\」而言，它的规则内容为，以关键字「hi」开头，接下来的内容将必须符合「字符串」规则。
为了更加严谨的描述我们的语法，我们需要使用各种标记语言，而扩展巴科斯范式「EBNF」就是这些标记语言中的其中一种。
通过 EBNF 可以将我们的语法表示为：
可以看出，EBNF 描述规则的表达式为:
终结符「Terminal Symbol」就是词法中不能被分解的最小单元，反之为非终结符「Nonterminal Symbol」。比如规则「say_hi」的右边，"hi" 为终结符；而 string 则为非终结符，因为它还有与之对应的规则。
EBNF 中使用了如下的符号:
我们使用 EBNF 来总结一下 hi 的语法：
我们增加了一条新的规则「prog」作为我们未来进行解析的起始规则。我们的 hi 语言将只包含一条语句「Statement」类型，就是「say_hi」。
W3C's EBNF
如果大家通过搜索引擎来检索关键字「EBNF」，那么会发现很多链接中都介绍了上一节的 EBNF 语法。它是由 ISO 制定的。ISO 是一个全球化的组织，制定了很多的标准，其中也就包括了 ISO/IEC 14977，也就是上一小节介绍的 EBNF 标记法。
ISO 制定 EBNF 标准的目的就是为了扩展和统一 BNF 的使用方法，因为在此之前大家在描述语法的时候，都或多或少的加入了自己的喜好，使之成了 BNF 的方言「Dialect」。
我们好像忘记介绍 BNF 了，没关系，一句话来概括它：就是没有扩展前的 EBNF、功能和 BNF 一样，都是用来描述语法的，缺点就是灵活性不如它的后辈 EBNF。
只是大家对 ISO 制定的 EBNF 标准并不满意，因为它使用起来还是很麻烦，甚至在 ISO 后来的标准制定中涉及语法描述的部分，都没有使用自家制定的「ISO/IEC 14977」。
所以这里我们要介绍由另一个组织 W3C 制定的 EBNF 标记法。W3C 是主要负责万维网标准制定的组织。它定义的 EBNF 标记法被自身和外界广泛使用。它的特点主要是参考了正则表达式「Regular Expression」的语法。接下来我们来一起看一下它的语法。
首先，语法中的每个规则定义一个符号「Symbol」，形式为：
如果 Symbol 定义词法元素「Token」的话，那么首字母大写；如果是定义语法元素，比如「Statement」或「Expression」的话，那么首字母小写。
我们怎么来确定语法中哪些元素应该视为词法元素还是语法元素呢？简单地说，不能再进行划分的，我可以视为词法元素，比如关键字，字符串，数值，它们在编程语言语法组成中的地位都好比我们自然语言中的单词。而编程语言中类比到人类语言中句型定义的部分，规则名称需要小写，比如定义疑问句的规则，定义陈述句的规则之类。
规则右边的内容，也就是 expression 用来匹配一个或者多个连续的字符。可以出现在右边的表达式的内容具有以下几种形式：
#xN
单个字符。N 是一个十六进制数，整个表达式用来表示一个字符，前导的 0 可以省略，也就是说 \x03 可以直接写成 \x3。具体的数值源于该字符在 Unicode 中的 code-point。比如，a 的 code-point 为 0x61，那么可以使用 #x61 来表示字符 a
[a-zA-Z], [#xN-#xN]
字符区间。表示匹配位于该区间内的任意字符，包含区间的其实和结束字符在内。比如 [a-z] 表示匹配所有位于 a 之间的字符 z，包括 a 和 z。如果直接写成 [\x0-\xff] 的话，那么数值形式的区间很好理解；如果是字符形式的区间，则可以理解成先将起始和结束的字符转换成它们对应的 code-point，然后取 code-point 对应的数值区间。
[abc], [#xN#xN#xN]
字符枚举。表示接下来出现的字符列举在方括号内，可以和「字符区间」写在同一个方括号内。
[^a-z], [^#xN-#xN]
字符区间排除。表示接下来的字符不处于区间之内。
[^abc], [^#xN#xN#xN]
字符枚举排除。表示接下来的字符不处于枚举之列，也可以和「字符区间排除」写在同一个方括号内。
"string"
匹配双引号中的字符。
'string'
匹配单引号中的字符。
(expression)
括号中的表达式被划定为一个分组。
A?
表示 A 出现的次数为 0 或者 1。
A B
表示 A 后面紧接着 B。这个操作的优先级高于符号为 | 的交替操作，比如 A B | C D 等同于 (A B) | (C D)
A | B
表示 A 或者 B 交替出现于该位置，即该位置出现的内容需要满足非 A 即 B
A+
表示一个或者多个连续出现的 A。该操作具有比符号为 | 的交替操作更高的优先级，比如 A+ | B+ 等同于 (A+) | (B+)
A*
表示零个或者多个连续出现的 A。该操作具有比交替操作更高的优先级。
/*... */
表示注释。
所以我们可以将 sayHi 的语法写成 W3C'S EBNF 的形式：
注意我们将词法元素的规则进行了大写区分。
我们可以将 W3C'S EBNF 转换成对应的语法图「Syntax Diagram 或 Railroad Diagram」:
prog:
say_hi:
STRING:
我们可以使用 Railroad Diagram Generator 来生成这些图。
我们在看这些图的时候，使用从左往右的方向，以左边的箭头为起点，遇到分支就可以自由的选择不同的分路、除了不能回头，直到到达最右边。
比如第一个图，有两个分支，如果我们在第一个分支处，采取向右直行的分支，那么到达最右端之前，将不会遇到任何的位置匹配，这就表示了我们语法中的零条 say_hi 语句的情况。
在比如，如果在第一个分支处，我们选取了经过 say_hi 的分支，那么在到达第二个分支处时，表示我们已经匹配了一条 say_hi 语句，此时如果我们选择直接向右的路线，那么由于到达了终点，此条轨迹表示我们匹配一条语句的情况。而如果我们选择回到第一条分支的路线，那么则会继续匹配 say_hi 语句。
这几种情况的合集，就表示了我们的第一条规则：匹配零条或多条 say_hi 语句。
Last updated
