Stanford Compiler PA2翻译

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

拖了很久，总算继续开始学习这门课程，这次先对PA2进行翻译。

编程作业 II

1.编程项目概述

编程作业II-V将指导您设计和构建Cool编译器。每个作业将覆盖编译器的一个组成部分：词法分析，解析，语义分析和代码生成。每次作业最终会生成一个可以与其他阶段进行交互的编译器工作阶段。您可以选择使用C++或Java来完成项目。

​ 对于这次作业，您将使用词法分析生成器编写词法分析器，也称为扫描器。（C++工具称为flex；Java工具称为jlex。）您将以适当的输入格式描述Cool的token集，词法分析生成器将生成用于识别Cool中token的实际代码（C++或Java）程序。

​ 该项目所需工具的在线文档都可以在课程网站的“其他材料”部分中找到。这包括flex和jlex的手册（在此作业中使用），bison和java_cup的文档（在下一个作业中使用）以及spim模拟器的手册。

Flex允许您通过编写与用户定义的正则表达式匹配的规则并为每个匹配的模式执行指定的操作来实现词法分析器。

2.Flex/JLex简介

Flex允许您通过编写与用户定义的正则表达式匹配的规则并为每个匹配的模式执行指定的操作来实现词法分析器。Flex将您的规则文件（例如”lexer.l”）编译为C（如果您使用的是JLex，则编译为Java）源代码，实现一个自动识别您在规则文件中指定的正则表达式的有限自动机。幸运的是，您无需了解甚至无需查看自动生成的实现规则文件（通常非常混乱）。

​ flex中的规则文件的结构如下：

%{
Declarations
%}
Definitions
%%
Rules
%%
User subroutines

​ 声明（Declarations）和用户子例程（User subroutines）部分是可选的，您可以用C（对于JLex，使用Java）编写声明和帮助函数。 定义（Definitions）部分也是可选的，但通常非常有用，因为定义允许您为正则表达式命名。 例如，如下定义

\ DIGIT [0-9]

允许您定义一个数字。 在这里，DIGIT是正则表达式的名称，该正则表达式与$0$到$9$之间的任何单个字符匹配。下表概述了可以在Flex中指定的常见正则表达式：

$$\begin{aligned} x && 字符"x" \\ “x” && "x”，即使x是运算符。\\ \backslash x && "x”，即使x是运算符。\\ [xy] && 字符x或y。\\ [x-z] && 字符x,y,\ldots, z。\\ [\text{^} x]&& 除x外的任何字符。\\ . && 除换行符外的任何字符。\\ \text{^} x&& 以x为开头的行。\\ <y>x &&当\mathrm{Lex}处于开始条件y时表示x。\\ x $ && x 在行尾。 \\ x? && 可选的x。\\ x * && 0,1,2,...个 x的实例。\\ x +&& 1,2,3，... x的实例。\\ x | y&& x或y。\\ (x)&&一个x。\\ x / y &&一个x，但仅在后跟y的情况下。\\ \{xx\} &&xx在定义部分中的翻译。\\ x\{m,n\} && 出现m至n次x \end{aligned}$$

​ 词法分析器最重要的部分是“规则”部分。如果输入与规则开头的正则表达式或定义匹配，则Flex中的规则指定要执行的操作。通过编写常规C（或Java）源代码来指定要执行的操作。 例如，假设一个数字代表我们语言中的token（请注意，在Cool中情况并非如此），则规则如下：

{DIGIT} {
    cool_yylval.symbol = inttable.add_string(yytext);
    return DIGIT_TOKEN;
}

将数字的值记录在全局变量cool_yylval中，并返回适当的token代码。（有关全局变量cool_yylval的更详细讨论，请参考第5节和第6节；有关上述代码段中使用的inttable的讨论，请参见4.2。）

​ 重要一点是，如果当前输入（即 ，对yylex()的函数调用的结果将匹配多个规则，Flex将选择与最大字符数匹配的规则。 例如，如果您定义以下两个规则

