第1章编译原理答案(主编张晶)

《编译原理》

教师：王文晶为什么要学习编译原理必修主干课程：操作系统和编译系统构成程序设计者与计算机之间的基本界面。通过学习该课程，掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统结构和机理。能运用所学技术解决实际问题，能独立编写一个小型编译系统。此外，通过学习编译原理可以更好地理解程序语言的内部机制,从而更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术完成相关软件工具的设计和开发工作。学习方法平时（40%）一本教材，认真听课：以讲义为主，板书为辅---做适当的笔记上机（编程+练习20分）+考勤（10分）+作业（实验报告、随堂作业10分）课程特点：理论性强，算法复杂补充：公共邮箱wwjjsj@163.com密码20122012

期末（60%）:闭卷笔试编译理论自动机和形式语言离散数学数据结构操作系统素材基础控制对象编译原理与其它课程关系要求先学习以下课程1.程序设计语言2.算法与数据结构：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。

3.离散数学：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。

最好学习过或同时学习以下课程1.软件工程：掌握大型程序设计以及工程化的软件生产方法。2.形式语言与自动机：相当于本课程中词法分析与语法分析的理论基础。

第一章引言第二章文法和语言第三章词法分析第四章语法分析—自顶向下分析方法第五章语法分析—自底向上分析方法第六章语法分析—LR方法目录第一章引言学习目标了解和掌握高级程序设计语言与编译程序的关系了解和掌握编译程序的功能

了解和掌握编译程序的体系结构了解和掌握编译程序的工作过程

1.1编译程序、汇编程序、解释程序1.2编译过程及结构1.3编译程序的组织及开发目录低级语言（LowlevelLanguage)字位码、机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁 琐、费时、易出错高级语言

--Fortran、Pascal、C语言等特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。1.1翻译程序、编译程序、解释程序源程序

用汇编语言或高级语言编写的程序称为源程序目标程序（翻译后的程序）用目标语言所表示的程序目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。翻译程序

将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。概念：源程序、翻译程序、目标程序三者关系：源程序翻译程序目标程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM输入输出翻译程序（Translator）是一种程序，其输入是某种语言的一系列语句，而其输出则是另一种语言的一系列语句。1.1.1翻译程序源语言程序目标语言程序Translator输入输出如汇编程序：汇编语言翻译为机器语言。编译程序（Compiler）是一种程序。它把用高级语言写的源程序作为数据接收，经过翻译转换，产生面向机器的代码作为输出。这当中代码还可能要由汇编程序或装配程序作进一步加工，得出目标程序，交给计算机执行。1.1.2编译程序高级语言源程序面向机器代码Compiler目标程序代码汇编装配源程序的编译和运行编译或汇编阶段运行阶段源程序目标程序编译程序或汇编程序输出数据目标程序+运行子程序输入数据工作过程解释程序（Interpreter）（类似于口译，不生成目标代码）

对源程序进行解释执行的程序。输出数据解释程序输入数据源程序1.1.3解释程序优点：提供一种直接的交互调试能力，在执行用户程序时可以修改用户程序。对新的类型可动态地修改，如符号的意义。提高良好的诊断信息不依赖于目标机，移植性较好。

事实上，纯粹的解释程序并不多见，通常做某种程序的结合。编译过程是指将高级语言程序翻译为等价的目标程序的过程。翻译外文资料：1、能识别出句子中的一个单词；2、分析句子的语法结构；3、根据句子的含义进行初步翻译；4、对译文进行修饰；5、写出最后的译文。1.2编译程序的基本结构翻译和编译工作的比较翻译外文编译程序分析识别单词分析句子根据语义进行初步翻译词法分析语法分析语义分析、生成中间代码综合修辞加工写出译文代码优化目标代码生成符号表管理源程序目标代码生成目标程序出错处理词法分析优化语义分析语法分析编译过程1.2.1词法分析任务所做转换依据构词规则主要理论基础自动机理论源程序字符串单词符号输入源程序；扫描、分解字符串，识别出一个个单词（定义符、标识符、运算符、界符、常数）概念单词token：是语言的基本语法单位保留字reservedword(有时也叫关键字)

