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

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

你如何解决一个复杂度与理解去创造一个解释器或编译器一样的事情呢? 一开始它看起来非常像一堆乱七八糟的纱线,你需要解开才能得到完美的球。

解决方法就是一次解开一根线,一次一个结。 有时候,你可能觉得自己不会马上理解某些事情,但你必须坚持下去。 如果你足够坚持,你最终会清醒,我保证(诶呀,以前如果我每次不明白的花就放25美分,那么我很久以前就是个富人了)

在理解如果写一个解释器和编译器的过程中,我可能会给你最好的建议之一就是阅读文章中的源代码,甚至编写相同的代码。来使你感觉这些东西和代码对你来说十分自然,然后学习新的主题。不要匆忙,只是放慢速度,花时间深入理解基本思想。 这种看似缓慢的方法将在未来取得成效,相信我。

你最追将获得最完美的纱线球。 而且,你知道什么吗?即使它并不是那么完美,但它仍然比啥也不做、不主动学习,或者快速阅读然后忘了它的方案更好。

记住,保持一次解开一个结,一次一根线。并通过编写代码来练习你所学到东西。

今天,您将使用您从系列之前的文章中学到的所有知识,并学习如何解析和解释任何数量的加减乘除的算术表达式。您将编写一个能够解释“14 + 2 * 3 - 6 / 2”的表达式解释器。

在深入研究并编写一些代码之前,我们先讨论一下运算符的关联性和优先级。

按照约定,7 + 3 + 1 与 (7 + 3) + 1 相同,7 - 3 - 1 相当于(7 - 3)- 1,这里没有变化。我们都在某一时刻学会了这一点,并从那时起就把它视为理所当然。如果我们将7 - 3 - 1 视作 7 - (3 - 1),那么结果就是5而不是3。

在通常的算术和大多数编程语言中,加减乘除法是左结合的:

7 + 3 + 1 相当于 (7 + 3) + 1
7 - 3 - 1 相当于 (7 - 3) - 1
8 * 4 * 2 相当于 (8 * 4) * 2
8 / 4 / 2 相当于 (8 / 4) / 2

那么操作符左结合意味着什么呢?

当表达式7 + 3 + 1 中,3的两边都有加号时,我们需要一个约定来决定哪个运算符适用于3。左边还是右边?+运算符关联到左边,因为两边都有左关联的加号运算符,所以我们说加法运算符是左关联的。 这就是为什么7 + 3 + 1相当于(7 + 3)+ 1的结合性约定。

好吧,那么像7 + 5 * 2这样的表达式,我们5的两边有着不同类型的运算符? 表达式是否相当于7 + (5 * 2)或者(7 + 5)* 2 我们如何解决这种歧义呢?

在这种情况下,结合性约定对我们没有帮助,因为他仅仅适用于一种运算符,可以是(+,-)或(*,/)。 我们在同一个表达式中有着不同类型的运算符时,我们需要另一个约定来解决歧义。 我们需要定义运算符的相对优先级。

所以:我们说如果操作符在*或+之前取其操作数,那么它就具有更高优先级。在我们所知和使用中,乘法和除法比加减法有更高的优先级。 所以表达式7 + 5 * 2相当于7 + (5 * 2),7 - 8 / 4 相当于 7 - (8 / 4)。

在我们有一个具有相同优先级的运算符表达式的情况下,我们只关心从左往右执行

7 + 3 - 1 相当于 (7 + 3) - 1
8 / 4 * 2 相当于 (8 / 4) * 2

我希望你不要因为谈论操作符的关联性和优先级而让你想到生死。 关于这些约定的好处是我们可以从表中构造算术表达式的语法,该表显示了算术运算符的关联性和优先级。 然后,我们可以按照第四章概的指南将语法翻译成代码,除了关联性之外,我们的解释器还能够处理运算符的优先级

这是我们的优先级表:

从表中可以看出,运算符 + 和 - 具有相同的优先级,并且他们都是左关联的。 您还可以看到 * 和 / 也是左关联的,它们具有相同的优先级,但具有比加减法更高的优先级。

以下是我们如何从优先级表构造语法的规则:

  1. 对于每个优先级定义一个非终止符,非终止符的产生式主体应该包含来自该级别的运算符和非终止符的下一个更高级别的优先级。

  2. 为基本的表达式单元创建一个额外的非终止符因子,在我们的例子中是整数。一般的规则是,如果您有N级优先级,那么总共需要N + 1个非终止符;每个级别一个非终止加一个基本表达式单元的非终止符。

