使用 Scala 解析器组合器创建编程语言

一则或许对你有用的小广告

欢迎加入小哈的星球 ,你将获得:专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡/ 赠书活动

目前,正在 星球 内带小伙伴们做第一个项目:全栈前后端分离博客项目,采用技术栈 Spring Boot + Mybatis Plus + Vue 3.x + Vite 4手把手,前端 + 后端全栈开发,从 0 到 1 讲解每个功能点开发步骤,1v1 答疑,陪伴式直到项目上线,目前已更新了 204 小节,累计 32w+ 字,讲解图:1416 张,还在持续爆肝中,后续还会上新更多项目,目标是将 Java 领域典型的项目都整上,如秒杀系统、在线商城、IM 即时通讯、权限管理等等,已有 870+ 小伙伴加入,欢迎点击围观

设计自己的编程语言绝非易事。但是,使用 Scala 解析器库,您可以非常轻松地设计出功能齐全的解释型语言。在本文中,我将演示如何使用 Scala 解析器组合器创建一种包含 if-else 条件、循环甚至函数调用的编程语言。在本文的末尾,我提供了一个指向 GitHub 上代码的链接,您可以按自己的意愿进行分叉和操作。让我们开始吧!

使用 Scala 解析器组合器的语言项目包含三个主要组件:

  1. 解析器本身,它定义语言的语法并执行解析。

  2. 解释器,它遍历步骤 1 创建的抽象语法树 (AST)。

  3. 每种语言构造的普通旧 Scala 类。例如,我们将有一个 LoopStatement 类,其中包含循环的迭代次数和循环内的语句列表。

让我们从解析器开始。第一步是扩展 StandardTokenParsers 类并定义我们语言中的保留字和分隔符。


 class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")

lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=", "<", ">", "==", "!=", "<=", ">=", ",", ":") }


接下来,我们通过添加每个解析器规则来添加到我们的 SmallLanguageParser 类。该语言将包含一个“主要”入口点,它将作为我们应用程序的主要功能。让我们为这个“主要”结构添加一个解析器规则。


 class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")

lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=", "<", ">", "==", "!=", "<=", ">=", ",", ":") }


让我们稍微检查一下这个“程序”函数。您会注意到返回值是一个 Parser[Program]。剥离复杂性,这实际上只是返回 Program 类的一个实例,我们将在稍后定义它。这个 Program 类是属于步骤 3 的普通旧 Scala 类之一。因此,您会注意到这些规则中的每一个都将简单地返回其中一个类的实例,每个类代表我们编程语言中的一个构造。

该规则的下一部分是 (rep(function) <~ ("main" ~ ":")) 。这意味着我们可以在我们的语言中有一个重复的函数列表(即 rep(function) )。这个函数列表后面跟着 main: 保留字。然后是代码块。请注意, 代码块 函数 只是我们稍后将在解析器中定义的解析器规则。

该规则的最后一部分是 ^^ { ... }。 Scala 中的 ^^ 运算符只是简单地告诉解析器接下来是触发此解析器规则时我们要执行的 Scala 代码。 { ... } 中的 Scala 代码只是返回 Program 类的实例,其构造函数采用函数列表和代码块。

我们现在可以为每个解析器规则重复这个过程。每个规则都将定义语法(或允许的关键字和文本)以及返回类型。当您想到一种编程语言时,它包含诸如循环、条件、函数调用等构造。因此,如果我们为这些构造中的每一个添加解析器规则,我们将得到以下 SmallLanguageParser:


 class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")

lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=", "<", ">", "==", "!=", "<=", ">=", ",", ":") }


代码有点长,但它实际上只是我们的语言将处理的每种语言结构的解析器规则。有一个关于如何处理 if 语句的规则,一个用于处理循环的规则,一个关于如何解析函数调用的规则,等等。唯一不符合这个描述的是名为“parseAll”的底层函数。这个“parseAll”函数将采用我们的 SmallLanguageParser 的一个实例和我们将要运行的输入源代码。它将返回解析操作的结果,这将是源代码的抽象语法树 (AST)。然后这个 AST 可以被我们的解释器解释(这是我们上面列表中的步骤 #2)。

这是解释器的代码:


 class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")

lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=", "<", ">", "==", "!=", "<=", ">=", ",", ":") }


这个解释器简单地遍历 AST 并在每次遇到树中的节点时做一些事情。以最后一个 case 语句为例。如果解释器遇到 if 语句,解释器将简单地评估条件。如果条件为真,解释器遍历代码的真分支。如果条件评估为 false,则解释器遍历代码的 false 分支。

此时,我们已完成步骤#1 和#2。我们有一个解析器和一个解释器来处理我们的解析结果。最后一块拼图是用于每种语言构造的普通旧 Scala 类。与其详细介绍本文中的每个类(毕竟它们是普通的旧 Scala 类,我在下面的 GitHub 上提供了所有代码的链接),不如让我们看一下其中一个类,即“条件”。当在源代码中找到条件(或 if 语句)时,您会注意到解析器正在创建并返回这个类。


 class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")

lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=", "<", ">", "==", "!=", "<=", ">=", ",", ":") }


此类仅存储条件左侧和条件右侧的运算和求值表达式,分别为 true 和 false 分支。所以,这些部分之间的关​​系看起来是这样的:


源代码 -> 解析器 -> {普通的旧 Scala 类} -> 解释器


唯一缺少的是处理此事件流的驱动程序应用程序。下面是一些读取输入源文件、调用解析器、然后根据解析结果调用解释器的 Scala 代码:


 class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")

lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=", "<", ">", "==", "!=", "<=", ">=", ",", ":") }


看,创建一种编程语言毕竟不是那么困难!当然,这是一种解释性语言,这使得它更简单。然而,这是熟悉语言设计的好方法。最好的部分是,您可以在 Scala 中完成这一切。


以下是 GitHub 上所有源代码的链接:https: //github.com/travisdazell/javaone-2013-BOF-small-language


我还提供了有关此主题的幻灯片的链接,来自我的 JavaOne 2013 BOF 会议: http ://www.slideserve.com/manton/developing-small-languages-with-scala-parser-combinators