Let’s Build A Simple Interpreter.是一个用Python实现了语言解释器的系列文章。我对这个系列的每一篇文章都做了一个简要的介绍,如果你打算看这系列的文章,可以把我的这些简介作为这系列文章的提纲或者目录,帮助你快速的抓住每篇文章的核心内容。

  1. https://ruslanspivak.com/lsbasi-part1/

    讲了编译器的基本概念,以及一个实现了计算3+5的最简单的解释器。通过这个解释器,简单的介绍了一下词法分析以及通过 eat 函数来实现了语法分析。

  2. https://ruslanspivak.com/lsbasi-part2/

    语法分析增加了对空格的处理,词法分析增加了对多个数字组成的数字的识别。增加了减法操作。

  3. https://ruslanspivak.com/lsbasi-part3/

    介绍了使用 Syntax diagrams 来描述语法信息;事实上个人更喜欢BNF范式的描述方式,而不是很喜欢这种用图像来描述语法的方式。细化了语法分析的代码,根据给定的 Syntax diagrams 图的语法来构建代码,把数字的识别部分单独提升为一个函数。

  4. https://ruslanspivak.com/lsbasi-part4/

    介绍 EBNF 范式,并且用此范式来描述文法;介绍了终结符、非终结符、起始符号的概念。介绍了4种把EBNF范式转化为方法的套路:

    • 对于每一个产生式,都应该定义一个方法来与之对应;
    • 选择符号 | 对应代码 if...elif...else...
    • 对于 (...)* 这种重复符号,使用代码 while
    • 对于每一个非终结符(Token),都使用 eat() 方法来进行语法分析,判断当前token和语法定义中的是否一致,不一致则应该报错
  5. https://ruslanspivak.com/lsbasi-part5/

    介绍了算术表达式的“左关联”的特性,和引入了操作的“优先级”的概念。高优先级总是比低优先级先执行,同样的优先级则执行“左关联”(即从左向右执行)。为了符合高优先级先执行的特性,则需要把高优先级作为一个完整的non-terminal,使其在AST的靠近下方的位置。例如:

    expr: term((+|-)term)*
    term: factor((*|/)factor)*
    factor: num
    

    这样书写产生式的目的在于要让高优先级的产生式先执行

  6. https://ruslanspivak.com/lsbasi-part6/

    引入了括号的优先级概念,并且这种语法将产生递归操作。例如:

    expr: term((+|-)term)*
    term: factor((*|/)factor)*
    factor: num|LPAREN expr RPAREN
    

    因为相加、相乘(即运算符)操作的可能对应的是数字,也有可能是一个括号整体。

  7. https://ruslanspivak.com/lsbasi-part7/

    引入了中间表示(IR)、分析树和抽象语法树(AST)的概念。

    分析树用来记录输入程序的解析操作,

    • 分析树的根节点是 start symbol
    • 分析树的内部节点都是非终结符,代表了一个产生式规则
    • 分析树的叶子节点都是终结符,其实是一个个的token

      分析树和AST的主要区别:

    • AST使用操作符作为根节点和内部节点,使用操作数作为它们的子节点
    • 和分析树不同,AST不使用内部节点来代表语法
    • AST不会描述真实语法中的所有的细节;例如,没有规则节点,没有括号
    • 对于同样的语法结构,AST和分析树是很相似的

      AST的定义:对一个语法结构的抽象;其中根节点和内部节点代表操作符,它们的子节点代表操作数
      对于高优先级操作,只需要把它放到AST靠下的位置即可。

      后面还介绍了如何构建一棵抽象语法树,以及在解释器中使用后序遍历和观察者模式来对树进行解析。(解析的时候用了Python的一个小trick:getattr函数)

  8. https://ruslanspivak.com/lsbasi-part8/

    给表达式添加了一元操作符(+、-),一元操作符作为操作数的父节点来构造AST。

  9. https://ruslanspivak.com/lsbasi-part9/

    介绍了Pascal的语法;更新了lexer、parser、和interpreter来适应Pascal的语法。利用递归下降分析算法进行了语法分析。

  10. https://ruslanspivak.com/lsbasi-part10/

    进一步完善了对Pascal语法的支持,增加了包申明、变量类型管理、整除操作,等等。

  11. https://ruslanspivak.com/lsbasi-part11/

    对前面的所有内容做了一个回复和总结。介绍了使用符号表,使得在进行AST解析的时候能够得到正确的解析,符号表就是用来保存一些编译AST的时候的信息的。

    在这个过程中, 根据语言的语义规则来识别语义错误, 要识别语义错误 就必须编译 AST, 因为是树的遍历, 假如你先遍历到了 int a 这个节点, 接着又遍历到了一个表达式 a = 4 这个节点, 你需要检查变量 a 有没有声明啊, 变量 a 和 4 的类型批不匹配呢? 这时你如果没有保存变量 a 的信息, 那么你怎么检查? 所以就需要符号表来保存这些信息了。

  12. https://ruslanspivak.com/lsbasi-part12/

    介绍了Pascal的过程描述语法,把此语法添加进来,进一步完善了编译器和解释器。

  13. https://ruslanspivak.com/lsbasi-part13/

    引入了语义分析的概念,更加深入的对语义分析进行了讨论。

  14. https://ruslanspivak.com/lsbasi-part14/

    引入了变量作用域,等等的概念,进一步完善了编译器。