EECE 6083/5183编译器项目
1编译器项目
类项目是手工构建一个简单的递归体面（LL（1））编译器（不使用编译器诸如flex或antlr的构造工具）。你可以使用任何支持递归的命令式块结构编程语言，我可以为它安装一个标准的debian包在我的电脑上测试你的解决方案。学生在本课程中使用的语言示例包括：c、c++、go、rust、java和python。如果你不确定你想要的编程语言是否可以，请与我核实。虽然你可以使用多种语言，但你不能使用任何语言特征来构建编译器子系统（正则表达式解析器，等也就是说，我鼓励您使用这些更复杂的内置据结构诸如哈希表之类的语言。同样，如果你对自己能做什么和不能做什么有疑问，请问。除了向我发送您的编译器源代码和构建环境之外，我还可以在Linux工作站（您有责任确保它将构建在标准的Linux盒子上；如果如果你在Haiku这样的奇异系统上构建它，我们可以在那个平台上讨论一个演示），你必须还可以提交一份一页的报告来记录编译器。它应该记录您的软件结构、构建过程和正确实现的语言功能以及编译器中未完成的那些元素。最后，报告还应强调您在系统中实现的任何独特功能。我将编译器项目分为5个开发阶段，最后期限分散整个课程学期。虽然这些最后期限很软，但我将使用您的历史记录为你的期末成绩分配加号/减号。我鼓励你尝试
尽早完成这些阶段。2024年1月2日-12:28 1EECE 6083/5183编译器项目
2词汇分析：扫描仪
2.1代币词法分析包括将输入语言中的字符串转换为标记。这是一位代表标记的对象类型示例。
//全局可见的枚举（lexer和解析器都需要
枚举标记类型={PLUS，MINUS，IF_RW，LOOP_RW，END_RW，L_PAREN，R_PAREN，L_BRACKET，R_BRACKET，数字，标识符｝类标记
标记类型：tt
tokenMark:tm
结束类令牌标记可以是记录关于令牌的次要信息的复杂数据类型。对于许多令牌类型（例如PLUS），不需要令牌标记数据，令牌类型值完全表征令牌。对于其他令牌类型（例如IDENTIFIER），令牌标记将包含用于表征所述令牌的附加信息；最初，这主要是为了保存一个标识符字符串，但稍后它很可能包含有关复杂类型（如函数/过程）的信息以及它们的参数列表签名/返回类型等。在某些系统中，编译器可能会将算术运算符、关系运算符、乘法器运算符等转换为通用的令牌类型，以及使用令牌标记来记录所表示的令牌类的特定成员。
2.2支持功能/对象有一些关键的支持函数可以使编译器的构建更加容易；尤其是如果您用一个强大的API封装它们，该API允许对底层进行重组/扩展实施我将把这些支持功能分为三个部分：（I）输入处理，（ii）以及（iii）符号表管理和保留字设置。低于I将为这些组成部分中的每一个提出建议。您不需要设置解决方案这样，这些只是我给你的建议。我将在在面向对象的基础上，您不需要设置/使用面向对象的语言，这只是一个方便我提出想法的方式。
2.2.1输入处理
我建议您创建一个对象来管理输入文件设置和位置记录（当前正在处理文件中的哪一行）。这对这个项目来说可能有点多，但是它有助于封装与正在处理的输入文件相关的内容。建造它是个好计划就好像你转向了一种更复杂的语言，在这种语言中处理多个文件，同时处理指定的输入文件，很容易有一堆文件点/行计数变量记录系统处理所需各种文件的位置。
2024年1月2日-12:28 2
EECE 6083/5183编译器项目通常，lineCnt变量将用于记录扫描仪在输入文件中的哪一行正在进行中。在此项目中，此值主要用于帮助生成有意义的错误消息。
类inFile私有的
file:filePtr=null//输入文件
string:fileName
int:lineCnt=0//行计数；初始化为零
平民的
bool:attachFile（string）//打开命名文件char:getChar（）//获取下一个字符
void：ungetChar（char）//将字符推回输入文件字符串void：incLineCnt（）
void：getLineCnt（）
结束类
2.2.2警告和错误报告
主程序应该有一个用于报告错误和警告的对象。理想情况下，这些功能将使用标准格式（例如。，https://gcc.gnu.org/onlinedocs/gcc-3.3.6/gnat_ug_unx/Output-and-Error-Message-Control.html例如，emacs可以用来自动将文本编辑器/IDE定位到正确的文件以及与警告/错误相对应的行号。API对此非常简单。分类报告
私有的
bool:errorStatus=False//如果编译器发现错误，则为true平民的
void reportError（char*消息）void reportWarning（char*消息）bool getErrorStatus（）
结束类
当编译器试图在同时存在错误和警告的情况下继续时
条件通常会导致编译器只进行解析和类型检查阶段；
的解析中遇到错误时，不应进行代码优化和生成
输入程序。通常，reportError函数会设置私有变量errorStatus为True。
2.2.3符号表管理/保留字
大多数编译器将使用输入文件中所见符号的哈希表；这被称为符号表。这些符号将是标识符和函数。这也是一个方便的地方2024年1月2日-12:28 3
EECE 6083/5183编译器项目
删除语言中保留单词的条目（如if、loop、end等）。符号当您构建编译器的后面部分时，表将被修改和扩展，因此必须您可以通过和API保持对其设置的访问权限，以便轻松修改其实际实现后来hashLook函数将查找符号表并返回字符串的标记论点如果这是该字符串第一次出现符号表条目，则新的
条目是使用默认的令牌定义（通常为IDENTIFIER）创建的。类符号表
私有的
hashTable＜token＞：符号选项卡
平民的
token:hashLook（string）//在哈希表中查找字符串void：setToken（string）//更改此符号的标记值结束类
通常，lexer将查找符号表中的每个候选标识符字符串，并返回存储在该字符串的符号表中的令牌。因此，为了让生活更轻松，一个好主意是用保留的字符串预先设置符号表，并为每个字符串设置令牌，以便在返回标记IDENTIFIER时，代 写EECE 6083/5183编译器项目将返回该保留字的正确标记。因此在开始处理文件之前，您将构建一个简单的外观来迭代保留的以便用保留的字标记初始化符号表。
常量
因此，有时会出现这样一个问题，即我们如何处理词汇中的字符串和数值分析阶段。对此没有统一的答案。你可以把它们：（i）直接当作令牌，（ii），将它们注册到符号表中，或者，（iii）构建一个单独的字符串/数字表1到
存储项目的令牌表示。如果我们假设令牌的lexer匹配字符串为存储为变量tokenString中的ASCII字符串，然后lexer的示例返回代码这些选项中的每一个都可以概括为（显示STRING令牌和INTEGER代币
（i） 返回新的令牌（STRING，tokenString）返回新的令牌（INTEGER，atoi（tokenString））（ii）tok=symbolTable.hashLook（tokenString）if（tok.tt！=字符串）｛tok.tt=字符串｝返回tok
tok=symbolTable.hashLook（tokenString）1两者都有一个通用的常量表，或者有两个单独的表，一个用于字符串，一个用作数字是可能的。
2024年1月2日-12:28 4
EECE 6083/5183编译器项目
if（tok.tt！=整数）｛tok.tt=整数｝//可选地，我们还可以构建/向令牌添加整数值
返回tok
（iii）返回新的令牌（STRING，constantTable.hashLook（tokenString））返回新的token（INTEGER，constantTable.hashLook（tokenString））当然，在这个编码示例中有许多变体。使用符号表的选项或者单独的常量表是压缩最终存储映射的好方法。也就是说，如果你储存在符号表中，则（在每个范围内）公共常量将表示为一项其必须在代码生成阶段期间被映射到存储器中。如果相反，您存储所有常量表中的常量超过了所有范围，您可以潜在地减少存储映射尺寸更大防止发生。
扫描仪应该识别的标记是在项目语言规范中找到的标记。我还建议定义字符类来简化扫描仪的定义。在里面
简而言之，这意味着您应该定义一个数组，该数组由映射ASCII字符转换为字符类。例如，将所有数字[0-9]映射到数字中字符类，将字母[a-zA-Z]转换为字母字符类，等等（当然你必须在某些枚举类型中定义字符类。我会在课堂上为你复习更多。我将保留本节的其余部分；它来自的早期版本
这份文件可能对您有帮助，也可能对您没有帮助。
虽然扫描仪可以被构造为分别识别保留字和标识符，
我强烈建议您将它们折叠在一起，作为扫描仪和种子中的常见案例具有保留字的符号表及其对应的令牌类型。更确切地说，我建议您在最初的扫描仪实现中加入一个基本的符号表。而符号表条目的数据类型可能会随着构建其他功能，最初您可以让符号表条目记录令牌
2024年1月2日-12:28 5
EECE 6083/5183编译器项目
键入并具有指向标识符/保留字的字符串的指针。例如，每个元素在符号表中可以具有以下结构：
sym_table_entry:记录
token_type:token_TYPES；
token_string：*char；
结束记录
其中，TOKEN TYPES是所有令牌类型的枚举类型。在操作上，我将构建符号表，以便使用令牌类型创建新条目字段初始化为IDENTIFIER。然后，您可以使用扫描仪的初始化方法中的保留字为符号表种子（在上述扫描仪初始化步骤期间）。最容易这样做的方法是设置一个保留字及其标记类型的数组。然后穿过数组，对每个保留的字符串进行哈希查找，并将令牌类型字段更改为指定的令牌类型。我们将在课堂上复习这个。
2024年1月2日-12:28 6
EECE 6083/5183编译器项目
3解析器
构建一个递归的体面解析器，它只关注下一个令牌来控制解析。也就是说，根据其他地方给出的项目编程语言规范构建LL（1）解析器在这些网页中。如果你真的更喜欢构建一个LALR解析器，这是可能的，但请先和我讨论一下。解析程序应该至少有一个重新同步点，以便尝试从解析错误中恢复。2024年1月2日-12:28 7EECE 6083/5183编译器项目
4型式检查将类型检查合并到解析器中，并在语句已解析。您主要关心的是作用域和类型匹配。至少对于表达式和语句，现在必须扩展解析规则才能返回的类型结果构造刚刚解析。上层规则将使用该类型信息在其数量必须构造包含作用域数据的完整符号表。你必须能够定义一个范围并在进行解析时删除一个范围。您可以通过嵌套符号表，或通过将符号表中的条目链接在一起并放置范围入口点可用于控制解析器离开作用域时如何删除号。
2024年1月2日-12:28
EECE 6083/5183编译器项目
5代码生成代码生成有两个选项。第一个（也是推荐的）选项是使用LLVM后端优化器和代码生成器。在这种情况下，您的代码生成阶段实际上是转换为LLVM中间形式（驻留在内存中的IR或LLVM程序集）。第二种选择是生成一个文件，其中包含所记录的受限C程序空间在下面
5.1生成C
基本上，生成的文件应该有内存空间、寄存器空间和平面C（没有子例程），goto用于围绕生成的C文件进行分支。您生成的C必须遵循加载/存储体系结构的风格。您可使用寄存器文件大小可根据您的最大需要和通用的2地址指令格式。你不必担心寄存器分配问题，不应该从表达式中结转寄存器/变量的使用表达。因此，一个程序有两个表式：
c:=a+b；
d:=a+c+b；
会产生类似的东西：
//c:=a+b；
R[1]=毫米[44]；//假设变量a位于MM位置44R[2]=毫米[56]；//假设变量b位于MM位置56R[3]=R[1]+R[2]；
MM[32]=R[3]；//假设变量c位于MM位置32//d:=a+c+b；
R[1]=毫米[44]；
R[2]=毫米[32]；
R[3]=R[1]+R[2]；
R[4]=毫米[56]；
R[5]=R[3]+R[4]；
MM[144]=R[5]；//假设变量d位于MM位置144您还可以使用寄存器外的间接寻址来定义要加载到寄存器中的内存位置。例如，您的代码生成器可以生成如下内容：
R[1]=毫米[R[0]+4]；
您可以为特定的堆栈操作（指针）静态地分配/分配一些寄存器。堆栈必须构建在您的内存空间中。对于条件分支（goto），可以将if语句与then子句一起使用，但不能与一起使用其他条款。此外，在if之前，必须将条件评估为真/假（0/1）语句，以便if语句中的条件仅限于与true/false的简单比较。因此，对于条件分支，只允许if语句的种形式：2024年1月2日-12:28 9EECE 6083/5183编译器项目如果（R[2]＝true），则转到标签；代码生成器输出一个受限形式的C，看起来很像3地址加载/存储建筑学您可以假设一组无限制的寄存器，一个64M字节的内存空间，包含静态内存和堆栈内存的空间。你的机器代码应该看起来像（我忘记了C语法，所以你可能不得不把它翻译成正的C）：Reg[3]=MM[Reg[SP]]；
Reg[SP]＝Reg[SP]{2；
Reg[4]=MM[12]；//假设为静态
//变量在
//位置12
Reg[5]=Reg[3]+Reg[4]
MM[12]=Reg[5]；
您必须使用简单的C:赋值语句、goto语句和if语句。无程序、切换语句等。您必须计算“if语句”中的条件表达式，并简单地引用结果（存储在寄存器中）在生成的C代码的if语句中。
基本上，您应该生成看起来像简单的3地址汇编语言的C代码。5.2生成LLVM程序集
请参阅LLVM的其他讲义。
5.3激活记录
请参阅其他关于代码生成和图1的课堂讲稿。
2024年1月2日-12:28 10
EECE 6083/5183编译器项目
FP
服务提供商
返回地址
arg 2
局部变量1
局部变量2
arg 1
返回值ptr
旧SP
旧FP
旧FP
旧SP
FP：帧指针
SP:堆栈指针激活记录k+1激活记录k
上一个
下一个
上一个
下一个
激活记录k激活记录k+1当前激活记录图1：激活记录的调用链；左侧为堆栈模型，右侧为堆模型2024年1月2日-12:28 11
EECE 6083/5183编译器项目
6运行时
如果您使用的是LLVM基础设施，则可以使用libc支持的gets、put、atoi等用作运行时系统。这意味着您最终不会编写运行库除了使代码生成器适应libc标准的接口之外。对于运行时环境，应输入运行时函数名称和类型签名在开始解析输入文件之前，请先将其插入到符号表中。为这些生成代码函数，您可以对它们进行特殊处理并使用C函数调用，也可以使用静态（手写）带有预定义标签的程序（手写代码上的C代码调用您的库函数）可以转到。第二种选择听起来更困难，但可能更容易实现，因为它在代码生成器中不是特殊情况。运行时支持提供了几个（全局可见）预定义过程环境中描述的功能，即在