StepByStep上海交通大学计算机系编译原理课程设计钱风@上海交通大学计算机科学与工程系E-mail:shinyflute@gmail.com2005年8月第一版最后更新2005年9月8日CompilerStepByStep上海交通大学ACM试点班编译原理课程设计StepByStepCourseDesigninCompilerTheoryFengQian@SJTUDepartmentofComputerScienceandEngineeringE-mail:shinyflute@gmail.comFirstEdition:Aug2005LastUpdate:Sep8,2005-2-CompilerStepByStep上海交通大学ACM试点班编译原理课程设计目录第0部分项目概览50.1项目目标50.2主要步骤50.3Tiger语言语法概要5第1部分词法分析71.1Tiger.flex清单71.2Jflex的使用101.3本阶段的主要困难10第2部分语法分析第3部分抽象语法树112.1Symbol包112.2Absyn包112.3Grm.Cup清单132.4JavaCup的使用192.5词法分析器与文法分析器的连接202.6本阶段的主要困难20第4部分语义分析224.1入口(Entry)224.2tEnv和vEnv224.3Type包234.4语义分析的一般步骤254.5具体表达式/声明/变量的检查264.6本部分中与中间代码生成有关的问题30第5部分活动记录325.1Frame的结构和函数调用步骤325.2抽象的Frame325.3用于Mips机的Access-InFrame和InReg335.4用于Mips机的Frame–Mips.MisFrame345.5层(Level)385.6ProcEntryExit总结38第6部分中间代码生成406.1中间代码406.2Translate包中的表达式416.3Ex,Cx和Nx426.4段(Frag)48-3-CompilerStepByStep上海交通大学ACM试点班编译原理课程设计6.5翻译成IR树的一般过程496.6具体翻译过程49第7部分规范化55第8部分指令选择568.1常用MIPS汇编指令568.2MIPS中的寄存器568.3Assem.Instr数据类型578.4生成汇编指令588.5寄存器的临时表示648.6MIPS汇编语言语法65第9部分活性分析与寄存器分配679.1抽象的图结构679.2流图679.3活性分析689.4干扰图699.5寄存器分配719.6把以上步骤联起来749.7本部分中的类关系图74第10部分使成为整体7610.1错误报告7610.2编译器的输入和输出7610.3编译全过程7610.4函数声明、调用的翻译7810.5汇编源程序在虚拟机上的运行79第11部分FAQ81第12部分附录8412.1主要类图8412.2压缩包内容8412.3编译器使用方法8612.4一个范例8612.5参考资料和工具89-4-CompilerStepByStep上海交通大学ACM试点班编译原理课程设计第0部分项目概览0.1项目目标制作Tiger语言编译器0.2主要步骤1.词法分析(LexicalAnalysis):把Tiger源程序分割成符号(单词),要求制作自动机文件,词法分析程序由工具JFlex生成2.语法分析(SyntaxParsing):识别程序的语法结构,检查语法错误,要求制作文法文件,语法分析程序由工具JavaCup生成3.抽象语法树(AbstractSyntaxTree):根据语法结构生成抽象语法树4.语义分析(SemanticAnalysis):进行变量和类型检查等5.活动记录(ActivationRecord):与函数调用相关的活动记录6.中间代码生成(IntermediateCode):生成中间表示树(IRTrees),它与程序和机器语言无关7.规范化(Canonicalize):优化表达式、条件分支等,只需复制代码8.指令选择(InstructionSelection):生成基本的MIPS汇编指令9.活性分析与寄存器分配(LivenessAnalysisandRegisterAllocation)10.使之成为整体:生成完整的编译器程序0.3Tiger语言语法概要类型:整数int字符串string数组arrayofi