# 框架中部分实现的解释

## lexer中字符串的识别

在lexer定义代码中可以看到：

```rust
...
'"[^"\\]*(\\.[^"\\]*)*"' = 'StringConst'
'"[^"\\]*(\\.[^"\\]*)*' = 'UnterminatedString'
...
```

前一个定义就是匹配一般的字符串常量的正则表达式，可参考<https://stackoverflow.com/questions/37032620/regex-for-matching-a-string-literal-in-java> 中对它的解释。

而第二个定义则比较奇怪，可以看出它比第一个少了末尾的一个引号。是因为decaf语言要求检查这种语法错误：不闭合的字符串，即直到程序的末尾也没有出现末尾的引号。

在java版本的框架中，为了识别`StringConst`这个终结符，利用了lex/flex中的"状态"机制，即看到`"`时进入专门匹配字符串常量的状态，这其中的词法规则可以不同于识别其他终结符时的词法规则，这样就可以比较容易的检测这个错误。

但是re2dfa没有提供这样的"状态"机制，整个dfa的转移规则都是一样的，也不允许在在词法动作中执行代码，所以没有办法在词法分析阶段检查字符串常量中的各种错误(至于为什么re2dfa的功能这么受限制，其实只是因为我觉得这样lexer generator比较好写而已)。

产生式中只写了`Expr -> StringConst`而没有写`Expr -> UnterminatedString`，即使这样写了，这个规约也不可能被执行(可以根据lalr(1)分析的原理考虑为什么，注意`UnterminatedString`后一定是文件结尾)。所以对于不闭合的字符串的内容检查无法在语法动作中进行，只能在parser因为遇到它而无法移进，从而报错时检查。与之相比，`StringConst`中的错误可以在语法动作检查。

对于字符串内容的检查实现在`check_str`函数中，目前它会检查不闭合的字符串，字符串中换行，和不合法的转义字符这三种错误。decaf目前只支持`\\`，`\"`，`\n`，`\r`，`\t`这几种转义字符。值得注意的是，它仅仅只是扫描一遍字符串，并不会将转义字符替换成真正想表达的字符(例如，将`\n`替换成值为10的ascii字符)，这是因为在之后的每个编译阶段中，但凡需要输出这个字符串常量的内容的地方，都直接输出了替换前的原始字符，在这里如果进行了替换，在输出的时候反而又要替换回来，没有必要。

总之，通过在词法动作中执行代码(甚至还可以选择到底返回哪个非终结符)，lex/flex生成的lexer的能力事实上超越了正则语言/dfa的表达能力；而re2dfa生成的lexer则完全就是正则语言/dfa。不过通过把需要执行的代码从词法动作中转移到语法动作中或者是其它地方，还是实现了一样的效果。

## `SynTy`与`Ty`

`Syn`是`Syntactic`的缩写，`Ty`是`Type`的缩写。区分出这两个struct的意义在于，`SynTy`是语法层面上的类型，例如为了表示类类型，这里直接使用类类型的名字(`SynTy::Named`)；`Ty`是语义层面上的类型，例如为了表示类类型，这里使用对相关类定义的引用(`Ty::Object`/`Ty::Class`)。当然二者也有一定的交集，例如为了表示整数，二者都可以直接使用`Int`。

可以看出，语法分析阶段只能得出`SynTy`的结果，为了得到`Ty`则必须经过pa2的语义分析。pa1中把它留在了这里，但是没有用到，大家可以当它不存在。

## `Ref`

`common`中提供了struct `Ref`，它的作用是用指针值来比较引用值的的等价性(同时仍然保留引用的生命周期信息，不需要用到unsafe)。之所以提供这个struct是因为在后续的分析中，有时需要给ast节点附加一个临时的属性，直接把这样的属性放在ast节点的定义中显得比较ad-hoc，而且需要修改节点的构造等其他地方的代码，不是很方便。我们使用一个键为`Ref<...>`的`HashMap`或者`HashSet`来表示这种临时的属性。

之所以不直接使用引用，是因为对于引用的`Eq`/`Ord`/`Hash`被实现为返回它指向的对象的相关函数值，而这里想表达的含义是每个地址不同的引用都被认为是不同的，所以引用的`Eq`/`Ord`/`Hash`需要被实现为指针的的相关函数值。