[0-9]+ { // action 1}
[0-9a-z]+ { // action 2}

如果字符序列2a出现在要扫描的文件的下一个，则将执行操作2，因为第二个规则比第一个规则匹配更多的字符。如果多个规则匹配相同数目的字符，则选择在文件中第一个出现的规则。

​ 在Flex中编写规则时，可能有必要根据先前遇到的标记执行不同的操作。例如，在处理注释结束token时，您可能想知道先前是否遇到过注释开始token。跟踪状态的一种显式方法是在声明部分中声明全局变量，当遇到某些感兴趣的token时将其设置为true。Flex还通过使用状态声明来提供语法糖，以实现类似的功能，例如：

%Start COMMENT

可以通过编写BEGIN(COMMENT)将其设置为true。要仅在先前遇到注释时才执行操作，可以使用以下语法在COMMENT上声明规则：

<COMMENT> {
	// the rest of your rule ...
}

​ 还有一个称为INITIAL的特殊默认状态，除非您明确指示新状态的开始，否则该状态为活动状态。您可能会发现此语法对于此作业的各个方面都很有用，例如错误报告。我们强烈建议您在编写自己的词法分析器之前，先阅读Lesk＆Schmidt所写的Lex文档，该文档链接到课程网页上的“其他材料”部分。

3.文件和目录

要开始编程任务，请从OpenClassroom网站下载启动程序代码，并将其解压缩到本地计算机上的目录中。确保下载与计算机体系结构匹配的压缩包。您也可以从“资源”页面单独下载此任务的各个部分，但我们强烈建议您按原样下载并使用完整的tarball。

​ 有了编程作业的工作副本后，请转到当前分配的目录。对于作业的C ++版本，请导航至

[cool root]/assignments/PA2/

对于Java，请导航至

[cool root]/assignments/PA2J/

（请注意路径名中的”J”。）在此目录中输入make将设置工作区并将许多文件复制到您的目录中。该目录中的某些文件是只读的（使用符号链接）。您不应该编辑这些文件，实际上，如果您制作和修改这些文件，可能会发现无法完成作业，请参见README文件中的说明。

您需要修改的文件是：

• cool.flex（在C ++版本中）/ cool.lex（在Java版本中）
  • 此文件包含有关Cool的词汇描述的框架。有一些注释指出了您需要在代码中查找的位置，但这并不一定是一个完整的指南。编程作业的一部分是确保您拥有正确且正常工作的词法分析器。除指示的部分外，欢迎您对我们的框架进行修改。实际上，您可以使用框架的描述来构建扫描器，但是并不能做很多事情。您应该阅读flex/jlex手册，以了解本说明的作用。您希望编写的任何辅助程序都应在相应的部分中直接添加到此文件中（请参阅文件中的注释）。
• test.cl
  • 该文件包含一些要扫描的样本输入。它并没有使用所有的词汇规范，但这仍然是一个有趣的测试。这不是一个适合入手的测试，也不能对您的扫描器提供足够的测试。您的部分任务是提供良好的测试输入和测试策略。（不要觉得这很简单，创建好的测试输入是非常难的，而忘记测试某些东西是评分过程中最可能导致分数损失的原因。）您应该使用您认为足以使扫描仪充分使用的测试来修改此文件。我们的test.cl类似于真实的Cool程序，但您的测试不必如此。 您可以根据需要保留或多或少的测试内容。
• README
  • 本文档包含有关作业的详细说明以及许多有用的技巧。您还应该编辑此文件以包括项目的内容。您应该解释设计决策，为什么您的代码正确，为什么您的测试用例足够。这是作业的一部分，目的是清楚，简洁地解释文本中的内容以及注释您的代码。

尽管这些文件不完整，但词法分析器会编译并运行（make lexer）。

4.扫描器结果

在此作业中，您应按照Cool手册的第10节和图1中的描述，在Cool中定义有效token的适当正则表达式上匹配Flex规则，并执行适当的操作，例如返回token正确类型的代码，在适当的情况下记录词素（lexeme）的值，或者在遇到错误时报告错误。在开始此作业之前，请确保已阅读Cool手册的第10节和图1。 然后研究cool-parse.h中定义的不同标记。您的实现需要定义与正则表达式匹配的Flex/Jlex规则，这些正则表达式定义cool-parse.h中定义的每个标记，并为每个匹配的标记执行适当的操作。例如，如果您在token BOOL_CONST上进行匹配，则词法分析器必须记录其值是true还是false。 同样，如果您匹配TYPEID token，则需要记录类型的名称。请注意，并非每个token都需要存储其他信息。例如，对于某些token（例如关键字），仅返回token类型就足够了。

​ 您的扫描器应该是鲁棒的——可应用于任何可能的输入。例如，您必须处理错误，例如出现在字符串或注释中间的EOF以及过长的字符串常量。这些只是可能发生的一些错误。其余请参见手册。

​ 如果发生致命错误，则必须为正常终止做一些准备。内核转储或未捕获的异常是不可接受的。

内核转储定义：

http://blog.chinaunix.net/uid-20653148-id-1591419.html

4.1 错误处理

所有错误都应传递给解析器。您的词法分析器不应打印任何内容。通过返回一个称为ERROR的特殊错误token，将错误传达给解析器。（请注意，对于此作业，您应忽略称为error的小写token；在PA3中由解析器使用。）报告和恢复词法错误有几个要求：

• 当遇到无效字符（不能作为任何token的开始），则应将仅包含该字符的字符串作为错误字符串返回。在下一个字符处恢复lexing。
• 如果字符串包含未转义的换行符，则将该错误报告为”Unterminated string constant”，并在下一行的开始处继续词法分析——我们假设程序员只是忘记了右引号。
• 如果字符串太长，请在ERROR token中的错误字符串中将错误报告为”String constant too long’’。如果字符串包含无效字符（例如空字符），则将其报告为”String contains null character’’。 无论哪种情况，都应在字符串末尾之后恢复lexing。字符串的末尾定义为
  1. 如果遇到这些错误后发生了未转义的换行符，则表示下一行的开头；
  2. 否则是结束引号(“)后。
• 如果遇到EOF时注释仍处于打开状态，请报告此错误并显示消息”EOF in comment”。不要仅仅因为缺少终止符就标记了注释的内容。同样对于字符串，如果在结束引号之前遇到EOF，则将此错误报告为”EOF in string constant”。
• 如果您在注释之外看到”)”，则将此错误报告为”Unmatched )’’,，而不是将其标记为*和）。

