[翻译]编译器(5)-语言规格说明书

原文在此
————翻译分隔线————

编译器(5)-语言规格说明书

第一部分:介绍
第二部分:编译、转译和解释
第三部分:编译器设计概览
第四部分:语言设计概述

这是最后一部分关于 Calc 的设计规格!

设计语言

我希望尽量让语言保持简单。我管这个语言叫 Calc。很明了,就是用于计算器(calculator)。聪明吗,聪明吗?好,嗯,继续!

我还希望有一个单一的基础类型。我决定做一些与这个语言名字一样聪明的事情,就叫它 Integer(整数)。我知道,聪明绝顶。你的赞赏将被载入史册。为了简单期间,我决定避免处理浮点数,以及二进制、八进制、十六进制还有科学计数法。我将添加其他计数方式作为练习留给你。

我们还需要表示文件结尾、注释和数学符号。

在开始解析和执行我们的语言之前,还有一个需要确定的基本内容是运算符优先级和封装方式。祝福也好,诅咒也罢,这次我决定不在运算符优先级上把事情搞砸了。所以我决定使用预定义的符号和 Lisp 样式的表达式。也就是说运算符将在参数前,并由左右括号封装。二加三的例子如下:

例子 1 (简单表达式):

(+ 2 3)
Result: 5

这样有两个好处:1)明确了运算符优先级;以及,2)我们可以让运算符处理任意值的数字。

例子 2 (运算符优先级):

(* (+ 3 1) (/ 4 2))
Result: 8

这里没有什么运算符以什么样的顺序执行的问题。在计算乘法之前,加法和除法是分别进行计算的。没有算术运算符优先级(BEDMAS)!

例子 3 (多值):

(* 1 2 3 4 5)
Result: 120

在这个情况下,我们对表达式的每个元素从左到右的进行处理。所以也可以将这个函数用下面的等价的形式编写:

(*5(*4(*3(*2 1)))) == ((((1*2)*3)*4)*5) == 1*2*3*4*5

因此,我们需要定义左右(开闭)括号的标识符,和每个想要使用的数学符号。

最后,还应当具有注释。我们将仅增加单行注释,不过多行应该也不会很难添加。让我们使用一个分号来表示一段注释吧。

所需要用到的标识符

  • 左括号
  • 右括号
  • 加号
  • 减号
  • 乘号
  • 除号(商)
  • 取模(余)
  • 整数
  • 分号(注释)

这就是开始词法分析前所需要的所有的东西了。有心人应当已经留意到,我并未对任何关键字、内建函数或变量定义标识符。因为我们简单的语言并未有任何这些东西。

这一系列最初的目的并不是教你设计一个图灵完备的,功能完整的编程语言。核心目的只是提供一些基础的计数来编写一个初级的、可以工作的编译器。

在系列接下来的内容中,我会描述如何添加这些特性。

空白字符

接下来要决定的事情就是如何处理空白字符。在像 Lisp 或 Go 这样的语言中,空白字符通常被忽略。我说通常是因为并不是完全被忽略。字符串和注释不会忽略空白字符。同时也被用于间隔例如数字这样的元素。然而,从被忽略就能看出它对于一个语言的语法或者语句来说并不是十分的重要。

顺便说一下,空白字符通常是空格、tab 或换行。在 Windows 上,你还应当包括回车等等。基本上,任何能通过键盘输入的不直接显示出来的字符都算是。

当前来说,你的语言也可以将空白字符纳入考虑之中。例如在 Python 中,它们就非常重要,作为语句的标示分隔。Calc 不会这样做。

语法

我们已经列出了代码中将含有的所有元素。现在需要给它们赋予各自的含义。

由于想要用于表达数学方程。我们对语言中的表达式给与了巨大的关注。但是没有涉及语句(一个糟糕的笑话,我希望有人能看懂)。

每个表达式必须在括号之间,从运算符开始,并且需要两个或两个以上的运算对象。一个例子:

“(“ operator operand1 operand2 [… [operandN]] “)”

我将括号放在引号内来表示他们是文本,是必须的元素,而不是可扩展的语言规则。运算符和两个运算对象也是必须的元素。方括号表示额外的运算符是可选的。

我们的运算符可以是什么?它们只能是以下符号之一:+ – * / %

那么运算对象又如何呢?好吧,现在事情开始变得有趣起来,不过我觉得咱们可以处理得了。运算对象可以是数字或表达式。这样允许我们通过表达式的嵌套来进行复杂的计算。

我更喜欢用另外一种形式来表达语法。这是一种用于定义某些事情的,叫做上下文无关语法。这种特殊的形式与传统的巴科斯—诺尔表达式(BNF)不同。用这种记号法,可以让我们的语言表达为这样:

file ::= expr
expr ::= “(“ operator whitespace expr (whitespace expr)+ ”)” | integer
operator ::= [+-*/%]
whitespace ::= [ \t\n\r]+
integer ::= digit+
digit ::= [0-9]

我并不是上下文无关语法的专家,所以希望我没有把它搞错。如同你已经看到的那样,它把上面的所需要的清单表达得相当简洁,也会让我们的解析器设计起来更加容易。

后记

我们的语言非常简单,不过在语法的帮助下,我们期望会更加清晰。并且编写扫描器和解析器会更加容易。

例如整数的定义,我们需要扫描什么一目了然。我们需要扫描一位或者多位从零到九的数字。对于空白符号也是一样,只要有一个或者多个空格、tab 或换行。

这样我们就知道了实际上该解析什么。程序是由一个表达式组成。每个表达式都包裹在括号内,并且表达式的第二个元素一定是一个运算符。运算对象可以是表达式或数字。至少需要两个运算对象。

Join the Conversation

3 Comments

  1. 弱弱的问句,那个关于表达式和语句的笑话是什么?笑点在于表达式和语句的区别么?

Leave a comment

Your email address will not be published. Required fields are marked *