来写一个简单的解释器(四)

 

来写一个简单的解释器(四)

你是否在被动的学习这些文章种的内容?或是主动的学习?我希望你一直是主动的、积极的练习它。(真的)

还记得孔子说过的话吗?

「不聞不若聞之,聞之不若見之,見之不若知之,知之不若行之;學至于行之而止矣。」

英文:“I hear and I forget. I see and I believe. I do and I understand.”

在之前的文章里,你已经学习了如何解析和解释任意个整数的加减计算表达式,比如“7 - 3 + 2 - 1”。你也学到了有关语法图和如何使用它们来描述编程语言的语法。

今天,你将要学到如何去解析解释任意个整数的乘除计算表达式,比如“7 * 4 / 2 * 3”。本章将划分的是整数除法,所以“9 / 4”,结果会是“2”。

我也会谈一谈另一个广泛使用的,用于指定编程语言的语法的表示法————上下文无关语法(context-free grammars),简称语法(grammars)或者 BNF(Backus-Naur Form)。出于本文的目的,我不会使用纯的BNF表示法,而是像修改过的EBNF表示法。

用这种语法的几个原因:

  1. grammar以简洁的方式指定编程语言语法。与语法图不同,语法非常的紧凑。您将在以后的文章中看到我越来越多的使用这种语法。

  2. grammar可以作为很好的文档。

  3. 即使你从头开始写编译器,grammar也是一个很好的开始。通常,您可以通过遵循一组简单的规则将语法转换为代码。

  4. 有一种工具,称作解析器生成器,它们接受语法作为输入,然后根据语法自动生成解析器。本文将在最后讨论这些工具。

现在,让我们开始讨论语法的机械方面吧?

这是一个描述算术表达式的语法,如“7 * 4 / 2 * 3”(它只是语法可以被生成的种多表达式之一)

语法由一系列规则组成,称作产生式(productions)。我们语法中,有两条规则:

规则包括非终结符式(non-terminal),称作产生式的头或左侧,冒号,以及一些列终结符或非终结符,称作正文或右侧。

在我上面显示的语法中,像MUL、DIV、和INTEGER这样的标记称作终端,而像exprfactor这样的变量称作非终结符。非终结符通常是由一些列终结符和非终结符组成:

第一个规则左侧的非终结符号称作起始符号。

在我们的语法下,开始符号是expr

您可以将规则expr理解成:“expr可以是一个因子,后面可选的跟着乘法或者除法运算符后跟一个因子,然后可选地后面跟乘法或者除法后跟一个因子,以此类推。”

什么是因子(factor)呢?出于本文目的,因子只是一个整数。

所以我们快速浏览一下我们语法中的符号和意义。

  • | - 备选方案。意思是“或”。(MUL DIV) 意思是或者MUL或者DIV
  • ( … ) - 开闭括号表示如(MUL DIV)中的终结或非终结字符的分组
  • ( … )* - 表示将里面的内容多次匹配

译者注: 这就是个正则表达式

如果你以前使用过正则表达式,那么这些符号对你来说应该非常熟悉

语法通过解释它可以形成的句子来定义语言。

这就是你如何使用语法派生算术表达式;首先从符号expr开始,然后用非终结符的规则重复替换非终结,知道你生成一个包含终结的句子为止。

这些句子构成的语法而定义语言。

如果语法无法派生某个算术表达式,则它不支持该表达式,并且解析器在尝试识别表达式的时候将产生语法错误。我认为有几个例子是有序的。这就是语法产生3的方式:

这是如何产生“3*7”的:

这是如何产生“3 * 7 / 2”的:

哇。这么多的理论。

我想,当我第一次阅读有关语法的相关术语和所有爵士乐内容时,我的感觉像这样:

我敢保证,我不是这样:

我花了一些时间来熟悉符号是如何工作的,以及它与解析器和词法分析器的关系,但我必须告诉你,从长远来看,它是值得的,因为它在实践和编译器文献中被广泛使用。你肯定会在某些时候遇到它。那么,为什么不早点呢?

现在,让我们把语法映射到代码。

以下是我们将用于将语法糖转换为源代码的原则。 通过遵循它们,您可以直接将语法翻译成工作解析器:

  1. 在语法定义的每个规则R成为具有相同名称的方法,并且对该规则的应用方法调用:R()。该方法遵循规则主体的流动,并且遵循相同的指导方针。

  2. (a1 a2 an) 变成 if-else-then 语法。
  3. 可选分组 (…)* 变成零次或多次的 while 循环

  4. 每个Token引用T,调用方法eateat(T)。 eat方法的工作方式是,他会用标记T,然后从词法分析器中获取一个新的标记,并且将该标记分配给 currentToken 内部变量

用图来说,就是这样的:

让我们根据上面的指南将语法转换为代码。

