# 1.3 我们的第一个语言 - hi

我们已经介绍了编译的基本概念，还实现了 Source 类。接下来我们将逐步实现自己的第一个编程语言。按照之前介绍的编译器结构，似乎我们应该开始介绍词法解析了，但是词法解析是需要根据语言的语法来进行的，所以还是让我们先了解一下，如何来对编程语言进行描述。

## 扩展巴科斯范式「EBNF, Extended Backus–Naur Form」

我们通过语法「Grammar」来定义我们的编程语言。语法的是由一组规则「Production Rules」组成的，通过这些规则来构成语法。

这些规则由两部分所构成：1). 规则名称 2). 规则内容。比如我们将要实现的语言「称之为 hi」：

```
「say_hi」需要满足: hi 字符串
「字符串」需要满足: " 除了「"」的任意字符 "
```

如果上面的描述看不懂的话，我们来看一下使用我们的 hi 语言书写的程序：

```
hi "lexer"
hi "parser"
hi "compiling"
```

看到了吧，我们的 hi 语言就只有一种类型的语句，通过它你可以 「say hi to everyone」。

在上面的语法中，我们定义了两个规则，分别是「字符串」和「say\_hi」。

对于规则「字符串」而言，它的规则内容为，以「"」开头，接收任意除了「"」的任意字符，直到接收到「"」后结束该规则，在该规则内接收的字符串，都被打包到了我们的「字符串」规则中。

对于规则「say\_hi\」而言，它的规则内容为，以关键字「hi」开头，接下来的内容将必须符合「字符串」规则。

为了更加严谨的描述我们的语法，我们需要使用各种标记语言，而扩展巴科斯范式「EBNF」就是这些标记语言中的其中一种。

通过 EBNF 可以将我们的语法表示为：

```
say_hi = "hi", string ;
string = '"' , { all characters - '"' }, '"' ;
```

可以看出，EBNF 描述规则的表达式为:

```
规则名称 = 终结符和非终结符的组合
```

终结符「Terminal Symbol」就是词法中不能被分解的最小单元，反之为非终结符「Nonterminal Symbol」。比如规则「say\_hi」的右边，`"hi"` 为终结符；而 `string` 则为非终结符，因为它还有与之对应的规则。

EBNF 中使用了如下的符号:

| 符号       | 含义                                        |
| -------- | ----------------------------------------- |
| =        | 定义规则，左边为规则名称，右边为(非)终结符的组合                 |
| ,        | 表示连接位于其左右两边的(非)终结符                        |
| \|       | 表示位于其左右两边的(非)终结符为二选一的关系                   |
| \[ ... ] | 表示方括号中的(非)终结符为可选项，在该位置出现次数为 0 或 1         |
| { ...}   | 表示大括号中的(非)终结符为重复出现的，在该位置出现次数 >= 0         |
| ( ...)   | 表示小括号中的(非)终结符在该位置以组合的形式出现                 |
| " ... "  | 表示终结符                                     |
| ' ... '  | 表示终结符，主要用于需要表示 '"' 的情况                    |
| ( *...*) | 表示注释                                      |
| ?...?    | 表示其中的内容具有特殊含义，对该含义的定义不在 EBNF 标准之内，有使用者来决定 |
| -        | 表示将右边的内容从左边进行排除                           |

我们使用 EBNF 来总结一下 hi 的语法：

```
prog = { say_hi } ;
say_hi = "hi", string ;
string = '"' , { all characters - '"' }, '"' ;
```

我们增加了一条新的规则「prog」作为我们未来进行解析的起始规则。我们的 hi 语言将只包含一条语句「Statement」类型，就是「say\_hi」。

## W3C's EBNF

