Kaleidoscope 系列第一章:新语言特性和 Lexer

本贴最后更新于 1876 天前,其中的信息可能已经东海扬尘

原文链接 Kaleidoscope 系列第一章:新语言特性和 Lexer

本文是 [使用 LLVM 开发新语言 Kaleidoscope 教程] (https://www.tuhaoxin.cn/articles/2019/10/01/1569927157476.html) 系列第一章,主要介绍 Kaleidoscope 语言特性和词法分析器的构建。

Kaleidoscope 语言特性

本教程以一种名为“Kaleidoscope”(google 翻译为万花筒,源自“美丽,形式和视野”)的玩具语言进行开发。Kaleidoscope 是一种过程语言,可让我们轻松定义函数,使用条件语句,数学表达式等。在本教程中,我们将扩展 Kaleidoscope 以支持 if/then/else 语句,for 循环,用户定义运算符,支持使用 JIT 进行简单的命令行界面编译、调试等。

再次说明,我们希望使设计语言保持简单,因此 Kaleidoscope 中唯一的数据类型是 64 位浮点类型(在 C 语言中为“ double”)。这样,所有值都隐式地具有双精度,并且该语言不需要类型声明。这为该语言提供了一种非常不错且简单的语法。例如,以下简单示例计算斐波纳契数:

# Compute the x'th fibonacci number.
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)
# This expression will compute the 40th number.
fib(40)

我们还允许 Kaleidoscope 调用标准库函数,因为 LLVM JIT 使得此操作非常容易。这意味着我们可以在使用函数之前使用'extern'关键字定义一个函数(这对于相互递归的函数也很有用)。例如:

extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);

atan2(sin(.4), cos(42))

第 6 章中提供了一个更有趣的示例,其中我们编写了一个迷你 Kaleidoscope 应用程序,该应用程序以不同的放大倍数显示 Mandelbrot 集

接下来我们开始深入探讨这种语言的实现。

词法分析器

在实现语言方面,首先需要的是处理文本文件并识别其内容。传统方法是使用“词法分析器”(又称“扫描器”)将输入分解为“token”。词法分析器返回的每个 token 都包含 token 代码和潜在的一些元数据(例如数字的数值等)。首先,我们定义以下 token:

// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
  tok_eof = -1,

  // commands
  tok_def = -2,
  tok_extern = -3,

  // primary
  tok_identifier = -4,
  tok_number = -5,
};

static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal;             // Filled in if tok_number

我们的词法分析器返回的每个 token 要么是 Token 枚举类型中的某值之一,要么是“未知”字符(如“ +”),并以其 ASCII 值返回。如果当前 token 是标识符,则 IdentifierStr 全局变量将保存标识符的名称。如果当前标记是数字(如 1.0),则 NumVal 保留其值。为了简单起见,我们使用全局变量,但这不是真正的语言实现的最佳选择。

词法分析器实际由 gettok 的函数实现。gettok 调用该函数以从标准输入返回下一个标记。其定义开始于:

/// gettok - Return the next token from standard input.
static int gettok() {
  static int LastChar = ' ';

  // Skip any whitespace.
  while (isspace(LastChar))
    LastChar = getchar();

gettok 通过调用 C 中 getchar() 函数从标准输入一次读取一个字符来工作。它在识别到它们后就删除它们,并将最后读取但未处理的字符存储在 LastChar 中。它要做的第一件事是忽略 token 之间的空格。该功能主要由 while 循环完成。

接下来 gettok 要做的是识别标识符和特定的关键字,例如 “def”。Kaleidoscope 通过以下简单循环完成此操作:

if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
  IdentifierStr = LastChar;
  while (isalnum((LastChar = getchar())))
    IdentifierStr += LastChar;

  if (IdentifierStr == "def")
    return tok_def;
  if (IdentifierStr == "extern")
    return tok_extern;
  return tok_identifier;
}

请注意,此代码在 IdentifierStr 对标识符进行词法化时都会设置成全局值。另外,由于语言关键字是由同一循环匹配的,因此我们在此对它们进行内联处理。对于处理数值也是类似的:

if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
  std::string NumStr;
  do {
    NumStr += LastChar;
    LastChar = getchar();
  } while (isdigit(LastChar) || LastChar == '.');

  NumVal = strtod(NumStr.c_str(), 0);
  return tok_number;
}

这是用于处理输入的非常简单的代码。从输入读取数值时,我们使用 C 中 strtod 函数将其转换为存储在中的数值 NumVal。请注意,这并没有进行足够的错误检查:它将错误地读取“ 1.23.45.67”,并像处理“ 1.23”一样处理它。当然,我们可以随意更改它!

接下来我们处理注释:

if (LastChar == '#') {
  // Comment until end of line.
  do
    LastChar = getchar();
  while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');

  if (LastChar != EOF)
    return gettok();
}

我们通过跳到行尾来处理注释,然后返回下一个标记。最后,如果输入与以上情况之一不匹配,则该输入可能是运算符,例如“ +”,或者是文件结尾。这些使用以下代码处理:

  // Check for end of file.  Don't eat the EOF.
  if (LastChar == EOF)
    return tok_eof;

  // Otherwise, just return the character as its ascii value.
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

这样,我们就拥有了用于基本 Kaleidoscop 语言的完整词法分析器(该词法分析的完整代码清单可在本教程的下一章中找到)。接下来,我们将构建一个简单的解析器,使用它来构建抽象语法树。当我们有了它时,我们将包括一个驱动程序,以便我们可以同时使用 lexer 和解析器。


参考:Kaleidoscope Introduction and the Lexer

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    729 引用 • 1327 回帖
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 5 关注
  • 代码片段

    代码片段分为 CSS 与 JS 两种代码,添加在 [设置 - 外观 - 代码片段] 中,这些代码会在思源笔记加载时自动执行,用于改善笔记的样式或功能。

    用户在该标签下分享代码片段时需在帖子标题前添加 [css] [js] 用于区分代码片段类型。

    69 引用 • 372 回帖
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 232 回帖 • 2 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    125 引用 • 588 回帖
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 1 关注
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 63 关注
  • danl
    132 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 6 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 587 关注
  • CSS

    CSS(Cascading Style Sheet)“层叠样式表”是用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言。

    198 引用 • 550 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 19 关注
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 431 关注
  • 安全

    安全永远都不是一个小问题。

    199 引用 • 816 回帖
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 167 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    266 引用 • 665 回帖
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    200 引用 • 120 回帖
  • 工具

    子曰:“工欲善其事,必先利其器。”

    286 引用 • 729 回帖
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    222 引用 • 473 回帖 • 1 关注
  • 导航

    各种网址链接、内容导航。

    40 引用 • 173 回帖
  • Jenkins

    Jenkins 是一套开源的持续集成工具。它提供了非常丰富的插件,让构建、部署、自动化集成项目变得简单易用。

    53 引用 • 37 回帖
  • V2Ray
    1 引用 • 15 回帖 • 1 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 721 关注
  • 区块链

    区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。所谓共识机制是区块链系统中实现不同节点之间建立信任、获取权益的数学算法 。

    91 引用 • 751 回帖 • 2 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 724 关注