继续!

让我们遵循规则并构建我们的语法。

通过规则1,我们将定义两个非终止符:一个非终止符称作expr给第二级和一个称作term的非终止符为第一级。并且通过遵循规则2,我们将为算术表达式的基本单位————整数,定义一个非终止符因子。

我们新语法的开始符号是exprexpr的产生式会包含一个表示使用第二级运算符的主体。在我们的例子中,这个主体的运算符是+和-,并包下一个更高优先级的term非终止符,level 1:

term的产生式将有呈现第一级操作符*和/的主体,并且他会包含非终止符fator(表示基本单位整数):

非终止符factor的产生式将会是:

你已经将上面的结果看作前面文章中语法和语法图的一部分,但在这里,我们将它们组合成一个语法。该语法考虑到了运算符的关联性和优先级:

下面是上述语法对应的语法图:

图表中的每一个矩形框都是另一个图表的“方法调用”。如果你处理表达式7 + 5 * 2然后图表一开始调用expr然后向下走到最下面的factor图表,你应该能看到,在较低的关系图中,较高优先级的运算符*和/比低优先级的+和-更早执行。

为了使运算符的优先级更清楚。我们来看看根据上述语法和语法图解释相同的算术表达式7 + 5 * 2。这是只是另一种方式,表明优先级高的运算符比优先级低的运算符先执行

OK,让我们遵循第四章的指南,转换以下的语法到代码,看看我们新的解释器如何工作的吧。

再贴一次语法:

这是完整的计算器代码,它可以处理包含整数和任意的加减乘除运算符的合法的算术表达式。

以下是与第四章的新增内容:

  • Lexer类可以Token化+,-,*,/(这里没什么新的,我们仅仅是合并了前几章的东西)

  • 重新调用了定义在语法中的每一个规则(产生式),R,变成了同样名字的代码,并且对该规则的引用成为一个方法调用,R()。因此,解释器类里面现在有三个方法对应语法的非终端:expr、term和factor。

const INTEGER = 'INTEGER'
const PLUS = 'PLUS'
const MINUS = 'MINUS'
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(PLUS, '+')
      } else if (this.currentChar === '-') {
        this.advance()
        return new Token(MINUS, '-')
      } 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
  }

  term = () => {
    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 = () => {
    let result = this.term()
    while ([PLUS, MINUS].indexOf(this.currentToken.type) !== -1) {
      const token = this.currentToken
      if (token.type === PLUS) {
        this.eat(PLUS)
        result += this.term()
      } else if (token.type === MINUS) {
        this.eat(MINUS)
        result -= this.term()
      }
    }
    return result
  }
}

然后我们的测试代码变成了这样:

import { Interpreter } from '../src'

describe('Unit test', () => {
  it('Interpreter run success', () => {
    expect((new Interpreter('1+2')).expr()).toBe(3)
    expect((new Interpreter('1+9')).expr()).toBe(10)
    expect((new Interpreter('20+20')).expr()).toBe(40)
    expect((new Interpreter('20-20')).expr()).toBe(0)
    expect((new Interpreter('1-2')).expr()).toBe(-1)
    expect((new Interpreter('1+2+3+4')).expr()).toBe(10)
    expect((new Interpreter('10 + 1 + 2 - 3 + 4 + 6 - 15')).expr()).toBe(5)
    expect(new Interpreter('7 * 4 / 2').expr()).toBe(14)
    expect(new Interpreter('7 * 4 / 2 * 3').expr()).toBe(42)
    expect(new Interpreter('10 * 4  * 2 * 3 / 8').expr()).toBe(30)
    expect(new Interpreter('7 - 8 / 4').expr()).toBe(5)
    expect(new Interpreter('14 + 2 * 3 - 6 / 2').expr()).toBe(17)
  })
})

接下来是今天的新测试:

  • 像本文描述的那样,编写一个解释器,不要偷看文中的代码。为你的翻译器写一些测试,确保通过。

  • 扩展编译器以处理圆括号运算符。比如:7 + 3 * (10 / (12 / (3 + 1) - 1))

检查你的理解:

  1. 运算符的左关联是什么?

  2. +和-是左关联还是右关联?*和/呢?

  3. +的优先级是否高于*?

期待下一章

You can’t perform that action at this time.