4.2 字符串表

程序趋向于多次出现相同的词素。例如，一个标识符通常在一个程序中被多次引用（否则它不是很有用！）。 为了节省空间和时间，常见的编译器做法是将词素存储在字符串表中。我们为C++和Java提供了一个字符串表实现。有关详细信息，请参见以下各节。

​ 在决定如何处理基本类(Object, Int, Bool, String)，SELF_TYPE和self的特殊标识符时会存在问题，但是直到编译器的后续阶段这个问题才会出现。扫描器应像对待其他标识符一样完全对待特殊标识符。

​ 不要测试整型文字是否在Cool手册中指定的表示形式内，只需创建一个符号，将整个文字的文本作为其内容，而不管其长度如何。

4.3 字符串

扫描器应将字符串常量中的转义字符转换为正确的值。 例如，如果程序员输入入以下八个字符：

$$\begin{array}{|l|l|l|l|l|l|l|l|} \hline " &\mathrm{a} & \mathrm{b} & \backslash & \mathrm{n} & \mathrm{c} & \mathrm{d} &" \\ \hline \end{array}$$

您的扫描器将返回token STR_CONST，其语义值为以下5个字符：

$$\begin{array}{|l|l|l|l|l|l|l|l|} \hline \mathrm{a} & \mathrm{b} & \backslash \mathrm{n} & \mathrm{c} & \mathrm{d} \\ \hline \end{array}$$

其中$ \backslash \mathrm{n}$表示换行符的ASCII字符。

