Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
328 lines (222 sloc) 10.9 KB
title description tags
来写一个简单的解释器(四)
翻译自 Ruslan's Blog
翻译

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

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

还记得孔子说过的话吗?

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

英文:“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. 什么是语法的起始符号?

敬请期待下一章。

You can’t perform that action at this time.