CS143 PA1

Lexer

整体项目结构

宏观的目录结构如下：

  $ tree cs143 -L 1
  cs143
  ├── assignments
  ├── bin
  ├── etc
  ├── examples
  ├── handouts
  ├── include
  ├── lib
  └── src

cs143 目录包含了所有实验所需的文件，其中：

include 目录包含了实验所需头文件
assignments 目录包含了所有实验所需的源文件，实验过程中只需要修改 assignments 目录下的源文件就可以了
bin 目录包含了部分实验所需的二进制文件，比如 MIPS 模拟器 spim 等
etc 目录包含了一个名为 link-object 的二进制程序
examples 目录包含了一些 cool 语言写的代码示例
handouts 目录包含了实验手册
lib 目录包含了一些 java 的库文件，如果选择使用 C++ 来做实验，可以忽略这个目录
src 目录包含了实验中所有用到的源文件以及一些二进制文件，不太明白这个目录的意义，但是应该可以忽略

assigments 目录结构如下所示：

  $ tree assigments
  assigments
  ├── PA1
  │   ├── Makefile
  │   ├── README
  │   ├── atoi.cl
  │   ├── stack.cl
  │   ├── stack.s
  │   └── stack.test
  ├── PA2
  │   ├── Makefile
  │   ├── README
  │   ├── cool-lex.cc
  │   ├── cool-lex.d
  │   ├── cool-lex.o
  │   ├── cool.flex
  │   ├── handle_flags.cc
  │   ├── handle_flags.d
  │   ├── handle_flags.o
  │   ├── lexer
  │   ├── lextest.cc
  │   ├── lextest.d
  │   ├── lextest.o
  │   ├── mycoolc
  │   ├── stringtab.cc
  │   ├── stringtab.d
  │   ├── stringtab.o
  │   ├── test.cl
  │   ├── test.output
  │   ├── utilities.cc
  │   ├── utilities.d
  │   └── utilities.o
  ├── PA3
  │   ├── Makefile
  │   ├── README
  │   ├── bad.cl
  │   ├── cool-parse.d
  │   ├── cool-tree.aps
  │   ├── cool-tree.cc
  │   ├── cool-tree.d
  │   ├── cool-tree.handcode.h
  │   ├── cool.output
  ...

每一个实验所需的源文件都位于单独的目录中，实验使用 make 作为构建工具。实验提供了标准二进制程序供我们参考，例如PA2中，可以使用 bin/lexer 作为参考程序，当我们实现了自己的词法分析器后，可以对比 bin/lexer 的输出和我们自己写的词法分析器的输出来判断我们的实现是否正确。 examples 目录中有一些 cool 程序可供使用。

Makefile

PA2提供的 Makefile 中，最重要的目标是 lexer ， make lexer 会生成二进制程序 lexer 。除此之外， dotest 目标会使用生成的 lexer 对测试代码 test.cl 做词法分析。

lexer代码分析

从 `main` 函数开始

lexer 的入口位于 lextest.cc:main ，它的作用是不断地对命令行参数提供的 cool 源文件进行词法分析，并打印出得到的 tokens 。主要代码为：

  while ((token = cool_yylex()) != 0) {
    dump_cool_token(cout, curr_lineno, token, cool_yylval);
  }

cool_yylex() 函数会从 fin 文件句柄输入读取字符串（这个功能是在 cool.flex 里通过重新定义 YY_INPUT 宏来实现的），并分析其中的 token ，为了分析不同的文件， main 函数先使用如下代码将文件打开为 fin 文件句柄：

  fin = fopen(argv[optind], "r");

cool_yylex() 函数实际上就是 yylex() 函数（使用宏定义实现函数重命名），而 yylex() 函数是由 flex 生成的。调用 yylex() 函数会去执行 cool.flex 里 rules 中的规则匹配，如果匹配到相应的字符串，会执行对应的 action 。当遇到EOF或者遇到 actions 里的 return 语句后， yylex() 函数返回；当再次调用 yylex() 函数时，会接着分析 fin 中剩余的字符。关于 yylex() 以及 flex 所生成的其他文件细节，请阅读Flex Manual: Ch.9 The Generated Scanner。打印 tokens 是通过 TODO 函数来实现的，这里使用到了名为 TODO 的全局变量，这个变量是在 TODO 定义的，并且在 TODO 头文件中通过 extern 导出。

`flex` 简介

flex 是一款基于 Lex 的词法分析器生成器。它可以用来自动生成用于解析输入流的程序代码。它接受一个词法规则文件作为输入，该文件包含了要匹配的模式以及对应的操作（ action ）。 flex 会根据这些规则生成一个C语言程序，该程序可以读入输入流并根据规则进行匹配和解析。

在 flex 中，用户可以使用正则表达式来描述模式。这些模式可以包括字符、字符集、元字符、子表达式等等。在识别出匹配的模式之后， flex 会执行相应的操作，这些操作可以是输出到文件、修改词法分析器状态等等。用户也可以使用自定义的C代码来替代 flex 生成的默认操作（默认操作是将匹配到的模式输出到标准输出中）。

