编译原理第一章Introduction to Course

北京化工大学信息科学与技术学院计算机系赵瑞莲rlzhao@编译原理2023/10/7北京化工大学信息科学与技术学院计算机系2课程简介●

课程简介

课程名称编译原理课程代码CSE3250C课程类型必修考试类型考试总学时56(含上机8学时)学分3.5教学班级计科1101～1105课程名称编译原理课程设计课程代码CSE3933P课程类型必修考试类型考查总学时1周学分1教学班级计科1101～11052023/10/7北京化工大学信息科学与技术学院计算机系3●

参考书籍

编译程序构造原理和实现技术金成植高等教育出版社编译原理吕映芝清华大学出版社

编译原理Compilers:Principles,Techniques,andtoolsAlfredV.Aho机械工业出版社（中文）/人民邮电出版社（英文）编译程序设计原理杜淑敏等北京大学出版社程序设计语言编译程序陈火旺等国防工业出版社编译原理及实践CompilerConstructionPrincipleandPracticeKennethC.Louden机械工业出版社参考书籍参考书籍参考书籍2023/10/7北京化工大学信息科学与技术学院计算机系4选用教材●

选用教材

《编译原理与实践》CompilerConstructionPrincipleandPracticeKenneth,C.Clouden

机械工业出版社《编译原理》Compilers:Principles,Techniques,andToolsAlfredV.Aho

机械工业出版社（中）/人民邮电出版社（英）2023/10/7北京化工大学信息科学与技术学院计算机系5●

考核方式考核方式考试成绩评定百分制评分比例平时成绩40%（出勤+作业+上机）期末成绩60%

额外奖励：大作业考核方式2023/10/7北京化工大学信息科学与技术学院计算机系6内容简介高等数学Ｃ(PASCAL…)离散数学汇编语言数据结构●

先行课程

2023/10/7北京化工大学信息科学与技术学院计算机系7掌握编译的基本原理和实现方法编写简单的编译器能够将编译中使用的方法和技术，灵活应用到以后问题的解决上（问题->形式化描述->计算机化）●课程学习的目的2023/10/7北京化工大学信息科学与技术学院计算机系8掌握编译程序的总体结构在系统级上认识算法学习有关的原理、方法和技术典型方法的实现和综合学习有关的工具软件培养计算机思维●教学要求2023/10/7北京化工大学信息科学与技术学院计算机系9理解编译系统的结构和工作原理；提高对程序设计、离散数学、数据结构、操作系统等课程的理解；经典分析方法和工具，在软件工程、自然语言理解、搜索引擎、人工智能等领域都是必备的基础。●课程的作用2023/10/7北京化工大学信息科学与技术学院计算机系10编译基础知识和方法编译器（部分模块）的编写常用工具（Lex、Yacc）的使用编程（Programming）是学习本课程最需要，同时也最希望提高的能力●关注重点2023/10/7北京化工大学信息科学与技术学院计算机系11基础的语言知识，不试图掌握一切细节清晰的逻辑思维，数据结构和算法先进的架构思想，盖楼前的规划良好的编程习惯，规范性高效的编程工具，无需追求特殊善于利用资源，Google……正确的心态（不害怕）●谈编程2023/10/7北京化工大学信息科学与技术学院计算机系12学习方法●

学习方法1课堂——听2课下——看3课下——练2023/10/7北京化工大学信息科学与技术学院计算机系13第1章编译简介1.1

编译器

1.2

源程序的结构

1.3

编译器的实例

1.4

与编译相关的数据结构

1.5

编译器各阶段的分组

2023/10/7北京化工大学信息科学与技术学院计算机系141.1编译器CompilerSourceProgramTargetProgram2023/10/7北京化工大学信息科学与技术学院计算机系151.1编译简介●程序设计语言程序设计语言低级语言：面向机器的语言机器语言汇编语言过程式语言Fortran,Pascal,C…函数式语言Lisp…逻辑式语言Prolog…对象式语言C++…高级语言2023/10/7北京化工大学信息科学与技术学院计算机系160011010010101010…0100101110110100目标模块0011010010101010……0100101110110100#include<iostream.h>intmain(void){inta;…;cin>>…;…;return0;}源程序TextEditor文本编辑器Linker链接器Compiler编译Preprocessor预处理程序Translator翻译程序系统库●Buildinga

Program

构建程序可执行目标代码2023/10/7北京化工大学信息科学与技术学院计算机系17基础程序

Interpreters解释程序

Assemblers汇编程序

Linkers连接程序

Loaders装入程序

Preprocessors预处理程序●编译相关程序IDE程序（IntegratedDevelopmentEnvironment）Editors编辑器Debuggers调试器Profilers剖析器Projectmanagers

