crafting-interpreters3

编译器实践第三课，Representing Code

上一章节我们提到如何把代码作为字符串，识别出对应的变量，关键字，表达式，运算符等，并把它们提取出来。而这一章后面一章，将会把这些token转化为更为复杂的内容。这一章关注的是，关于这些“更为复杂的内容”的定义。

上一章我们着重关注的是lexial grammar也就是词法，而这一张我们将会偏重于context-free grammar。在scanner语法中，字母表是单个字符，而字符串(也叫token)是一个单词。现在我们认为每一个token是字母表，而字母表组成在一起，叫做表达式。

一个正式语法的作用手机确定什么字符串时有效的，什么不是。就类似英语里面喷段一个句子的语法结构是否正确一样。(而不是单词拼写是否正确)

句法语法

下面用一张图介绍语法。感觉这种构造方式和之前fuzz里面基于语法的fuzzing很类似。例如下面的一个breakfast。其构造方法是第一句所描述的规则。并且如果我们制定引号引起来的是terminal也就是可以不再扩展，我们可以通过逐级拆解每个变量。(例如breakfast拆分成protein，protein拆分成cooked eggs，而cooked拆分成poached等等，以此类推即可)

breakfast  → protein "with" breakfast "on the side" ;
breakfast  → protein ;
breakfast  → bread ;

protein    → crispiness "crispy" "bacon" ;
protein    → "sausage" ;
protein    → cooked "eggs" ;

crispiness → "really" ;
crispiness → "really" crispiness ;

cooked     → "scrambled" ;
cooked     → "poached" ;
cooked     → "fried" ;

bread      → "toast" ;
bread      → "biscuits" ;
bread      → "English muffin" ;

最终得到的结果类似下图。直到我们的所有句子内容都是terminal就终止扩展。

句法语法的扩展

可以参考以下内容。我们可以用问号(问号之前的内容至多出现一次)，星号(出现任意次)，加号(出现至少一次)，竖线(表示选择)来进一步形式化语言。

breakfast → protein ( "with" breakfast "on the side" )?
          | bread ;

protein   → "really"+ "crispy" "bacon"
          | "sausage"
          | ( "scrambled" | "poached" | "fried" ) "eggs" ;

bread     → "toast" | "biscuits" | "English muffin" ;

LOX语法的表示

根据上面的语法规则，对于Lox我们可以使用以下语法表达式。

expression     → literal
               | unary
               | binary
               | grouping ;

literal        → NUMBER | STRING | "true" | "false" | "nil" ;
grouping       → "(" expression ")" ;
unary          → ( "-" | "!" ) expression ;
binary         → expression operator expression ;
operator       → "==" | "!=" | "<" | "<=" | ">" | ">="
               | "+"  | "-"  | "*" | "/" ;

以下是一个表达式的例子。1是NUMBER，-是operator（在binary中）之后是binary中左侧的grouping，内部包含了一个新的expression。再之后是右侧的expression，是<4的标志，然后其实这整个还是作为一个大的binary的，因为用等号将两边连接起来。

1 - (2 * 3) < 4 == false

为了用面向对象的方式将这些表达式写出来，如下

package com.craftinginterpreters.lox;

abstract class Expr { 
  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }

    final Expr left;
    final Token operator;
    final Expr right;
  }

  // Other expressions...
}

我们可以一个一个手写，但是作者给了我们一个简单的方法，用脚本自动生成。这里碰到一个问题卡了很久。。就是新建一个tool的包知乎，eclipse里面就不能直接运行代码了，必须用java运行。

折磨了一个小时，还是没找到解决办法。但是没有关系，毕竟这个tool还是一个命令行工具。参考链接下的做法，编译得到一个新文件expr.java。

具体的方法是先在lox/ 下面生成一个.class文件，如下

之后到src/下面去生成

这里我把GenerateAst移动到了lox/下面，不然总是报找不到主类的错误

visitor mode

访问者模式。作者举了一个例子，我们在设计不同类时，如果想要横向的添加一层，非常容易，但是如果纵向添加一层，则困难许多。

因为纵向添加往往意味着对于每一个类，都要添加一个新的成员函数。而有一种解决方案被称为访问者模式。这个网站写的很详细

访问者模式建议将新行为放入一个名为访问者的独立类中， 而不是试图将其整合到已有类中。 现在， 需要执行操作的原始对象将作为参数被传递给访问者中的方法， 让方法能访问对象所包含的一切必要数据。

在我们编写的tool.GenerateAST中，对应的代码如下

@Override
<R> R accept(Visitor<R> visitor) {
  return visitor.visitBinaryExpr(this);
}

个人理解:就是为了防止在每个类中都加入新的内容，所以用一个visitor，这个visitor可以定义一些能够操纵类内部数据的函数，然后我们如果想要在类中添加新的细节，不需要重写所有类，只需要将类中需要修改的函数指向这个visitor即可。

以下时生成的类。可以看到基本规则就是填上每一种表达式的拆分后的细节，以及创建一些visitor。

package lox;

import java.util.List;

abstract class Expr {
  interface Visitor<R> {
    R visitBinaryExpr(Binary expr);
    R visitGroupingExpr(Grouping expr);
    R visitLiteralExpr(Literal expr);
    R visitUnaryExpr(Unary expr);
  }
  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }

    @Override
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitBinaryExpr(this);
    }

    final Expr left;
    final Token operator;
    final Expr right;
  }
  static class Grouping extends Expr {
    Grouping(Expr expression) {
      this.expression = expression;
    }

    @Override
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitGroupingExpr(this);
    }

    final Expr expression;
  }
  static class Literal extends Expr {
    Literal(Object value) {
      this.value = value;
    }

    @Override
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitLiteralExpr(this);
    }

    final Object value;
  }
  static class Unary extends Expr {
    Unary(Token operator, Expr right) {
      this.operator = operator;
      this.right = right;
    }

    @Override
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitUnaryExpr(this);
    }

    final Token operator;
    final Expr right;
  }

  abstract <R> R accept(Visitor<R> visitor);
}

感觉这一章主要就是介绍了LOX语法的表示细节，然后创建了一个用于生成表达式类的tool。