编译原理 第1章 绪论

第1章绪论编译原理CompilerPrinciples张丽第1章绪论教材：《编译原理教程》(第三版)胡元义，西安电子科技大学出版社,2010年讲授：45学时实验：9学时第1章绪论课程的性质与任务本课程属于计算机科学与技术专业的一门重要的专业必修课。通过本课程学习，使学生掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法，各种语法分析技术和中间代码生成、符号表的构造、代码优化、运行时存储空间的组织等基本方法和主要实现技术。第1章绪论编译原理（内容）第1章绪论（2学时）第2章词法分析（6+2学时）第3章语法分析（18+2学时）第4章语义分析和中间代码生成（4+2学时）第5章代码优化（4+2学时）（4+2学时）第6章目标程序运行时存储空间组织（0学时）第7章目标代码生成（2学时）第8章符号表与错误处理（0学时）复习辅导（1学时）第1章绪论学习建议编译原理课程是计算机专业的专业课程，由于讨论的是程序的实现问题，并且涉及到形式语言的有关内容，相对于其它专业课程来说，有一定的难度，但并非高不可攀，只要认真对待、用心去学，同样会在学习的过程中感受到探索的无穷乐趣！第1章绪论•一定要预习：因课程有很强的理论性；•上课专心致志：有许多问题是前后有连贯性的，中断后难以接续，增加课后负担；•充分利用答疑：自学是一种很好的学习方法，对个人学习能力的提高很有帮助。在本课程的学习过程中，利用答疑的机会与教师充分地讨论，将会给同学们的学习节省很多宝贵时间；重视习题：本课程讲述的一些具体方法，常常涉及到很多知识，不通过练习，很难真正全面地掌握。所以，建议同学们独立完成每章给定的习题，同学们将会发现，练习会加深对课程内容的理解，在本课程的学习中尤其如此；第1章绪论•确立好学习的角度：在学习的过程中，同学们应站在编译程序的实现者的角度来看问题，而不仅仅是为了掌握课程的知识点，并且尽可能从编译程序的全局来把握问题，这对同学们理解各知识点会有很大的帮助；•重视实习：实习是深入理解课程内容的一个好帮手。在课程学习的过程中，通过自己的努力完成编译的一部分功能，不仅会让同学们深刻理解编译程序的工作原理，而且会让同学们有一种成就感，有助于同学们提高对本课程的学习信心。另外，在目前的学习阶段，较大的编程任务不多，本课程的实习正好可以实践程序设计语言课程所学的编程方法，锻炼一下自己的编程能力。急功近利是学习的一大敌人。有很多课程的学习都是对我们解决问题的能力的一种训练，在学习过程中不一定能马上看到它的作用。编译原理就是这样的一门课。由于本课程涉及程序的实现，所以对本课程的深刻理解，将有助于同学们今后对本专业许多问题的理解。第1章绪论第1章绪论1.1程序设计语言和编译程序1.2编译程序的历史及发展1.3编译过程和编译程序结构1.4编译程序的开发1.5构造编译程序所应具备的知识内容第1章绪论1.1程序设计语言和编译程序为了处理和解决实际问题，每一种计算机都具有其特定的功能，而这些功能是通过计算机执行一系列相应的操作来实现的。计算机所能执行的每一种操作称为一条指令，计算机能够执行的全部指令集合就是该计算机的指令系统。由于计算机硬件的器件特性，决定了计算机本身只能直接接受由0和1编码的二进制指令和数据，这种二进制形式的指令集合称为该计算机的机器语言，它是计算机惟一能够直接识别并接受的语言。第1章绪论用机器语言编写程序很不方便且容易出错，编写出来的程序也难以调试、阅读和交流。为此，出现了用助记符代替机器语言二进制编码的另外一种语言，这就是汇编语言。汇编语言是建立在机器语言之上的，因为它是机器语言的符号化形式，所以较机器语言直观；但是计算机并不能直接识别这种符号化语言，用汇编语言编写的程序必须翻译成机器语言之后才能执行，这种“翻译”是通过专门的软件——汇编程序实现的。第1章绪论尽管汇编语言与机器语言相比在阅读和理解上有了长足的进步，但其依赖具体机器的特性是无法改变的，这给程序设计增加了难度。随着计算机应用需求的不断增长，出现了更加接近人类自然语言的功能更强、抽象级别更高的面向各种应用的高级语言。高级语言已经从具体机器中抽象出来，摆脱了依赖具体机器的问题。用高级语言编制的程序几乎能够在不改动的情况下在不同种类的计算机上运行且不易出错，这是汇编语言难以做到的，但高级语言程序翻译（编译）成最终能够直接执行的机器语言程序的难度却大大增加了。第1章绪论由于汇编语言和机器语言一样都是面向机器的，故相对于面向用户的高级语言来说，它们都称之为低级语言，而FORTRAN、PASCAL、C、ADA、Java这类面向应用的语言则称之为高级语言。因此，编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序，见图1–1。第1章绪论图1-1编译程序的功能高级语言程序(源程序)编译程序计算机低级语言程序(目标程序)第1章绪论一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，如图1–2所示。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。第1章绪论图1-2源程序的编译和运行阶段源程序(高级语言)编译程序计算机目标程序(机器语言)编译阶段初始数据目标程序计算机运行系统计算结果运行阶段第1章绪论如果编译生成的目标程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段，它将编译生成的汇编语言目标程序再经过汇编程序变换成机器语言目标程序，如图1–3所示。第1章绪论图1–3源程序的编译、汇编和运行阶段源程序(高级语言)编译程序计算机目标程序(汇编语言)汇编程序计算机目标程序(机器语言)运行系统计算机计算结果初始数据编译阶段汇编阶段运行阶段第1章绪论用高级语言编写的程序也可通过解释程序来执行。解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行，如图1–4所示。解释程序与编译程序的主要区别是：编译程序是将源程序翻译成目标程序后再执行该目标程序，而解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。典型的解释型高级语言是BASIC语言。第1章绪论图1-4解释程序解释执行过程的示意源程序(高级语言)初始数据解释程序计算机计算结果第1章绪论1.2编译程序的历史及发展第1章绪论1.3编译过程和编译程序结构编译程序的工作过程是指从输入源程序开始到输出目标程序为止的整个过程，此过程是非常复杂的。一般来说，整个编译过程可以划分成五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段。第1章绪论1．词法分析词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号，如基本字(if、for、begin等)、标识符、常数、运算符和界符(如“()”、=”、“；”)等，将所识别出的单词用统一长度的标准形式（也称内部码）来表示，以便于后继语法工作的进行。因此，词法分析工作是将源程序中字符串变换成单词符号流的过程，词法分析阶段工作遵循的是语言的构词规则。第1章绪论词法分析position:=initial+rate*60;单词类型单词值标识符1(id1)position运算符(赋值):=标识符2(id2)initial运算符(加)+标识符3(id3)rate运算符(乘)*常数（整数）60界符（分号）；第1章绪论又如一个C源程序片断：inta;a=a+2;词法分析后可能返回:单词类型单词值基本字（保留字）int标识符(变量名)a界符;标识符(变量名)a运算符(赋值)=标识符(变量名)a运算符(加)+常数2界符；第1章绪论2．语法分析语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号流分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子（语句）”、“程序段”和“程序”。通过语法分析可以确定整个输入串是否构成一个语法上正确的“程序”。语法分析所遵循的是语言的语法规则，语法规则通常用上下文无关文法描述。第1章绪论语法分析功能:依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).position:=initial+rate*60;规则赋值语句::=标识符“:=”表达式表达式::=表达式“+”表达式表达式::=表达式“*”表达式表达式::=“(”表达式“)”表达式::=标识符表达式::=整数表达式::=实数第1章绪论赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*第1章绪论id1:=id2+id3*N:=+N60*id1Positionid2initialid3rate第1章绪论3．语义分析和中间代码生成这一阶段的任务是对各类不同语法范畴按语言的语义进行初步翻译，包含两个方面的工作：一是对每种语法范畴进行静态语义检查，如变量是否定义、类型是否正确等；二是在语义检查正确的情况下进行中间代码的翻译。注意，中间代码是介于高级语言的语句和低级语言的指令之间的一种独立于具体硬件的记号系统，它既有一定程度的抽象，又与低级语言的指令十分接近，因此转换为目标代码比较容易。把语法范畴翻译成中间代码所遵循的是语言的语义规则，常见的中间代码有四元式、三元式、间接三元式和逆波兰记号等。第1章绪论中间代码生成id1:=id2+id3*60(1)(inttoreal,60，-，t1)(2)(*,id3，t1，t2)(3)(+,id2，t2，t3)(4)(:=,t3，-，id1)第1章绪论4．优化优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效（节省时间和空间）的目标代码。常用的优化措施有删除冗余运算、删除无用赋值、合并已知量、循环优化等。例如，其值并不随循环而发生变化的运算可提到进入循环前计算一次，而不必在循环中每次循环都进行计算。优化所遵循的原则是程序的等价变换规则。第1章绪论代码优化id1:=id2+id3*60(1)(inttoreal，60，-，t1)(2)(*，id3，t1，t2)(3)(+，id2，t2，t3)(4)(:=，t3，-，id1)变换（1）(*，id3，60.0，t1)(2）（+，id2，t1，id1)第1章绪论5．目标代码生成这一阶段的任务是把中间代码（或经优化处理之后）变换成特定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作。最后阶段的工作因为目标语言的关系而十分依赖硬件系统，即如何充分利用机器现有的寄存器，合理地选择指令，生成尽可能短且有效的目标代码，这些都与目标机器的硬件结构有关。第1章绪论目标代码生成(*,id3，60.0，t1)(+,id2，t1，id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1第1章绪论上述编译过程的五个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这五个阶段的任务分模块进行设计。编译程序的结构示意如图1–5所示。第1章绪论图1–5编译程序结构示意表格管理词法分析器语法分析器语义分析与中间代码生成器优化目标代码生成器出错处理源程序目标程序单词符号语法单位四元式四元式第1章绪论编译过程中源程序的各种信息被保留在不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，编译过程的绝大部分时间是用在造表、查表和更新表格的事务上，因此，编译程序中还应包括一个表格管理程序。出错处理与编译的各个阶段都有联系，与前三个阶段的联系尤为密切。出错处理程序应在发现错误后，将错误的有关信息如错误类型、出错地点等向用户报告。此外，为了尽可能多地发现错误，应在发现错误后还能继续编译下去，以便发现更多的错误。第1章绪论一个编译过程可分为一遍、两遍或多遍完成，每一遍完成所规定的任务。例如，第一遍只完成词法分析的任务，第二遍完成语法分析和语义加工工作并生成中间代码，第三遍再实现代码