作者都是各自领域经过审查的专家,并撰写他们有经验的主题. 我们所有的内容都经过同行评审,并由同一领域的Toptal专家验证.
在本系列中,我们将开发一种新的脚本语言,并逐步描述该过程.
任何好奇的读者的第一个问题可能是: “我们真的需要一种新的编程语言吗?”
为了回答这个问题,我允许自己跑题.
假设你是一个建筑师(一个真正的实体建筑师), 不是软件的问题), 你很不幸地出生在一个非常官僚的国家. 你有一个在你欠发达的家乡建购物中心的好主意, 所以你创建了这个项目,并申请了建筑许可证. 当然,他们会立即拒绝你,理由是你没有注册公司. 你注册了一家公司. 为了做到这一点,你需要存一些钱. 然后,你为你的公司想出了一个名字,但被拒绝了. 在你第五次尝试时,它被接受了,你的申请就会被扔到堆的底部. 最终,你要么放弃,要么意识到别人在此期间建了一个购物中心.
但我们不是真正的建筑师. We are 软件工程师我们有把我们的想法变成现实的特权,没有许可,也没有官僚主义. 我们唯一需要的是空闲时间,以及将其用于编程而不是数独游戏的意愿.
如果你仍然坚持编程的动机不可能是纯粹的好奇心, 我先提一下 编程语言 我设计的东西是出于需要,而不仅仅是出于好奇. 然而,这不应该是阅读这篇博客的首要动机. 我认为,即使您实际上不需要创建自己的编程语言,您也会在这里遇到许多非常有趣和创新的想法,以保持您的兴趣.
Our goal of developing a small-footprint scripting language inspired me to name it “Stork”; and luckily, 我们不需要说服任何官僚批准这个名字.
在本系列课程中,我将开发编程语言, 所以我也有可能开发出一些bug. 随着剧集接近尾声,这些问题应该会得到解决.
这里描述的所有内容的完整源代码都是免费的 GitHub.
Finally, 从这一段的标题来回答这个问题, 我们实际上并不需要一种新的编程语言, 但是因为我们要演示如何用c++编写一门编程语言, 我们将创建一个用于演示目的.
我不知道其他程序员是否经常面临同样的问题, 但我经常遇到这个问题:
我需要一个键值容器,应该检索值快,在对数时间. 然而,一旦我初始化了容器,我就不想给它添加新值了. Therefore, std::map
(or std::unordered_map
)是多余的,因为它也允许快速插入.
我完全反对不必要的优化, 但是在这种情况下, 我觉得很多记忆都是白白浪费的. 不仅如此,稍后我们还需要实现 maximal munch 算法在这样的容器之上,并且 map
这不是最好的容器吗.
第二个选择是 std::vector
,插入后排序. 这种方法的唯一问题是代码的可读性较差,因为我们需要记住向量是排序的, 所以我开发了一个小班来保证这个约束.
(所有函数、类等. 在名称空间中声明的 stork
. 为了可读性,我将省略该名称空间.)
template
类查找{
public:
using value_type = std::pair;
using container_type = std::vector;
private:
container_type _container;
public:
使用iterator = typename container_type::const_iterator;
使用const_iterator = iterator;
lookup(std::initializer_list init) :
_container (init)
{
排序(_container std::.开始(),_container.end());
}
查找(container_type container):
_container (std::移动(容器))
{
排序(_container std::.开始(),_container.end());
}
Const_iterator begin()
返回_container.begin();
}
Const_iterator end()
返回_container.end();
}
template
const_iterator find(const K .& key) const {
Const_iterator = std::lower_bound(
begin(),
end(),
key,
[] (const value_type& p, const K& key) {
return p.first < key;
}
);
return it != end() && it->first == key ? it : end();
}
size() const {
返回_container.size();
}
};
正如您所看到的,这个类的实现非常简单. 我不想实现所有可能的方法,只实现我们需要的那些. 底层容器是 vector
,因此可以使用预填充的 vector
, or with initializer_list
.
标记器将从输入流中读取字符. 在项目的这个阶段, 我很难决定输入流是什么, so I will use std::function
instead.
using get_character = std::function;
我将使用c风格流函数中众所周知的约定,例如 getc
,它返回 int
instead of char
以及一个表示文件结束的负数.
However, 提前读几个字真的很方便, 在标记器中假设标记类型之前. 为此,我实现了一个允许我们取消读取某些字符的流.
类push_back_stream {
private:
const get_character& _input;
std::stack _stack;
size_t _line_number;
size_t _char_index;
public:
push_back_stream (const get_character& input);
int运营商()();
Void push_back(int c);
line_number() const;
Size_t char_index();
};
为了节省空间,我将省略实现细节,您可以在我的 GitHub page.
如你所见, push_back_stream
初始化方法 get_character
function. 的重载 operator()
用于检索下一个字符,而 push_back
用于将字符返回到流中. line_number
and char_number
便利方法是否用于错误报告.
记住这一点 char_index
is not the index of the character in the current line but overall; otherwise, 我们必须将所有过去的字符保存在某个容器中以实现 push_back
功能正确.
标记器是最底层的编译器组件. 它必须读取输入并“吐出”令牌. 我们感兴趣的代币有四种类型:
我们对评论不感兴趣,所以标记器只会“吃掉”它们,而不会通知任何人.
为了确保这种语言的吸引力和全球普及,我们将使用众所周知的类c语法. 这对C来说非常有效, C++, JavaScript, Java, C#, 和objective - c, 所以它一定也适用于鹳鸟. 如果你需要复习课程,你可以参考我们之前的一篇文章 C/ c++学习资源.
以下是保留令牌枚举:
Enum struct reserved_token {
inc,
dec,
add,
sub,
concat,
mul,
div,
idiv,
mod,
bitwise_not,
bitwise_and,
bitwise_or,
bitwise_xor,
shiftl,
shiftr,
assign,
add_assign,
sub_assign,
concat_assign,
mul_assign,
div_assign,
idiv_assign,
mod_assign,
and_assign,
or_assign,
xor_assign,
shiftl_assign,
shiftr_assign,
logical_not,
logical_and,
logical_or,
eq,
ne,
lt,
gt,
le,
ge,
question,
colon,
comma,
semicolon,
open_round,
close_round,
open_curly,
close_curly,
open_square,
close_square,
kw_if,
kw_else,
kw_elif,
kw_switch,
kw_case,
kw_default,
kw_for,
kw_while,
kw_do,
kw_break,
kw_continue,
kw_return,
kw_var,
kw_fun,
kw_void,
kw_number,
kw_string,
};
以“kw_”为前缀的枚举成员是关键字. 我必须给它们加上前缀,因为它们通常与c++关键字相同. 没有前缀的是操作符.
它们几乎都遵循C惯例. 没有的是:
-concat
and concat_assign
(..
and ..=
),它将用于连接
- idiv
and idiv_assign
(\
and \=
),它将用于整数除法
- kw_var
对于变量声明
- kw_fun
For函数声明
- kw_number
对于数字变量
- kw_string
对于字符串变量
我们将根据需要添加其他关键字.
有一个新的关键字值得描述: kw_elif
. 我坚信单语句块(没有花括号)是不值得的. 我不使用它们(我不觉得有什么遗漏),除了两种情况:
for
, while
, or if
语句. If I am lucky, 它返回编译时错误, but sometimes, 它会产生一个虚拟的if语句和一个始终执行的块. 幸运的是,多年来,我从错误中吸取了教训,所以这种情况很少发生. Pavlov’s dog 最后也学会了.else if
, that’s an else
块中只有一个语句,即if语句.Therefore, elif
可以用来完全消除无括号语句吗. 我们是否允许它是一个可以等待的决定.
有两个辅助函数返回保留令牌:
std::optional get_keyword(std::string_view word);
std::optional get_operator(push_back_stream& stream);
The function get_keyword
从传递的单词返回可选关键字. 这个“单词”是一个字母序列, digits, 和下划线, 以字母或下划线开头. 它将返回 reserved_token
如果这个词是关键字. 否则,标记器将假定它是一个标识符.
The function get_operator
是试图读取尽可能多的字符,只要序列是一个有效的操作符. 如果它读得更多, 它将取消读取在最长识别操作符之后读取的所有额外字符.
为了有效地实现这两个函数,我们需要在两者之间进行两次查找 string_view
and reserved_keyword
.
const lookup operator_token_map {
{“+ +”,reserved_token:: . n:行情)},
{"——",reserved_token:: 12月},
{“+”,reserved_token::添加},
{“-”,reserved_token:子},
{"..”,reserved_token:: concat},
/*更多激动人心的运算符*/
};
const lookup keyword_token_map {
{“如果”,reserved_token:: kw_if},
{“其他”,reserved_token:: kw_else},
{elif, reserved_token:: kw_elif},
{“开关”,reserved_token:: kw_switch},
{“案例”,reserved_token:: kw_case},
{“默认”,reserved_token: kw_default},
{“为”,reserved_token:: kw_for},
{“虽然”,reserved_token:: kw_while},
{“做”,reserved_token:: kw_do},
{“打破”,reserved_token:: kw_break},
{“继续”,reserved_token:: kw_continue},
{“回归”,reserved_token: kw_return},
{“var”,reserved_token:: kw_var},
{“有趣”,reserved_token:: kw_fun},
{“空白”,reserved_token:: kw_void},
{number, reserved_token: kw_number},
{“字符串”,reserved_token:: kw_string}
};
The get_keyword
实现是完全直接的,但是对于 get_operator
, 我们需要一个自定义比较器,将给定字符与候选操作符进行比较, 只考虑第n个字符.
类maximal_munch_comparator {
private:
size_t _idx;
public:
Maximal_munch_comparator (size_idx):
_idx(idx)
{
}
Bool操作符()(char 1, char r) const {
return l < r;
}
bool运营商()(
std::pair l,
char r
) const {
return l.first.size() <= _idx || l.first[_idx] < r;
}
bool运营商()(
char l,
std::pair r
) const {
return r.first.size() > _idx && l < r.first[_idx];
}
bool运营商()(
std::pair l,
std::pair r
) const {
return r.first.size() > _idx &&
(
l.first.size() < _idx ||
l.first[_idx] < r.first[_idx]
);
}
};
这是一个普通的词汇比较器,它只考虑位置上的字符 idx
,但如果字符串较短,则将其视为在位置上有空字符 idx
,这比任何其他字符都要小.
这是实现的 get_operator
,这应该使 maximal_munch_operator
类更清晰:
std::optional get_operator(push_back_stream& stream) {
Auto candidate = std::make_pair(
operator_token_map.begin(),
operator_token_map.end()
);
std::optional ret;
match_size = 0;
std::stack chars;
for (size_t idx = 0; candidates.first != candidates.second; ++idx) {
chars.推动(流());
候选人= std::equal_range(
candidates.first,
candidates.second,
char(chars.top()),
maximal_munch_comparator (idx)
);
if (
candidates.first != candidates.second && candidates.first->first.Size () == idx + 1
) {
Match_size = 0 + 1;
Ret =候选人.first->second;
}
}
while (chars.size() > match_size) {
stream.push_back方法(字符.top());
chars.pop();
}
return ret;
}
基本上,我们在开始时将所有操作符视为候选操作符. 然后,我们逐个字符读取,并通过调用筛选当前的候选人 equal_range
,只比较第n个字符. 我们不需要比较前面的字符,因为它们已经比较过了, 我们不想比较后面的字符,因为它们仍然是不相关的.
当范围非空时, 检查范围内的第一个元素是否不再有字符(如果存在这样的元素), 在对查找进行排序时,它总是位于范围的开头). 在这种情况下,我们匹配了一个合法操作符. 最长的此类操作符是返回的操作符. 在那之后,我们会取消读所有的字符.
由于令牌是异构的,因此令牌是一个方便的类,用于包装 std::variant
不同的令牌类型,即:
class token {
private:
using token_value = std::variant;
token_value _value;
size_t _line_number;
size_t _char_index;
public:
Token (token_value value, size_t line_number, size_t char_index);
Bool is_reserved_token() const;
Bool is_identifier() const;
Bool is_number() const;
Bool is_string() const;
Bool is_eof() const;
get_reserved_token() const;
Std::string_view get_identifier()
Double get_number() const;
Std::string_view get_string()
get_line_number() const;
get_char_index();
};
The identifier
是否只是一个类的单个成员 std::string
type. 它的存在是为了方便,在我看来, std::variant
如果所有的替代品都是不同的类型,是否更清洁.
现在,我们可以编写标记器了. 这将是一个可以接受的函数 push_back_stream
并返回下一个令牌.
诀窍是使用不同的代码分支, 根据我们读到的第一个字符的字符类型.
get_keyword
函数来检查它是关键字还是标识符./
),我们将检查下一个字符是斜杠还是星号(*
),在这种情况下,我们将跳过行/块注释.get_operator
function.下面是tokenize函数的实现. 我将省略它正在调用的函数的实现细节.
令牌标记(push_back_stream& stream) {
While (true) {
Size_t line_number = stream.line_number ();
Size_t char_index = stream.char_index();
Int c = stream();
Switch (get_character_type(c)) {
案例character_type:: eof:
返回{eof(), line_number, char_index};
案例character_type::空间:
continue;
案例character_type:: alphanum:
stream.push_back(c);
返回fetch_word(流);
案例character_type:: punct:
switch (c) {
case '"':
返回fetch_string(流);
case '/':
{
Char c1 = stream();
switch(c1) {
case '/':
skip_line_comment(流);
continue;
case '*':
skip_block_comment(流);
continue;
default:
stream.push_back方法(c1);
}
}
default:
stream.push_back(c);
返回fetch_operator(流);
}
break;
}
}
}
您可以看到,在调用低级函数之前,它将读取的字符推回. 性能损失几乎不存在,而且底层函数代码更加清晰.
在一次反对例外的咆哮中,我哥哥曾经说过:
“有两种人:抛出异常的人和必须捕捉异常的人. 我总是处于悲伤的第二组.”
我同意这一发言的精神. 我不太喜欢例外, 抛出它们会使任何代码更难以维护和阅读. Almost always.
我决定破例(坏的双关语). 从编译器抛出异常以从编译的深度展开是非常方便的.
下面是异常实现:
类错误:public std::exception {
private:
std:: string _message;
size_t _line_number;
size_t _char_index;
public:
Error (std::string message, size_t line_number, size_t char_index) noexcept;
Const char* what() Const noexcept override;
Size_t line_number() const noexcept;
Size_t char_index()常量noexcept;
};
但是,我保证在顶级代码中捕获所有异常. I even added line_number
and char_index
用于漂亮打印的成员,以及完成它的函数:
空白format_error (
const error& err,
get_character来源,
std::ostream& output
);
这就是我们系列的第一部分. 也许它不是太令人兴奋, 但是我们现在有了一个有用的标记器, 以及基本的解析错误处理. 这两者都是我将在接下来的文章中介绍的更有趣的内容的重要组成部分.
我希望你能从这篇文章中得到一些好的想法,如果你想探索细节,请访问我的 GitHub page.
通过编写语言语法和运行时上下文,编译后的代码可以在其中执行.
它的语法、语法规则和语义是最小的词汇单位——记号.
Tokenizer是一个从流中读取字符并给出最小词法单位的组件, tokens, 实现为c++对象, as a result.
Jakisa拥有超过15年的跨平台应用开发经验. 他的大部分技术专长是c++开发.
世界级的文章,每周发一次.
世界级的文章,每周发一次.