在Swift中实现编程语言-第2部分：语法-设计我们的第一语言
这是“用Swift编写编程语言”教程系列的第二部分。请务必阅读 第1部分 。
如本系列的介绍中所述，我们将首先创建尽可能最小的“实用”解释器之一，即我们自己的计算器，仅包括数字*，/，+和-。
不够激动？
不用担心，因为稍后，我们将把它用作我们自己的编程语言的基础。
为什么我们关心语法？
在接下来的教程中，我们实际上将使用3个核心模块来实现我们的解释器，每个模块都在自己的教程中。
词法分析器 ：执行词法分析。 这是关于将输入的字符串转换为令牌列表，令牌的信息结构比简单的字符或单词还丰富。
解析：关于将令牌转换为称为抽象语法树的树结构。
主要功能（解释过程）：该函数使用我们的Lexer和Parser创建抽象语法树 ，然后通过遍历它来“解释”输出。
在执行之前，我提到的所有步骤都不需要正式的语法。 但是我还是出于某种原因决定将本章包括在语法中：
- 当我学习计算机科学时，我发现关于形式语言的教科书很少能轻松地解释语法。 对我来说，他们对这个问题有太多的满足感，这反过来又使这个概念过于艰巨。 维基百科也是如此。
- 实际上，可以使用OysterKit和ANTLR4等工具从语法（半）自动生成前两个步骤（Lexer和Parser）的高度优化的实现。 因此，我发现有必要在我们开始手动实现此功能之前引入这些选项（不过，请保证，我发誓我会使其易于理解）。
“上下文”一词并没有太多上下文
在实现我们的计算器之前，毋庸置疑，我们必须从设计语言的结构开始。
为此，我们将为我们的语言创建上下文无关的语法 。
上下文无关的语法是一组生产规则，它们以给定的形式语言描述所有可能的字符串。 生产规则是简单的替代。 例如，规则
A⇒α
用α代替A
（维基百科）
现在是一些定义的时候了：
非终结符是可以用其他符号代替的符号，例如“α”。但是，如果“A⇒α”是我们唯一的规则，则这意味着“α”无法用某些东西代替其他。 因此，它是一个终端符号。
但是，“上下文无关”到底是什么意思？
所谓“上下文”，是指符号在文本中出现的位置。 更具体地说，在特定符号之前或之后的符号。
可以根据上下文将语法分为两类：上下文无关和鼓声…上下文相关。
我发现区分两者的最佳方法是简单地比较两个示例。 每种类型一个。
请考虑以下两个语法：
:: = 0 1 | 01
和…
:: = 0 1
:: = 0 |
:: = 1
前者是上下文无关的 。 在之前或之后没有非终结 。 只需将其替换为01或01 。
是被0取代， 被1取代？ 还是唯一被替换为01那个？
两者都是正确的，但是我们通常解释该规则的方式与第二种选择相距不远：
因此，您可以看到之前的 上下文必须申请将替换为01 。 它是上下文相关的。
不要担心尖括号（ ）。 这种特殊字符的使用使许多人感到恐惧。 但我保证，这很简单。
， ::=和|的用法 我们称之为Backus-Naur形式（BNF）。 但是，不要让这个花哨的名字欺骗了您，解释说它几乎比名字本身少用几个字符。
只是写正式语法的一种符号。 代替：
A⇒0
A⇒AB
我们说：
:: = 0 |
在BNF中，我们使用::=来分隔要用替换符号替换的符号，在非终端周围可以看到尖括号，并且该位置都存在，因此我们可以看到终端与非终端之间的差异。
如果我们不这样做，将很难看到A是否被端子“ A”和“ B”或非端子A和B代替。
然后，我们还用|分隔右侧选项| 符号，因此我们可以在同一行中容纳多个规则。 真的就是全部。
我们语言的语法
对于我们的语言，主要的非结尾将是数字和运算符。 此外，我们将有一个称为E （用于表达式）的递归非终结符，以说明我们的语言是无限的（包含无限的字符串集）这一事实。
:: = | | （）
:: = + |-| * | /
:: = <十进制>。 |
:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
注意： 该语法实际上包含了诸如“ 000001234”之类的数字，我们将不支持该数字，但我发现这使语法对新手来说不那么让人不知所措。
现在，让我们尝试通过使用语法来验证以下代码来形象化我们的语言：
2 *（1 + 3）
我们语法的决策树如下所示：
E =数字运算符E
数字=小数
小数= 2
运算子= *
E =（E）
E =数字运算符E
数字=小数
小数= 1
运算子= +
E =数字
数字=小数
小数= 3
这是更漂亮的ASCII艺术表现形式：
*
/ \
2（+）
/ | \
1 + 3
扰流板警报； 从技术上讲，您现在可以查看我们的语法，并且可以通过查看我们的语法看到关于如何实现语言的重要提示。
在我们的语法中， 的定义之一是 而不是 。 我们这样做是为了消除语言中的左递归，这是因为我们将在本教程中使用的解析方法（递归体面解析）不支持左递归。 但是，在以后的教程中会更多地介绍这一点。
从这往哪儿走
如上所述，学习如何定义编程语言的语法实际上是生成完全优化的解析器所需的全部。 这就是为什么我强烈建议您研究解析器生成工具的原因。
实现解析器后，我可能会写一篇有关如何使用这些工具的教程，但是已经有很多资料了。
也有很多工具，但是唯一与Swift相关的工具是OysterKit和ANTLR4。 OysterKit是纯Swift，但它是全新的，并且没有经过严格测试，因此我建议改用ANTLR4。
尽管ANTLR已有近30年的历史，但有关如何使用ANTLR的书籍很少。 这并不是因为不受欢迎，ANTLR被广泛使用。 只是计算机科学教授（Terrence Parr）写了一本书非常成功地解释了如何使用ANTLR，没有人敢与它竞争：
权威的ANTLR 4参考：构建领域特定的语言（实用程序）
—会员链接（请参阅本文的页脚）
接下来：最后一些Swift！
如果我们在本教程的开头查看TODO列表，就会发现Lexer执行了Parser和Main函数所依赖的核心功能。 因此，自然而然地，这将是第一件事。 接下来，Lexer。 是! 最后是一些Swift。
敬请关注！
PS随时在Twitter（valdi101）上或在Medium上随时关注我，以获取有关将来教程的通知和讨论。