（如:if、else、while）标识符identifier（如:max、min、str）常数（如:12、6.8）分界符(有时也叫运算符)（如:+、-、*、/、;、（、））示例FORK:=1TO100M:=I+10*KN:=J+10*KNEXTKTONEXTFORKNMIJKKK:=100:=:=11010+**+关键字标识符分界符运算符常数词法分析程序的结果-----二元式(如：FORK:=1TO100)单词值单词类别FOR关键字K标识符:=分界符1常数TO关键字100常数…..……1.2.2语法分析任务所做转换依据语法规则主要理论基础上下文无关文法单词符号语法单位（语法范畴）在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。如：Thislineisalongersentence语法分析又例：position:=initial+rate*60;（Pascal）规则<赋值语句>::=<标识符>“:=”<表达式><表达式>::=<表达式>“+”<表达式><表达式>::=<表达式>“*”<表达式><表达式>::=“(”<表达式>“)”<表达式>::=<标识符><表达式>::=<整数><表达式>::=<实数>

赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*id1:=id2+id3*N :=+N60*id1Positionid2initialid3rate进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等规定。审查静态语义使用的变量声明了吗？允许操作的运算对象吗？类型正确吗？…1.2.3语义分析

语义分析句子的结构理解了，扑捉它的“含义”如：杰克说杰瑞把他的作业落在了家里。“他的”是谁的？又：杰克说杰克把他的作业落在了家里。几个杰克？语义分析杰克把她的作业落在了家里。（杰克是男生）“杰克”和“她的”不一致。“杰克”和“他的”才匹配语义分析（语言的规定和实现）intarr[2],c;c=arr*10;

“中间代码”是一种含义明确、便于处理的记号系统。如：三元式、四元式、逆波兰式。例：四元式（运算符，第一运算量，第二运算量，结果）

x:=a*b+c（*，a，b，T1）（+，T1,c,T2）(:=,T2,-，x)1.2.4中间代码 id1:=id2+id3*60(1) (inttoreal, 60 - t1 )(2) (* , id3 t1 t2 )(3) (+ , id2 t2 t3 )(4) (:= , t3 - id1 )1.2.5代码优化任务所做转换依据程序等价变换规则主要理论基础数据流方程中间代码中间代码（优化后）对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码。代码优化 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.2.6目标代码生成任务所做转换依据硬件体系结构、指令系统中间代码目标代码将中间代码变换成特定机器上的低级语言代码目标代码形式绝对指令、可重定位指令、汇编指令(* , id3 60.0 t1 )(+ , id2 t1 id1 )movf id3,R2mulf #60.0,R2movf id2,R1addf R2,R1movf R1,id16.目标代码生成按逻辑功能不同，可将编译过程划分为五个基本阶段，与此相对应，我们将实现整个编译过程的编译程序划分为五个逻辑阶段（即五个逻辑子过程）。每个阶段中都要有，符号表管理和错误处理诊察错误，并能报告用户错误性质和位置出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。填表：把源程序中的信息和编译过程中所产生的信息登记在表格中查表：在随后的编译过程中同时又要不断的查找这些表格中的信息1.2.7符号表管理1.2.8错误处理目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结S.PO.P1.3编译程序的组织及开发编译程序是一个非常复杂的软件系统，虽然编译理论和技术不断发展，开发周期缩短，但研制仍需大量时间。追求目标过程自动化。

根据编译程序各部分功能，将编译程序分成前端和后端前端：通常将与源程序有关的编译部分称为前端。 词法分析、语法分析、语义分析、中间代码生成 ---分析部分特点：与源语言有关后端：与目标机有关的部分称为后端。代码优化、代码生成---综合部分特点：与目标机有关编译程序的前端和后端.java

java源程序文件.class二进制字节码文件Java虚拟机（JVM)本地计算机系统编译同一前端+不同后端不同机器构成同一语言的编译程序例如Java语言

同一前端+不同后端不同机器构成同一语言的编译程序例如.NET框架

不同前端+同一后端同一机器生成几个语言的编译程序例如GCC

第一遍 第二遍 ……

S.P中间形式1S.P中间形式2C2C1S.PO.P对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，通常称之为一遍。遍上一遍的结果是下一遍的输入，最后一遍生成目标程序。一遍扫描即可完成整个编译工作的称为一遍扫描编译程序遍的划分视具体情况而定（内存的大小、源语言的繁简、目标程序质量的高低）

优点：1、减少对内存容量的要求2、编译程序结构清晰、各遍功能独立、相互联系简单缺点：增加读写中间文件的次数，降低效率应用：大部分软件工具的开发，都要使用编译技术和方法语法制导的结构化编辑器程序格式化工具软件测试工具静态分析器：不可能执行的