flex 的内部实现是基于 DFA（Deterministic Finite Automaton，确定有限状态自动机） 算法的。 DFA 是一种表示正则表达式的图形化方法，它将每个正则表达式都转化为一个有限状态自动机。在词法分析的过程中， flex 将输入文本逐个字符地与 DFA 中的状态进行匹配，直到匹配到一个终止状态，即可确定匹配到的单词类型。

flex 的内部实现包括两个主要部分：扫描器生成器和扫描器。扫描器生成器是用于生成自定义的词法分析器的工具，它将 flex 输入的规则转化为C语言程序。扫描器是由生成器生成的C语言程序，它接收输入文本并对其进行词法分析，返回匹配到的单词类型和相应的值。

在实现中， flex 使用了许多技术来提高词法分析的性能和效率，例如快速字符串匹配算法、状态压缩、缓存等等。这些技术使得 flex 能够快速地处理大量的输入数据，并生成高效的词法分析器。

充分利用 `flex` 这一工具

flex 常用于编译器和解释器的开发中，它可以生成高效且可靠的词法分析器，帮助程序员简化词法分析的实现过程。

在PA1中，我们使用 flex 来实现语法分析器。

使用 flex 进行词法分析的一般步骤如下：

定义词法规则：使用正则表达式定义词法单元（token）的模式和匹配规则。例如，可以定义一个词法规则，使得在输入文本中匹配到数字串时识别出它是一个数字类型的词法单元。
生成词法分析器代码：使用flex工具将词法规则文件转化为C语言词法分析器代码。
编译和链接：将生成的C语言词法分析器代码编译成可执行程序，并将其链接到主程序中。
运行程序：输入要分析的文本，词法分析器会根据预定义的规则逐个识别单词，并输出匹配到的词法单元类型和值。

下面是一个简单的例子，用于匹配最简单的算术表达式：

定义词法规则（.flex）文件

  %{
  #include <stdio.h>
  %}

  %%
  [0-9]+     { printf("NUMBER %s\n", yytext); }
  [-+*/()]  { printf("OPERATOR %c\n", yytext[0]); }
  [ \t\n]    { /* ignore whitespace */ }
  .          { printf("INVALID %c\n", yytext[0]); }
  %%

  int main() {
      yylex();
      return 0;
  }

使用 flex 生成词法分析器代码（C语言代码）：
```
  $ flex lexer.flex
```
上述命令会生成名为 lex.yy.c 的文件。
编译并链接生成的C文件：
```
  $ gcc -o lexer lex.yy.c -lfl
```

运行程序：

  $ ./lexer < input.txt

其中， input.txt 内容如下：

  1 + 2 * 3 - (4 / 2)

运行程序后会得到如下输出：

  NUMBER 1
  OPERATOR +
  NUMBER 2
  OPERATOR *
  NUMBER 3
  OPERATOR -
  OPERATOR (
  NUMBER 4
  OPERATOR /
  NUMBER 2
  OPERATOR )

为了使用 flex 对 cool 程序进行词法分析，需要定义 cool 的词法规则。

我们要做的任务

我们要做的任务主要是使用 flex 对 cool 的词法规则进行说明。

编写词法规则的一般步骤如下：

使用正则表达式定义词法单元的模式和匹配规则。
将每个模式与对应的动作（action）关联起来。动作是在匹配到相应模式时要执行的C语言代码。
在规则文件的头部声明C语言头文件和其他需要使用的库或函数。
在规则文件的主体部分定义每个词法单元的模式和对应的动作。

flex 的规则及动作编写方法细节请参考手册。

以 INT_CONST 为例，需要先在 lexer.flex 文件的 definitions 部分使用正则表达式定义整数的模式，接着在 rules 部分定义匹配到 INT_CONST 后该执行什么操作。从 lexer.flex 截取出的代码如下：

  %{
  ...
  %}

  ...
  DIGIT  [0-9]

  %%

  {DIGIT}+  {
    yylval.symbol = inttable.add_string(yytext);
    return INT_CONST;
  }

  %%

  ...

我们在 definitions 部分定义了 DIGIT 的模式为0-9的数字，并在 rules 部分说明了，匹配到若干个 DIGIT （ {DIGIT}+ ）后，调用 add_string 函数将 yytext 添加到 inttable 中，同时设置全局变量 yylval.symbol 为这个 token 的指针，方便后面使用；最后返回这个 token 的类型 INT_CONST 。 flex 实际上会把我们这里编写的 rules 代码原封不动地粘贴到 yylex 函数中，也就是说，在我们调用 yylex 函数的时候，如果匹配到 {DIGIT}+=， =yylex 函数会返回 INT_CONST 。（所以在 lextest.cc 的 main 函数中，其实是在不断地执行 yylex() 函数来获取每一个 token ）

接着，只需要按照上述方式把其他规则描述出来即可。这里就不贴其他的规则实现了。