项目管理器2023/10/7北京化工大学信息科学与技术学院计算机系18目标程序源程序编译程序初始数据计算结果功能工作结果实现技术上编译程序源程序的一个转换系统源程序的目标代码把中间代码转换成目标程序解释程序源程序的一个执行系统源程序的执行结果执行中间代码源程序解释程序初始数据计算结果●

编译和解释程序

2023/10/7北京化工大学信息科学与技术学院计算机系19基础程序

Interpreters解释程序

Assemblers汇编程序

Linkers连接程序

Loaders装入程序

Preprocessors预处理程序●编译相关程序IDE程序Editors编辑器Debuggers调试器Profilers描述器Projectmanagers

项目管理器2023/10/7北京化工大学信息科学与技术学院计算机系20翻译外文资料阅读原文识别单词分析句子修辞加工写出译文1.2编译器的结构翻译外文资料与编译源程序进行类比。2023/10/7北京化工大学信息科学与技术学院计算机系21翻译外文资料编译源程序阅读原文识别单词分析句子输入并扫描源程序词法分析语法分析修辞加工写出译文代码优化目标代码生成1.2编译器的结构翻译外文资料与编译源程序进行类比。综合分析2023/10/7北京化工大学信息科学与技术学院计算机系22词法分析源程序目标程序语法分析语义分析文字表、符号表处理错误处理中间代码优化中间代码生成●

Thephaseofacompiler编译程序的结构●

Thephaseofacompiler编译程序的结构

目标代码生成2023/10/7北京化工大学信息科学与技术学院计算机系23●

Thephaseofacompiler

编译程序的结构词法分析Scanner语法分析Parser语义分析SemanticAnalyzer代码优化CodeOptimizer中间代码生成IntermediateCodeGenerator前端后端●

Thephaseofacompiler编译程序的结构目标代码生成TargetCodeGenerator文字表LiteralTable错误处理ErrorHandler符号表SymbolTable源程序SourceCode目标程序TargetCode24编译器的分析/综合模式

前端：只依赖于源语言结构的分析；后端：只依赖于目标语言的分析与处理；中间代码：前端与后端的分界.25编译器的分析/综合模式

编译器基础架构（Infrastructure）源代码的中间表示C++parserAdaparserJavaparserC++源程序Ada源程序Java源程序...X86A86/A386...26例1.

Pascal源程序语句如下：

varx,y,z:real;x:=y+z*60;（记号流）(id,1),(:=),(id,2),(+),(id,3),(*),(60)依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).语法分析1.3编译器的实例2023/10/7北京化工大学信息科学与技术学院计算机系27赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*:=id1+id2*id360语法树x:=y+z*60;28中间代码的形式与作用：(序号)(op，arg1,arg2,result)result:=arg1oparg2

(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1):=id1+id2*id3itr601234yreal4zreal8......符号表部分内容xreal0中间代码生成x:=y+z*60;29(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)(1)(*,id3,60,T1)(2)(+,id2,T1,id1)MOVF R2,id3MULF R2,#60MOVF R1,id2ADDFR1,R2MOVFid1,R1x:=y+z*60;R2:=id3R2:=R2*60R1:=id2R1:=R1+R2id1:=R1id1:=id2+id3*602023/10/7北京化工大学信息科学与技术学院计算机系30Thescanner

(Lexicalanalysis)

Input:astreamofcharacters,Output:a,[,index,],=,4,+,2(Tokens)Theparser(Determinethestructureoftheprogram):Input:theformsoftokensOutput:aparsetreeorasyntaxtree例2：a[index]=4+21.3编译器的实例2023/10/7北京化工大学信息科学与技术学院计算机系31expressionAssign-expressionexpression=expressionSubscript-expressionAdditive-expressiveexpression[expression]expressionexpressionIdentifieraIdentifierindexNumber4Number2+●parsetreeAssign-expressionSubscript-expressionAdditive-expressiveIdentifieraIdentifierindexNumber4Number2●abstractsyntaxtreea[index]=4+22023/10/7北京化工大学信息科学与技术学院计算机系32●Thesemanticanalyzer

Assign-expressionSubscript-expressionintegerAdditive-expressiveintegerIdentifieraArrayofintegerIdentifierindexintegerNumber4integerNumber2integer●Intermediate

codeoptimizerAssign-expressionSubscript-expressionintegerIdentifieraArrayofintegerIdentifierindexinteger

Number6integera[index]=4+22023/10/7北京化工大学信息科学与技术学院计算机系33●Thecodegenerator●Thetargetcodeoptimizer