如果大家通过搜索引擎来检索关键字「EBNF」，那么会发现很多链接中都介绍了上一节的 EBNF 语法。它是由 ISO 制定的。ISO 是一个全球化的组织，制定了很多的标准，其中也就包括了 [ISO/IEC 14977](http://standards.iso.org/ittf/PubliclyAvailableStandards/s026153_ISO_IEC_14977_1996\(E\).zip)，也就是上一小节介绍的 EBNF 标记法。

ISO 制定 EBNF 标准的目的就是为了扩展和统一 [BNF](https://en.wikipedia.org/wiki/Backus–Naur_form) 的使用方法，因为在此之前大家在描述语法的时候，都或多或少的加入了自己的喜好，使之成了 BNF 的方言「Dialect」。

我们好像忘记介绍 BNF 了，没关系，一句话来概括它：就是没有扩展前的 EBNF、功能和 BNF 一样，都是用来描述语法的，缺点就是灵活性不如它的后辈 EBNF。

只是大家对 ISO 制定的 EBNF 标准并不满意，因为它使用起来还是很麻烦，甚至在 ISO 后来的标准制定中涉及语法描述的部分，都没有使用自家制定的「ISO/IEC 14977」。

所以这里我们要介绍由另一个组织 W3C 制定的 EBNF 标记法。W3C 是主要负责万维网标准制定的组织。它定义的 EBNF 标记法被自身和外界广泛使用。它的特点主要是参考了正则表达式「Regular Expression」的语法。接下来我们来一起看一下它的语法。

首先，语法中的每个规则定义一个符号「Symbol」，形式为：

```
symbol ::= expression
```

如果 Symbol 定义词法元素「Token」的话，那么首字母大写；如果是定义语法元素，比如「Statement」或「Expression」的话，那么首字母小写。

我们怎么来确定语法中哪些元素应该视为词法元素还是语法元素呢？简单地说，不能再进行划分的，我可以视为词法元素，比如关键字，字符串，数值，它们在编程语言语法组成中的地位都好比我们自然语言中的单词。而编程语言中类比到人类语言中句型定义的部分，规则名称需要小写，比如定义疑问句的规则，定义陈述句的规则之类。

规则右边的内容，也就是 expression 用来匹配一个或者多个连续的字符。可以出现在右边的表达式的内容具有以下几种形式：

**#xN**

单个字符。N 是一个十六进制数，整个表达式用来表示一个字符，前导的 0 可以省略，也就是说 `\x03` 可以直接写成 `\x3`。具体的数值源于该字符在 Unicode 中的 [code-point](https://github.com/hsiaosiyuan0/icj/tree/8cd8591f0fb2468225c66c0c9c2b2af413f99ec8/part1/code-point.md)。比如，`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 的形式：

```
prog ::= say_hi*
say_hi ::= HI STRING
HI ::= "hi"
STRING ::= '"' [^"]* '"'
```

注意我们将词法元素的规则进行了大写区分。

我们可以将 W3C'S EBNF 转换成对应的语法图「Syntax Diagram 或 Railroad Diagram」:

**prog:**

![](/files/-LgNJa7_kEthRNxpQUtI)

**say\_hi:**

![](/files/-LgNJa7b9gomcqVMZbgr)

**STRING:**

![](/files/-LgNJa7dKZ80rHY0MjtV)

*我们可以使用* [*Railroad Diagram Generator*](https://bottlecaps.de/rr/ui) *来生成这些图。*

我们在看这些图的时候，使用从左往右的方向，以左边的箭头为起点，遇到分支就可以自由的选择不同的分路、除了不能回头，直到到达最右边。

比如第一个图，有两个分支，如果我们在第一个分支处，采取向右直行的分支，那么到达最右端之前，将不会遇到任何的位置匹配，这就表示了我们语法中的零条 `say_hi` 语句的情况。

在比如，如果在第一个分支处，我们选取了经过 `say_hi` 的分支，那么在到达第二个分支处时，表示我们已经匹配了一条 `say_hi` 语句，此时如果我们选择直接向右的路线，那么由于到达了终点，此条轨迹表示我们匹配一条语句的情况。而如果我们选择回到第一条分支的路线，那么则会继续匹配 `say_hi` 语句。

这几种情况的合集，就表示了我们的第一条规则：匹配零条或多条 `say_hi` 语句。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hsiaosiyuan0.gitbook.io/icj/part1/1-3-hi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.