我们语法中有两条规则:一条expr和一条因子规则。

根据指南,您需要创建一个名为factor(规则1)的方法,该方法只需调用eat方法来使用INTEGER Token(规则4):

factor = () => this.eat(INTEGER)

很简单,对吧?

规则expr成为expr方法(同样根据指南1)。 规则的主体以对factor成为factor()方法调用引用开始。 可选分组 (…)* 成为while循环,(MUL|DIV) 变成if-else-then语句。

通过组合这些部分,我们得到了以下expr方法:

  expr = () => {
    let result = this.factor()

    while ([MUL, DIV].indexOf(this.currentToken.type) !== -1) {
      const token = this.currentToken
      if (token.type === MUL) {
        this.eat(MUL)
        result *= this.factor()
      } else if (token.type === DIV) {
        this.eat(DIV)
        result /= this.factor()
      }
    }
    return result
  }

请花一些时间研究如何将语法映射到代码。确保你理解那些部分,稍后会派上用场。

我忍不住再提一下语法树,这是同一个expr规则的语法图的样子:

现在是我们挖掘新的算术表达式解释器的源代码的时候了。 下面是一个计算器的代码,它可以处理包含整数和任意数量的乘法除法(整数除法)运算符的表达式。 您还可以看到我将词法分析器重构成了单独的类Lexer并更新了Interpreter类并将Lexer实例作为成员参数:

const INTEGER = 'INTEGER'
const MUL = 'MUL'
const DIV = 'DIV'
const EOF = 'EOF'

class Token {
  type: string
  value: any

  constructor (type: string, value: any) {
    this.type = type
    this.value = value
  }

  toString = () => `Token(${this.type}, ${this.value})`
}

class Lexer {
  text: string
  pos: number
  currentToken: Token = new Token(EOF, null)
  currentChar: string | null

  constructor (text: string) {
    this.text = text
    this.pos = 0
    this.currentChar = this.text[this.pos]
  }

  error = (): never => {
    throw Error('Invalid character')
  }

  advance = () => {
    this.pos++
    if (this.pos > this.text.length - 1) {
      this.currentChar = null
    } else {
      this.currentChar = this.text[this.pos]
    }
  }

  skipWhitespace = () => {
    while (this.currentChar != null && this.currentChar === ' ') {
      this.advance()
    }
  }

  integer = () => {
    let result = ''
    while (this.currentChar != null && /[0-9]/.test(this.currentChar)) {
      result += this.currentChar
      this.advance()
    }
    return Number(result)
  }

  getNextToken = (): Token => {
    while (this.currentChar != null) {
      if (/ /.test(this.currentChar)) {
        this.skipWhitespace()
        continue
      }

      if (/[0-9]/.test(this.currentChar)) {
        return new Token(INTEGER, this.integer())
      } else if (this.currentChar === '*') {
        this.advance()
        return new Token(MUL, '*')
      } else if (this.currentChar === '/') {
        this.advance()
        return new Token(DIV, '/')
      }
      return this.error()
    }
    return new Token(EOF, null)
  }
}

export class Interpreter {
  lexer: Lexer
  currentToken: Token

  constructor (text: string) {
    this.lexer = new Lexer(text)
    this.currentToken = this.lexer.getNextToken()
  }

  error = (): never => {
    throw Error('Invalid syntax')
  }

  eat = (tokenType: string) => {
    if (this.currentToken.type === tokenType) {
      this.currentToken = this.lexer.getNextToken()
    } else {
      this.error()
    }
  }

  factor = () => {
    const token = this.currentToken
    this.eat(INTEGER)
    return token.value
  }

  expr = () => {
    let result = this.factor()

    while ([MUL, DIV].indexOf(this.currentToken.type) !== -1) {
      const token = this.currentToken
      if (token.type === MUL) {
        this.eat(MUL)
        result *= this.factor()
      } else if (token.type === DIV) {
        this.eat(DIV)
        result /= this.factor()
      }
    }
    return result
  }
}

我知道你等不及了这部分:) 这是今天的新练习:

  • 编写一个描述任意数量 +, -, *, / 运算符的算术表达式语法。 通过gramma,你应该能够推导出“2 + 7 * 4”,“7 - 8 / 4”,“14 + 2 * 3 - 6 / 2”等表达式

  • 使用grammar,编写解释器,要求和上一条一样

  • 如果你已经完成了上述练习,放松并欣赏:)

检查你的理解。

记住今天文章中的语法,回答下列问题,根据需要参考下图:

  1. 什么是上下文无关语法?

  2. 语法有多少规则?

  3. 什么是终结符?(找到图中所有的)

  4. 什么是非终结符?(同上)

  5. 什么是规则的头?

  6. 什么是规则的正文?

  7. 什么是语法的起始符号?

敬请期待下一章。