MOVR0,indexMULR0,2MOVR1,&aADDR1,R0MOV*R1,6MOVR0,indexSHLR0MOV&a[R0],6Input:intermediatecodeOutput:machinecode,codeforthetargetmachinea[index]=4+22023/10/7北京化工大学信息科学与技术学院计算机系341.4与编译相关的数据结构

●枚举类型：记号(tokens)种类、语法单位等的命名.●结构体：分析树(parsertree)、语法树(syntaxtree)的结点，符号表(symboltable)等.●树型结构：分析树、语法树、注释树等.●线性表、哈希表：符号表、常数表(literaltable).●文件：输入、输出、临时文件(temporaryfiles).2023/10/7北京化工大学信息科学与技术学院计算机系35编译程序的前端：与源语言有关，而与目标机无关的编译程序.编译程序的后端：与目标机有关，而与源语言无关的编译程序.遍（趟）：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序。1.5编译器各阶段的分组2023/10/7北京化工大学信息科学与技术学院计算机系36第2章一个微小编译器2.1Micro语言描述2.2Micro语言的词法分析2.3Micro语言的语法分析2.4Micro语言的语义分析2.5Micro语言的目标代码2023/10/7北京化工大学信息科学与技术学院计算机系372.1Micro语言描述Micro语言（称Micro,Pascal语言的子集）begin

varx1:real;

varz1:real;

x1:=0.5;

z1:=x1+56;

read(x1);write(z1+2.3)

end.Main(){

floatx1;

floatz1;

x1=0.5;

z1=x1+56;

scanf(“%f”,&x1);printf(“%f”,z1+2.3);}PascalC2023/10/7北京化工大学信息科学与技术学院计算机系382.1Micro语言描述Micro语言的定义PbeginVDL;SLend.VDLVD|VD;VDLVDvarid:TSLS|S;SLSid:=E|write(E)|read(id)Tint|realEid|num|E+E|E*E|(E)2023/10/7北京化工大学信息科学与技术学院计算机系392.1Micro语言描述Micro语言（称Micro,Pascal语言的子集）程序组成声明性语句使用性语句赋值语句输入语句输出语句begin

varx1:real;

varz1:real;

x1:=0.5;

z1:=x1+56;

read(x1);write(z1+2.3)end.2023/10/7北京化工大学信息科学与技术学院计算机系40●

Micro语言中单词/记号的种类：2.2Micro语言的词法分析１.特点：

不依赖于语言的语法定义，只依赖于单词/记号的文法定义。以字母开头：保留字：begin,end,var,read,write,int,real标识符：字母/数字串以数字开头：整常数：数字开头的数字串实常数：整数.整数符号词：+，-，*，/，(，)，:，:=，;，.控制词：