​ 按照Cool手册第15页的说明，对于包含原义null字符的字符串，必须返回错误。但是，允许使用如下两个字符的序列：

$$\begin{array}{|l|l|l|l|l|l|l|l|} \hline \backslash &0 \\ \hline \end{array}$$

应将其转换为一个字符

$$\begin{array}{|l|l|l|l|l|l|l|l|} \hline 0 \\ \hline \end{array}$$

4.4 其他说明

扫描器应保留变量curr_lineno，该变量指示当前正在扫描源文本中的哪一行。此功能将帮助解析器打印有用的错误消息。

​ 您应该忽略token LET_STMT。它仅由解析器（PA3）使用。 最后，请注意，如果词法规范不完整（某些输入没有匹配的正则表达式），则由flex和jlex生成的扫描程序会执行不需要的操作，确保您的说明完整。

5.作业C ++版本的注释

如果您正在使用Java版本，请跳过以下部分。

• 扫描器上的每次调用都会从输入中返回下一个token和词素。函数cool_yylex返回的值是表示语法类别的整数代码（例如，整数文字，分号，if关键字等）。所有token的代码均在cool-parse.h中定义。第二个组件，即语义值或词素，位于YYSTYPE类型的全局联合cool_yylval中。YYSTYPE类型也定义在cool-parse.h中。单个字符token（例如”;”和”,”）的标记仅由字符本身的整数（ASCII）值表示。在Cool手册的Cool语法中列出了所有单个字符标记。
• 对于类标识符，对象标识符，整数和字符串，语义值应存储在字段cool_yylval.symbol中的Symbol。对于布尔常量，语义值存储在cool_yylval.boolean中。除了错误（请参阅下文）外，其他token的词素不携带任何有趣的信息。
• 我们为您提供了一个字符串表实现，在“Cool支持代码导览”和该代码的文档中将对此进行详细讨论。目前，您只需要知道字符串表条目的类型是Symbol。
• 当遇到词法错误时，常规cool_yylex例程应返回token ERROR。语义值是表示错误消息的字符串，该字符串存储在字段cool_yylval.error_msg中（请注意，该字段是普通字符串，而不是符号）。有关错误消息中应该放入的内容，请参见上一节。

6.Java版本的注释

如果您正在处理C++版本，请跳过这一节。

• 扫描器上的每次调用都返回输入中的下一个token和词素。CoolLexer.next_token的方法返回值是类型为java_cup.runtime.Symbol的一个对象。此对象有一个字段，表示标记的语法类别（例如，整型文字、分号、if关键字等）。所有标记的语法代码都在TokenConstants.java中定义。组件、语义值或词素（如果有的话）也被放置在jjava cup.runtime.Symbol对象中。java_cup.runtime.Symbol文档以及其他的支持代码都在课程网页上。其使用的例子也在骨架中给出。
• 对于类标识符、对象标识符、整数和字符串，语义值应为AbstractSymbol类型。对于布尔常量，语义值的类型为java.lang.Boolean。除了错误（见下文），其他标记的词素不包含任何有趣的信息。因为java_cup.runtime.Symbol的值域具有泛型类型java.lang.Object，在调用它的任何方法之前，需要将它转换为适当的类型。
• 我们在AbstractTable.java中为您提供了一个字符串表实现。目前，您只需要知道字符串表条目的类型是AbstractSymbol。
• 当遇到词法错误时，例程CoolLexer.next_token应该返回一个java_cup.runtime.Symbol对象，其语法类别为TokenConstants.ERROR，其语义值为错误消息字符串。 见第4.1节有关如何构造错误消息的信息。

7.测试扫描器

至少有两种方法可以测试扫描器。第一种方法是生成样例输入并使用lexer运行它们，该输出会打印出扫描仪识别的每个token的行号和词素。另一种方法是尝试运行mycoolc来与所有其他编译器阶段（我们提供的）一起调用词法分析器。 这将是一个完整的Cool编译器，您可以尝试任何测试程序。