## ast的输出

在`print`的`ast.rs`中实现了对ast节点的输出。这里利用宏简化了一些重复机械的操作，但是如果有必要的话(节点的格式比较复杂，现在提供的宏不能直接使用)，对于每种节点的输出也是可以单独手动实现的。

这其中可能有些节点的名字输出比较奇怪，例如类中的变量定义输出为`VarDef`，而表达式中的变量定义输出为`LocalVarDef`。这完全是因为测例是由其它框架造出来的，他们就是这么实现的(定义了两个类)，我的实现与他们不一样，为了把测例对上只能这样输出。

## 其它

１. 根目录下的`Cargo.toml`中有几行：

```
cargo-features = ["profile-overrides"]
...
[profile.dev.overrides."*"]
opt-level = 3
```

这是指定所有外部依赖的crate在非优化的编译模式下(即默认的`cargo build`)，都使用优化编译。这主要是为了提高lalr1的速度，毕竟parser generator的工作量还是很大的，而不开优化的rust的效率的确比较一般。

这个选项并不会影响到本项目内的模块的编译，所以在非优化的编译模式下的代码调试还是没有任何问题的。

２. 整个项目中用的散列表都是`hashbrown::HashMap`/`hashbrown::HashSet`，没有用`std`提供的。这纯属我的个人爱好：前者的速度比后者要优越不少，这在我编写和测试lalr1的时候已经有了明显感受。

其实，从[rust 1.36](https://blog.rust-lang.org/2019/07/04/Rust-1.36.0.html)开始`std`的散列表就已经使用了`hashbrown`的实现，但是后者仍然快一些，这是因为二者选择的散列函数不同，`std`的[SipHash](https://en.wikipedia.org/wiki/SipHash)更慢但抵抗冲突的能力更强，这里不用考虑那么多，快就完事了。

３. `driver`的`test_util.rs`中提供了一些测试用的struct和函数。一次测试的可能结果用`ResultKind`来表示：

```rust
pub enum ResultKind {
  Pass,
  Fail { first_diff: usize, out: String, ans: String },
  IOError(io::Error),
  RuntimeError(PanicInfo),
}
```

其中`Pass`表示通过；`Fail`表示答案错误，并且列出了一些具体的错误内容；`IOError`表示出现了io错误，如输错路径导致找不到文件等；`RuntimeError`表示你的decaf编译器`panic!()`了。

rust反对使用异常来实现一般的控制流，所以`panic!()`通常是不可恢复的错误。尽管如此，rust还是提供了捕获`panic!()`的方法，虽然不像java等支持异常的语言一样方便。具体实现可以查看`test_one_caught`函数，弄不清楚对做实验也没有任何影响，只需要知道，即使在你的代码中触发了`unimplemented!()`或者数组越界之类的异常，也不会导致整个测试框架崩溃，而是会捕获现场的简略信息后被catch住。

如果需要更详细的信息，可以使用`test_one`函数，它不会捕获`panic!()`，所以出现问题时程序会崩溃，并且打印出更详细的信息，方便调试。

我个人更喜欢的一种调试方式是使用`compile`函数，虽然它只负责编译，不会像`test_one`一样还会调用一些其它工具来进一步获得最终结果(只在pa3-5中会这样)，但它的输出结果也非常有参考价值。用于调试时，它的通常使用方式是这样的：

```rust
println!("{:?}", compile(r#"
  // your decaf code here
"#, &Alloc::default(), Pa::[your pa here].to_cfg()));
```

实际的测试结果存储在`TestResult`中，它除了包含外`ResultKind`，还包含了路径信息。它的输出函数非常美观，并且如果配合合适的ide或者插件，输出到控制台中的这些路径都可以直接导航到具体文件中。不过经测试Windows上的颜色显示可能不太正常，如果显示出来了一些奇怪的字符，在调用`test_all`前执行一句：

```rust
colored::control::set_override(false);
```

即可关闭颜色的显示，输出正常的字符。

(当然，如果您非常强，直接一遍全部`Pass`，上面这些都当我没说)