(换行符）

2023/10/7北京化工大学信息科学与技术学院计算机系41输出输入输出程序的字符串序列Token序列（单词的内部表示）２.任务：

Token定义：

二元组（单词种类，单词自身值）标识符:($id,标识符）如($id,x)整常数:($intC,整常数）如（$intC,5)实常数:($realC,实常数）如($realC,0.5)保留字:($begin,-),($end,-),($var,-)…符号词:($plus,-),($mult,-),($LParen,-),($Rparen,-),($colon,-),($assig,-),($semi,-)换行符:($line,-),($stop,-)

2023/10/7北京化工大学信息科学与技术学院计算机系42Micro的词法分析图源程序在文件中的表示beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.空格2023/10/7北京化工大学信息科学与技术学院计算机系43Micro的词法分析

读当前字符流，直至文件结束。如果是：

(1)标识符时判断是保留字还是变量标识符，构造Token表示；

(2)数字时判断是整型还是实型，构造Token表示；

(3)构造其它合法的符号的Token表示；

(4)遇到非法符号则报错。2.2Micro语言的词法分析3.词法分析过程2023/10/7北京化工大学信息科学与技术学院计算机系44Micro的词法分析beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.图词法分析后的TOKEN表示2023/10/7北京化工大学信息科学与技术学院计算机系45●Micro语言的词法分析程序Procedurescanner();beginwhile~Eofdo{Noblank(ch);casechof‘A’..’Z’|’a’..’z’{Identifier(name);casenameof“begin”GenToken($begin);“end”GenToken($end);“var”GenToken($var);“int”GenToken($int);“real”GenToken($real);“read”GenToken($read);“write”GenToken($write);otherGenToken($id,name);end};例：beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.Noblank(ch):跳过空格符串将第一个非空格字符读到ch中（删除空格符）。2023/10/7北京化工大学信息科学与技术学院计算机系46●Micro语言的词法分析程序Procedurescanner();beginwhile~Eofdo{Noblank(ch);casechof‘A’..’Z’|’a’..’z’{Identifier(name);casenameof“begin”GenToken($begin);“end”GenToken($end);“var”GenToken($var);“int”GenToken($int);“real”GenToken($real);“read”GenToken($read);“write”GenToken($write);otherGenToken($id,name);end};例：beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.Identifier(name)：从输入流把当前标识符名读到name中（它可能是保留字）。在调用时，当前字符一定是字母，且已被读到ch中。GenToken(token)将token送入TOKEN区。2023/10/7北京化工大学信息科学与技术学院计算机系47Procedurescanner();beginwhile~Eofdo{Noblank(ch);casechof‘A’..’Z’|’a’..’z’{Identifier(name);…}

‘0’..’9’{Constant(class,C);GenToken(Class,C)};‘(’GenToken($Lparen);Read(ch);‘)’GenToken($Rparen);Read(ch);‘+’GenToken($plus);Read(ch);‘*’GenToken($mult);Read(ch);‘;’GenToken($semi);Read(ch);‘:’{Read(ch);ifch=‘=’then{GenToken($assig);Read(ch)}elseGenToken($colon)}

‘.’GenToken($stop);Read(ch);‘

’GenToken($line);Read(ch);‘other’LexicalError(ch)end}end

Constant(class,C)：从输入流读到当前常数，并在class中给出常数的类型标志，C中给出常数的二进制数值。调用时当前字符定是数字（在ch中）。词法错误2023/10/7北京化工大学信息科学与技术学院计算机系48ProcedureIdentifier(name:string);Beginname:=“”;Append(name,ch);Read(ch);whileisLetter(ch)orisDigit(ch)do{Append(name,ch);Read(ch);}End●

Micro语言的词法分析程序的相关子程序(1)Identifier(name)：从输入流把当前标识符名读到name中。在调用时，当前字符一定是字母，且已被读到ch中。isLetter(ch):

如果ch是字母，则取true，否则取false。isDigit(ch):

如果ch是数字，则取true，否则取false。——读标识符，保留字（关键字）2023/10/7北京化工大学信息科学与技术学院计算机系49ProcedureConstant(class:classType,C:ConstType);Begin

IntConst(N1,L1);ifch=‘.’then{Read(ch);if(~IsDigit(ch))LexicalError(ch);

IntConst(N2,L2);

class:=$realC;C:=N1+N2*(1.0/10)^L2}Else{class:=$intC;C:=N1}End●

Micro语言的词法分析程序的相关子程序(2)Constant(class,C)：从输入流读到当前常数，并在class中给出常数的类型标志，C中给出常数的二进制数值。调用时当前字符定是数字（在ch中）。整数(小数点左部)整数(小数点右部)——读整/实常数2023/10/7北京化工大学信息科学与技术学院计算机系50●

Micro语言的词法分析程序的相关子程序(3)IntConst(N,L):从输入流读当前整常数，并在N中给出所读常数的二(十)进制值，在L中给出整常数的位数。调用时当前字符应是数字。ProcedureIntConst(N,L);BeginN:=Num(ch);

L:=1;Read(ch);whileisDigit(ch)do{N:=N*10+Num(ch);L:=L+1;Read(ch)}End——读整常数Num(ch):数字字符ch对应的二(十)进制值。2023/10/7北京化工大学信息科学与技术学院计算机系51Procedurescanner();beginwhile~Eofdo{Noblank(ch);casechof‘A’..’Z’|’a’..’z’{Identifier(name);casenameof“begin”GenToken($begin);“end”GenToken($end);“var”GenToken($var);“int”GenToken($int);“real”GenToken($real);“read”GenToken($read);“write”GenToken($write);otherGenToken($id,name);end};‘0’..’9’{Constant(class,C);GenToken(Class,C)};‘(’GenToken($Lparen);Read(ch);‘)’GenToken($Rparen);Read(ch);‘+’GenToken($plus);Read(ch);‘*’GenToken($mult);Read(ch);‘;’GenToken($semi);Read(ch);‘:’{Read(ch);ifch=‘=’then{GenToken($assig);Read(ch)}elseGenToken($colon)}‘.’GenToken($stop);Read(ch);‘

’GenToken($line);Read(ch);‘other’LexicalError(ch)end}end例：beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.2023/10/7北京化工大学信息科学与技术学院计算机系52

1.任务：检查程序是否有语法（语法结构）上的错误。

2.输入：词法分析后得到的Token表输出：具体语法错误提示和语法全部正确提示。2.３Micro语言的语法分析说明：语法分析只用到单词的Token表示，并不改变单词的Token表示。2023/10/7北京化工大学信息科学与技术学院计算机系53声明检查：beginvarid:real;(声明的位置)赋值语句