编译原理第一章习题答案

编译原理电子教案第一章绪论谢强计算机科学与技术学院13851481944[e-mail]上一页下一页2课程简介编译原理是一门理论与实践相结合的计算机科学技术学科的专业基础课，是计算机科学技术专业学生的必修课程。编译器的编写涉及到程序设计语言、计算机体系结构、语言理论、算法和软件工程等学科，是计算机科学技术的重要基础。另外，编译原理课程中蕴涵着许多计算机学科中解决问题的思路、抽象问题和解决问题的方法，这对计算机科学技术专业的学生今后学习其它专业课程和从事科研工作非常重要。课程主要介绍程序设计语言编译程序构造的一般原理、基本设计方法和主要实现技术。课程内容主要包括：编译过程和编译程序的结构，文法的构造，正规表达式与有限自动机的等价性，有限自动机的确定化和最小化，消除文法的左递归和回溯，递归下降子程序的构造，预测分析表的构造，算符优先分析表和优先函数的构造，LR分析表的构造，属性的计算，表达式和控制语句的翻译，名字的作用范围和栈式存储分配的实现，DAG表示及其应用，循环优化等。上一页下一页3前修课程、能力和知识结构要求本课程的先修课程包括：离散数学Ⅰ(1)，离散数学Ⅰ(2),计算机科学导论，程序设计语言Ⅰ(1)，程序设计语言Ⅰ(2)，数据结构等，学生通过上述课程的学习需要熟悉计算机的基本结构，具有分析问题和进行形式化思维的能力，掌握高级程序设计语言和数据结构。上一页下一页4课程结构说明课程内容分为四大部分：词法分析、语法分析、语义分析及中间代码的产生、优化。主要内容包括为：文法、有限自动机、词法分析、LL(1)分析、算符优先分析、LR分析、属性文法及语法制导的翻译、中间语言及高级语言主要语句的翻译、运行时存储空间的组织、中间代码的优化等。课程主要以课堂教学为主，动手实践为辅，其中词法分析和语法分析分别安排上机实验。上一页下一页5课程考核形式与要求课程考核采用闭卷考试方法，考核成绩由平时成绩+上机+考试组成，其中平时成绩包括考勤、上课情况和作业情况，分数可以以平时成绩（20%）+上机（10%）+考试（70%），可以根据实际情况略做调整。重点在于考查学生对主要知识的理解和灵活应用，试题中一般不会出现识记题。考试的重点在于词法分析、语法分析（自上而下、自下而上），知识单元分数分配大致为：绪论5%，文法15%，词法分析20%，语法分析30%，语义分析15%，存储空间的组织5%，优化10%。上一页下一页6学习编译原理的重要作用通过本课程的学习，使学生掌握和理解编译系统的结构、工作流程以及编译程序各组成部分的设计原理和实现技术，获得分析、设计、实现和维护编译系统的初步能力；通过学习编译的理论和方法，提高学生对程序设计语言、操作系统、计算机原理和体系结构等课程知识的综合理解。对于将来从事编译系统设计工作的学生来说，编译原理课程将为其打下坚实的能力和知识基础；编译原理蕴涵着抽象问题、解决问题的思路、方法和技术，对学生今后的学习和研究有很重要的作用。编译程序是计算机系统中的系统软件，包含许多软件设计和开发技术，为学生提供了一个大型软件设计的参考。课程介绍的经典的语言分析方法和工具，对于设计一些实用的工具和软件，如自然语言理解、网络信息处理、网络协议的分析与实现等，都是必备的基础。此外，学习这门课程有利于对程序设计语言的理解，有利于迅速掌握新的语言工具。上一页下一页7参考书[1]AlfredV.Aho，MonicaS.Lam，RaviSethi，等著，赵建华，郑滔，等译，编译原理（第二版），机械工业出版社，2009.1（龙书）[2]（美）安佩尔，（美）金斯伯格著，赵克佳，黄春，沈志宇译，现代编译原理-C语言描述，人民邮电出版社，2006.4（虎书）[3]（美）StevenS.Muchnick著，赵克佳，沈志宇译，高级编译器设计与实现，机械工业出版社，2005.7（鲸书）[4]KennethC.Louden著，冯博琴冯岚等译，编译原理及实践（CompilerConstructionPrinciplesandPractice），机械工业出版社，2000.3上一页下一页8本章的主要内容什么是编译程序编译程序的逻辑结构编译程序各阶段的工作编译程序的组织上一页下一页9本章要求清楚编译程序的总框架，了解编译程序工作的大致过程，能分辨清楚编译前端与后端的区别及其相互配合的方法，要清楚编译程序是如何生成的。请大家记忆并理解以下概念：编译程序，解释程序，翻译程序，目标机、源语言、目标语言、编译程序实现语言、扫描器，分析器，编译前端与后端，符号表，“遍”的概念等。上一页下一页10本章教学线索1编译程序的概念及功能1.1为什么要用编译器1.2翻译程序1.3编译程序1.4编译程序与解释程序1.5编译器的发展阶段2编译程序的逻辑结构及过程概述3编译程序（器）的组织4编译程序的生成上一页下一页111.1为什么要用编译器机器语言：C70600000002汇编语言：MOVX,2高级语言：x=2上一页下一页12阶乘的C语言实现算法描述，求某整数n的阶乘fact(n),n≥01//n==0fact(n)=n*fact(n-1)//n!==n*(n-1)!伪语言描述fact(n)=ifn≤0then1elsen*fact(n-1)高级程序设计语言描述，（如C语言）intfact(intn){if(n=0)return1;elsereturn(n*fact(n-1));}上一页下一页13c程序foo.cAnsiCcompilerccObjectfileLinker/连接程序a.out/可执行程序库函数或其它object文件编译和执行过程a.out/可执行程序loader/装入程序计算机输入数据计算结果上一页下一页141.2翻译程序翻译程序（器）：接受某种语言的源语言程序后，将它改造成另一种逻辑上等价的目标语言程序。汇编程序：源语言为汇编语言，目标语言为机器语言的翻译程序。编译程序（器）：源语言为高级语言，目标语言是低级语言（汇编或机器语言）的翻译程序。上一页下一页151.3编译程序把高级语言程序翻译成等价的低级语言程序编译程序目标程序编译系统：编译程序和运行程序源语言程序编译程序：就是能够把某种语言程序（称为：源语言程序）转换成另一种语言程序（称为：目标语言程序）的程序，而后者与前者在逻辑上是等价的。源语言：一般指某种高级语言，易于理解和掌握。目标语言：汇编语言、机器语言等宿主机：运行编译程序的计算机目标机：运行编译程序产生目标代码的计算机。编译程序实现语言：用于生成编译程序的语言。C、Java、C#、Fortran、Ada、Pascal…上一页下一页161.4编译程序与解释程序高级语言程序也可通过解释程序来执行解释程序：以源程序为输入，在执行过程中不再产生目标程序，而是边解释边执行。解释程序运行效率不高，空间开销大。目前，纯粹的解释程序已不多见，通常是将编译和解释作某种程度的结合。编译程序是现今任何计算机系统的最重要的系统程序。本课程的目的，在于向大家介绍设计和构造编译程序的基本原理和基本方法，其中许多方法也适用于构造解释程序或汇编程序。上一页下一页171.5编译器的发展阶段Fortran编译器的开发Chomsky文法1954~1957IBM的JohnBackusNoamChomsky分析问题（词法分析、语法分析、语义分析）60~70年代代码优化编译器的自动构造70年代后期~80年代早期编译器本身算法的发展IDE80年代以后1975Yacc:SteveJohnsonLex：MikeLesk并行编译技术上一页下一页18本章教学线索1编译程序的概念及功能2编译程序的逻辑结构及过程概述2.1编译程序的结构2.2编译程序的主要过程2.3表格和表格管理2.4出错处理3编译程序（器）的组织4编译程序的生成上一页下一页192.1编译程序的结构词法分析器语法分析器语义分析与中间代码产生器优化器目标代码生成器源程序目标代码表格处理出错处理单词符号语法单位中间代码中间代码编译程序的逻辑结构上一页下一页202.2编译程序的主要过程第一阶段：词法分析（lexicalanalysisorscanning）词法分析的任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个一个的单词。如：基本字、标识符、常数、算符和界符（标点符号、括号、分号等）。基本字又称为保留字，界符又称为分隔符。词法分析阶段遵循词法规则。上一页下一页21例1-1：PROGRAMm;VARa,b,c:real;BEGINa:=b+c*60;END.基本字，PROGRAM标识符，m界符，;保留字,VAR标识符,a标识符,b标识符,c界符,:标识符,real界符,;基本字,BEGIN标识符,a赋值符,:=标识符,b算符,+标识符,c算符,*常数,60基本字,END界符,.例2-2forI:=1to100do基本字，for标识符，I赋值号，：=整常数，1基本字，to整常数，100基本字，do上一页下一页22第二阶段：语法分析（syntaxanalysisorparsing）语法分析的任务：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。语法分析遵循语法规则，常用的语法规则用上下文无关文法描述。注意：1.词法分析是一种线性分析，而语法分析是一种层次结构的分析。2.有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法结构的语法树。上一页下一页23比如：A=B+C*60其中B+C*60代表一个“算术表达式”，因此，语法分析就是要识别B+C*60为算术表达式，并且识别上述整个符号串为赋值语句这个范畴。赋值语句变量A=表达式表达式项因子B+项项*因子C因子60赋值语句A=B+C*60的语法分析树上一页下一页24这一阶段的任务：对语法分析所识别出的各类语法范畴分析其含义，并进行初步翻译，产生中间代码。包括两方面的工作：静态语义检查。中间代码的翻译。这一阶段所依循的是语言的语义规则。第三阶段语义分析和中间代码的产生semanticanalysisandintermediatecodegeneration上一页下一页25中间代码：是一种含义明确、便于处理的记号系统，它通常独立于具体硬件。常见的记号系统有：四元式、三元式、间接三元式、逆波兰式、树形表示等。四元式：算符左操作数右操作数结果例子：A=B+C*60四元式表示NO算符左操作数右操作数结果（1）*C60T1（2）+BT1T2（3）=T2A例子：A=B+C*60四元式表示上一页下一页26树形表示（抽象语法树）：树形表示（抽象语法树）：=AB*C60+生成中间代码：temp1=C*60temp2=B+temp1A=temp2上一页下一页27第四阶段优化（codeoptimization）优化阶段的任务：对前一阶段产生的中间代码进行加工交换，以期在最后阶段能够产生出运行效率更高的（省时间和空间）的目标代码。优化的主要方法有：公共子表达式的提取、强度削弱、删除无用代码等。forK:=1to100dobeginM:=I+10*K;N:=J+10*K;endM:=IN:=JforK:=1to100dobeginM:=M+10;N:=N+10;end优化上一页下一页28第五阶段目标代码的生成codegeneration这一阶段的任务：把中间代码（或经过优化处理之后）变换成特定机器上的低级语言代码。目标代码的形式：绝对指令代码可重定位的指令代码汇编代码A:=B+C*60.0的汇编指令：LDR0,60.0MULR0,CADDR0,BSTR0,A上一页下一页29usingSystem;namespaceConsoleApplication1{classProgram